# Consistent Spectral Clustering of Network Block Models under Local Differential Privacy

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2021.

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

- [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)
- [Fitting Low-rank Models on Egocentrically Sampled Partial Networks](https://mlsanity.com/paper/2303.11230/) (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)
- [Near-optimal node-private community estimation in polynomial-time](https://mlsanity.com/paper/2607.09441/) (2026)

## Abstract (arXiv)

The stochastic block model (SBM) and degree-corrected block model (DCBM) are network models often selected as the fundamental setting in which to analyze the theoretical properties of community detection methods. We consider the problem of spectral clustering of SBM and DCBM networks under a local form of edge differential privacy. Using a randomized response privacy mechanism called the edge-flip mechanism, we develop theoretical guarantees for differentially private community detection, demonstrating conditions under which this strong privacy guarantee can be upheld while achieving spectral clustering convergence rates that match the known rates without privacy. We prove the strongest theoretical results are achievable for dense networks (those with node degree linear in the number of nodes), while weak consistency is achievable under mild sparsity (node degree greater than √n). We empirically demonstrate our results on a number of network examples.