Markov Properties And Factorization Of Gaussian Graphs

Why Graph Structure Matters

A multivariate Gaussian distribution can involve many variables, but its conditional dependence structure may be sparse. An undirected graph represents that structure: vertices stand for variables, and an edge indicates a possible direct conditional dependence. The graph is useful not only as a picture of precision-matrix zeros, but also because it identifies which variables can be separated by conditioning on a chosen set.

The key connection is between graph separation and conditional independence. For a Gaussian model, the density also decomposes into factors involving only variables in graph cliques. The resulting factorization is the bridge between a matrix representation and the graph’s separation properties.

Graphs and Markov Properties

Let \(G=(V,E)\) be a finite undirected graph with vertex set \(V=\{1,\ldots,p\}\), and let \(X=(X_1,\ldots,X_p)^T\) have a nonsingular Gaussian distribution \(N_p(\mu,\Sigma)\). Its precision matrix is \(K=\Sigma^{-1}\). We consider graphs whose edges include every pair with a nonzero off-diagonal entry of \(K\); equivalently, \(K_{ij}=0\) whenever \(\{i,j\}\notin E\). An edge may be present even if the corresponding entry is zero, so a graph can encode a model with additional zeros.

For a nonsingular Gaussian vector, the standard precision-matrix characterization is \(X_i\perp X_j\mid X_{V\setminus\{i,j\}}\) if and only if \(K_{ij}=0\). Thus the pairwise Markov property is exactly the condition that nonedges correspond to precision-matrix zeros. In a Gaussian model, pairwise, local, and global Markov properties are equivalent. The factorization and separation arguments below explain how the global property follows from a clique factorization.

Cliques and Density Factorization

A clique is a set of vertices in which every pair is joined by an edge. A maximal clique is a clique not contained in a larger clique. A clique potential is a nonnegative function of the variables indexed by a clique. A density factorizes over the cliques of \(G\) when it can be written as a product of such functions, up to a normalizing constant.

For a Gaussian vector, the density has the form

Write \(z=x-\mu\). Expanding the quadratic form gives

The coefficient of each cross-product \(z_i z_j\) is zero for a nonedge. Every remaining term involves either one vertex or the two endpoints of an edge. Both are cliques, so these terms can be grouped into clique potentials.

Proof of factorization from precision zeros. For each vertex and edge define

Then the density is the normalizing constant times \(\prod_i\psi_i(z_i)\prod_{\{i,j\}\in E}\psi_{ij}(z_i,z_j)\), because the omitted cross-terms have \(K_{ij}=0\). Each vertex factor is supported on a singleton clique and each edge factor on a two-vertex clique. Group factors into maximal cliques to obtain the stated factorization.

Proof that factorization implies global Markov. Suppose \(S\) separates \(A\) and \(B\). Remove the vertices in \(S\); the remaining graph breaks into connected components. A clique can intersect vertices outside \(S\) in at most one such component, since two vertices from different components cannot be joined by an edge. Fix \(x_S\). The product of clique potentials therefore splits into a factor depending on \(x_S\) alone and separate factors, one for each component, depending on that component’s variables and \(x_S\). The conditional density of \(X_{V\setminus S}\) given \(X_S=x_S\) is proportional to this product. Its normalizing integral splits into the product of component integrals by Tonelli’s theorem for nonnegative functions; for almost every \(x_S\) the conditional density is defined and normalized. Thus the components are conditionally independent given \(X_S\). Since no component can contain both a vertex of \(A\) and a vertex of \(B\), integrating out components that meet neither set yields \(X_A\perp X_B\mid X_S\). For a Gaussian vector, this global property implies the pairwise property by taking \(S=V\setminus\{i,j\}\) for each nonedge, and the precision-matrix characterization then gives \(K_{ij}=0\). \(\square\)

Worked Gaussian Graphs

What the Factorization Says—and What It Does Not

A clique factorization is a structural statement about how the joint density is assembled. It does not say that variables in different cliques are independent: maximal cliques can overlap, and their factors share variables. Instead, the factorization guarantees conditional independence when a separator blocks every graph path between two sets.

One common mistake is to interpret a zero precision entry as marginal independence. In the chain example, \(K_{13}=0\) gives independence of \(X_1\) and \(X_3\) conditional on \(X_2\), not necessarily marginal independence. Indeed, direct inversion gives

so \(\operatorname{Cov}(X_1,X_3)=1/4\ne0\). The correction is to read a missing edge as a conditional-independence statement given the other variables, and to use graph separators to identify the relevant conditioning set.

This connection matters because a sparse graph makes the dependence structure interpretable and gives a compact representation of a high-dimensional Gaussian density. The graph describes which interactions may appear in the density’s clique factors, while separation identifies conditional independences that hold across groups of variables.