{"ID":2892541,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.14835","arxiv_id":"2507.14835","title":"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 $(\\varepsilon,δ)$-DP mechanism that, given an input graph $G$ with $n$ vertices, $m$ edges and local sensitivity of triangles $\\ell_{3}(G)$, generates a synthetic graph $G'$ in polynomial time, approximating the triangle-motif sizes of all cuts $(S,V\\setminus S)$ of the input graph $G$ up to an additive error of $\\tilde{O}(\\sqrt{m\\ell_{3}(G)}n/\\varepsilon^{3/2})$. Additionally, we provide a lower bound of $Ω(\\sqrt{mn}\\ell_{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 $K_h$-motif cut for any constant $h\\geq 2$.","short_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...","url_abs":"https://arxiv.org/abs/2507.14835","url_pdf":"https://arxiv.org/pdf/2507.14835v2","authors":"[\"Pan Peng\",\"Hangyu Xu\"]","published":"2025-07-20T06:20:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}