Belief Propagation on Trees and Why Loopy Message Passing Fails

On a tree, exact inference has a shape that repeated elimination does not advertise. Root the tree anywhere, eliminate variables from the leaves inward, and every intermediate factor turns out to be a summary of the subtree that lies behind it. Whoever wants a marginal deep inside that subtree can reuse the summary instead of redoing the elimination. That reuse is belief propagation, and the objects being passed along edges are exactly the intermediate factors of a leaf-to-root elimination order, kept rather than discarded.

Messages are eliminated subtrees, summarized

The structural reason trees are easy was established in Exact Inference by Variable Elimination and the Cost of Treewidth: eliminating a variable induces edges among its remaining neighbours, and on a tree a neighbour set of a leaf has size one, so no edges are ever added. Every intermediate factor stays confined to the two variables of an edge, and a message that flows from variable $i$ towards variable $j$ is a function of $x_j$ alone, with size equal to the domain size $d$ whatever the size of the subtree behind it. For a pairwise model with factors $\psi_{ij}$ on edges and unary factors $\phi_i$, the message from $i$ to $j$ is

$$\mu_{i \rightarrow j}(x_j) ;\propto; \sum_{x_i} \phi_i(x_i),\psi_{ij}(x_i, x_j) \prod_{k \in N(i) \setminus j} \mu_{k \rightarrow i}(x_i)$$

The product collects everything $i$ has already heard from its other neighbours; the sum removes $x_i$. Once every edge has carried a message in both directions, the belief at a variable is proportional to its unary factor times all incoming messages:

$$b_i(x_i) ;\propto; \phi_i(x_i) \prod_{k \in N(i)} \mu_{k \rightarrow i}(x_i)$$

and on a tree $b_i$ is the exact marginal $p(x_i)$. A clique marginal is obtained by combining the two messages across the edge that links the clique’s endpoints with the edge factor. The partition function has a closed form in the same quantities: with normalized messages, the sum of the beliefs (or the trace of a product of edge matrices) reproduces $Z$, which is the estimate that loopy variants then turn into an approximation of the object described in Markov Random Fields and the Intractability of the Partition Function.

The schedule is what makes it exact

Two passes suffice. Messages travel from every leaf inward to the root along the tree’s edges, then back outward from the root, and each edge carries exactly one message in each direction. The work is $O(n,d^2)$ for $n$ variables and domain size $d$: each message sums $d$ terms for each of $d$ values of the target variable. A single message can be reused by every query on its other side, so the cost of computing all single-variable marginals equals the cost of computing one, which is the property variable elimination lacks. Variable elimination answers one query per pass, and answering a second query whose variable was eliminated first requires starting over or paying for a wider order.

The generalization to factors of arbitrary arity needs a bipartite factor graph with nodes for variables and for factors, and one message rule for each direction. A variable-to-factor message is the product of the messages it received from all other factors; a factor-to-variable message sums the factor times all its other incoming messages. Grouping a product of pairwise factors into a single higher-order factor changes the graph but not the algorithm, and a tree of factors still has exact messages. The important structural condition is that the factor graph be a tree — a loop-free structure — not that the original model be pairwise.

Exactness on a cyclic model can also be recovered by enlarging the units that exchange messages. A clique tree is a tree whose nodes are clusters of variables chosen so that every potential lies inside some cluster and the clusters containing any single variable form a connected subtree; the two-pass schedule then works unchanged, with each message a table over the separator between two adjacent clusters. Because a message is indexed by the joint assignments of its separator, a clique tree for a graph of treewidth $w$ passes tables with $d^{w+1}$ entries, the same exponential that variable elimination pays. Loopy belief propagation is what remains when clusters are kept at the size of a single edge and the tree condition is dropped: the messages stay small, the schedule stays local, and the exactness argument is gone.

What happens when the graph has cycles

Running the same update equations on a graph with loops is a different algorithm with the same code. Convergence is no longer guaranteed by the schedule, because no leaf-to-root order exists, and the usual fix is to iterate all messages repeatedly, either synchronously or in some fixed or randomized order, until the change between iterations falls below a threshold or an iteration cap is reached. Messages in a cyclic graph can also grow or shrink without bound across iterations, since the recursion multiplies rather than normalizes along a cycle; renormalizing each message after every update keeps the arithmetic finite without changing the resulting beliefs.

When the iteration does converge, there is a characterization of the fixed point. On a tree the messages are stationary points of the Bethe free energy, an approximation to the free energy $-\log Z$ built from single-variable and edge marginals with a correction for overlapping regions, and that free energy is exact on a tree. On a graph with loops the same function has stationary points, and the fixed points of loopy belief propagation are among them. The correspondence runs in one direction: a loopy fixed point is a stationary point of an approximate objective, and a stationary point of that objective need not be a minimum, so a converged run is not evidence of a good approximation.

Failure modes worth checking for

The defects are predictable enough to enumerate. Divergence or oscillation is the common one: synchronous updates on a graph with strong positive couplings can enter a two-cycle in which messages alternate between two states, and damping — updating a message as a convex combination of its old and new values — is the standard remedy. Even after convergence, the marginals can be qualitatively wrong in models near a phase transition, where the Bethe approximation is known to give the wrong answer about which of several long-range orders the distribution favours, and the error does not shrink as the model gets larger. Short loops do more damage than long ones, since a message that returns to its origin after three steps has carried correlated information rather than fresh evidence; graphs whose girth is large behave better than densely loopy ones.

Two further limits are practical. The error of a loopy run is not bounded by any function of the graph’s treewidth, so a low-width instance where exact inference would have been cheap can still be answered approximately by a converged loopy run; the method does not detect that a cheaper exact route existed. And the number of iterations required is not bounded in advance, so the runtime is best described as iterations times edges times $d^2$, with the first factor set by a stopping rule rather than by the graph.

Where the approximation is deliberately accepted

Loopy message passing is the method of choice when the graph is fixed and sparse, the domain is small, and an approximate marginal is genuinely enough. Decoding of low-density parity-check codes uses the sum-product recursion on a sparse factor graph with cycles, where the messages are probability vectors over the two values of a bit and one iteration costs a number of operations proportional to the number of edges. The generalization to region-based free energies, in which larger overlapping clusters replace single edges, refines the approximation at the cost of message size exponential in the cluster size, which places the method on the same width-versus-exactness axis as variable elimination. Where the goal is a bound rather than an estimate, the optimization view described in Variational Inference and the Evidence Lower Bound trades the message-passing fixed point for a guarantee that the returned value never exceeds the true log-normalizer.