Advanced Inference in PGMs: Junction Tree Algorithm

While approximate methods like MCMC and Variational Inference are essential tools for handling large or complex Probabilistic Graphical Models (PGMs), situations arise where exact inference is both desirable and computationally feasible. The Junction Tree algorithm (also known as the Clique Tree or Join Tree algorithm) stands as a primary method for performing exact inference, particularly for computing marginal probabilities of variables in singly connected or moderately complex multiply connected graphs. It cleverly transforms the original graph into a tree structure composed of clusters of variables (cliques), enabling efficient message passing for belief propagation.

This algorithm builds upon the concepts of variable elimination but organizes the computations in a way that avoids redundant calculations, especially when multiple marginal queries are needed. The core idea is to leverage the structure of the graph to perform calculations efficiently.

From Graphs to Trees: Triangulation and Clique Identification

The path to a junction tree begins with preparing the graph. If starting with a directed graph like a Bayesian Network, the first step is moralization. This involves "marrying" the parents of each node by adding undirected edges between them and then making all original directed edges undirected. This process creates the moral graph, an undirected representation capturing the conditional dependencies relevant for inference.

The next critical step is triangulation (or making the graph chordal). An undirected graph is triangulated if every cycle of length four or more has a chord (an edge connecting two non-adjacent nodes in the cycle). Triangulation involves adding edges to the moral graph to eliminate chordless cycles. While finding an optimal triangulation (one that minimizes the size of the resulting cliques) is NP-hard, heuristic methods are often used in practice. Why triangulate? Because triangulated graphs have a special property: their maximal cliques (subsets of nodes where every pair is connected, and which are not subsets of larger cliques) can be arranged into a tree structure satisfying the running intersection property.

Once the graph is triangulated, we identify all its maximal cliques. These cliques will become the nodes of our junction tree.

Constructing the Junction Tree

A junction tree is constructed from the maximal cliques of the triangulated graph. The nodes of the junction tree are the maximal cliques $C_1, C_2, \dots, C_k$. Edges are added between cliques $C_i$ and $C_j$ if they share variables. The set of shared variables $S_{ij} = C_i \cap C_j$ is called a separator.

The requirement for a valid junction tree is the running intersection property (or Junction Tree Property): For any two cliques $C_i$ and $C_j$ in the tree, all cliques on the unique path between them must contain the intersection $C_i \cap C_j$. This property ensures that information about shared variables flows consistently through the tree. Constructing a tree that satisfies this property can often be done using a maximum spanning tree algorithm on a graph where nodes are cliques and edge weights are the sizes of the separators $|C_i \cap C_j|$.

A simple example of a Junction Tree. Nodes represent maximal cliques from a triangulated graph. Edges connect cliques that share variables, with the shared variables (separators) indicated. This tree structure satisfies the running intersection property.

Belief Propagation via Message Passing

With the junction tree constructed, inference proceeds via message passing. Each clique $C_i$ is initially associated with a potential function $\psi_i$. This potential is typically formed by multiplying together the conditional probability tables (CPTs) or factors from the original PGM whose variables are contained entirely within $C_i$. Careful assignment ensures each original factor is assigned to exactly one clique.

The algorithm involves two phases:

1. Collect Evidence (Upward/Inward Pass): Choose an arbitrary clique as the root. Messages are passed from the leaves of the tree towards the root. A clique $C_j$ sends a message to its neighbor $C_i$ only after it has received messages from all its other neighbors.
2. Distribute Evidence (Downward/Outward Pass): Once the root has received messages from all its neighbors, messages are passed back down from the root towards the leaves. A clique $C_i$ sends a message to its neighbor $C_j$ only after receiving the message from its parent (the neighbor it received from during the collect phase).

