Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel; Joe Neeman; Allan Sly

Source-linked AI summary

Belief propagation, robust reconstruction and optimal recovery of block models

Elchanan Mossel, Joe Neeman, Allan Sly

arXiv:1309.1380v4Sep 5, 2013math.PRcs.SI

TL;DR

The paper asks how accurately communities can be recovered in sparse stochastic block models when exact recovery is impossible. It uses a belief-propagation variant initialized from a weak clustering to improve the labels, and proves optimal recovery at sufficiently high signal-to-noise ratio. Its analysis also establishes robust reconstruction results for regular and Poisson trees.

Problem
Sparse block models allow only a constant fraction of labels to be recovered, motivating the question of whether the best achievable recovery accuracy can be attained algorithmically.
Method
A belief-propagation algorithm locally improves an initial clustering, supported by an analysis of robust reconstruction on trees.
Results
The algorithm achieves the optimal asymptotic accuracy pG(a,b) with probability tending to one when (a−b)^2/(a+b) is sufficiently large.
Takeaways & Limitations
The paper provides an algorithm proven to attain optimal community-recovery accuracy in the high-signal regime and proves robust reconstruction for regular and Poisson trees.
Takeaways & Limitations
The presented algorithm is polynomial-time but not particularly efficient because it reruns BBPartition for almost every vertex.

Abstract

from arXiv · show

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.

1. Introduction.

The paper studies optimal community recovery in sparse stochastic block models, where exact recovery is impossible but the best achievable constant-fraction accuracy can still be characterized. It develops a belief-propagation-based algorithm achieving the optimal accuracy at sufficiently high signal-to-noise ratio and proves robust reconstruction results for trees.

Sparse stochastic block models: Sparse block models are important because constant average degree prevents exact recovery while matching the sparsity of many real networks.The paper motivates studying constant-degree models despite their inference limits because many large empirical networks are similarly sparse.
Sparse stochastic block models: The paper addresses a gap between known results for constant-degree block models and models whose average degree grows with graph size.Before this work, limited results were available for very sparse stochastic block models.
Optimal reconstruction: The main theorem gives a polynomial-time algorithm achieving the optimal asymptotic accuracy pG(a,b) with probability tending to one when (a−b)^2/(a+b) is sufficiently large.Earlier work established when accuracy above 1/2 is possible, but not an algorithm guaranteed to attain optimal accuracy.
Optimal reconstruction: The algorithm uses belief propagation to locally improve an initial community estimate supplied by a previous algorithm.The analysis does not establish optimality for vanilla belief propagation with random initialization.
Robust reconstruction: The analysis proves robust reconstruction for regular and Poisson Galton–Watson trees: sufficiently high signal-to-noise allows arbitrarily noisy leaf messages to converge to the optimal solution.The authors conjecture analogous results for general trees and lower signal-to-noise ratios.

2. Definitions and main results.

The paper restricts its stochastic block model to two classes of roughly equal size.

The stochastic block model considered here has two classes with roughly equal size.

2.1. The block model.

The block model assigns independent binary labels and includes edges independently according to whether endpoint labels agree. Its reconstructability is governed by the relation between (a−b)^2 and a+b, with a sharp threshold for detection above random guessing.

Each node receives an independent + or − label with equal probability, and each edge appears independently with probability a/n for equal labels or b/n otherwise.The resulting distribution is denoted G(n,a/n,b/n).
The parameters a and b are fixed while n tends to infinity, and the relation between (a−b)^2 and a+b determines reconstructability.
If (a−b)^2 < 2(a+b), labels cannot be inferred from the unlabeled graph with accuracy above 50%.
If (a−b)^2 > 2(a+b), labels can be inferred with accuracy above 50%.
The optimal-accuracy analysis uses the local tree-like structure of the sparse block model through a broadcast process on a tree.

2.2. Broadcasting on trees.

The tree broadcast process propagates binary labels from a root through a rooted tree with independent noise on each child edge. Reconstruction asks whether distant-generation labels retain information about the root, with a threshold determined by the tree’s branching number and channel parameter.

A rooted tree is represented as a prefix-closed subset of finite strings, with the root identified by the empty string.
For a vertex u, L_k(u) denotes its kth-level descendants and C(u) denotes the indices of its children.
The broadcast process assigns the root a random binary label and independently preserves or flips each child’s label according to η.The process is studied through labels observed at increasingly distant generations.
Tree reconstruction asks whether labels far from the root provide information about the root label, a question characterized for general trees using branching number.
If dθ^2 > 1, root reconstruction succeeds with probability bounded away from 1/2; if dθ^2 ≤ 1, no such algorithm exists.Here θ = 1−2η and d is the branching number.

