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 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 (-( 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 12 - SNR, which is only slightly better than random guess for small .

Tasks

Reproductions