# Belief propagation, robust reconstruction and optimal recovery of block models

arXiv: https://arxiv.org/abs/1309.1380 · HTML: https://mlsanity.com/paper/1309.1380/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2013.

## Built on by (most cited first, 18 of 18)

- [How transformers learn structured data: insights from hierarchical filtering](https://mlsanity.com/paper/2408.15138/) (2024)
- [Correlation detection in trees for planted graph alignment](https://mlsanity.com/paper/2107.07623/) (2021)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions](https://mlsanity.com/paper/2305.10227/) (2023)
- [Semidefinite Programming for Community Detection with Side Information](https://mlsanity.com/paper/2105.02816/) (2021)
- [Secrets of GFlowNets' Learning Behavior: A Theoretical Study](https://mlsanity.com/paper/2505.02035/) (2025)
- [Community Detection: Exact Recovery in Weighted Graphs](https://mlsanity.com/paper/2102.04439/) (2021)
- [Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information](https://mlsanity.com/paper/2201.05923/) (2022)
- [Ergodic Limits, Relaxations, and Geometric Properties of Random Walk Node Embeddings](https://mlsanity.com/paper/2109.04526/) (2021)
- [Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables](https://mlsanity.com/paper/2301.04088/) (2023)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [Streaming Belief Propagation for Community Detection](https://mlsanity.com/paper/2106.04805/) (2021)
- [Adversarially-Robust Inference on Trees via Belief Propagation](https://mlsanity.com/paper/2404.00768/) (2024)
- [Multi-View Stochastic Block Models](https://mlsanity.com/paper/2406.04860/) (2024)
- [The Spectral Barycentre of a Set of Graphs with Community Structure](https://mlsanity.com/paper/2502.00038/) (2025)

## Abstract (arXiv)

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