Private analysis of graph structure

Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, Grigory Yaroslavtsev

Research output: Contribution to journalArticlepeer-review

56 Scopus citations


We present efficient algorithms for releasing useful statistics about graph data while providing rigorous privacy guarantees. Our algorithms work on datasets that consist of relationships between individuals, such as social ties or email communication. The algorithms satisfy edge differential privacy, which essentially requires that the presence or absence of any particular relationship be hidden. Our algorithms output approximate answers to subgraph counting queries. Given a query graph H, for example, a triangle, k-star, or k-triangle, the goal is to return the number of edge-induced isomorphic copies of H in the input graph. The special case of triangles was considered by Nissim et al. [2007] and a more general investigation of arbitrary query graphs was initiated by Rastogi et al. [2009]. We extend the approach of Nissim et al. to a new class of statistics, namely k-star queries.We also give algorithms for k-triangle queries using a different approach based on the higher-order local sensitivity. For the specific graph statistics we consider (i.e., k-stars and k-triangles), we significantly improve on the work of Rastogi et al.: our algorithms satisfy a stronger notion of privacy and add less noise to the answers before releasing them. We evaluate the accuracy of our algorithms both theoretically and empirically, using a variety of real and synthetic datasets. We give explicit, simple conditions under which these algorithms add a small amount of noise. We also provide the average-case analysis in the Erdo{combining double acute accent}s-Rényi-Gilbert G(n, p) random graph model. Finally, we give hardness results indicating that the approach Nissim et al. used for triangles cannot easily be extended to k-triangles (hence justifying our development of a new algorithmic approach).

Original languageEnglish (US)
Article number22
JournalACM Transactions on Database Systems
Issue number3
StatePublished - Sep 2014

All Science Journal Classification (ASJC) codes

  • Information Systems


Dive into the research topics of 'Private analysis of graph structure'. Together they form a unique fingerprint.

Cite this