Junction tree

A junction tree connects the maximal cliques of a chordal graph into a tree satisfying the running intersection property. Its edges carry separators equal to the intersections of the endpoint cliques. Assigning original factors to containing cliques permits exact sum-product belief propagation without summing independently over the entire collection of variables.

The junction tree algorithm performs exact inference in a finite probabilistic graphical model. First moralize a Bayesian network if necessary; then apply triangulation of an undirected graph, organize its maximal cliques into a junction tree, and assign each original factor to one containing clique. Inward and outward junction-tree sum-product messages compute the normalizing constant and marginal distributions. Its cost depends exponentially on the largest clique's number of variables, rather than necessarily on the total number of variables.

Junction-tree sum-product message ( $m_{i \to j} (x_{S_{ij}}) = \sum_{x_{C_{i} ∖ S_{ij}}} ψ_{i} (x_{C_{i}}) \prod_{k \sim i, k \neq = j} m_{k \to i}$ )

 0  0

Assign each factor exactly once to a containing clique and multiply the factors there into

ψ_{i}

. The displayed sum-product belief propagation message sums out variables of

C_{i}

outside the separator

S_{ij} = C_{i} \cap C_{j}

. By the running intersection property, eliminating all variables in the subtree on the

i

side creates precisely this function of the separator. An inward pass computes the normalizing constant at the root; an outward pass produces marginal distributions. For pedigree likelihoods, observed genotypes and penetrance factors simply multiply the relevant potentials.

Running intersection property ( $C_{i} \cap C_{j} \subseteq C_{k} along the path from i to j$ )

 0  0

The running intersection property says that every variable belongs to a connected subtree of a junction tree. Equivalently, every clique along the path between two cliques contains their intersection. This ensures that eliminating variables on one side of a tree edge leaves a message depending only on its separator with the other side.