Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts

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 (varepsilon,δ)-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,Vsetminus S) of the input graph G up to an additive error of tildeO(√mℓ3(G)n/varepsilon3/2). Additionally, we provide a lower bound of Omega(√mnℓ3(G)/varepsilon) 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 Kh-motif cut for any constant h≥ 2.