The R code below generates a random tree and finds the path between two particular vertices: the two vertices named “1” and “2” in this example. Because of the way the graph was created, you can think of these as just being a completely random pair of vertices. They need not be close together in the graph.

Think of this tree as being the junction tree of the cliques of some chordal graph (more precisely: a junction tree of …).

I give the vertices in the graph four different colours.

Vertex 1 is coloured red. Think of this vertex as being the “root clique” for the first (inward) stage of the junction tree algorithm. During this stage, one at a time, we think of a message as being passed from a leaf of the tree to its neighbour: the unique node or vertex closer to the root vertex. The potential functions of the separator and of the neighbour are updated. Marginalising over the variables which are in the leaf but not in its neighbour corresponds to simply cutting off that leaf from the tree, and deleting the potentials \(\phi_C\) and \(\psi_S\) of the leaf and the separator, from the “big” function of all the variables in all the cliques which we are marginalising: \[f(x) ~ = ~ \frac {\prod_C \phi_C(x)} {\prod_S \psi_S(x)}.\]

At any stage in this process, we have successively pruned off leaves of the tree towards some subtree. We have arrived at a factorisation of the marginalisation of the original function \(f\) down to the variables in the cliques in our subtree. But we could just as well leave all the leaves in place: we have arrived at a new factorisation of the original function \(f\)!

The fact that we can think of the intermediate results in these two ways, is the key to understanding the whole algorithm.

At some point we have applied the message passing algorithm till we arrive at the root: the red vertex. At that point, the potential function for that clique is the marginalisation of the orginal function \(f\) down to the variables in the clique corresponding to the root node of our junction tree.

The order in which leaves got removed can’t make any difference to intermediate or final results (try to understand why! I have already given you the clue to understanding this). So we can imagine that at some point all the vertices except vertex 2 (coloured green), vertex 1 (coloured red), and the orange vertices in between have been removed.

We now have a factorisation of the marginalisation of \(f\) to the variables in these cliques, only. After than, the green vertex and the orange vertices are removed, one by one, till finally the tree has been reduced to one vertex (vertex 1, coloured red).

After the first stage is complete, imagine putting back vertices along the path from the red node 1 to the green node 2, one at a time. In other words, we put back the orange nodes and the green node, ending with a rather small graph of cliques along the “stem” of the original tree which connects vertex 1 to vertex 2.

Because of the previously carried out marginalisation process, the product of potentials of cliques along this stem divided by the product of potentials of their separators is just the marginalisation of the whole thing to the variables in the cliques in this stem.

So we can imagine a new marginalisation process starting at the leaf vertex 1 and heading towards the root vertex 2. When it is finished, the potential of the clique at vertex 2 is the marginalisation of the whole table to the variables in that clique.

Because the order in which leaves are put back into the tree, one by one, starting at the root, doesn’t make any difference, we see that at the close of one complete inward sweep to a root node, followed by one outward sweep to all original leaves, every single potential (also of the separators) is the marginalisation of \(f\) to the variables in that set of variables. If we do any more “message passing”, nothing will change any more. We have reached equilibrium in a finite number of updating steps.

library(igraph)
set.seed(1234)
Nnodes <- 50
Nedges <- 100
g <- erdos.renyi.game(Nnodes, p.or.m = Nedges, type = "gnm")
while(!is.connected(g)) g <- erdos.renyi.game(Nnodes, p.or.m = Nedges, type = "gnm")
g <- minimum.spanning.tree(g)
layout <- layout.auto(g)   ## fix layout for all later graphs of g
g$layout <- layout
# plot(g)
path <- get.shortest.paths(g, 1, 2)$vpath[[1]]
colours <- rep("lightblue", Nnodes)
colours[path] <- "orange"
colours[1] <- "red"
colours[2] <- "green"
for (i in 1:Nnodes) V(g)[i]$color <- colours[i]
plot(g)

I’ll now pick another two vertices, at random, to be the root vertex coloured red, and the vertex of interest, coloured green.

twoNodes <- sample(Nnodes, 2, replace = FALSE)
redNode <- twoNodes[1]
greenNode <- twoNodes[2]
path <- get.shortest.paths(g, redNode, greenNode)$vpath[[1]]
while(length(path) <= 2) {
  twoNodes <- sample(Nnodes, 2, replace = FALSE)
  redNode <- twoNodes[1]
  greenNode <- twoNodes[2]
  path <- get.shortest.paths(g, redNode, greenNode)$vpath[[1]]   
}
colours <- rep("lightblue", Nnodes)
colours[path] <- "orange"
colours[redNode] <- "red"
colours[greenNode] <- "green"
for (i in 1:Nnodes) V(g)[i]$color <- colours[i]
plot(g)