Private Analysis of Graphs

We discuss algorithms for the private analysis of network data. Such algorithms work on data sets that contain sensitive relationship information (for example, romantic ties). Their goal is to compute approximations to global statistics of the graph while protecting information specific to individuals. Our algorithms satisfy a rigorous notion of privacy, called node differential privacy. Intuitively, it means that an algorithm's output distribution does not change significantly when a node and all its adjacent edges are removed from a graph. We present several techniques for designing node differentially private algorithms. We also develop methodology for analyzing the accuracy of such algorithms on realistic networks. Our techniques are based on combinatorial analysis, network flow, and linear and convex programming.

Based on joint work with Shiva Kasiviswanathan, Kobbi Nissim and Adam Smith.