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\epsilon20?20時 DP-2K [14] 的誤差低于 DK-1K [14]；當?≤20\epsilon\le20?≤20時結果相反。所有調查算法都只覆蓋圖查詢的一個子集；即使評估相同查詢，也可能使用不同誤差指標。例如 PrivHRG [18] 使用歸一化互信息 [30] 衡量社區檢測效用，LF-GDPR [26] 則使用調整蘭德指數 [31] 和調整互信息 [32]。本文提出綜合基準 PGB，主要貢獻如下：基準設計原則。基于全面文獻調查，將實證研究概括為四元組(M,G,P,U)(M,G,P,U)(M,G,P,U)：機制、圖數據集、隱私要求和效用指標。針對每個要素分析現有工作的局限，并提出保證結果可比的要求（第 IV 節）。基準實例化。提出滿足全部設計原則的 PGB，用于評估差分隱私圖生成算法。代碼和基準平臺均公開，未來工作可以方便地加入比較（第 V 節）。實證研究與發現。完成迄今規模最大的隱私圖生成算法實證評估，至少包含 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\epsilon0?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：差分隱私圖生成算法的通用步驟：表示、擾動和構造。表示。對原圖建模并尋找緊湊表示，例如度信息 [14], [24], [26]、鄰接矩陣 [15]–[17] 或社區結構 [19], [20], [25], [29]。緊湊表示通過降低維度，減少為保障 DP 所需的噪聲。擾動。向緊湊表示加入適當噪聲，常用拉普拉斯機制 [54]、指數機制 [55] 和隨機響應 [56]。根據后處理性質 [9]，后續合成過程不會進一步損害隱私。構造。從擾動表示構造合成圖。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 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\epsilon20?20時 DP-2K [14] 的誤差低于 DK-1K [14]；當?≤20\epsilon\le20?≤20時結果相反。所有調查算法都只覆蓋圖查詢的一個子集；即使評估相同查詢，也可能使用不同誤差指標。例如 PrivHRG [18] 使用歸一化互信息 [30] 衡量社區檢測效用，LF-GDPR [26] 則使用調整蘭德指數 [31] 和調整互信息 [32]。本文提出綜合基準 PGB，主要貢獻如下：基準設計原則。基于全面文獻調查，將實證研究概括為四元組(M,G,P,U)(M,G,P,U)(M,G,P,U)：機制、圖數據集、隱私要求和效用指標。針對每個要素分析現有工作的局限，并提出保證結果可比的要求（第 IV 節）。基準實例化。提出滿足全部設計原則的 PGB，用于評估差分隱私圖生成算法。代碼和基準平臺均公開，未來工作可以方便地加入比較（第 V 節）。實證研究與發現。完成迄今規模最大的隱私圖生成算法實證評估，至少包含 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\epsilon0?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：差分隱私圖生成算法的通用步驟：表示、擾動和構造。表示。對原圖建模并尋找緊湊表示，例如度信息 [14], [24], [26]、鄰接矩陣 [15]–[17] 或社區結構 [19], [20], [25], [29]。緊湊表示通過降低維度，減少為保障 DP 所需的噪聲。擾動。向緊湊表示加入適當噪聲，常用拉普拉斯機制 [54]、指數機制 [55] 和隨機響應 [56]。根據后處理性質 [9]，后續合成過程不會進一步損害隱私。構造。從擾動表示構造合成圖。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