PrivGraph: Differentially Private Graph Data Publication by Exploiting Community Information


Quan Yuan, Zhejiang University; Zhikun Zhang, Stanford University and CISPA Helmholtz Center for Information Security; Linkang Du, Zhejiang University; Min Chen, CISPA Helmholtz Center for Information Security; Peng Cheng and Mingyang Sun, Zhejiang University


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.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {291046,
author = {Quan Yuan and Zhikun Zhang and Linkang Du and Min Chen and Peng Cheng and Mingyang Sun},
title = {{PrivGraph}: Differentially Private Graph Data Publication by Exploiting Community Information},
booktitle = {32nd USENIX Security Symposium (USENIX Security 23)},
year = {2023},
isbn = {978-1-939133-37-3},
address = {Anaheim, CA},
pages = {3241--3258},
url = {},
publisher = {USENIX Association},
month = aug

Presentation Video