Belief Propagation, Robust Reconstruction, and Optimal Recovery of Block Models

Elchanan Mossel, Joe Neeman, Allan Sly

Published 2013-09-05, updated 2015-02-01Version 2

We consider the problem of reconstructing sparse symmetric block models with two blocks and connection probabilities $a/n$ and $b/n$ for inter- and intra-block edge probabilities respectively. It was recently shown that one can do better than a random guess if and only if $(a-b)^2 > 2(a+b)$. Using a variant of Belief Propagation, we give a reconstruction algorithm that is \emph{optimal} in the sense that if $(a-b)^2 > C (a+b)$ for some constant $C$ then our algorithm maximizes the fraction of the nodes labelled correctly. Along the way we prove some results of independent interest regarding {\em robust reconstruction} for the Ising model on regular and Poisson trees.