PGB: Benchmarking Differentially Private Synthetic Graph Generation Algorithms ICDE 2025

Liu, Shang, et al. “Pgb: Benchmarking differentially private synthetic graph generation algorithms.” 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 2025.

原文：PGB: Benchmarking Differentially Private Synthetic Graph Generation Algorithms
作者：Shang Liu, Hao Du, Yang Cao, Bo Yan, Jinfei Liu, Masatoshi Yoshikawa
版本：arXiv:2408.02928v4 [cs.DB]，2024 年 12 月 9 日
代码：https://github.com/dooohow/PGB
平台：https://pgb-result.github.io/

摘要

差分隐私图分析能够在保护个人信息的同时，从多种图数据中提取洞见，是一种强有力的工具。然而，为不同图查询设计隐私分析算法，往往需要从头开始。相比之下，差分隐私合成图生成提供了一种通用范式：只需生成一次，便可支持多种查询。

虽然人们已经提出多种差分隐私图生成算法，但由于隐私定义不同、图数据集多样、隐私要求各异以及效用指标繁多，要有效比较这些方法仍然很困难。为此，我们提出 PGB（Private Graph Benchmark，隐私图基准），这是一个综合性基准，旨在帮助研究人员公平比较差分隐私图生成算法。

首先，我们将现有工作的四个基本要素表示为四元组：机制、图数据集、隐私要求和效用指标。我们讨论这些要素应遵循的原则，以保证基准的全面性。随后，给出一个满足全部原则的基准实例，为评估现有及新提出的图生成算法建立新方法。通过广泛的理论和实证分析，我们深入了解了既有算法的优点与缺点。结果表明，不存在适用于所有情况的通用解决方案。最后，我们给出指导意见，帮助研究人员在不同场景下选择适当机制。

关键词：差分隐私、基准、合成图生成。

I. 引言

图分析是从社交网络、交通网络和流行病网络等多种图数据集中获得洞见的有效方法。例如，度分布 [1]–[3] 统计每个节点的连接数量，可以揭示社交图的连通性。三角形或星形等子图计数 [4]–[6] 有助于评估聚类系数 [7] 等核心属性；聚类系数反映一个人的两个联系人彼此相连的概率。然而，由于图分析经常作用于敏感信息，公开这些图统计量可能泄露个人信息 [8]。

差分隐私（DP）[9], [10] 已成为隐私保护的事实标准，即使攻击者拥有任意背景知识，也能保护个人隐私。不同于kkk-匿名、lll-多样性和ttt-接近性等早期定义，DP 保证单个节点或单条边的改变只会对输出产生很小影响。人们已针对度分布 [1]–[3]、子图计数 [4]–[6] 和社区检测 [11]–[13] 等查询设计了许多差分隐私图分析算法，但这些方案通常只适用于特定查询。若查询改变，往往必须重新设计算法。

一种解决方案，是以隐私方式生成与原图在语义上相似、同时满足 DP 的合成图。相较定制算法，该范式可以一次生成、支持多种查询。

尽管已有大量差分隐私合成图生成算法 [14]–[29]，目前仍没有公认且统一的实证研究流程，原因包括：

• 各算法使用不同隐私定义，例如边差分隐私 [14]–[21] 和节点差分隐私 [22], [23]；不同定义下的算法不能公平比较。
• 文献调查中的开源算法很少。由于算法本身复杂，正确复现十分困难。
• 许多算法的误差依赖数据，效用会受到图规模、平均聚类系数和图类型等输入图特征影响。
• 算法与隐私参数ϵ\epsilonϵ之间关系不同，在不同隐私要求下达到最佳效用。例如，在某图上，当ϵ>20\epsilon>20ϵ>20时 DP-2K [14] 的误差低于 DK-1K [14]；当ϵ≤20\epsilon\le20ϵ≤20时结果相反。
• 所有调查算法都只覆盖图查询的一个子集；即使评估相同查询，也可能使用不同误差指标。例如 PrivHRG [18] 使用归一化互信息 [30] 衡量社区检测效用，LF-GDPR [26] 则使用调整兰德指数 [31] 和调整互信息 [32]。

本文提出综合基准 PGB，主要贡献如下：

