Nested Covariance Determinants and Restricted Trek Separation in\n Gaussian Graphical Models

Mathias Drton, Elina Robeva, Luca WeihsarXiv 2018 · DOI · arXiv

Abstract

Directed graphical models specify noisy functional relationships among a collection of random variables. In the Gaussian case, each such model corresponds to a semi-algebraic set of positive definite covariance matrices. The set is given via parametrization, and much work has gone into obtaining an implicit description in terms of polynomial (in-)equalities. Implicit descriptions shed light on problems such as parameter identification, model equivalence, and constraint-based statistical inference. For models given by directed acyclic graphs, which represent settings where all relevant variables are observed, there is a complete theory: All conditional independence relations can be found via graphical $d$-separation and are sufficient for an implicit description. The situation is far more complicated, however, when some of the variables are hidden (or in other words, unobserved or latent). We consider models associated to mixed graphs that capture the effects of hidden variables through correlated error terms. The notion of trek separation explains when the covariance matrix in such a model has submatrices of low rank and generalizes $d$-separation. However, in many cases, such as the infamous Verma graph, the polynomials defining the graphical model are not determinantal, and hence cannot be explained by $d$-separation or trek-separation. In this paper, we show that these constraints often correspond to the vanishing of nested determinants and can be graphically explained by a notion of restricted trek separation.

Introduction

In causal inference, graphs serve as a fundamental language for representing how variables influence one another. When every variable in a system is observed, the theory of $d$-separation provides a complete mapping between the graph's structure and the conditional independence relations in the data. However, real-world scenarios frequently involve hidden (latent) variables, which introduce complex dependencies that $d$-separation cannot fully capture.

For Gaussian graphical models with latent variables, researchers have historically relied on trek separation to identify rank constraints in the covariance matrix. While powerful, trek separation fails to explain certain higher-order polynomial constraints, most notably the "Verma constraint" found in the Verma graph. This paper introduces a new framework—restricted trek separation—to bridge this gap and provide a unified graphical explanation for these complex constraints.

The Challenge of Hidden Variables

When variables are hidden, the implicit geometry of the model becomes significantly more complex. Simple independence is no longer sufficient to describe the model's constraints. The Verma graph is the classic example of this difficulty: it produces a polynomial constraint that is not a simple determinant, making it invisible to standard trek separation tools.

Figure 2: A mixed graph with a latent variable (node 5) influencing nodes 2 and 4, illustrating a structure where standard separation criteria fail to capture all polynomial constraints.

Methodology: Nested Determinants and Restricted Treks

The authors propose that these "missing" constraints are actually nested determinants—determinants of matrices where the entries themselves are determinants of smaller submatrices. To explain these graphically, they introduce two primary concepts:

  1. Restricted Trek Separation: Unlike standard treks, a restricted trek forces the "left side" of the path to remain within a specific set of vertices $P$, and the "right side" to remain within a set $Q$. This refinement allows for the identification of vanishing determinants that were previously hidden.
  2. The Swapping Property: This combinatorial property describes when a graph allows paths between two systems of treks to be "swapped" without creating intersections on the same side. This property is the key to showing how a large determinant factorizes into a nested structure.

Key Results and Characterizations

The paper provides a comprehensive analysis of small graph structures to validate the theory. A major result is the complete characterization of four-node acyclic mixed graphs. The authors demonstrate that all generators for the vanishing ideals of these graphs can be expressed as nested determinants with at most one level of nesting.

Figure 4: A catalog of four-node acyclic mixed graphs used to demonstrate that complex constraints can be systematically explained via nested determinants.

Furthermore, Theorem 3.7 establishes that for a broad class of "globally identifiable" mixed graphs, the model is entirely described by parentally nested determinants. This suggests that the geometry of hidden variable models is recursive: just as a nested determinant is a "determinant of determinants," graphical constraints are "separations within separations."

Conclusion and Future Work

By showing that the Verma constraint is not a mathematical outlier but a specific type of nested determinant, this work provides a more structured view of the complexity inherent in hidden variable models. While the paper provides sufficient conditions for these determinants to vanish, future work remains to determine if these conditions are necessary and to develop computationally efficient algorithms for finding restricted trek separations in larger, more complex systems.

Summary updated

Abstract

Directed graphical models specify noisy functional relationships among a\ncollection of random variables. In the Gaussian case, each such model\ncorresponds to a semi-algebraic set of positive definite covariance matrices.\nThe set is given via parametrization, and much work has gone into obtaining an\nimplicit description in terms of polynomial (in-)equalities. Implicit\ndescriptions shed light on problems such as parameter identification, model\nequivalence, and constraint-based statistical inference. For models given by\ndirected acyclic graphs, which represent settings where all relevant variables\nare observed, there is a complete theory: All conditional independence\nrelations can be found via graphical $d$-separation and are sufficient for an\nimplicit description. The situation is far more complicated, however, when some\nof the variables are hidden (or in other words, unobserved or latent). We\nconsider models associated to mixed graphs that capture the effects of hidden\nvariables through correlated error terms. The notion of trek separation\nexplains when the covariance matrix in such a model has submatrices of low rank\nand generalizes $d$-separation. However, in many cases, such as the infamous\nVerma graph, the polynomials defining the graphical model are not\ndeterminantal, and hence cannot be explained by $d$-separation or\ntrek-separation. In this paper, we show that these constraints often correspond\nto the vanishing of nested determinants and can be graphically explained by a\nnotion of restricted trek separation.\n
BibTeX
@misc{drton2018nested,
  author = {Mathias Drton and Elina Robeva and Luca Weihs},
  title = {{Nested Covariance Determinants and Restricted Trek Separation in\textbackslash\{\}n Gaussian Graphical Models}},
  year = {2018},
  eprint = {1807.07561},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.07561},
}
Figure