# Differentially Private Community Detection for Stochastic Block Models

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 31 Jan 2022.

## Builds on (most cited first, 12 of 12)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Achieving Optimal Misclassification Proportion in Stochastic Block Model](https://mlsanity.com/paper/1505.03772/) (2015)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Private Graphon Estimation for Sparse Graphs](https://mlsanity.com/paper/1506.06162/) (2015)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions](https://mlsanity.com/paper/1502.07738/) (2015)
- [Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy](https://mlsanity.com/paper/1905.10477/) (2019)
- [Detecting Communities under Differential Privacy](https://mlsanity.com/paper/1607.02060/) (2016)

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

- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [Community detection with the Bethe-Hessian](https://mlsanity.com/paper/2411.02835/) (2024)
- [Privacy-Preserving Community Detection for Locally Distributed Multiple Networks](https://mlsanity.com/paper/2306.15709/) (2023)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models](https://mlsanity.com/paper/2505.05816/) (2025)
- [Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions](https://mlsanity.com/paper/2312.07055/) (2023)
- [PrIsing: Privacy-Preserving Peer Effect Estimation via Ising Model](https://mlsanity.com/paper/2401.16596/) (2024)
- [Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy](https://mlsanity.com/paper/2504.17274/) (2025)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)
- [Differentially Private Relational Learning with Entity-level Privacy Guarantees](https://mlsanity.com/paper/2506.08347/) (2025)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)
- [Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stability](https://mlsanity.com/paper/2605.01987/) (2026)
- [Near-optimal node-private community estimation in polynomial-time](https://mlsanity.com/paper/2607.09441/) (2026)

## Abstract (arXiv)

The goal of community detection over graphs is to recover underlying labels/attributes of users (e.g., political affiliation) given the connectivity between users (represented by adjacency matrix of a graph). There has been significant recent progress on understanding the fundamental limits of community detection when the graph is generated from a stochastic block model (SBM). Specifically, sharp information theoretic limits and efficient algorithms have been obtained for SBMs as a function of p and q, which represent the intra-community and inter-community connection probabilities. In this paper, we study the community detection problem while preserving the privacy of the individual connections (edges) between the vertices. Focusing on the notion of (ε, δ)-edge differential privacy (DP), we seek to understand the fundamental tradeoffs between (p, q), DP budget (ε, δ), and computational efficiency for exact recovery of the community labels. To this end, we present and analyze the associated information-theoretic tradeoffs for three broad classes of differentially private community recovery mechanisms: a) stability based mechanism; b) sampling based mechanisms; and c) graph perturbation mechanisms. Our main findings are that stability and sampling based mechanisms lead to a superior tradeoff between (p,q) and the privacy budget (ε, δ); however this comes at the expense of higher computational complexity. On the other hand, albeit low complexity, graph perturbation mechanisms require the privacy budget ε to scale as Omega(log(n)) for exact recovery. To the best of our knowledge, this is the first work to study the impact of privacy constraints on the fundamental limits for community detection.