生成隐私保护的图数据，精准保留三角形结构切分信息
Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
- 基于差分隐私设计新算法，生成近似原图所有切分中三角形数量的合成图
- 合成图在所有切分上的误差为约 $\tilde{O}(\sqrt{m\ell_3(G)}n/\varepsilon^{3/2})$，理论最优
- 适用于社交网络、图聚类等需保护隐私的场景，支持加权图与高阶团结构
我们研究如何生成一个差分隐私（DP）合成图 $G'$，使其能良好逼近给定图 $G$ 的所有切分 $(S,V\setminus S)$ 中的三角形-基元数量。基元指复杂网络中频繁出现的子图。非私有版本的此类图已广泛应用于图聚类、图稀疏化和社交网络分析。本文提出首个 $(\varepsilon,δ)$-差分隐私机制：对于包含 $n$ 个顶点、$m$ 条边且三角形局部敏感度为 $\ell_3(G)$ 的输入图 $G$，可在多项式时间内生成合成图 $G'$，使得所有切分的三角形基元大小误差不超过 $\tilde{O}(\sqrt{m\ell_3(G)}n/\varepsilon^{3/2})$。此外，我们证明了任何回答所有 $(S,T)$-切分三角形基元查询的 DP 算法，其误差下界为 $Ω(\sqrt{mn}\ell_3(G)/\varepsilon)$。算法进一步推广至加权图，且下界可扩展至任意常数 $h\geq 2$ 的 $K_h$-基元切分。
原文摘要 · Abstract (English)
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$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。