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的有效性。