What is a message? A message $m_{ji}$ sent from clique $C_j$ to clique $C_i$ is essentially a summary of the information (beliefs or potentials) gathered in the subtree rooted at $C_j$ (when viewed from $C_i$'s perspective), marginalized down to the variables in the separator $S_{ij} = C_i \cap C_j$.

Calculating Messages: Let $\beta_j$ be the current potential associated with clique $C_j$ (initially $\psi_j$, then updated by incoming messages). The message $m_{ji}$ sent from $C_j$ to $C_i$ is computed as:

$$m_{ji}(S_{ij}) = \sum_{C_j \setminus S_{ij}} \beta_j^*(C_j)$$

where $\beta_j^*$ represents the potential $\beta_j$ potentially incorporating messages received by $C_j$ from neighbors other than $C_i$ during the current pass. Specifically, in the Collect phase, when $C_j$ sends to $C_i$, $\beta_j^*$ incorporates $\psi_j$ and messages from all neighbors $k \in N(j) \setminus \{i\}$. The summation marginalizes out variables present only in $C_j$ but not in the separator $S_{ij}$.

When a clique $C_i$ receives a message $m_{ji}(S_{ij})$, it updates its own potential:

$$\beta_i(C_i) \leftarrow \beta_i(C_i) \cdot m_{ji}(S_{ij})$$

Note that the message $m_{ji}$ is a function only of the separator variables $S_{ij}$, but it gets multiplied into the potential $\beta_i$ which is a function of all variables in $C_i$. This operation is sometimes referred to as "potential multiplication".

Final Beliefs: After both the Collect and Distribute phases complete, the potential $\beta_i(C_i)$ associated with each clique $C_i$ is proportional to the true joint marginal probability distribution over the variables in that clique, given any evidence incorporated into the initial potentials:

$$\beta_i(C_i) \propto P(C_i | \text{evidence})$$

From these final clique beliefs, we can easily compute the marginal probability for any single variable $X \in C_i$ or subset of variables within $C_i$ by summing out the remaining variables in $\beta_i(C_i)$. The running intersection property guarantees that the marginals computed for the same variable from different cliques containing it will be consistent.

Computational Complexity and Applicability

The efficiency of the Junction Tree algorithm depends critically on the size of the largest clique in the junction tree. The size of the largest clique is known as the treewidth of the graph (more accurately, the treewidth of the original graph is the minimum size of the largest clique minus one, over all possible triangulations).

The computational cost of message passing involves operations (multiplication, summation) over potentials defined on the cliques. If the maximum clique size (treewidth + 1) is $w_{max}$, and variables have at most $d$ states, the complexity is roughly exponential in $w_{max}$ (e.g., $O(k \cdot d^{w_{max}})$ where $k$ is the number of cliques).

Therefore, the Junction Tree algorithm is efficient for graphs where a triangulation with small maximal cliques can be found (i.e., graphs with low treewidth). For graphs with high treewidth (like dense grids or highly connected networks), the cliques become too large, and the computation becomes intractable. This is where approximate inference methods become necessary.

Advantages and Disadvantages

Advantages:

• Provides exact marginal probabilities for all variables and cliques.
• Efficient for graphs with low treewidth.
• After the initial message passing phases, multiple marginal queries can be answered quickly by marginalizing the final clique beliefs.
• Forms a theoretical basis for understanding inference complexity.

Disadvantages:

• Finding an optimal triangulation is NP-hard.
• Construction of the junction tree itself can be complex.
• Becomes computationally intractable for graphs with high treewidth.
• Primarily designed for discrete variables, although extensions for Gaussian graphical models exist.

In summary, the Junction Tree algorithm represents a significant theoretical and practical tool for exact inference in PGMs. It transforms the inference problem on a potentially complex graph into a more structured message-passing procedure on a tree. Its applicability is governed by the graph's structural properties, specifically its treewidth, highlighting the close relationship between graph structure and inference complexity. When the treewidth is manageable, it offers a powerful way to obtain exact probabilistic queries. When it is not, we turn to the approximate methods discussed in other sections.