An Efficient Private Algorithm for Community Detection
For researchers in privacy-preserving graph analysis, this work provides efficient algorithms that achieve exact recovery under differential privacy, a previously unsolved problem for practical parameter ranges.
This paper introduces the first differentially private algorithms for exact community detection in the stochastic block model, achieving near-linear time and space complexity while enabling exact recovery across a wide range of parameters. The algorithms scale to graphs with two orders of magnitude more nodes than prior work.
In this paper, we study the community detection problem in the stochastic block model (SBM) under privacy constraints. We introduce private and highly efficient algorithms for exact community detection within the SBM framework. Our algorithms represent the first differentially private methods capable of achieving exact recovery in a wide range of model parameters with near-linear time and space complexity. This is a significant improvement over previous SBM recovery algorithms, which either required pseudo-polynomial time or a quadratic scaling of resources for a constant privacy budget. Central to our approach is the introduction of a new concept, adaptive disjoint-star algorithms. These algorithms efficiently explore the graph's structure by querying node degrees on edge-disjoint subgraphs. We demonstrate that this general class of algorithms inherently offers strong privacy guarantees, a result that potentially holds value beyond the scope of SBM community detection. Finally, in we perform an empirical analysis of our algorithms showing that they can scale exact recovery on graphs with two orders of magnitude more nodes than prior work.