On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models
By: Antti Koskela, Mohamed Seif, Andrea J. Goldsmith
Potential Business Impact:
Finds hidden groups in data without sharing secrets.
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.
Similar Papers
Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency
Information Theory
Keeps online connections private while still working.
Differentially Private Community Detection in $h$-uniform Hypergraphs
Information Theory
Keeps private data safe when sharing network maps.
On the Price of Differential Privacy for Hierarchical Clustering
Data Structures and Algorithms
Organizes private data into groups with less error.