# PrivGraph: Differentially Private Graph Data Publication by Exploiting Community Information

arXiv: https://arxiv.org/abs/2304.02401 · HTML: https://mlsanity.com/paper/2304.02401/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2023.

## Built on by (most cited first, 13 of 13)

- [SoK: Dataset Copyright Auditing in Machine Learning Systems](https://mlsanity.com/paper/2410.16618/) (2024)
- [DPMLBench: Holistic Evaluation of Differentially Private Machine Learning](https://mlsanity.com/paper/2305.05900/) (2023)
- [ORL-AUDITOR: Dataset Auditing in Offline Deep Reinforcement Learning](https://mlsanity.com/paper/2309.03081/) (2023)
- [DPAdapter: Improving Differentially Private Deep Learning through Noise Tolerance Pre-training](https://mlsanity.com/paper/2403.02571/) (2024)
- [A Survey on Evaluating Quality and Trustworthiness in LLM-Generated Data](https://mlsanity.com/paper/2601.17717/) (2026)
- [S2NeRF: Privacy-preserving Training Framework for NeRF](https://mlsanity.com/paper/2409.01661/) (2024)
- [Adaptive Differentially Private Structural Entropy Minimization for Unsupervised Social Event Detection](https://mlsanity.com/paper/2407.18274/) (2024)
- [CoPHo: Classifier-guided Conditional Topology Generation with Persistent Homology](https://mlsanity.com/paper/2512.19736/) (2025)
- [Taipan: A Query-free Transfer-based Multiple Sensitive Attribute Inference Attack Solely from Auxiliary Graphs](https://mlsanity.com/paper/2602.06700/) (2026)
- [HoGS: Homophily-Oriented Graph Synthesis for Local Differentially Private GNN Training](https://mlsanity.com/paper/2602.08762/) (2026)
- [Differentially Private Modeling of Disease Transmission within Human Contact Networks](https://mlsanity.com/paper/2604.07493/) (2026)
- [DP-SelFT: Differentially Private Selective Fine-Tuning for Large Language Models](https://mlsanity.com/paper/2605.17432/) (2026)
- [Empirical Auditing of Edge-Private Graph Generators](https://mlsanity.com/paper/2609.25155/) (2026)

## Abstract (arXiv)

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.