Inference via Message Passing on Partially Labeled Stochastic Block Models

Abstract

We study the community detection and recovery problem in partially-labeled stochastic block models (SBM). We develop a fast linearized message-passing algorithm to reconstruct labels for SBM (with $n$ nodes, $k$ blocks, $p,q$ intra and inter block connectivity) when $\delta$ proportion of node labels are revealed. The signal-to-noise ratio $\mathsf{SNR}(n,k,p,q,\delta )$ is shown to characterize the fundamental limitations of inference via local algorithms. On the one hand, when $\mathsf{SNR}>1$, the linearized message-passing algorithm provides the statistical inference guarantee with mis-classification rate at most $\exp (-(\mathsf{SNR}-1)/2)$, thus interpolating smoothly between strong and weak consistency. This exponential dependence improves upon the known error rate $(\mathsf{SNR}-1{)}^{-1}$ in the literature on weak recovery. On the other hand, when $\mathsf{SNR}<1$ (for $k=2$) and $\mathsf{SNR}<1/4$ (for general growing $k$), we prove that local algorithms suffer an error rate at least $\frac{1}{2}-\sqrt{\delta \cdot \mathsf{SNR}}$, which is only slightly better than random guess for small $\delta$.

arXiv comment33 pages, 4 figures

References in corpus (10)

• Spectral redemption: clustering sparse networks
• Fast community detection by SCORE
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Stochastic Block Models and Reconstruction
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Phase transitions in semisupervised clustering of sparse networks
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Global and Local Information in Clustering Labeled Block Models

Cited by in corpus (7)

• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Fast Randomized Semi-Supervised Clustering
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• The Power of Side-information in Subgraph Detection
• Semi-supervised learning in unbalanced and heterogeneous networks