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 ${ \sf SNR}(n,k,p,q,\delta)$ is shown to characterize the fundamental limitations of inference via local algorithms. On the one hand, when ${ \sf SNR}>1$, the linearized message-passing algorithm provides the statistical inference guarantee with mis-classification rate at most $\exp(-({ \sf SNR}-1)/2)$, thus interpolating smoothly between strong and weak consistency. This exponential dependence improves upon the known error rate $({ \sf SNR}-1)^{ -1}$ in the literature on weak recovery. On the other hand, when ${ \sf SNR}<1$ (for $k=2$) and ${ \sf SNR}<1/4$ (for general growing $k$), we prove that local algorithms suffer an error rate at least $\frac{ 1}{ 2} - \sqrt{ \delta \cdot { \sf SNR}}$, which is only slightly better than random guess for small $\delta$.
Categories: math.ST stat.ML stat.TH