# Privacy-Preserving Community Detection for Locally Distributed Multiple Networks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 74 references that are in the map.
- First posted on arXiv 27 Jun 2023.

## Builds on (most cited first, 30 of 35)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [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)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Multilayer Networks](https://mlsanity.com/paper/1309.7233/) (2013)
- [The structure and dynamics of multilayer networks](https://mlsanity.com/paper/1407.0742/) (2014)
- [Inference for multiple heterogeneous networks with a common invariant subspace](https://mlsanity.com/paper/1906.10026/) (2019)
- [Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition](https://mlsanity.com/paper/2002.04457/) (2020)
- [Spectral and matrix factorization methods for consistent community detection in multi-layer networks](https://mlsanity.com/paper/1704.07353/) (2017)
- [Network cross-validation by edge sampling](https://mlsanity.com/paper/1612.04717/) (2016)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Private Graphon Estimation for Sparse Graphs](https://mlsanity.com/paper/1506.06162/) (2015)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Community detection in multi-relational data with restricted multi-layer stochastic blockmodel](https://mlsanity.com/paper/1506.02699/) (2015)
- [Latent space models for multiplex networks with shared structure](https://mlsanity.com/paper/2012.14409/) (2020)
- [Distributed High-dimensional Regression Under a Quantile Loss Function](https://mlsanity.com/paper/1906.05741/) (2019)
- [Communication-Efficient Distributed SVD via Local Power Iterations](https://mlsanity.com/paper/2002.08014/) (2020)
- [Detecting Communities under Differential Privacy](https://mlsanity.com/paper/1607.02060/) (2016)
- [Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis](https://mlsanity.com/paper/1702.08169/) (2017)
- [Determining the Number of Communities in Degree-corrected Stochastic Block Models](https://mlsanity.com/paper/1809.01028/) (2018)
- [Randomized Spectral Clustering in Large-Scale Stochastic Block Models](https://mlsanity.com/paper/2002.00839/) (2020)
- [Producing a Unified Graph Representation from Multiple Social Network Views](https://mlsanity.com/paper/1301.5809/) (2013)
- [Spectral Clustering for Multiple Sparse Networks: I](https://mlsanity.com/paper/1805.10594/) (2018)
- [Randomized spectral co-clustering for large-scale directed networks](https://mlsanity.com/paper/2004.12164/) (2020)
- [Towards effective visual analytics on multiplex and multilayer networks](https://mlsanity.com/paper/1501.01666/) (2015)
- [Distribution-Invariant Differential Privacy](https://mlsanity.com/paper/2111.05791/) (2021)
- [Sharing Social Network Data: Differentially Private Estimation of Exponential-Family Random Graph Models](https://mlsanity.com/paper/1511.02930/) (2015)

## Built on by (most cited first, 2 of 2)

- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [Enhancing Differentially Private Linear Regression via Public Second-Moment](https://mlsanity.com/paper/2508.18037/) (2025)

## Abstract (arXiv)

Modern multi-layer networks are commonly stored and analyzed in a local and distributed fashion because of the privacy, ownership, and communication costs. The literature on the model-based statistical methods for community detection based on these data is still limited. This paper proposes a new method for consensus community detection and estimation in a multi-layer stochastic block model using locally stored and computed network data with privacy protection. A novel algorithm named privacy-preserving Distributed Spectral Clustering (ppDSC) is developed. To preserve the edges' privacy, we adopt the randomized response (RR) mechanism to perturb the network edges, which satisfies the strong notion of differential privacy. The ppDSC algorithm is performed on the squared RR-perturbed adjacency matrices to prevent possible cancellation of communities among different layers. To remove the bias incurred by RR and the squared network matrices, we develop a two-step bias-adjustment procedure. Then we perform eigen-decomposition on the debiased matrices, aggregation of the local eigenvectors using an orthogonal Procrustes transformation, and k-means clustering. We provide theoretical analysis on the statistical errors of ppDSC in terms of eigen-vector estimation. In addition, the blessings and curses of network heterogeneity are well-explained by our bounds.