Belief Propagation, Robust Reconstruction and Optimal Recovery of Block Models
Abstract
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 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 robust reconstruction for the Ising model on regular and Poisson trees.
Cite
Text
Mossel et al. "Belief Propagation, Robust Reconstruction and Optimal Recovery of Block Models." Annual Conference on Computational Learning Theory, 2014. doi:10.1214/15-AAP1145Markdown
[Mossel et al. "Belief Propagation, Robust Reconstruction and Optimal Recovery of Block Models." Annual Conference on Computational Learning Theory, 2014.](https://mlanthology.org/colt/2014/mossel2014colt-belief/) doi:10.1214/15-AAP1145BibTeX
@inproceedings{mossel2014colt-belief,
title = {{Belief Propagation, Robust Reconstruction and Optimal Recovery of Block Models}},
author = {Mossel, Elchanan and Neeman, Joe and Sly, Allan},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2014},
pages = {356-370},
doi = {10.1214/15-AAP1145},
url = {https://mlanthology.org/colt/2014/mossel2014colt-belief/}
}