Private Analysis of Graph Structure
The authors present efficient algorithms for releasing useful statistics about graph data while providing rigorous privacy guarantees. Their 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. Their 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 edge-induced isomorphic copies of H in the input graph.