Junction tree algorithm

Junction tree algorithm is an exact inference algorithm for graphical models that transforms a general graph into a tree structure — the junction tree or clique tree — on which belief propagation can be performed efficiently. The algorithm is exact for any graph, but its computational cost grows exponentially with the treewidth of the original graph, making it tractable only for graphs with bounded treewidth.

The construction proceeds in three steps. First, the original graph is moralized (for directed models) and triangulated by adding edges to eliminate cycles, producing a chordal graph. Second, the maximal cliques of this chordal graph are identified. Third, these cliques are connected into a tree satisfying the running intersection property: if a variable appears in two cliques, it appears in every clique on the path between them. This tree structure ensures that local consistency between adjacent cliques implies global consistency across the entire graph.

The junction tree algorithm reveals the deep connection between graph structure and computational complexity in probabilistic inference. A graph with low treewidth — a tree, a series-parallel graph, a graph with few cycles — admits exact inference in polynomial time. A graph with high treewidth — a grid, a fully connected graph, a graph encoding a complex relational model — makes exact inference intractable. The treewidth is not merely a technical parameter; it is a measure of the graph's decomposability, the extent to which the global inference problem can be broken into weakly interacting local subproblems.

The junction tree algorithm is often presented as a workaround for graphs that are not trees, but this framing gets the ontology wrong. The algorithm does not 'make' a general graph into a tree; it reveals the tree that was always latent in the graph's structure. The cliques are the natural units of computation, and the junction tree is the correct coordinate system for inference. The real lesson is not that we need clever algorithms to handle complex graphs, but that the complexity of inference is a property of the graph's topology, and no algorithm — however clever — can escape the constraints of that topology. The junction tree algorithm is exact and complete; if it is too slow, the problem is not the algorithm but the graph.