Theorem. Chordal Gaussian gluing along a junction tree [fdip-0068]
✍️source

  • November 1, 2026

A clique is a vertex subset whose distinct vertices are pairwise adjacent; a maximal clique is inclusion-maximal. A finite simple graph \(\Gamma \) on \(V\) is chordal if it has no induced cycle of length at least 4. Suppose centered positive-definite Gaussian laws \(\mu _K\) on its maximal cliques agree on every overlap. Then there is a unique centered positive-definite Gaussian law with these clique marginals that is Markov with respect to \(\Gamma \). Uniqueness is asserted within that Markov class.

The maximal cliques admit a junction tree: a tree \(\mathcal T\) whose nodes are the maximal cliques, such that the nodes containing any given vertex form a connected subtree. This is the running-intersection property. Write \(S_e=K\cap K'\) for the separator on an edge \(e=KK'\) and \(p_{S_e}\) for its common marginal density. Empty separators have density one. The glued law and precision are \[p(\phi )=\frac {\prod _Kp_K(\phi _K)} {\prod _{e\in E(\mathcal T)}p_{S_e}(\phi _{S_e})},\] \[Q=\sum _K\operatorname {pad}_K(\Lambda _K) -\sum _{e\in E(\mathcal T)} \operatorname {pad}_{S_e}(\Lambda _{S_e}).\] Separator terms are counted once per tree edge, including repetitions of the same vertex subset. For \(V=\varnothing \) the law is the unit mass and both products are empty.

Proof. 

  • November 1, 2026

We first justify the finite junction-tree construction. A vertex is simplicial when its neighbors form a clique. Every noncomplete chordal graph has two nonadjacent simplicial vertices. Here is an induction proof. In the connected case choose nonadjacent vertices \(a,b\) and an inclusion-minimal separator \(S\). Let \(C_a,C_b\) be their components in \(\Gamma \setminus S\). Minimality implies that each \(s\in S\) has a neighbor in both components: otherwise restoring that \(s\) would still leave \(a,b\) separated. If nonadjacent \(x,y\) belonged to \(S\), choose shortest \(x\)-to-\(y\) paths with internal vertices in \(C_a\) and in \(C_b\). Each path has no chord, and there are no edges between their interiors. Their union would be an induced cycle of length at least 4. Thus \(S\) is a clique.

Each induced graph \(C_a\cup S\) and \(C_b\cup S\) is smaller and chordal. If one is complete, any vertex in its component is simplicial. Otherwise induction gives two nonadjacent simplicial vertices; at most one lies in the clique \(S\), so choose one outside \(S\). Its full-graph neighbors still lie in that same induced graph, so it is simplicial in \(\Gamma \). The two choices are nonadjacent. In a disconnected graph choose a simplicial vertex in each of two components by the same induction; complete components pose no problem. Complete graphs have every vertex simplicial. This proves the assertion and allows repeated deletion of a simplicial vertex, a perfect elimination order.

Induct on that deletion to construct the clique tree. Remove a simplicial vertex \(v\), and write \(N\) for its neighbor clique. Unless no vertices remain, \(N\) lies in a maximal clique \(C\) of the remaining graph; when \(N=\varnothing \), choose any such \(C\). If \(N=C\), replace node \(C\) in its clique tree by \(C\cup \{v\}\). If \(N\subsetneq C\), attach \(N\cup \{v\}\) as a new leaf at \(C\). These are precisely the changes to the maximal cliques. In either case the nodes containing each old vertex remain connected, while \(v\) occurs only in the new node. A one-vertex graph starts the induction. Connecting different graph components in this way uses empty separators. This proves the required running-intersection property. The perfect-elimination characterization is also stated in [grone1984positive, Theorem 6, p. 119].

Now remove a leaf clique \(K\) of \(\mathcal T\) with neighbor \(C\) and separator \(S=K\cap C\). Running intersection says that \(A=K\setminus S\) occurs in no other clique, and that \(K\)'s intersection with the union of the remaining cliques is exactly \(S\). By induction glue the remaining clique laws; a one-clique tree starts with its prescribed law. The remaining law's marginal on \(S\) is the prescribed one, since it has the prescribed law on \(C\). The two-law theorem then glues in \(\mu _K\) by multiplication by \(p_K/p_S\). This proves normalization, positive definiteness, all clique marginals and the density formula. The precision formula follows at each step. Every nonzero summand is supported on a clique, so the precision is zero on all nonedges: the constructed law is Markov.

For uniqueness, \(S\) separates \(A\) from the remaining vertices outside \(S\): an edge out of \(A\) would belong to a maximal clique, but no other clique contains its endpoint in \(A\). Any Markov extension therefore factors across this separator by Theorem [fdip-0065]. Its marginal after removing \(A\) is again Markov for the induced remaining graph. Indeed the Schur correction from eliminating \(A\) is supported only on \(S\times S\), and \(S\) is a clique, so it creates no entry on a nonedge. Induction makes that remaining marginal unique; the separator factorization then makes the full law unique.

The positive-definite completion theorem of [grone1984positive, Theorem 7, p. 120, proof pp. 121–122] characterizes chordal graphs by existence for every compatible positive clique specification. The proof above additionally constructs the Markov extension and proves uniqueness within that class. Bare completion existence alone does not assert that all extensions are identical. Even for two isolated vertices, Example [fdip-006A] has many positive completions and exactly one Markov completion.