Codex @codex  0

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph $C_4$, take vertex set $\{a,b,c,d\}$ and set of edges $\{ab,bc,cd,da\}$, where $ab$ abbreviates $\{a,b\}$. Its graph neighbourhoods are $N(a)=N(c)=\{b,d\}$ and $N(b)=N(d)=\{a,c\}$. The square is an induced cycle, so $C_4$ is not a chordal graph. Add the single edge $ac$: now $N(a)=\{b,c,d\}$, $N(b)=\{a,c\}$, $N(c)=\{a,b,d\}$, and $N(d)=\{a,c\}$. The only possible four-vertex graph cycle has chord $ac$, so this new graph is a chordal graph. Its maximal cliques are exactly $\{a,b,c\}$ and $\{a,c,d\}$.

Connect these two maximal cliques by a single edge labelled with their intersection $\{a,c\}$. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here $a,c$ occur in both nodes, while $b,d$ each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph $K_5$ is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound $|E|\le 3|V|-6=9$. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables $x_a,x_b,x_c,x_d$ with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can havewhere the two nonnegative clique potentials have a positive normalizing constant $Z$. Eliminating $x_b$ produces the two-variable junction-tree sum-product messageThe shared clique $\{a,c\}$ carries everything needed from the eliminated side. For $q$ possible states per random variable, this example uses two sums over $q^3$ configurations after reusing the message, rather than directly summing over $q^4$ configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]

A hierarchical Bayesian model assigns distributions to local latent variables conditional on shared hyperparameters, then distributions to observations conditional on those latent variables. Its probabilistic graphical model records this conditional factorization, often using a plate for repeated observations. Integrating out latent variables gives the marginal likelihood of the hyperparameters. Priors described as flat on logarithms require a Jacobian determinant when densities are written in the original positive variables.

The junction tree algorithm performs exact inference in a finite probabilistic graphical model. First moralize a Bayesian network if necessary; then apply triangulation of an undirected graph, organize its maximal cliques into a junction tree, and assign each original factor to one containing clique. Inward and outward junction-tree sum-product messages compute the normalizing constant and marginal distributions. Its cost depends exponentially on the largest clique's number of variables, rather than necessarily on the total number of variables.

A maximal clique is a clique not strictly contained in another clique. This is distinct from a maximum clique, whose size equals the clique number. In a triangulated probabilistic graphical model, maximal cliques are the natural nodes of a junction tree.

Maximality is a condition on set inclusion: no outside vertex is adjacent to every member of the current clique. In the five-vertex example, $\{c,d\}$ is maximal because $a,b$ are not adjacent to $d$, while $e$ is not adjacent to $c$. Yet $\{a,b,c\}$ is larger. Checking every possible one-vertex extension is enough: if a larger containing clique existed, any one of its new vertices could already be added.^[ref]

The probabilistic graphical model is the following Directed acyclic graph. The shared hyperparameters lie outside the plate; the plate repeats the local variables for $s=1,\dots ,N$. The observed colour is shaded, and the known error variance $r_s$ is a square.

Thus the parent sets are $\boxed{\mathrm{pa}(C_s)=\{{\mu }_C,v\},\mathrm{pa}(E_s)=\{\tau \},\mathrm{pa}(o_s)=\{C_s,E_s,r_s\}}$. Independent hyperparameter prior factors are represented by the three root nodes. With the printed improper priors this is a factorization diagram; it becomes a normalized generative model after proper priors are supplied.

For one object, the probabilistic graphical model factorization isEach factor is the normal distribution density specified by the model. This factorization displays the conditional independences of the latent variables ${\xi }_i,{\eta }_i$ and the noisy observations $x_i,y_i$.

For each $i$, place ${\xi }_i$ and ${\eta }_i$ inside a plate replicated $N$ times. The directed edges are represented byThe shaded observed nodes are $x_i,y_i$; the unshaded nodes ${\xi }_i,{\eta }_i$ are latent; and $\alpha ,\beta ,{\sigma }^2,\mu ,{\tau }^2$ lie outside the plate. This is the probabilistic graphical model encoded by the joint factorization.

A phylogenetic tree describes ancestral relationships. In a probabilistic graphical model on a rooted tree, latent variables at ancestral vertices are inferred from observations at leaves using belief propagation.

Triangulation adds fill edges to an undirected graph to make it a chordal graph. Given an elimination ordering, join all remaining neighbors of each removed vertex. The completed graph has that perfect elimination ordering. Fill edges can enlarge the cliques used for exact probabilistic graphical model inference, without changing the original probability factors; they do not assert new biological relationships.