Belief Propagation — Cavity Method

Loopy belief propagation on a sparse random Ising factor graph. Variable nodes (circles) send messages to factor nodes (squares) and vice versa, converging to approximate marginals. On trees, BP gives exact results; on sparse random graphs, it is asymptotically exact at large N.

N variables 10

Avg degree c 2.0

Coupling J 1.0

External field h 0.0

BP Iteration

Max Δmsg

—

Mean |m|

—

BP message (variable→factor): m_{i→a}(xᵢ) ∝ ∏_{b≠a} n_{b→i}(xᵢ)
BP message (factor→variable): n_{a→i}(xᵢ) ∝ Σ_{x∖i} ψₐ(x) ∏_{j∈∂a\i} m_{j→a}(xⱼ)