The junction (or clique) tree is a type of cluster graph for approximate inference with 🕍 Belief Propagation.
Instead of a any arbitrary cluster graph, we instead build a tree with nodes as clusters and each edge between with sepset . Furthermore, we still maintain the family preservation and running intersection properties. The following is an example of a 🗳️ Markov Random Field represented as a junction tree.
Intuitively, if we form a tree, our algorithm must converge in a finite number of steps because the leaves send a constant message, and then their neighbors send a constant message, and so on. In other words, since a cluster sends a message to another cluster that contains messages from all other neighbors beside the recipient, a leaf can only send its potential to its only neighbor. This logic can be used to show that a tree structure will converge correctly in a fashion that’s similar to 🔫 Variable Elimination.
A junction tree satisfies the running intersection property if and only if for every edge ,
where the first contains all variables on the side of , the second contains all variables on the side, and is the sepset edge.
Intuitively, we can think of and as two groups of variables on either side of our tree. Assume for contradiction that two variables not included in are not independent and thus shows up in a factor; then, by the family preservation property, we must have a cluster that contains this factor, and by the running intersection property, the variables must span the tree from one side to another. Then, these variables must also be included in , a contradiction.
