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