Abstract:

To address the challenges of limited feature extraction from sensitive subgraph data and the insufficient utility of synthetic graphs under strong privacy constraints in distributed graph scenarios， a Distributed graph publishing method based on dual-granularity privacy protection （DPP-DGP） was proposed. During the data collection phase， both coarse-grained and fine-grained information were acquired. Specifically， degree information was perturbed by the random jump algorithm， and neighbor lists were perturbed through randomized response. The neighbor lists were then sampled based on the perturbed degree information. During the synthetic graph generation phase， after receiving the privacy subgraph information from users， the data publisher employed a community detection algorithm to obtain community information，thereby retaining more topological structures. At the same time， edges were generated randomly based on edge count outside the community， and edges were generated within the community using a degree-sequence-based random graph generation method. Experimental results on four real-world datasets （email-Eu-core， Chameleon， Facebook， Wiki-Vote） show that the proposed method preserves more topological information on published synthetic graphs while guaranteeing differential privacy， compared with current distributed graph publishing methods such as Randomized Neighbor List and LDPGen. For instance， the Kullback-Leibler（KL）divergence of degree distribution of the proposed method is at least 8.0 lower than those of the baseline methods， and all four metrics（KL divergence of degree distribution， relative error of modularity， relative error of eigenvector centrality， and average path length） perform well under strong privacy protection.

Key words: local differential privacy, decentralized network graph, dual-granularity privacy protection, synthetic graph generation, community detection

摘要：

针对分布式图场景下，敏感子图数据可提取特征有限且强隐私约束下的合成图可用性不足的问题，提出一种基于双粒度隐私保护的分布式图发布方法（DPP-DGP）。本文方法在数据采集阶段获得粗细双粒度信息，分别为随机跳跃算法扰动后的度信息与随机响应扰动的邻居列表，并利用扰动度信息对邻居列表进行采样校准；在合成图生成阶段，数据发布方接收用户方传递的隐私子图信息后，使用社区发现算法获得社区信息以保留更多的拓扑结构，并在社区外部基于边数随机生成边，而在社区内部基于度序列随机生成图方法生成边。在email-Eu-core、Chameleon、Facebook和Wiki-Vote4个真实数据集上的实验结果表明，本文方法发布的合成图在保证差分隐私的同时，相较于随机邻居列表和LDPGen等分布式图发布方法可保留更多的拓扑信息，例如在度分布KL（Kullback-Leibler）散度上较基线方法低8.0以上，且4项指标（度分布KL散度、模块化相对误差、特征向量中心性相对误差和平均路径长度）在强隐私保护下均表现良好。

关键词: 本地差分隐私, 分布式网络图, 双粒度隐私保护, 合成图生成, 社区发现