2.3. Robust reconstruction on trees.

The noisy broadcast process adds independent noise at the leaves, unlike the propagating noise in the underlying broadcast process. Earlier work showed that leaf noise does not change whether the root can be reconstructed nontrivially, and this paper seeks a quantitative accuracy statement.

The noisy broadcast process independently flips each tree label with probability δ at the leaves.
Noise in the underlying broadcast process propagates down the tree, whereas added leaf noise does not.
Earlier work showed that leaf noise does not affect whether the root signal propagates arbitrarily far.
The graph–tree connection motivates studying tree reconstruction because graph neighborhoods resemble broadcast trees.

2.4. The block model and broadcasting on trees.

Sparse block-model neighborhoods are locally approximated by Galton–Watson trees whose labels follow a broadcast process. This correspondence explains why graph and tree reconstruction share a threshold, while the paper focuses on accuracy beyond detectability.

Block-model neighborhoods look like Galton–Watson trees with offspring distribution Pois((a+b)/2).
The neighborhood labels behave like a broadcast process, linking community reconstruction to root reconstruction on trees.
The shared threshold follows because the tree branching number is d = (a+b)/2 and the broadcast parameter determines signal propagation.
For more than two communities, the broadcast process has more than two states and the theory is substantially less developed.
The paper studies detailed reconstruction accuracy rather than only whether accuracy exceeds 1/2.

2.5. Reconstruction probabilities on trees and graphs.

The paper defines optimal reconstruction accuracy for trees and graphs and relates them through an upper bound. In the high-signal regime, its algorithm achieves the graph optimum.

pT(a,b) is the probability of correctly inferring the tree root from labels at infinity.
Tree reconstruction is nontrivial exactly when (a−b)^2 > 2(a+b).
Graph reconstruction is at most as accurate as tree reconstruction, so pG(a,b) ≤ pT(a,b).
The graph optimum pG(a,b) is the highest asymptotic fraction of labels that any algorithm can reconstruct correctly from an unlabeled graph.
In the high-signal regime, Algorithm 1 achieves accuracy pT(a,b).

2.6. Our results.

When (a−b)^2 is sufficiently large relative to a+b, robust reconstruction is unaffected by extra noise, enabling an algorithm to attain optimal block-model accuracy.

Main result: pG(a,b) = pT(a,b), equating optimal graph reconstruction accuracy with tree reconstruction accuracy.
Main result: A polynomial-time algorithm reconstructs labels with accuracy pG(a,b) − ε with probability tending to one as n →∞.This holds under the same sufficiently high signal-to-noise condition.
Algorithmic idea: The algorithm amplifies a slightly better-than-random clustering into an optimal clustering using robust tree reconstruction.
Robust reconstruction: If (a−b)^2 ≥ C(a+b), robust reconstruction achieves the tree accuracy without degradation from extra noise.The result applies for a constant C.
Scope: The proof does not extend naturally to the conjectured δ-independent robust accuracy for arbitrary parameters or more general trees.

2.7. Algorithmic amplification and robust reconstruction.

The graph problem can be related to robust tree reconstruction: a weakly correlated initial clustering can be amplified, while the resulting guarantee extends beyond the high-signal theorem but has broader-model limitations.

Amplification guarantee: For all a and b, pG(a,b) ≥ ˜pT(a,b).
Amplification guarantee: A polynomial-time algorithm achieves accuracy ˜pT(a,b) − ε with probability tending to one as n →∞.
Scope: Theorem 2.12 extends readily to more clusters or unbalanced classes, whereas Theorem 2.11 does not, so Theorem 2.9 may fail for general block models.
Algorithmic amplification: The algorithm removes a growing-radius neighborhood, obtains a correlated clustering on the remainder, then uses boundary communities to infer the removed node’s label.

2.8. Algorithm outline.

The algorithm combines local belief-propagation instances with a black-box clustering procedure: each node’s neighborhood is removed, the remainder is clustered, and boundary information is used for relabeling.

Algorithm outline: The inferred communities on the neighborhood boundary are then used to guess the removed node’s label through robust tree reconstruction.
Algorithm outline: Independence between the removed neighborhood and the clustering errors follows from independence of edges inside the neighborhood and outside it.
Belief propagation: On trees, belief propagation computes the optimal estimator from leaf labels, so the graph algorithm consists of multiple local belief-propagation applications.

