Graph data is used in a wide range of applications, while analyzing graph data without protection is prone to privacy breach risks. To mitigate the privacy risks, we resort to the standard technique of differential privacy to publish a synthetic graph. However, existing differentially private graph synthesis approaches either introduce excessive noise by directly perturbing the adjacency matrix, or suffer significant information loss during the graph encoding process. In this paper, we propose an effective graph synthesis algorithm PrivGraph by exploiting the community information. Concretely, PrivGraph differentially privately partitions the private graph into communities, extracts intra-community and inter-community information, and reconstructs the graph from the extracted graph information. We validate the effectiveness of PrivGraph on six real-world graph datasets and seven commonly used graph metrics.


翻译:图形数据在各种应用中得到了广泛的应用。分析图形数据时,如果没有保护,就很容易出现隐私泄漏的风险。为了减小隐私风险,我们采用标准的差分隐私技术来发布合成图形。然而,现有的差分隐私图形合成方法要么通过直接扰动邻接矩阵引入过度的噪声,要么在图形编码过程中遭受显著的信息损失。在本文中,我们提出了一种利用社区信息的有效图形合成算法,PrivGraph。具体而言,PrivGraph将私有图形差分地分成社区,提取社区内和社区间的信息,并从提取的图形信息中重新构建图形。我们在六个真实的图形数据集和七个常用的图形度量标准中验证了PrivGraph的有效性。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
4+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月22日
Arxiv
0+阅读 · 2023年5月19日
Adversarial Transfer Learning
Arxiv
12+阅读 · 2018年12月6日
Arxiv
11+阅读 · 2018年9月28日
VIP会员
相关VIP内容
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
4+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员