Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel, Joe Neeman, Allan Sly
Proceedings of The 27th Conference on Learning Theory, PMLR 35:356-370, 2014.

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 \emphoptimal 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-mossel14, title = {Belief propagation, robust reconstruction and optimal recovery of block models}, author = {Mossel, Elchanan and Neeman, Joe and Sly, Allan}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {356--370}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/mossel14.pdf}, url = {https://proceedings.mlr.press/v35/mossel14.html}, 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 \emphoptimal 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. } }
Endnote
%0 Conference Paper %T Belief propagation, robust reconstruction and optimal recovery of block models %A Elchanan Mossel %A Joe Neeman %A Allan Sly %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-mossel14 %I PMLR %P 356--370 %U https://proceedings.mlr.press/v35/mossel14.html %V 35 %X 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 \emphoptimal 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.
RIS
TY - CPAPER TI - Belief propagation, robust reconstruction and optimal recovery of block models AU - Elchanan Mossel AU - Joe Neeman AU - Allan Sly BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-mossel14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 356 EP - 370 L1 - http://proceedings.mlr.press/v35/mossel14.pdf UR - https://proceedings.mlr.press/v35/mossel14.html AB - 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 \emphoptimal 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. ER -
APA
Mossel, E., Neeman, J. & Sly, A.. (2014). Belief propagation, robust reconstruction and optimal recovery of block models. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:356-370 Available from https://proceedings.mlr.press/v35/mossel14.html.

Related Material