3. Robust reconstruction on regular trees.

The regular-tree proof establishes robust reconstruction by comparing exact and noisy magnetizations through recursive analyses. When dθ^2 is sufficiently large, noisy leaf information asymptotically retains the optimal reconstruction performance.

Proof setup: The proof analyzes regular trees first because they contain the main ideas later adapted to Poisson random trees.The central objects are reconstruction and robust reconstruction probabilities for broadcast and noisy broadcast processes.
Magnetization: Bayes’ rule identifies the success probabilities of optimal estimators as (1 + E|Xρ,k|)/2 and (1 + E|Yρ,k|)/2.X uses exact boundary labels, while Y uses noisy boundary labels.
Recursive comparison: The exact and noisy magnetizations satisfy the same recursion, differing primarily through their initial conditions.The exact process starts at ±1, whereas the noisy process starts at ±(1 − 2δ).
Large signal-to-noise ratio: When θ^2d is large, majority-based estimators perform well, and optimal magnetization estimators perform at least as well.The analysis uses first and second moments, Chebyshev’s inequality, and comparisons with optimal estimators.
Completing the proof: For sufficiently large θ^2d, the proof shows that exact and noisy reconstruction become asymptotically equivalent.The small-θ case uses Taylor expansions and second-moment bounds, while the full theorem combines small- and large-θ analyses.

4. Reconstruction accuracy on Galton–Watson trees.

The regular-tree argument is extended to Poisson Galton–Watson trees, where random branching requires weighted estimators and effective-conductance methods. Despite extinction and sparsity risks, exact and noisy reconstruction attain the same limiting magnetization when θ^2d is sufficiently large.

Random-tree difficulty: A Poisson Galton–Watson tree differs from a regular tree because its random branching can produce extinction or unusually thin subtrees.These events weaken reconstruction even when the broadcast noise parameter becomes small.
Main result: The Galton–Watson theorem states that limk→∞ E|Xρ,k| = limk→∞ E|Yρ,k| whenever θ^2d exceeds a universal constant.This equality transfers the robust reconstruction conclusion to the Poisson setting.
Large expected magnetization: The proof first establishes that magnetizations are sufficiently large using weighted linear estimators rather than unweighted majority votes.The weights are connected to effective conductance and can be computed from the tree.
Electrical-network method: Effective conductances and resistances encode information flow through random tree levels and support bounds on the weighted estimators.Additional noisy terminal nodes model leaf noise through modified resistances and conductances.
Two-regime analysis: The proof handles small and large θ separately, then combines the resulting propositions to establish the Galton–Watson theorem.The small-θ argument extends the regular-tree Taylor analysis, while the large-θ argument uses weighted majority and derivative bounds.

5. From trees to graphs.

The paper transfers tree-based reconstruction guarantees to sparse graphs by combining BBPartition with locally applied belief propagation. The resulting algorithm is optimal under sufficiently strong signal, though the presented implementation is polynomial-time and inefficient.

Algorithm construction: The algorithm operates on fixed-vertex-set block models and uses BBPartition on graphs obtained by removing each vertex’s local neighborhood and a small held-out set.This reduction creates a graph suitable for the black-box partitioning guarantee while preserving the local information needed for reconstruction.
From trees to local graph estimates: For each target vertex, noisy boundary labels are transformed through a two-stage weighted-and-recursive belief-propagation estimator that avoids requiring the unknown leaf-noise level δ.The construction is chosen so that the estimator satisfies the assumptions needed for robust tree reconstruction.
Algorithm construction: The method breaks the ± symmetry across repeated runs by holding out a high-degree vertex and aligning labels according to the majority sign of its neighbors.A suitable vertex exists asymptotically, and its neighborhood provides a reliable orientation for the recovered partition.
Optimality and efficiency: Theorem 5.4 matches the algorithm’s asymptotic error to the information-theoretic optimum, while the presented implementation is inefficient because it reruns BBPartition for almost every vertex.The authors note that an O(n^1+o(1)) modification exists, but do not present it because vanilla belief propagation is more efficient in practice.
From trees to local graph estimates: A coupling identifies each graph neighborhood and its noisy labels with a noisy broadcast process on a tree, allowing the tree reconstruction theorem to control the graph estimator.The coupling applies uniformly over the relevant local neighborhoods after a union bound.