On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models
This work addresses privacy concerns in community detection for applications like social network analysis, but it is incremental as it builds on existing differential privacy and spectral clustering methods.
The paper tackles the problem of privacy-preserving community detection in stochastic block models using edge differential privacy, establishing fundamental trade-offs between privacy budget and accurate recovery of community labels with theoretical guarantees.
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.