Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts

Abstract

We study the problem of releasing a differentially private (DP) synthetic graph G’ that well approximates the triangle-motif sizes of all cuts of any given graph G, where a motif in general refers to a frequently occurring subgraph within complex networks. Non-private versions of such graphs have found applications in diverse fields such as graph clustering, graph sparsification, and social network analysis. Specifically, we present the first (ε,δ)-DP mechanism that, given an input graph G with n vertices, m edges and local sensitivity of triangles ℓ_3(G), generates a synthetic graph G’ in polynomial time, approximating the triangle-motif sizes of all cuts (S,V∖ S) of the input graph G up to an additive error of Õ(√(mℓ_3(G))n/ε^3/2). Additionally, we provide a lower bound of Ω(√(mn)ℓ_3(G)/ε) on the additive error for any DP algorithm that answers the triangle-motif size queries of all (S,T)-cut of G. Finally, our algorithm generalizes to weighted graphs, and our lower bound extends to any K_h-motif cut for any constant h≥ 2.