  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$.
