On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models
Not on the map. Why?
Abstract (arXiv)
We investigate privacy-preserving spectral clustering for community detection within stochastic block models (SBMs). Specifically, we focus on edge differential privacy (DP) and propose private algorithms for community recovery. Our work explores the fundamental trade-offs between the privacy budget and the accurate recovery of community labels. Furthermore, we establish information-theoretic conditions that guarantee the accuracy of our methods, providing theoretical assurances for successful community recovery under edge DP.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 16 of its 38 references that are in the map. First posted on arXiv 9 May 2025.
Builds on
16 of 38 references.
References · 16
- 2017Community Detection and Stochastic Block Modelscited by 319
- 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 218
- 2021Numerical Composition of Differential Privacycited by 180
- 2013Consistency of spectral clustering in stochastic block modelscited by 129
- 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 86
- 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
- 2014Achieving Exact Cluster Recovery Threshold via Semidefinite Programmingcited by 33
- 2015Concentration and regularization of random graphscited by 25
- 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
- 2020Locally Differentially Private Analysis of Graph Statisticscited by 20
- 2021Private Graph Data Release: A Surveycited by 15
- 2022Differentially Private Community Detection for Stochastic Block Modelscited by 15
4 more
- 2016Detecting Communities under Differential Privacycited by 10
- 2021Consistent Spectral Clustering of Network Block Models under Local Differential Privacycited by 6
- 2024Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limitscited by 3
- 2022The Power of Two Matrices in Spectral Algorithms for Community Recoverycited by 2
Built on by
Citing papers per year: 2026: 2.
2 papers.