5.4 The Junction-Tree Algorithm (JTA)

We have at this point already derived the main ideas of the junction-tree algorithm, but there are many details to be handled, which we do in this section. To begin with, we reiterate the main intuitions behind the algorithm: We can think of the JTA as figuring out how, after all, to reuse intermediate computations from variable elimination (VE)—which in our examples generated clique trees (Section 5.2). Alternatively, we can make our goal be the application of belief propagation (BP) to arbitrary graphs, in which case the need to turn non-trees (graphs with loops) into trees becomes our express aim rather than a mere byproduct of VE (Section 5.3).

In our examples, we turned graphs into clique trees by treating subgraphs as single nodes. But we did not specify a definite procedure for doing so. Indeed, we do not even know whether it is always possible to do so in a way that produces a tree; or when the resulting tree is guaranteed to behave properly under either the Hugin algorithm (Eqs. 5.7 and 5.8) or the Shafer-Shenoy algorithm (Eqs. 5.15 and 5.16).

The first question is most easily handled: At the extreme, all nodes could be grouped into a single such “supernode,” which would certainly be a tree. Obviously, given our discussion above, this would be computationally hopeless, but less naïve strategies readily come to mind. The second question is harder. It is intuitive that such a guarantee is available if the sets of variables assigned to the supernodes were to constitute a disjoint partition of the original set of variables. In this case, there would be no need to enforce consistency between supernode potentials, since they make reference only to different random variables. But a disjoint partition is too strong a condition to require. Is there a weaker condition, and if so is there a procedure for constructing trees that ensures that this condition hold?

Two key converse propositions.

In this section, we will describe the junction-tree algorithm in terms of separator and clique potentials, i.e. in terms of the Hugin algorithm and Eqs. 5.7 and 5.8. Then we can say that the goal of the algorithm is to run a series of updates to these potentials such that the ratio of products

