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平臺(tái)：https://pgb-result.github.io/摘要差分隱私圖分析能夠在保護(hù)個(gè)人信息的同時(shí)，從多種圖數(shù)據(jù)中提取洞見，是一種強(qiáng)有力的工具。然而，為不同圖查詢?cè)O(shè)計(jì)隱私分析算法，往往需要從頭開始。相比之下，差分隱私合成圖生成提供了一種通用范式：只需生成一次，便可支持多種查詢。雖然人們已經(jīng)提出多種差分隱私圖生成算法，但由于隱私定義不同、圖數(shù)據(jù)集多樣、隱私要求各異以及效用指標(biāo)繁多，要有效比較這些方法仍然很困難。為此，我們提出 PGB（Private Graph Benchmark，隱私圖基準(zhǔn)），這是一個(gè)綜合性基準(zhǔn)，旨在幫助研究人員公平比較差分隱私圖生成算法。首先，我們將現(xiàn)有工作的四個(gè)基本要素表示為四元組：機(jī)制、圖數(shù)據(jù)集、隱私要求和效用指標(biāo)。我們討論這些要素應(yīng)遵循的原則，以保證基準(zhǔn)的全面性。隨后，給出一個(gè)滿足全部原則的基準(zhǔn)實(shí)例，為評(píng)估現(xiàn)有及新提出的圖生成算法建立新方法。通過(guò)廣泛的理論和實(shí)證分析，我們深入了解了既有算法的優(yōu)點(diǎn)與缺點(diǎn)。結(jié)果表明，不存在適用于所有情況的通用解決方案。最后，我們給出指導(dǎo)意見，幫助研究人員在不同場(chǎng)景下選擇適當(dāng)機(jī)制。關(guān)鍵詞：差分隱私、基準(zhǔn)、合成圖生成。I. 引言圖分析是從社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)和流行病網(wǎng)絡(luò)等多種圖數(shù)據(jù)集中獲得洞見的有效方法。例如，度分布 [1]–[3] 統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的連接數(shù)量，可以揭示社交圖的連通性。三角形或星形等子圖計(jì)數(shù) [4]–[6] 有助于評(píng)估聚類系數(shù) [7] 等核心屬性；聚類系數(shù)反映一個(gè)人的兩個(gè)聯(lián)系人彼此相連的概率。然而，由于圖分析經(jīng)常作用于敏感信息，公開這些圖統(tǒng)計(jì)量可能泄露個(gè)人信息 [8]。差分隱私（DP）[9], [10] 已成為隱私保護(hù)的事實(shí)標(biāo)準(zhǔn)，即使攻擊者擁有任意背景知識(shí)，也能保護(hù)個(gè)人隱私。不同于kkk-匿名、lll-多樣性和ttt-接近性等早期定義，DP 保證單個(gè)節(jié)點(diǎn)或單條邊的改變只會(huì)對(duì)輸出產(chǎn)生很小影響。人們已針對(duì)度分布 [1]–[3]、子圖計(jì)數(shù) [4]–[6] 和社區(qū)檢測(cè) [11]–[13] 等查詢?cè)O(shè)計(jì)了許多差分隱私圖分析算法，但這些方案通常只適用于特定查詢。若查詢改變，往往必須重新設(shè)計(jì)算法。一種解決方案，是以隱私方式生成與原圖在語(yǔ)義上相似、同時(shí)滿足 DP 的合成圖。相較定制算法，該范式可以一次生成、支持多種查詢。盡管已有大量差分隱私合成圖生成算法 [14]–[29]，目前仍沒(méi)有公認(rèn)且統(tǒng)一的實(shí)證研究流程，原因包括：各算法使用不同隱私定義，例如邊差分隱私 [14]–[21] 和節(jié)點(diǎn)差分隱私 [22], [23]；不同定義下的算法不能公平比較。文獻(xiàn)調(diào)查中的開源算法很少。由于算法本身復(fù)雜，正確復(fù)現(xiàn)十分困難。許多算法的誤差依賴數(shù)據(jù)，效用會(huì)受到圖規(guī)模、平均聚類系數(shù)和圖類型等輸入圖特征影響。算法與隱私參數(shù)?\epsilon?之間關(guān)系不同，在不同隱私要求下達(dá)到最佳效用。例如，在某圖上，當(dāng)?20\epsilon20?20時(shí) DP-2K [14] 的誤差低于 DK-1K [14]；當(dāng)?≤20\epsilon\le20?≤20時(shí)結(jié)果相反。所有調(diào)查算法都只覆蓋圖查詢的一個(gè)子集；即使評(píng)估相同查詢，也可能使用不同誤差指標(biāo)。例如 PrivHRG [18] 使用歸一化互信息 [30] 衡量社區(qū)檢測(cè)效用，LF-GDPR [26] 則使用調(diào)整蘭德指數(shù) [31] 和調(diào)整互信息 [32]。本文提出綜合基準(zhǔn) PGB，主要貢獻(xiàn)如下：基準(zhǔn)設(shè)計(jì)原則?；谌嫖墨I(xiàn)調(diào)查，將實(shí)證研究概括為四元組(M,G,P,U)(M,G,P,U)(M,G,P,U)：機(jī)制、圖數(shù)據(jù)集、隱私要求和效用指標(biāo)。針對(duì)每個(gè)要素分析現(xiàn)有工作的局限，并提出保證結(jié)果可比的要求（第 IV 節(jié)）?；鶞?zhǔn)實(shí)例化。提出滿足全部設(shè)計(jì)原則的 PGB，用于評(píng)估差分隱私圖生成算法。代碼和基準(zhǔn)平臺(tái)均公開，未來(lái)工作可以方便地加入比較（第 V 節(jié)）。實(shí)證研究與發(fā)現(xiàn)。完成迄今規(guī)模最大的隱私圖生成算法實(shí)證評(píng)估，至少包含 43,200 次獨(dú)立實(shí)驗(yàn)，涉及 6 種算法、8 個(gè)圖數(shù)據(jù)集、6 個(gè)隱私預(yù)算和 15 種查詢。結(jié)果顯示，一些算法總體表現(xiàn)強(qiáng)勁，但不存在萬(wàn)能方案（第 VI 節(jié)）。II. 相關(guān)工作A. 隱私圖生成已有多項(xiàng)研究關(guān)注差分隱私圖生成 [14]–[29], [33]–[35]。Gao 等人 [33] 使用持久同調(diào)發(fā)布在線社交網(wǎng)絡(luò)，但其方法未保護(hù)距離矩陣，可能危及個(gè)人隱私。Marek 等人 [34] 和 Felipe 等人 [35] 研究 DP 下帶屬性圖或加權(quán)圖的發(fā)布。本文評(píng)估五種最先進(jìn)方法 DP-dK [14]、TmF [15]、PrivSKG [17]、PrivHRG [18]、PrivGraph [19]，以及基線 DGG [24]。DP-dK。首先將圖壓縮為KKK-連通分量的度分布（dK-series），向?qū)W習(xí)參數(shù)加入拉普拉斯噪聲，再使用 dK-series 模型 [36] 根據(jù)擾動(dòng)參數(shù)生成合成圖。DP-2K 根據(jù)平滑敏感度而非全局敏感度校準(zhǔn)噪聲，因此噪聲幅度更??；但所需隱私預(yù)算仍大得不合理，即?≥100\epsilon\ge100?≥100。TmF。先將圖表示為鄰接矩陣，再向每個(gè)單元加入拉普拉斯噪聲。最后選擇噪聲值最大的前mmm個(gè)單元作為隨機(jī)鄰接矩陣的邊，其中mmm是帶噪邊數(shù)。當(dāng)?\epsilon?較小時(shí)，絕大多數(shù)真實(shí)邊無(wú)法保留在前mmm個(gè)單元中。PrivSKG。使用隨機(jī) Kronecker 圖模型表示圖，并構(gòu)造真實(shí)參數(shù)的隱私估計(jì)器。該估計(jì)器定義圖上的概率分布，最后從中采樣生成合成圖。由于生成過(guò)程由單一參數(shù)決定，PrivSKG 無(wú)法準(zhǔn)確捕獲真實(shí)圖的結(jié)構(gòu)屬性。PrivHRG。首先使用統(tǒng)計(jì)分層隨機(jī)圖（HRG）模型 [37] 表示圖，記錄任意節(jié)點(diǎn)對(duì)之間的連接概率，再通過(guò) MCMC [38] 以隱私方式采樣樹狀圖，最后根據(jù)噪聲連接概率生成合成圖。構(gòu)造 HRG 模型時(shí)可能丟失部分真實(shí)圖信息。PrivGraph。先使用社區(qū)檢測(cè)算法生成粗粒度節(jié)點(diǎn)劃分，并以指數(shù)機(jī)制隱私化社區(qū)分區(qū)；隨后計(jì)算社區(qū)內(nèi)部的度序列和社區(qū)之間的邊數(shù)；最后使用 CL 模型 [39] 根據(jù)噪聲度序列生成合成圖。通過(guò)利用社區(qū)信息，它比先前方法保留更多結(jié)構(gòu)信息。DGG。節(jié)點(diǎn)度是圖的基礎(chǔ)信息，已用于隱私圖生成 [24], [26]。本文將 DGG [24] 修改為滿足邊級(jí)中央差分隱私。它先計(jì)算節(jié)點(diǎn)度并使用拉普拉斯機(jī)制擾動(dòng)，再用 BTER 模型 [40] 生成合成圖。DGG 無(wú)法捕獲度數(shù)之外的圖結(jié)構(gòu)，因而丟失真實(shí)圖的細(xì)節(jié)。備注 1。少量工作 [41], [42] 使用 GAN 等深度學(xué)習(xí)方法在 DP 下生成合成圖，本文不將其納入基準(zhǔn)。其一，這些工作的隱私目標(biāo)不同：本文算法主要保護(hù)圖結(jié)構(gòu)，而既有深度學(xué)習(xí)方法同時(shí)考慮圖結(jié)構(gòu)和節(jié)點(diǎn)特征，保護(hù)節(jié)點(diǎn)特征需要額外隱私預(yù)算。其二，查詢類型不同：深度學(xué)習(xí)方法生成的圖主要通過(guò)鏈接預(yù)測(cè)等深度學(xué)習(xí)任務(wù)評(píng)估，與本文的統(tǒng)計(jì)查詢不同。B. DP 基準(zhǔn)近年來(lái)，圖數(shù)據(jù)和表格數(shù)據(jù)上的差分隱私分析基準(zhǔn)受到廣泛關(guān)注。Ning 等人 [43] 通過(guò)考察隱私、準(zhǔn)確率和性能之間的權(quán)衡，實(shí)現(xiàn)并評(píng)測(cè)了度分布與子圖計(jì)數(shù)等圖查詢；這些實(shí)現(xiàn)被集成到 DPGraph [44]。DPGraph 是差分隱私圖分析平臺(tái)，重點(diǎn)幫助研究人員理解現(xiàn)有算法在度分布和子圖計(jì)數(shù)上的權(quán)衡。這些工作啟發(fā)了本文對(duì)差分隱私合成圖算法綜合基準(zhǔn)的設(shè)計(jì)。表格數(shù)據(jù)方面，DPBench [45] 是評(píng)估一維和二維范圍查詢等 DP 算法的原則性框架；DPComp [46] 是支持隱私數(shù)據(jù)分析原則性評(píng)估的公開 Web 系統(tǒng)；Tao 等人 [47] 系統(tǒng)評(píng)估 GAN、邊緣分布和工作負(fù)載驅(qū)動(dòng)的差分隱私表格合成數(shù)據(jù)方法；Basu 等人 [48] 評(píng)估使用抑郁和性騷擾推文進(jìn)行 BERT 中央與聯(lián)邦訓(xùn)練的效用；Sch?ler 等人 [49] 設(shè)計(jì)滿足所有要求的www-event DP 機(jī)制基準(zhǔn)；Rosenblatt 等人 [50] 提出以可復(fù)現(xiàn)性為基礎(chǔ)的 DP 合成器評(píng)估方法；Gonzalo 等人 [51] 比較五個(gè)主流開源 DP 庫(kù)；Dmitry 等人 [52] 綜述隱私風(fēng)險(xiǎn)攻擊、方法和指標(biāo)。由于圖具有獨(dú)特的隱私定義、表示與效用指標(biāo)，這些基準(zhǔn)不能直接用于圖數(shù)據(jù)。III. 預(yù)備知識(shí)A. 差分隱私DP [9], [10] 是個(gè)人隱私保護(hù)的事實(shí)標(biāo)準(zhǔn)。對(duì)于由節(jié)點(diǎn)和邊構(gòu)成的圖，可定義邊 DP 與節(jié)點(diǎn) DP [3]。邊 DP 隱藏某條好友關(guān)系是否存在；節(jié)點(diǎn) DP 隱藏某個(gè)用戶及其全部相鄰邊是否存在。節(jié)點(diǎn) DP 同時(shí)保護(hù)節(jié)點(diǎn)和邊，保證更強(qiáng)，但以效用為代價(jià)。定義 1（差分隱私 [9]）。給定隱私預(yù)算?0\epsilon0?0。若對(duì)于任意相差一條數(shù)據(jù)的相鄰數(shù)據(jù)庫(kù)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],則隨機(jī)算法M\mathcal MM滿足?\epsilon?-DP。定義 2（節(jié)點(diǎn) CDP [3]）。若任意相差一個(gè)節(jié)點(diǎn)及其全部相鄰邊的圖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?-節(jié)點(diǎn) DP。定義 3（邊 CDP [53]）。若任意只相差一條邊的圖G,G′G,G'G,G′都滿足上述不等式，則M\mathcal MM滿足?\epsilon?-邊 CDP。定義 4（邊 LDP [24]）。對(duì)任意用戶viv_ivi?，令Mi\mathcal M_iMi?為其隨機(jī)算法。若對(duì)任意只相差一條邊的鄰接位向量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 給出涵蓋調(diào)查中全部機(jī)制的通用差分隱私圖生成框架，包含表示、擾動(dòng)和構(gòu)造三個(gè)階段。圖 1：差分隱私圖生成算法的通用步驟：表示、擾動(dòng)和構(gòu)造。表示。對(duì)原圖建模并尋找緊湊表示，例如度信息 [14], [24], [26]、鄰接矩陣 [15]–[17] 或社區(qū)結(jié)構(gòu) [19], [20], [25], [29]。緊湊表示通過(guò)降低維度，減少為保障 DP 所需的噪聲。擾動(dòng)。向緊湊表示加入適當(dāng)噪聲，常用拉普拉斯機(jī)制 [54]、指數(shù)機(jī)制 [55] 和隨機(jī)響應(yīng) [56]。根據(jù)后處理性質(zhì) [9]，后續(xù)合成過(guò)程不會(huì)進(jìn)一步損害隱私。構(gòu)造。從擾動(dòng)表示構(gòu)造合成圖。BTER [40] 和 Chung-Lu（CL）[39] 等模型用于保留目標(biāo)結(jié)構(gòu)屬性。圖構(gòu)造器已有大量研究 [57]，不同工作采用不同構(gòu)造器，例如 LDPGen [24] 使用 BTER，PrivGraph [19] 使用 CL。備注 2。本文將差分隱私圖生成算法視為黑盒，目標(biāo)是為不同場(chǎng)景的算法選擇提供依據(jù)。算法內(nèi)部在表示、擾動(dòng)和構(gòu)造各步驟的具體選擇不屬于本基準(zhǔn)范圍。IV. 基準(zhǔn)設(shè)計(jì)原則本節(jié)闡述 PGB 的基本設(shè)計(jì)原則。這些原則對(duì)于全面、公平且有意義地比較差分隱私圖合成算法至關(guān)重要。既有工作經(jīng)常忽視它們，導(dǎo)致評(píng)估不完整或存在偏差。我們調(diào)查 CCS、VLDB、SIGMOD、TKDE 等會(huì)議和期刊的重要文獻(xiàn)，將實(shí)證研究的關(guān)鍵要素定義為四元組(M,G,P,U)(M,G,P,U)(M,G,P,U)：MMM：待比較機(jī)制的集合；GGG：圖數(shù)據(jù)集的集合；PPP：隱私要求的集合；UUU：效用指標(biāo)的集合。A. 機(jī)制MMM機(jī)制應(yīng)滿足四項(xiàng)原則M1M_1M1?–M4M_4M4?。1. 隱私定義（M1M_1 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平臺(tái)：https://pgb-result.github.io/摘要差分隱私圖分析能夠在保護(hù)個(gè)人信息的同時(shí)，從多種圖數(shù)據(jù)中提取洞見，是一種強(qiáng)有力的工具。然而，為不同圖查詢?cè)O(shè)計(jì)隱私分析算法，往往需要從頭開始。相比之下，差分隱私合成圖生成提供了一種通用范式：只需生成一次，便可支持多種查詢。雖然人們已經(jīng)提出多種差分隱私圖生成算法，但由于隱私定義不同、圖數(shù)據(jù)集多樣、隱私要求各異以及效用指標(biāo)繁多，要有效比較這些方法仍然很困難。為此，我們提出 PGB（Private Graph Benchmark，隱私圖基準(zhǔn)），這是一個(gè)綜合性基準(zhǔn)，旨在幫助研究人員公平比較差分隱私圖生成算法。首先，我們將現(xiàn)有工作的四個(gè)基本要素表示為四元組：機(jī)制、圖數(shù)據(jù)集、隱私要求和效用指標(biāo)。我們討論這些要素應(yīng)遵循的原則，以保證基準(zhǔn)的全面性。隨后，給出一個(gè)滿足全部原則的基準(zhǔn)實(shí)例，為評(píng)估現(xiàn)有及新提出的圖生成算法建立新方法。通過(guò)廣泛的理論和實(shí)證分析，我們深入了解了既有算法的優(yōu)點(diǎn)與缺點(diǎn)。結(jié)果表明，不存在適用于所有情況的通用解決方案。最后，我們給出指導(dǎo)意見，幫助研究人員在不同場(chǎng)景下選擇適當(dāng)機(jī)制。關(guān)鍵詞：差分隱私、基準(zhǔn)、合成圖生成。I. 引言圖分析是從社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)和流行病網(wǎng)絡(luò)等多種圖數(shù)據(jù)集中獲得洞見的有效方法。例如，度分布 [1]–[3] 統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的連接數(shù)量，可以揭示社交圖的連通性。三角形或星形等子圖計(jì)數(shù) [4]–[6] 有助于評(píng)估聚類系數(shù) [7] 等核心屬性；聚類系數(shù)反映一個(gè)人的兩個(gè)聯(lián)系人彼此相連的概率。然而，由于圖分析經(jīng)常作用于敏感信息，公開這些圖統(tǒng)計(jì)量可能泄露個(gè)人信息 [8]。差分隱私（DP）[9], [10] 已成為隱私保護(hù)的事實(shí)標(biāo)準(zhǔn)，即使攻擊者擁有任意背景知識(shí)，也能保護(hù)個(gè)人隱私。不同于kkk-匿名、lll-多樣性和ttt-接近性等早期定義，DP 保證單個(gè)節(jié)點(diǎn)或單條邊的改變只會(huì)對(duì)輸出產(chǎn)生很小影響。人們已針對(duì)度分布 [1]–[3]、子圖計(jì)數(shù) [4]–[6] 和社區(qū)檢測(cè) [11]–[13] 等查詢?cè)O(shè)計(jì)了許多差分隱私圖分析算法，但這些方案通常只適用于特定查詢。若查詢改變，往往必須重新設(shè)計(jì)算法。一種解決方案，是以隱私方式生成與原圖在語(yǔ)義上相似、同時(shí)滿足 DP 的合成圖。相較定制算法，該范式可以一次生成、支持多種查詢。盡管已有大量差分隱私合成圖生成算法 [14]–[29]，目前仍沒(méi)有公認(rèn)且統(tǒng)一的實(shí)證研究流程，原因包括：各算法使用不同隱私定義，例如邊差分隱私 [14]–[21] 和節(jié)點(diǎn)差分隱私 [22], [23]；不同定義下的算法不能公平比較。文獻(xiàn)調(diào)查中的開源算法很少。由于算法本身復(fù)雜，正確復(fù)現(xiàn)十分困難。許多算法的誤差依賴數(shù)據(jù)，效用會(huì)受到圖規(guī)模、平均聚類系數(shù)和圖類型等輸入圖特征影響。算法與隱私參數(shù)?\epsilon?之間關(guān)系不同，在不同隱私要求下達(dá)到最佳效用。例如，在某圖上，當(dāng)?20\epsilon20?20時(shí) DP-2K [14] 的誤差低于 DK-1K [14]；當(dāng)?≤20\epsilon\le20?≤20時(shí)結(jié)果相反。所有調(diào)查算法都只覆蓋圖查詢的一個(gè)子集；即使評(píng)估相同查詢，也可能使用不同誤差指標(biāo)。例如 PrivHRG [18] 使用歸一化互信息 [30] 衡量社區(qū)檢測(cè)效用，LF-GDPR [26] 則使用調(diào)整蘭德指數(shù) [31] 和調(diào)整互信息 [32]。本文提出綜合基準(zhǔn) PGB，主要貢獻(xiàn)如下：基準(zhǔn)設(shè)計(jì)原則?；谌嫖墨I(xiàn)調(diào)查，將實(shí)證研究概括為四元組(M,G,P,U)(M,G,P,U)(M,G,P,U)：機(jī)制、圖數(shù)據(jù)集、隱私要求和效用指標(biāo)。針對(duì)每個(gè)要素分析現(xiàn)有工作的局限，并提出保證結(jié)果可比的要求（第 IV 節(jié)）?；鶞?zhǔn)實(shí)例化。提出滿足全部設(shè)計(jì)原則的 PGB，用于評(píng)估差分隱私圖生成算法。代碼和基準(zhǔn)平臺(tái)均公開，未來(lái)工作可以方便地加入比較（第 V 節(jié)）。實(shí)證研究與發(fā)現(xiàn)。完成迄今規(guī)模最大的隱私圖生成算法實(shí)證評(píng)估，至少包含 43,200 次獨(dú)立實(shí)驗(yàn)，涉及 6 種算法、8 個(gè)圖數(shù)據(jù)集、6 個(gè)隱私預(yù)算和 15 種查詢。結(jié)果顯示，一些算法總體表現(xiàn)強(qiáng)勁，但不存在萬(wàn)能方案（第 VI 節(jié)）。II. 相關(guān)工作A. 隱私圖生成已有多項(xiàng)研究關(guān)注差分隱私圖生成 [14]–[29], [33]–[35]。Gao 等人 [33] 使用持久同調(diào)發(fā)布在線社交網(wǎng)絡(luò)，但其方法未保護(hù)距離矩陣，可能危及個(gè)人隱私。Marek 等人 [34] 和 Felipe 等人 [35] 研究 DP 下帶屬性圖或加權(quán)圖的發(fā)布。本文評(píng)估五種最先進(jìn)方法 DP-dK [14]、TmF [15]、PrivSKG [17]、PrivHRG [18]、PrivGraph [19]，以及基線 DGG [24]。DP-dK。首先將圖壓縮為KKK-連通分量的度分布（dK-series），向?qū)W習(xí)參數(shù)加入拉普拉斯噪聲，再使用 dK-series 模型 [36] 根據(jù)擾動(dòng)參數(shù)生成合成圖。DP-2K 根據(jù)平滑敏感度而非全局敏感度校準(zhǔn)噪聲，因此噪聲幅度更??；但所需隱私預(yù)算仍大得不合理，即?≥100\epsilon\ge100?≥100。TmF。先將圖表示為鄰接矩陣，再向每個(gè)單元加入拉普拉斯噪聲。最后選擇噪聲值最大的前mmm個(gè)單元作為隨機(jī)鄰接矩陣的邊，其中mmm是帶噪邊數(shù)。當(dāng)?\epsilon?較小時(shí)，絕大多數(shù)真實(shí)邊無(wú)法保留在前mmm個(gè)單元中。PrivSKG。使用隨機(jī) Kronecker 圖模型表示圖，并構(gòu)造真實(shí)參數(shù)的隱私估計(jì)器。該估計(jì)器定義圖上的概率分布，最后從中采樣生成合成圖。由于生成過(guò)程由單一參數(shù)決定，PrivSKG 無(wú)法準(zhǔn)確捕獲真實(shí)圖的結(jié)構(gòu)屬性。PrivHRG。首先使用統(tǒng)計(jì)分層隨機(jī)圖（HRG）模型 [37] 表示圖，記錄任意節(jié)點(diǎn)對(duì)之間的連接概率，再通過(guò) MCMC [38] 以隱私方式采樣樹狀圖，最后根據(jù)噪聲連接概率生成合成圖。構(gòu)造 HRG 模型時(shí)可能丟失部分真實(shí)圖信息。PrivGraph。先使用社區(qū)檢測(cè)算法生成粗粒度節(jié)點(diǎn)劃分，并以指數(shù)機(jī)制隱私化社區(qū)分區(qū)；隨后計(jì)算社區(qū)內(nèi)部的度序列和社區(qū)之間的邊數(shù)；最后使用 CL 模型 [39] 根據(jù)噪聲度序列生成合成圖。通過(guò)利用社區(qū)信息，它比先前方法保留更多結(jié)構(gòu)信息。DGG。節(jié)點(diǎn)度是圖的基礎(chǔ)信息，已用于隱私圖生成 [24], [26]。本文將 DGG [24] 修改為滿足邊級(jí)中央差分隱私。它先計(jì)算節(jié)點(diǎn)度并使用拉普拉斯機(jī)制擾動(dòng)，再用 BTER 模型 [40] 生成合成圖。DGG 無(wú)法捕獲度數(shù)之外的圖結(jié)構(gòu)，因而丟失真實(shí)圖的細(xì)節(jié)。備注 1。少量工作 [41], [42] 使用 GAN 等深度學(xué)習(xí)方法在 DP 下生成合成圖，本文不將其納入基準(zhǔn)。其一，這些工作的隱私目標(biāo)不同：本文算法主要保護(hù)圖結(jié)構(gòu)，而既有深度學(xué)習(xí)方法同時(shí)考慮圖結(jié)構(gòu)和節(jié)點(diǎn)特征，保護(hù)節(jié)點(diǎn)特征需要額外隱私預(yù)算。其二，查詢類型不同：深度學(xué)習(xí)方法生成的圖主要通過(guò)鏈接預(yù)測(cè)等深度學(xué)習(xí)任務(wù)評(píng)估，與本文的統(tǒng)計(jì)查詢不同。B. DP 基準(zhǔn)近年來(lái)，圖數(shù)據(jù)和表格數(shù)據(jù)上的差分隱私分析基準(zhǔn)受到廣泛關(guān)注。Ning 等人 [43] 通過(guò)考察隱私、準(zhǔn)確率和性能之間的權(quán)衡，實(shí)現(xiàn)并評(píng)測(cè)了度分布與子圖計(jì)數(shù)等圖查詢；這些實(shí)現(xiàn)被集成到 DPGraph [44]。DPGraph 是差分隱私圖分析平臺(tái)，重點(diǎn)幫助研究人員理解現(xiàn)有算法在度分布和子圖計(jì)數(shù)上的權(quán)衡。這些工作啟發(fā)了本文對(duì)差分隱私合成圖算法綜合基準(zhǔn)的設(shè)計(jì)。表格數(shù)據(jù)方面，DPBench [45] 是評(píng)估一維和二維范圍查詢等 DP 算法的原則性框架；DPComp [46] 是支持隱私數(shù)據(jù)分析原則性評(píng)估的公開 Web 系統(tǒng)；Tao 等人 [47] 系統(tǒng)評(píng)估 GAN、邊緣分布和工作負(fù)載驅(qū)動(dòng)的差分隱私表格合成數(shù)據(jù)方法；Basu 等人 [48] 評(píng)估使用抑郁和性騷擾推文進(jìn)行 BERT 中央與聯(lián)邦訓(xùn)練的效用；Sch?ler 等人 [49] 設(shè)計(jì)滿足所有要求的www-event DP 機(jī)制基準(zhǔn)；Rosenblatt 等人 [50] 提出以可復(fù)現(xiàn)性為基礎(chǔ)的 DP 合成器評(píng)估方法；Gonzalo 等人 [51] 比較五個(gè)主流開源 DP 庫(kù)；Dmitry 等人 [52] 綜述隱私風(fēng)險(xiǎn)攻擊、方法和指標(biāo)。由于圖具有獨(dú)特的隱私定義、表示與效用指標(biāo)，這些基準(zhǔn)不能直接用于圖數(shù)據(jù)。III. 預(yù)備知識(shí)A. 差分隱私DP [9], [10] 是個(gè)人隱私保護(hù)的事實(shí)標(biāo)準(zhǔn)。對(duì)于由節(jié)點(diǎn)和邊構(gòu)成的圖，可定義邊 DP 與節(jié)點(diǎn) DP [3]。邊 DP 隱藏某條好友關(guān)系是否存在；節(jié)點(diǎn) DP 隱藏某個(gè)用戶及其全部相鄰邊是否存在。節(jié)點(diǎn) DP 同時(shí)保護(hù)節(jié)點(diǎn)和邊，保證更強(qiáng)，但以效用為代價(jià)。定義 1（差分隱私 [9]）。給定隱私預(yù)算?0\epsilon0?0。若對(duì)于任意相差一條數(shù)據(jù)的相鄰數(shù)據(jù)庫(kù)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],則隨機(jī)算法M\mathcal MM滿足?\epsilon?-DP。定義 2（節(jié)點(diǎn) CDP [3]）。若任意相差一個(gè)節(jié)點(diǎn)及其全部相鄰邊的圖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?-節(jié)點(diǎn) DP。定義 3（邊 CDP [53]）。若任意只相差一條邊的圖G,G′G,G'G,G′都滿足上述不等式，則M\mathcal MM滿足?\epsilon?-邊 CDP。定義 4（邊 LDP [24]）。對(duì)任意用戶viv_ivi?，令Mi\mathcal M_iMi?為其隨機(jī)算法。若對(duì)任意只相差一條邊的鄰接位向量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 給出涵蓋調(diào)查中全部機(jī)制的通用差分隱私圖生成框架，包含表示、擾動(dòng)和構(gòu)造三個(gè)階段。圖 1：差分隱私圖生成算法的通用步驟：表示、擾動(dòng)和構(gòu)造。表示。對(duì)原圖建模并尋找緊湊表示，例如度信息 [14], [24], [26]、鄰接矩陣 [15]–[17] 或社區(qū)結(jié)構(gòu) [19], [20], [25], [29]。緊湊表示通過(guò)降低維度，減少為保障 DP 所需的噪聲。擾動(dòng)。向緊湊表示加入適當(dāng)噪聲，常用拉普拉斯機(jī)制 [54]、指數(shù)機(jī)制 [55] 和隨機(jī)響應(yīng) [56]。根據(jù)后處理性質(zhì) [9]，后續(xù)合成過(guò)程不會(huì)進(jìn)一步損害隱私。構(gòu)造。從擾動(dòng)表示構(gòu)造合成圖。BTER [40] 和 Chung-Lu（CL）[39] 等模型用于保留目標(biāo)結(jié)構(gòu)屬性。圖構(gòu)造器已有大量研究 [57]，不同工作采用不同構(gòu)造器，例如 LDPGen [24] 使用 BTER，PrivGraph [19] 使用 CL。備注 2。本文將差分隱私圖生成算法視為黑盒，目標(biāo)是為不同場(chǎng)景的算法選擇提供依據(jù)。算法內(nèi)部在表示、擾動(dòng)和構(gòu)造各步驟的具體選擇不屬于本基準(zhǔn)范圍。IV. 基準(zhǔn)設(shè)計(jì)原則本節(jié)闡述 PGB 的基本設(shè)計(jì)原則。這些原則對(duì)于全面、公平且有意義地比較差分隱私圖合成算法至關(guān)重要。既有工作經(jīng)常忽視它們，導(dǎo)致評(píng)估不完整或存在偏差。我們調(diào)查 CCS、VLDB、SIGMOD、TKDE 等會(huì)議和期刊的重要文獻(xiàn)，將實(shí)證研究的關(guān)鍵要素定義為四元組(M,G,P,U)(M,G,P,U)(M,G,P,U)：MMM：待比較機(jī)制的集合；GGG：圖數(shù)據(jù)集的集合；PPP：隱私要求的集合；UUU：效用指標(biāo)的集合。A. 機(jī)制MMM機(jī)制應(yīng)滿足四項(xiàng)原則M1M_1M1?–M4M_4M4?。1. 隱私定義（M1M_1