Inference via Message Passing on Partially Labeled Stochastic Block Models
Tony Cai, Tengyuan Liang and Alexander Rakhlin
-
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 δ proportion of node labels are revealed. The signal-to-noise ratio SNR(n,k,p,q,δ) is shown to characterize the fundamental limitations of inference via local algorithms. On the one hand, when SNR > 1, the linearized message-passing algorithm provides the statistical inference guarantee with mis-classification rate at most exp(-(SNR-1)/2), thus interpolating smoothly between strong and weak consistency. This exponential dependence improves upon the known error rate (SNR-1)-1 in the literature on weak recovery. On the other hand, when SNR < 1 (for k = 2) and SNR < 1/4 (for general growing k), we prove that local algorithms suffer an error rate at least 1/2 - √ δ ⋅ SNR , which is only slightly better than random guess for small δ.
- Paper: pdf file.