1. 基准设计原则。基于全面文献调查，将实证研究概括为四元组(M,G,P,U)(M,G,P,U)(M,G,P,U)：机制、图数据集、隐私要求和效用指标。针对每个要素分析现有工作的局限，并提出保证结果可比的要求（第 IV 节）。
2. 基准实例化。提出满足全部设计原则的 PGB，用于评估差分隐私图生成算法。代码和基准平台均公开，未来工作可以方便地加入比较（第 V 节）。
3. 实证研究与发现。完成迄今规模最大的隐私图生成算法实证评估，至少包含 43,200 次独立实验，涉及 6 种算法、8 个图数据集、6 个隐私预算和 15 种查询。结果显示，一些算法总体表现强劲，但不存在万能方案（第 VI 节）。

II. 相关工作

A. 隐私图生成

已有多项研究关注差分隐私图生成 [14]–[29], [33]–[35]。Gao 等人 [33] 使用持久同调发布在线社交网络，但其方法未保护距离矩阵，可能危及个人隐私。Marek 等人 [34] 和 Felipe 等人 [35] 研究 DP 下带属性图或加权图的发布。本文评估五种最先进方法 DP-dK [14]、TmF [15]、PrivSKG [17]、PrivHRG [18]、PrivGraph [19]，以及基线 DGG [24]。

DP-dK。首先将图压缩为KKK-连通分量的度分布（dK-series），向学习参数加入拉普拉斯噪声，再使用 dK-series 模型 [36] 根据扰动参数生成合成图。DP-2K 根据平滑敏感度而非全局敏感度校准噪声，因此噪声幅度更小；但所需隐私预算仍大得不合理，即ϵ≥100\epsilon\ge100ϵ≥100。

TmF。先将图表示为邻接矩阵，再向每个单元加入拉普拉斯噪声。最后选择噪声值最大的前mmm个单元作为随机邻接矩阵的边，其中mmm是带噪边数。当ϵ\epsilonϵ较小时，绝大多数真实边无法保留在前mmm个单元中。

PrivSKG。使用随机 Kronecker 图模型表示图，并构造真实参数的隐私估计器。该估计器定义图上的概率分布，最后从中采样生成合成图。由于生成过程由单一参数决定，PrivSKG 无法准确捕获真实图的结构属性。

PrivHRG。首先使用统计分层随机图（HRG）模型 [37] 表示图，记录任意节点对之间的连接概率，再通过 MCMC [38] 以隐私方式采样树状图，最后根据噪声连接概率生成合成图。构造 HRG 模型时可能丢失部分真实图信息。

PrivGraph。先使用社区检测算法生成粗粒度节点划分，并以指数机制隐私化社区分区；随后计算社区内部的度序列和社区之间的边数；最后使用 CL 模型 [39] 根据噪声度序列生成合成图。通过利用社区信息，它比先前方法保留更多结构信息。

DGG。节点度是图的基础信息，已用于隐私图生成 [24], [26]。本文将 DGG [24] 修改为满足边级中央差分隐私。它先计算节点度并使用拉普拉斯机制扰动，再用 BTER 模型 [40] 生成合成图。DGG 无法捕获度数之外的图结构，因而丢失真实图的细节。

备注 1。少量工作 [41], [42] 使用 GAN 等深度学习方法在 DP 下生成合成图，本文不将其纳入基准。其一，这些工作的隐私目标不同：本文算法主要保护图结构，而既有深度学习方法同时考虑图结构和节点特征，保护节点特征需要额外隐私预算。其二，查询类型不同：深度学习方法生成的图主要通过链接预测等深度学习任务评估，与本文的统计查询不同。

B. DP 基准

近年来，图数据和表格数据上的差分隐私分析基准受到广泛关注。Ning 等人 [43] 通过考察隐私、准确率和性能之间的权衡，实现并评测了度分布与子图计数等图查询；这些实现被集成到 DPGraph [44]。DPGraph 是差分隐私图分析平台，重点帮助研究人员理解现有算法在度分布和子图计数上的权衡。这些工作启发了本文对差分隐私合成图算法综合基准的设计。

表格数据方面，DPBench [45] 是评估一维和二维范围查询等 DP 算法的原则性框架；DPComp [46] 是支持隐私数据分析原则性评估的公开 Web 系统；Tao 等人 [47] 系统评估 GAN、边缘分布和工作负载驱动的差分隐私表格合成数据方法；Basu 等人 [48] 评估使用抑郁和性骚扰推文进行 BERT 中央与联邦训练的效用；Schäler 等人 [49] 设计满足所有要求的www-event DP 机制基准；Rosenblatt 等人 [50] 提出以可复现性为基础的 DP 合成器评估方法；Gonzalo 等人 [51] 比较五个主流开源 DP 库；Dmitry 等人 [52] 综述隐私风险攻击、方法和指标。由于图具有独特的隐私定义、表示与效用指标，这些基准不能直接用于图数据。

