# Locally Differentially Private Analysis of Graph Statistics

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2020.

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

- [Towards Private Learning on Decentralized Graphs with Local Differential Privacy](https://mlsanity.com/paper/2201.09398/) (2022)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Preserving Node-level Privacy in Graph Neural Networks](https://mlsanity.com/paper/2311.06888/) (2023)
- [SoK: Differential Privacy on Graph-Structured Data](https://mlsanity.com/paper/2203.09205/) (2022)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Fine-grained Poisoning Attack to Local Differential Privacy Protocols for Mean and Variance Estimation](https://mlsanity.com/paper/2205.11782/) (2022)
- [Differentially Private Densest Subgraph Detection](https://mlsanity.com/paper/2105.13287/) (2021)
- [Blink: Link Local Differential Privacy in Graph Neural Networks via Bayesian Estimation](https://mlsanity.com/paper/2309.03190/) (2023)
- [On the Robustness of LDP Protocols for Numerical Attributes under Data Poisoning Attacks](https://mlsanity.com/paper/2403.19510/) (2024)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [Privacy-Preserving Graph Embedding based on Local Differential Privacy](https://mlsanity.com/paper/2310.11060/) (2023)
- [Robustness of Locally Differentially Private Graph Analysis Against Poisoning](https://mlsanity.com/paper/2210.14376/) (2022)
- [Privacy-Preserving Community Detection for Locally Distributed Multiple Networks](https://mlsanity.com/paper/2306.15709/) (2023)
- [On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models](https://mlsanity.com/paper/2505.05816/) (2025)
- [Differentially Private Graph Neural Network with Importance-Grained Noise Adaption](https://mlsanity.com/paper/2308.04943/) (2023)
- [Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions](https://mlsanity.com/paper/2312.07055/) (2023)
- [Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy](https://mlsanity.com/paper/2504.17274/) (2025)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)
- [HoGS: Homophily-Oriented Graph Synthesis for Local Differentially Private GNN Training](https://mlsanity.com/paper/2602.08762/) (2026)
- [Differentially Private Range Subgraph Counting](https://mlsanity.com/paper/2606.08179/) (2026)

## Abstract (arXiv)

Differentially private analysis of graphs is widely used for releasing statistics from sensitive graphs while still preserving user privacy. Most existing algorithms however are in a centralized privacy model, where a trusted data curator holds the entire graph. As this model raises a number of privacy and security issues -- such as, the trustworthiness of the curator and the possibility of data breaches, it is desirable to consider algorithms in a more decentralized local model where no server holds the entire graph. In this work, we consider a local model, and present algorithms for counting subgraphs -- a fundamental task for analyzing the connection patterns in a graph -- with LDP (Local Differential Privacy). For triangle counts, we present algorithms that use one and two rounds of interaction, and show that an additional round can significantly improve the utility. For k-star counts, we present an algorithm that achieves an order optimal estimation error in the non-interactive local model. We provide new lower-bounds on the estimation error for general graph statistics including triangle counts and k-star counts. Finally, we perform extensive experiments on two real datasets, and show that it is indeed possible to accurately estimate subgraph counts in the local differential privacy model.