\frac{\prod_{\mathcal{C}\in\mathbb{\mathbf{C}}}\rho_{\mathcal{C}}({\color[rgb]% {.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{\mathcal% {C}}})}{\prod_{\mathcal{S}\in\mathbb{\mathbf{S}}}\phi_{\mathcal{S}}({\color[% rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{% \mathcal{S}}})}

remains equal to the joint distribution, but the potentials become (proportional to) the local marginals probabilities (possibly conditioned on observations).

There are two key facts about this process, which we prove below. First, since the various potential functions reference overlapping sets of variables, if they become proportional to the marginal probabilities, they must also become consistent with one another. Somewhat remarkably, in an appropriately structured clique tree, the converse also holds: If the potentials become consistent with each other, then they have also become proportional to the local marginal probabilities. Second, if the potentials are all consistent with each other (global consistency), then a fortiori neighboring cliques are consistent with each other (local consistency). But here, too, the converse holds: In an appropriately structured clique tree, local consistency implies global consistency. Putting these two facts together, we see that it will be sufficient to make sure that our update procedure brings about local consistency.

1.

High-level interpretation. We can think of JTA either as figuring out how, after all, to reuse intermediate computations from VE; or alternatively as trying to turn graphs with loops into trees and thereby allow BP to run.
2.
What this tree looks like.
- •
  
  We transform the graph into a tree by grouping nodes into “super nodes”—more precisely, elimination cliques. We call this a clique tree.
- •
  
  One way to generate a clique tree is to run VE: each elimination clique becomes a clique in the tree, and we draw edges betweeen cliques whose “messages” (intermediate potentials $m$ ) get multiplied together.^†^†margin: Example: MIJ’s favorite graph In fact, this guarantees that the clique tree have the running-intersection property (RIP). Such trees are called junction trees.
  
  There are actually better ways to construct junction trees, but we’ll get to those later.
- •
  
  We will explicitly represent the separator sets as nodes in the graph. So the junction tree is really a bipartite graph.
3.
Goal of the algorithm. We haven’t talked about how to parameterize this tree; we’ll get to that. But the goal will be to update our parameterization so that
- •
  
  the potential on a clique node is the marginal distribution over those nodes;
- •
  
  the potentials on clique nodes are globally consistent, i.e. give the same marginal probabilities over any variables they have in common.
4.
Main ideas
- •
  
  If the clique tree is a junction tree, then local consistency, i.e. between (all) neighboring cliques in the graph, guarantees global consistency. (This should be intuitive but can be proved easily from RIP.) So we only need to enforce local consistency!
- •
  
  We can enforce local consistency with a message-passing protocol just like BP’s, which works for the same reason (it’s a tree).
5.
Parameterizating junction trees.
- •
  
  Assign each potential from the original graph to one clique node. The map will typically be many-to-one. Obviously, all the variables referenced by the potential have to be among (i.e., a subset of) the variables in the clique.^†^†margin: Example: MIJ’s favorite graph.
- •
  
  Define the joint to be the product over the clique potentials, divided by the product of the separator potentials—initially, all ones.
- •
  
  Example: Markov chain.^†^†margin: Show what the initial parameterization looks like, that one potential is not a marginal; show how to fix, motivating update procedure.
6.
Updating junction trees. Consider a simple two-node junction tree:

$\displaystyle\phi_{S}^{*}({\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{S}})$

$\displaystyle{}\stackrel{{\scriptstyle\text{set}}}{{=}}\sum_{\bm{\hat{x}}_{V% \setminus S}}\rho_{V}(\bm{\hat{x}}_{V\setminus S},{\color[rgb]{.75,0,.25}% \definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{S}})$

make $\phi_{S}$ consistent w/ $\rho_{V}$

$\displaystyle\rho_{W}^{*}({\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{W}})$

$\displaystyle{}\stackrel{{\scriptstyle\text{set}}}{{=}}\frac{\phi_{S}^{*}({% \color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x% }_{S}})}{\phi_{S}({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{% rgb}{.75,0,.25}\bm{x}_{S}})}\rho_{W}({\color[rgb]{.75,0,.25}\definecolor[named% ]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{W}})$

retain relationship b/n $\rho_{W}$ and $\phi_{S}$

$\displaystyle\rho_{V}^{*}({\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{V}})$

$\displaystyle{}\stackrel{{\scriptstyle\text{set}}}{{=}}\rho_{V}({\color[rgb]{% .75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{V}})$

null update (for consistent starring)

$\displaystyle\phi_{S}^{**}({\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{S}})$

$\displaystyle{}\stackrel{{\scriptstyle\text{set}}}{{=}}\sum_{\bm{\hat{x}}_{W% \setminus S}}\rho_{W}^{*}(\bm{\hat{x}}_{W\setminus S},{\color[rgb]{.75,0,.25}% \definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{S}})$

make $\phi_{S}$ consistent w/ $\rho_{W}$

$\displaystyle\rho_{V}^{**}({\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{V}})$

$\displaystyle{}\stackrel{{\scriptstyle\text{set}}}{{=}}\frac{\phi_{S}^{**}({% \color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x% }_{S}})}{\phi_{S}^{*}({\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{S}})}\rho_{V}^{*}({\color[rgb]{% .75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{V}})$

retain relationship b/n $\rho_{V}$ and $\phi_{S}$

$\displaystyle\rho_{W}^{**}({\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{W}})$

$\displaystyle{}\stackrel{{\scriptstyle\text{set}}}{{=}}\rho_{W}^{*}({\color[% rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{W}})$

null update (for consistent starring)

Notes:
- •
  
  The first update can be thought of as clique node $V$ passing a message to separator node $S$ . In a more general graph, it might pass multiple messages to each of its separator neighbors.
- •
  
  But even in a more general graph, each separator node will only have a single other neighbor: separator nodes sit between two clique nodes; whereas clique nodes can have multiple separator neighbors.
- •
  
  For tables, you can think of the renormalization as broadcast multiplication and division.)
- •
  
  This set of updates guarantees local consistency:
  
  $\begin{split}\sum_{\bm{\hat{x}}_{V\setminus S}}\rho_{V}^{**}(\bm{\hat{x}}_{V% \setminus S},{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{% .75,0,.25}\bm{x}_{S}})=\sum_{\bm{\hat{x}}_{V\setminus S}}\frac{\phi_{S}^{**}({% \color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x% }_{S}})}{\phi_{S}^{*}({\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{S}})}\rho_{V}^{*}({\color[rgb]{% .75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{x}_{V}})\end{split}$
7.
Generalizing to a tree
- •
  
  Message passing protocol (MPP) is just like BP: A (clique) node sends a message to a (clique) neighbor if it has received messages from all its other neighbors.
- •
  Does it work? Suppose $W$ has received messages from all neighboring clique nodes except, possibly, $V$ , to which it now sends a message.
  - –
    
    If $V$ had already sent a message to $W$ , then by the MPP, $V$ must already have received all of its other messages, and so the information (local marginal) it sends to $W$ will be out of date.
  - –
    
    If $V$ had not already sent a message to $W$ , then it may still have messages to receive from its other neighbors, which can indeed change its information about the variable(s) in common with $W$ . But once it receives those messages, it will send a message to $W$ , re-establishing consistency with $W$ .
  So this MPP guarantees that clique neighbors $V$ and $W$ make consistent claims about their common variables.
- •
  What goes wroing in a clique tree without RIP?
  - –
    
    Example: four-node cycle.^†^†margin: This also shows that we can’t just assign maximal cliques to the clique tree.
  - –
    
    Interestingly, the joint is still correct in this case, because updates do not change the ratio of clique to separator products. So the problem is that the local potentials are not marginals.
  - –
    
    Intuitively, RIP is necessary to guarantee that local potentials are (the correct) marginals.
- •
  
  Perhaps surprisingly, RIP is also sufficient to guarantee that local potentials are (the correct) marginals!
8.
JTA yields potentials proportional to local marginals. Proof idea (by induction):
- •
  
  Consider a graph with $N$ nodes that has the global consistency and the correct local marginals.
- •
  Now consider a graph of size $N+1$ that consists of the first graph plus one leaf clique-node $C$ (and its separator node $S$ ).
  - –
    
    We can enforce local consistency with the MPP.
  - –
    
    This enforces global consistency by RIP.
- •
  What about local marginals?
  - –
    
    The new separator node is (after updates) consistent with its neighbor, so its potential $\phi_{S}$ must likewise be the correct marginal distribution over $S$ .
  - –
    
    No other nodes in the graph “talk about” ${\bm{\hat{X}}}_{C}$ , so marginalizing the whole joint except ${\bm{\hat{X}}}_{C}$ is the same as marginalizing just $S$ from this leaf’s potential, and therefore yields the correct marginal.
9.
Constructing junction trees.
- •
  VE yields a JT—but is it the best one? (The JT is not unique.)
  - –
    
    Notice that we cannot simply use the cliques of (say) any undirected graph as the clique nodes in the junction tree.^†^†margin: Insert example with four nodes connected in a cycle
- •
  
  Fact: a run of VE yields a triangulated graph, i.e. one without any chordless cycles.^†^†margin: See example
- •
  
  Chordless cycle: a cycle in which no two vertices are connected by an edge that isn’t itself part of the cycle.
- •
  
  Being triangulated is necessary and sufficient for having a junction tree.
- •
  
  (Intuitively, for any triangulated graph, there exists an elimination ordering that adds no new edges. So every triangulated graph corresponds to an elimination ordering….)
- •
  
  Fact: a clique tree is a JT iff it has maximal “weight,” i.e. sum of cardinalities of separator sets.
- •
  So, from the triangulated graph, we can construct a JT by solving a “maximal spanning tree” problem ( $\mathcal{(}O)(N^{2})$ )
  - –
    
    Kruskal’s:
    
    *
    
    start with no edges
    
    *
    
    add the edge with max $|S|$ as long as it doesn’t create a cycle
    
    *
    
    stop once graph is connected
  - –
    
    Prim’s: add nodes rather than edges
10.

The Hugin algorithm…