Source-linked AI summary
Trek separation for Gaussian graphical models
Seth Sullivant, Kelli Talaska, Jan Draisma
TL;DR
Gaussian graphical models link conditional independence to low-rank covariance submatrices, but d-separation does not generally characterize rank drops for arbitrary submatrices. The paper gives trek separation criteria for these ranks across directed, undirected, and mixed graphs, with theorem-level characterizations for directed and mixed graphs.
Problem
For arbitrary covariance submatrices, rank drops do not generally correspond to conditional independence or a d-separation criterion.
Source: §1 · p. 2Method
The paper develops t-separation using the trek rule and determinant expansions of trek-based covariance polynomials, with combinatorial results including the Gessel–Viennot–Lindström lemma and Menger’s theorem.
Source: §1 · pp. 2–3Results
For directed and mixed graphs, covariance submatrices have rank at most r for all consistent covariance matrices exactly when the corresponding vertex sets t-separate them with separator-set sizes totaling at most r.
Source: §2.1 · p. 6, §2.3 · p. 11Takeaways & Limitations
T-separation extends determinantal constraints used for inference beyond the vanishing tetrads used by TETRAD to infer hidden-variable graph structure.
Source: §1 · p. 2In general mixed graphs, vanishing low-rank submatrices can fail to characterize distributions belonging to the model.
Source: §4 · p. 21
Abstract
from arXiv · showhide
Gaussian graphical models are semi-algebraic subsets of the cone of positive definite covariance matrices. Submatrices with low rank correspond to generalizations of conditional independence constraints on collections of random variables. We give a precise graph-theoretic characterization of when submatrices of the covariance matrix have small rank for a general class of mixed graphs that includes directed acyclic and undirected graphs as special cases. Our new trek separation criterion generalizes the familiar $d$-separation criterion. Proofs are based on the trek rule, the resulting matrix factorizations and classical theorems of algebraic combinatorics on the expansions of determinants of path polynomials.
1. Introduction.
In Gaussian graphical models, conditional independence corresponds to particular low-rank covariance submatrices. The introduction presents t-separation as a graph criterion for characterizing rank drops in covariance submatrices, beyond those captured by d-separation.
1. Introduction.
- For directed acyclic graphs, d-separation characterizes conditional independence, which for normal variables is equivalent to rank ΣA∪C,B∪C = #C.Source: §1 · p. 1
- For directed graphical models, t-separation completely characterizes when covariance submatrices drop rank and their generic lower rank.Source: §1 · p. 2
- The criterion unifies rank conditions implied by d-separation with the tetrad representation theorem [12].Source: §1 · p. 2
- T-separation offers broader determinantal constraints for constraint-based inference than TETRAD’s use of vanishing tetrads to infer hidden-variable graph structure.Source: §1 · p. 2
- The proof strategy uses trek-based covariance polynomials, determinant expansions, the Gessel–Viennot–Lindström lemma, and Menger’s theorem.Source: §1 · pp. 2–3
2. Treks and t-separation.
The section introduces trek separation as a graph criterion for low-rank covariance submatrices, then gives necessary and sufficient characterizations for directed, undirected, and mixed graphs.
2.1. Directed graphs.
- For directed acyclic graphs, Σ_A,B has rank at most r for all model covariances exactly when sets C_A,C_B with total size at most r t-separate A from B; generic rank reaches the bound.T-separation requires every trek from A to B to meet C_A on its first path or C_B on its second.Source: §2.1 · p. 6
- The directed-graph criterion also characterizes conditional independence through a partition of the conditioning set, and explains the choke-point minor missed by d-separation.The theorem includes the tetrad representation theorem as a special case.Source: §2.1 · p. 7
2.2. Undirected graphs.
- For undirected graphs, Σ_A,B has rank at most r exactly when a separating vertex set of size at most r exists; generic rank reaches the bound.The authors report no new rank constraints beyond those implied by conditional independence.Source: §2.2 · p. 9
2.3. Mixed graphs.
- For mixed graphs, rank at most r holds exactly when a triple of sets t-separates A from B and has total size at most r; generic rank reaches the bound.The mixed-graph criterion also characterizes conditional independence, but conditional independence and vanishing minors do not characterize the full model covariance set.Source: §2.3 · p. 11
3. Proofs.
The proofs connect determinant and covariance-minor vanishing to path and trek intersection criteria, using blocking sets and graph transformations to establish rank and separation claims across directed, undirected, and mixed graphs.
3.1. Proof of Theorem 2.8 (directed graphs).
- For directed acyclic graphs, detΣA,B vanishes identically exactly when every system of simple treks from A to B has a sided intersection.The proof applies Cauchy–Binet and path-system determinant criteria; checking simple trek systems suffices.Source: §3.1 · pp. 12–14
- When the smallest blocking set has size r, ΣA,B has generic rank r for generic λ and φ parameters.The proof relates sided intersections to blocking sets using Menger’s theorem.Source: §3.1 · pp. 14–15
3.2. Proof of Theorem 2.15 (undirected graphs).
- For undirected G, det((I − Ψ)^−1)A,B vanishes identically exactly when every system of |A| directed paths in bG has two paths sharing a vertex.The graph bG replaces each undirected edge by oppositely directed edges with the same weight.Source: §3.2 · p. 16
3.3. Proof of Theorem 2.17 (mixed graphs).
- Bidirected subdivision preserves generic rank and the existence of a t-separating set of any given size.The proof reduces graphs with bidirected edges to their subdivision while retaining the t-separation condition.Source: §3.3 · p. 17
- Without undirected edges, rank at most r for all compatible covariance matrices is equivalent to a t-separating pair CL, CR with |CL| + |CR| ≤ r.This case reduces to directed acyclic graphs through bidirected subdivision.Source: §3.3 · p. 18
- In mixed graphs with directed and undirected edges, universal sided crossings force a Cauchy–Binet factor to vanish, whereas a trek system without sided crossing implies detΣA,B is nonzero.The proof establishes the crossing direction through products of directed- and undirected-path determinants.Source: §3.3 · pp. 19–20
- In the determinant argument, specializing parameters for disjoint middle paths makes each relevant trek monomial correspond to a unique trek, preserving a nonzero determinant expression.The construction adds labeled bidirected edges for nonempty middle paths and deletes undirected edges; disjointness supports the specialization and uniqueness.Source: §3.3 · pp. 20–21
- For |A|=|B|=r+1, the determinant vanishes exactly when every system of ℓ treks from A to B has a sided intersection.The proof then applies Menger’s theorem to characterize this condition.Source: §3.3 · p. 21
- A 3m-vertex graph encodes treks in G as directed paths, so Menger’s theorem yields a t-separating triple with total size at most r.The separator consists of middle-part vertices and right-side vertices in the transformed graph, which induce the triple in G.Source: §3.3 · p. 21
4. Conclusions and open problems.
The t-separation criterion characterizes vanishing covariance determinants in Gaussian directed, undirected, and mixed graph models, with potential applications to inference. Open questions concern when low-rank constraints characterize model membership and how t-separation applies beyond normal variables.
4. Conclusions and open problems.
- T-separation characterizes vanishing covariance determinants in Gaussian directed, undirected, and mixed graph models, with potential applications to inference procedures extending tetrad-based methods.The results also extend to graphs with cycles through a more general version of the Gessel–Viennot–Lindström lemma.Source: §4 · p. 21
- Whether vanishing low-rank submatrices characterize model membership is known for acyclic directed and undirected graphs but can fail for general mixed graphs.Source: §4 · p. 21
- The significance of t-separation for non-normal variables, especially discrete variables, and its translation into density constraints remain open problems.Source: §4 · p. 21