Private analysis of graph structure

Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, Grigory Yaroslavtsev

Research output: Contribution to journalConference articlepeer-review

127 Scopus citations


We present efficient algorithms for releasing useful statistics about graph data while providing rigorous privacy guarantees. Our algorithms work on data sets 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, e.g., a triangle, k-star or k-triangle, the goal is to return the number of edgeinduced isomorphic copies of H in the input graph. The special case of triangles was considered by Nissim, Raskhodnikova and Smith (STOC 2007), and a more general investigation of arbitrary query graphs was initiated by Rastogi, Hay, Miklau and Suciu (PODS 2009). We extend the approach of [NRS] 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., H stars and k-triangles), we significantly improve on the work of [RHMS]: our algorithms satisfy a stronger notion of privacy, which does not rely on the adversary having a particular prior distribution on the data, 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 data sets. We give explicit, simple conditions under which these algorithms add a small amount of noise. We also provide the average-case analysis in the Erd̃os-Ŕenyi-Gilbert G(n,p) random graph model. Finally, we give hardness results indicating that the approach NRS used for triangles cannot easily be extended to k-triangles (and hence justifying our development of a new algorithmic approach).

Original languageEnglish (US)
Pages (from-to)1146-1157
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number11
StatePublished - Aug 2011
Event37th International Conference on Very Large Data Bases, VLDB 2011 - Seattle, United States
Duration: Aug 29 2011Sep 3 2011

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Computer Science(all)


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

Cite this