Belief Propagation and Message Passing

Given a Bayesian network factored into small local pieces, a natural next question is: what is the probability of some variable of interest, given evidence observed elsewhere in the network? Multiplying out the full joint distribution and marginalizing directly is exactly the astronomically large computation the factorization was supposed to avoid. Belief propagation solves this without ever forming the full joint: each node sends small "messages" — compact summaries of what it currently believes — to its neighbors, each node updates its own belief from the messages it receives, and after one pass through the graph every node holds the exact marginal probability it would have gotten from grinding through the whole joint distribution.

The analogy: passing a rumor down a line, but honestly

Imagine a line of people, each only able to talk to their immediate neighbors, trying to collectively figure out the probability of some event based on clues each person individually holds. Instead of everyone shouting their raw clue to everyone else (impossible in a large crowd), each person combines their own clue with whatever summary message their neighbor just handed them, then passes an updated summary further down the line. By the time a summary has traveled from one end of the line to the other and back, everyone holds a belief that correctly reflects everyone's clues combined — without any single person ever having heard every clue directly. Belief propagation is this process formalized: a message is a compact function (not the raw data), passed link by link, that mathematically guarantees the same exact answer as if everything had been computed jointly.

The message and belief update rules

A message from node $i$ to a neighboring node $j$ summarizes everything $i$ knows, excluding what it just heard from $j$ itself (to avoid double-counting):

$$m_{i \to j}(x_j) = \sum_{x_i} \phi(x_i)\, \psi(x_i, x_j) \prod_{k \in N(i) \setminus j} m_{k \to i}(x_i)$$

In words: to tell $j$ what it believes about $j$'s possible values, node $i$ takes its own local evidence $\phi(x_i)$, combines it with the compatibility function $\psi(x_i,x_j)$ linking $i$ and $j$, multiplies in every message $i$ has received from its other neighbors (everyone except $j$, since $j$ already knows its own message), and sums out $i$'s own possible values — the result is a function of $x_j$ alone, exactly the summary $j$ needs. Once every message has been passed, a node's final belief is the product of all incoming messages and its own local evidence:

$$b(x_j) \propto \phi(x_j) \prod_{i \in N(j)} m_{i \to j}(x_j)$$

In words: node $j$'s final belief about its own value is proportional to its own evidence times every incoming message, combining everything the rest of the graph told it into one normalized probability.

Worked example 1: a 3-node chain by hand

Take the rain-train-late chain $R \to T \to L$ from Bayesian network factorization, with the same numbers: $p(R{=}\text{yes})=0.2$, $p(T{=}\text{yes}\mid R{=}\text{yes})=0.7$, $p(T{=}\text{yes}\mid R{=}\text{no})=0.1$, $p(L{=}\text{yes}\mid T{=}\text{yes})=0.8$, $p(L{=}\text{yes}\mid T{=}\text{no})=0.05$. To find $p(L{=}\text{yes})$ with no evidence observed: the message from $R$ to $T$ is just $R$'s marginal folded through the conditional, $m_{R\to T}(T{=}\text{yes}) = 0.2(0.7) + 0.8(0.1) = 0.14+0.08=0.22$. This becomes $T$'s belief: $p(T{=}\text{yes}) = 0.22$ (so $p(T{=}\text{no})=0.78$). The message from $T$ to $L$: $m_{T\to L}(L{=}\text{yes}) = 0.22(0.8) + 0.78(0.05) = 0.176 + 0.039 = 0.215$. So $p(L{=}\text{yes}) = 0.215$ — computed by passing two small messages down the chain, never touching a joint table over all three variables at once.

Worked example 2: updating the belief after evidence arrives

Now suppose you directly observe $T{=}\text{yes}$ (you know for a fact the train was delayed). $T$'s belief is now fixed at $p(T{=}\text{yes})=1$ rather than the computed $0.22$, and it sends a fresh message forward: $m_{T\to L}(L{=}\text{yes}) = 1(0.8) + 0(0.05) = 0.8$. $L$'s belief updates immediately to $p(L{=}\text{yes}\mid T{=}\text{yes}) = 0.8$ — a large jump up from the unconditional $0.215$, computed simply by replacing one message with the new evidence and re-propagating, without recomputing anything about $R$ or re-deriving the whole joint distribution from scratch.

Each belief-propagation message is a function of one node's possible values, combined and squashed the same general way the curve above combines an input into a bounded probability-like output.

What this means in practice

Exact belief propagation as described here is guaranteed correct only on graphs without cycles (trees, or chain-like structures); on graphs with loops, the same message-passing rules are still applied anyway — called loopy belief propagation — and while no longer exact, it converges to good approximations in practice and underlies decoding algorithms in communications (turbo codes, LDPC codes) as well as inference in financial graphical models like credit contagion networks. The message-passing idea itself was later generalized and borrowed directly by message-passing neural networks and GNNs, which replace belief propagation's exact probabilistic messages with learned vector messages — the algorithmic skeleton is the same.

Practice

1. Recompute $p(L{=}\text{yes})$ if instead $p(R{=}\text{yes})=0.5$, keeping all conditional probabilities the same.
2. Explain in one sentence why belief propagation is only guaranteed exact on a graph with no cycles.
3. After observing $T{=}\text{no}$ instead of $T{=}\text{yes}$, recompute $L$'s updated belief.