Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel, Joe Neeman, Allan Sly

Research output: Contribution to journalConference article

36 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)356-370
Number of pages15
JournalJournal of Machine Learning Research
Volume35
StatePublished - Jan 1 2014
Externally publishedYes
Event27th Conference on Learning Theory, COLT 2014 - Barcelona, Spain
Duration: Jun 13 2014Jun 15 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Belief propagation, robust reconstruction and optimal recovery of block models'. Together they form a unique fingerprint.

  • Cite this