# Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 8 Oct 2025.

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

- [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)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy](https://mlsanity.com/paper/2208.04591/) (2022)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank](https://mlsanity.com/paper/2207.06944/) (2022)
- [Detecting Communities under Differential Privacy](https://mlsanity.com/paper/1607.02060/) (2016)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Consistent Spectral Clustering of Network Block Models under Local Differential Privacy](https://mlsanity.com/paper/2105.12615/) (2021)
- [Differentially Private Densest Subgraph](https://mlsanity.com/paper/2106.00508/) (2021)
- [Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2405.05724/) (2024)
- [Robustness of Locally Differentially Private Graph Analysis Against Poisoning](https://mlsanity.com/paper/2210.14376/) (2022)
- [Locally Differentially Private Graph Clustering via the Power Iteration Method](https://mlsanity.com/paper/2505.11169/) (2025)

## Abstract (arXiv)

We study spectral graph clustering under edge differential privacy. We propose a matrix shuffling mechanism that combines randomized edge flipping with a random permutation of the adjacency matrix. While edge flipping alone provides only a constant varepsilon guarantee as the graph grows, shuffling amplifies privacy so that the effective varepsilon tends to zero with the number of nodes. We develop a unified error analysis framework -- based on Davis--Kahan perturbation theory and a classification-margin bound -- that gives explicit misclassification rates for all the mechanisms considered as a function of the privacy budget, eigengap, and number of communities. Applying this framework, we show that the matrix shuffling mechanism achieves an error rate scaling of tildeO(1/n), a clear improvement over two canonical DP baselines from the private PCA literature: the Gaussian mechanism applied directly to the adjacency matrix (Analyze Gauss) and the noisy power method, both of which scale as tildeO(1) in n. We further propose a private spectral gap detection algorithm for estimating the number of communities. Experiments on synthetic and real-world networks validate our theoretical findings.