III. 预备知识

A. 差分隐私

DP [9], [10] 是个人隐私保护的事实标准。对于由节点和边构成的图，可定义边 DP 与节点 DP [3]。边 DP 隐藏某条好友关系是否存在；节点 DP 隐藏某个用户及其全部相邻边是否存在。节点 DP 同时保护节点和边，保证更强，但以效用为代价。

定义 1（差分隐私 [9]）。给定隐私预算ϵ>0\epsilon>0ϵ>0。若对于任意相差一条数据的相邻数据库D,D′∈XD,D'\in\mathcal XD,D′∈X及任意S⊆Range⁡(M)S\subseteq\operatorname{Range}(\mathcal M)S⊆Range(M)，都有

Pr⁡[M(D)∈S]≤eϵPr⁡[M(D′)∈S], \Pr[\mathcal M(D)\in S]\le e^\epsilon\Pr[\mathcal M(D')\in S],Pr[M(D)∈S]≤eϵPr[M(D′)∈S],

则随机算法M\mathcal MM满足ϵ\epsilonϵ-DP。

定义 2（节点 CDP [3]）。若任意相差一个节点及其全部相邻边的图G,G′G,G'G,G′都满足

Pr⁡[M(G)∈S]≤eϵPr⁡[M(G′)∈S], \Pr[\mathcal M(G)\in S]\le e^\epsilon\Pr[\mathcal M(G')\in S],Pr[M(G)∈S]≤eϵPr[M(G′)∈S],

则M\mathcal MM满足ϵ\epsilonϵ-节点 DP。

定义 3（边 CDP [53]）。若任意只相差一条边的图G,G′G,G'G,G′都满足上述不等式，则M\mathcal MM满足ϵ\epsilonϵ-边 CDP。

定义 4（边 LDP [24]）。对任意用户viv_ivi​，令Mi\mathcal M_iMi​为其随机算法。若对任意只相差一条边的邻接位向量Ai,Ai′A_i,A_i'Ai​,Ai′​及任意输出集合SSS，都有

Pr⁡[Mi(Ai)∈S]≤eϵPr⁡[Mi(Ai′)∈S], \Pr[\mathcal M_i(A_i)\in S]\le e^\epsilon\Pr[\mathcal M_i(A_i')\in S],Pr[Mi​(Ai​)∈S]≤eϵPr[Mi​(Ai′​)∈S],

则Mi\mathcal M_iMi​满足ϵ\epsilonϵ-边 LDP。

B. 使用 DP 合成图

图 1 给出涵盖调查中全部机制的通用差分隐私图生成框架，包含表示、扰动和构造三个阶段。

图 1：差分隐私图生成算法的通用步骤：表示、扰动和构造。

1. 表示。对原图建模并寻找紧凑表示，例如度信息 [14], [24], [26]、邻接矩阵 [15]–[17] 或社区结构 [19], [20], [25], [29]。紧凑表示通过降低维度，减少为保障 DP 所需的噪声。
2. 扰动。向紧凑表示加入适当噪声，常用拉普拉斯机制 [54]、指数机制 [55] 和随机响应 [56]。根据后处理性质 [9]，后续合成过程不会进一步损害隐私。
3. 构造。从扰动表示构造合成图。BTER [40] 和 Chung-Lu（CL）[39] 等模型用于保留目标结构属性。图构造器已有大量研究 [57]，不同工作采用不同构造器，例如 LDPGen [24] 使用 BTER，PrivGraph [19] 使用 CL。

备注 2。本文将差分隐私图生成算法视为黑盒，目标是为不同场景的算法选择提供依据。算法内部在表示、扰动和构造各步骤的具体选择不属于本基准范围。

IV. 基准设计原则

本节阐述 PGB 的基本设计原则。这些原则对于全面、公平且有意义地比较差分隐私图合成算法至关重要。既有工作经常忽视它们，导致评估不完整或存在偏差。我们调查 CCS、VLDB、SIGMOD、TKDE 等会议和期刊的重要文献，将实证研究的关键要素定义为四元组(M,G,P,U)(M,G,P,U)(M,G,P,U)：

• MMM：待比较机制的集合；
• GGG：图数据集的集合；
• PPP：隐私要求的集合；
• UUU：效用指标的集合。

A. 机制MMM

机制应满足四项原则M1M_1M1​–M4M_4M4​。

1. 隐私定义（M1M_1