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.

A key component of our work is the design of efficiently computable Lipschitz extensions of commonly computed graph statistics. Given a graph statistic f, we seek to design a new function g that is efficiently computable and "robust" to the addition or removal of vertices, yet agrees with f on as large a set of graphs as possible. Our techniques are based on combinatorial analysis, network flow, and linear and convex programming.

Based on joint work with Shiva Kasiviswanathan, Kobbi Nissim and Sofya Raskhodnikova.

Bio: Adam Smith is an associate professor in the Department of Computer Science and Engineering at Penn State; currently, he is on sabbatical at Boston University. His research interests lie in cryptography, privacy and their connections to information theory, quantum computing and statistics. He received his Ph.D. from MIT in 2004 and was subsequently a visiting scholar at the Weizmann Institute of Science and UCLA.