Private analysis of graph structure

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).