论文题目：PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs
Songlei Wang1, Yifeng Zheng2, Xiaohua Jia3, Haibo Hu2
1 Shenzhen University
2 The Hong Kong Polytechnic University
3 City University of Hong Kong
导读：我院王松磊老师的最新研究成果《PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs》近期发表于国际数据库顶级会议VLDB 2025（CCF-A、CS Rankings）。该成果由深圳大学人工智能学院、香港理工大学、香港城市大学合作完成，面向去中心化社交网络中关系敏感、数据难以集中、隐私风险显著的关键挑战，提出了差分隐私分布式图生成模型PrivAGM。PrivAGM基于差分隐私（Differential Privacy）与安全多方计算（Secure Multiparty Computation）的协同建模机制，无需暴露真实用户的社交关系即可安全构建有向属性图生成模型，从而实现去分布式社交图的隐私合成与高保真结构重建。
引言：在去中心化社交网络中，用户的关系与属性信息分散存储于各终端节点，平台或研究机构难以在不违反隐私合规的前提下直接获取完整社交图进行分析。由于社交关系高度敏感，涉及个人兴趣、社群归属等，直接汇聚或共享数据将带来严重的隐私泄露风险。因此，如何在不暴露真实社交关系的前提下生成可用于分析的高保真社交图，成为分布式图数据分析的关键难题。尽管现有差分隐私图生成方法在集中式场景下可以取得较好效果，但在分布式数据持有、多方安全协同、有向与属性关联结构建模等方面仍存在明显不足。针对上述挑战，本文提出了差分隐私分布式图生成模型，在无需收集分布式图数据的前提下，实现图数据的隐私合成与结构保真重建，为可信社会计算、数字安全治理及跨机构数据协同提供了新的技术方向。
核心贡献：
1. 稀疏感知的分布式图数据聚合机制：通过将Randomized Neighbor List（RNL）机制与Selective MPC进行分层融合，实现了隐私保护、图结构稀疏性保留与安全高效邻居节点访问之间的三重平衡。
2. 差分隐私图统计特征提取：构建面向有向属性图的差分隐私特征提取方法，支持对节点度分布、属性—边相关性、三角子图结构等关键结构信息进行安全统计，确保隐私泄露可控且可量化。
3. 高保真有向属性图生成与边重连策略：通过对经典Chung–Lu图生成框架进行有向化扩展，并引入基于属性相关性的边重连机制，模型能够在差分隐私保护下同时保持图的方向性特征、社交语义一致性与整体结构稳定性，从而实现高保真的有向属性图重建。
方法介绍：
图1 PrivAGM的模型框架
1. 模型框架：图1展示了PrivAGM的整体模型流程。首先，模型通过稀疏感知的安全邻居聚合机制，在不暴露原始图结构的前提下高效汇聚分布式图数据，并结合差分隐私约束元数据的信息泄露上限。模型在安全多方计算范式下提取关键图统计特征，并在计算过程中注入差分隐私噪声，从而在保证隐私可控的前提下，使生成的模型参数具备良好的数据可用性。最后，将经典的Chung–Lu图生成机制进行有向化扩展，并融合属性驱动的概率采样与边重连策略，生成在结构形态、方向性模式与属性关联上均高度贴近原始图的高保真隐私合成图，实现从隐私输入→安全建模→图生成与共享的完整闭环。
图2 稀疏感知的分布式图数据聚合框架
2. 稀疏感知的分布式图数据聚合：针对分布式社交网络中如何在隐私保护前提下高效聚合邻居节点这一核心难题，本文提出了一种兼具差分隐私强度、稀疏性保留与邻居节点可访问性的安全聚合机制（见图2）。首先，研究发现，传统基于邻接矩阵的密集编码方式会显著破坏图数据的稀疏性，导致通信与计算成本剧增；而基于倒排结构的稀疏编码虽然能降低开销，但难以支持后续建模所需的高效、安全邻居节点访问。基于这一“隐私—稀疏性—可用性”三者之间的结构性矛盾，本文提出将RNL机制与Selective MPC进行分层融合。该方法既避免了传统RNL扰动导致图结构严重失真问题，也克服了稀疏编码无法进行高效邻居节点访问的技术瓶颈，从而实现隐私保护、稀疏性保留与高效邻居节点访问的三重平衡。
图3 高保真有向属性图生成框架
3. 高保真有向属性图生成：图3展示了该模型的整体框架。首先，模型在经典Chung–Lu图生成机制的基础上引入方向性设计，并从差分隐私的度分布上采样得到初始有向边集合。在此之上，提出基于三角结构对齐的边重连算法，通过逐步调整图结构，在差分隐私约束下恢复原始图的局部三角子图模式与结构特性。除了结构重建，该方法还基于提取的差分隐私属性分布为每个节点生成属性向量，并利用属性—边相关性分布构建Accept/Reject采样机制，迭代式更新有向边集合，使生成图在属性驱动的连接模式上逼近真实数据。通过“方向感知+三角结构对齐+属性相关性重建”三重机制，最终构建兼具方向性语义、三角结构模式与属性关联规律的高保真差分隐私有向属性图。
实验结果：
图4 稀疏感知的分布式图数据聚合开销对比
实验一：稀疏感知的分布式图数据聚合开销对比
图4的实验结果显示，在稀疏感知机制的加持下，用户向每个服务器上传的数据量仅为2.1 KB（MOOC）、23.8 KB（Twitter）和31.5 KB（Gplus），远小于用户本地邻居列表的真实规模。“本地数据/上传数据”比例分别仅为0.25、0.01、0.05，充分体现了所提出的分布式图数据聚合方法在通信成本上的优势。在相同隐私预算条件下，该方法相比直接对完整邻居列表进行保护，可节省最高达90%的存储开销。这些结果共同验证了基于RNL + Selective MPC的设计在降低通信与存储开销、减轻信道负载、提升分布式可扩展性等方面具备显著优势。
图5 各方法生成图的结构保真度对比
实验二：各方法生成图的结构保真度对比
本实验采用KS统计量与Hellinger距离两项指标评估合成图的结构保真度：前者衡量两者累计分布之间的最大差异，后者进一步刻画分布在细粒度上的差异程度。图5的实验结果显示，在相同隐私预算下，PrivAGM在两项指标上均显著优于对比方法，表明其生成图在入度/出度模式、局部连接结构以及整体拓扑形态上均更接近真实图数据。实验结果充分说明，PrivAGM能在严格差分隐私保护的前提下，重建高保真的有向属性图。
总结展望：本文提出的方法在分布式场景下实现了差分隐私保护、有向结构表达与属性关联建模的有机融合，有效应对了传统隐私图生成方法在数据分散、关系敏感与结构复杂性条件下难以同时兼顾“隐私—可用—效率”的问题。通过稀疏感知的图数据聚合、差分隐私图特征建模以及高保真的有向属性图生成机制，该方法能在不暴露真实图结构的前提下合成有向属性图，为隐私敏感场景下的图数据分析提供一条可行的技术路径和新的研究思路。
然而，差分隐私图生成模型仍存在广阔的研究空间。例如，如何进一步支持动态图与流式图处理，适应跨域协同场景下的图计算需求，以及在真实应用中构建更具鲁棒性与可解释性的隐私图合成机制，都是未来值得持续探索的方向。
