Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel, Joe Neeman, Allan Sly

Research output: Contribution to journalArticle

13 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- A nd 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 labeled correctly. Ours is the only algorithm proven to achieve the optimal fraction of nodes labeled 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)2211-2256
Number of pages46
JournalAnnals of Applied Probability
Volume26
Issue number4
DOIs
StatePublished - Aug 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

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