Learning Unfaithful $K$-separable Gaussian Graphical Models

De Wen Soh, Sekhar TatikondaJMLR 2019 · OpenReview

TL;DR

This paper introduces a novel algorithm to test for "faithfulness" in Gaussian graphical models, a crucial property for accurately inferring graph structures. They then leverage this test to develop efficient algorithms for learning the structure of $K$-separable Gaussian graphical models, even when the underlying conditional independence relations are unfaithful, with improved sample complexity.

What Problem Does This Paper Address?

Gaussian graphical models (GGMs) are powerful tools for representing conditional independence relationships between variables. A key property is the global Markov property: if a set of nodes $S$ separates two nodes $u$ and $v$, then the variables associated with $u$ and $v$ are conditionally independent given the variables in $S$. However, the converse isn't always true – conditional independence doesn't necessarily imply graph separation. When the converse does hold, the relationship is called "faithful."

Faithfulness is critical for structural learning in GGMs because it allows us to directly infer the absence of an edge between two nodes if we find a set $S$ that conditionally independs them. The challenge is that real-world data might not always exhibit this faithful property, making standard learning algorithms unreliable. This paper tackles this by:

  1. Characterizing faithfulness: Providing a way to understand when this property holds.
  2. Developing a faithfulness test: Creating an algorithm to detect faithfulness using only local conditional independence information.
  3. Learning unfaithful models: Using the faithfulness test to learn the structure of GGMs, specifically $K$-separable models, even when faithfulness is violated.

Methods

The core of the paper lies in two main contributions:

  1. Faithfulness Test (Algorithm 1): The authors propose an algorithm to test if a conditional independence relation $X_u \perp X_v \mid X_S$ is faithful. The key idea is to construct a new graph where nodes are the variables not in $S$ (i.e., $S^c$). An edge exists between two nodes in this new graph if they are conditionally independent given $X_S$. If there's a path between $u$ and $v$ in this new graph, the original relation is deemed unfaithful. If no path exists, it's faithful. This test relies on local conditional independence information and doesn't require assumptions about the population covariance matrix.
  2. Structure Learning for $K$-separable GGMs:
    • Weakly $K$-separable: For graphs where any two non-adjacent nodes can be separated by a set of at most $K$ nodes, they develop an algorithm that uses the faithfulness test. It iterates through potential separator sets $S$ and checks for conditional independence. If a set $S$ is found that conditionally independs $u$ and $v$, and the relation is faithful, it implies no edge between $u$ and $v$. This algorithm achieves $\Omega(K \log p)$ sample complexity.
  3. Strongly $K$-separable: This is a stricter condition where even for adjacent nodes, a separator set of size at most $K$ exists in a modified graph. They extend their approach to learn not only the graph structure but also the precision matrix entries (edge weights). This also leverages the faithfulness test and provides error bounds for learning these weights.

Datasets

Not discussed in the paper. The algorithms are presented for learning from a given covariance matrix or from samples of a multivariate Gaussian distribution.

Key Insights and Ideas

  • Faithfulness is not guaranteed, but testable: The paper highlights that faithfulness is a desirable but not universal property of GGMs. Crucially, they show it can be tested using local conditional independence information, which is a significant step beyond assuming it.
  • $K$-separability as a structural assumption: The concept of $K$-separability provides a useful structural constraint that allows for efficient learning algorithms with controlled sample complexity, particularly in high-dimensional settings. It's a more general assumption than bounded degree.
  • Unfaithfulness is manageable: By developing a faithfulness test, the authors can handle models that violate this property, broadening the applicability of their learning algorithms.
  • Bridging conditional independence and graph structure: The core insight is that by carefully testing conditional independence relations and their faithfulness, one can reliably infer the presence or absence of edges in the graphical model.

Key Results

  • Algorithm for Faithfulness Testing: A novel algorithm is presented that tests the faithfulness of a conditional independence relation $X_u \perp X_v \mid X_S$.
  • Structure Learning for Weakly $K$-separable GGMs: An algorithm is proposed that learns the graph topology with $\Omega(K \log p)$ sample complexity, making no assumptions about faithfulness.
  • Structure and Precision Matrix Learning for Strongly $K$-separable GGMs: An algorithm is developed for learning both the graph structure and the precision matrix entries, also with improved sample complexity and error bounds.
  • Subsumption of Degree Bounds: The $K$-separable assumption is shown to subsume traditional degree-bounded assumptions, allowing the algorithms to handle a wider class of graphs.

Limitations and Future Work

  • Assumptions: While the faithfulness test itself requires no assumptions on the covariance matrix (beyond it being Gaussian), the learning algorithms rely on the $K$-separable property (weakly or strongly).
  • Computational Complexity: While sample complexity is improved, the algorithms still involve searching through sets of nodes, which can be computationally intensive for large $K$ or $p$.
  • General Markov Random Fields: The authors suggest extending their work to other types of Markov random fields, such as Ising models, where faithfulness is also a relevant concept but may behave differently.
  • Faithfulness in other models: Investigating when unfaithful conditional independence relations occur and how to identify them in other graphical model families is an open area.

Summary updated

Abstract

The global Markov property for Gaussian graphical models ensures graph separation implies conditional independence. Specifically if a node set $S$ graph separates nodes $u$ and $v$ then $X_u$ is conditionally independent of $X_v$ given $X_S$. The opposite direction need not be true, that is, $X_u \perp X_v \mid X_S$ need not imply $S$ is a node separator of $u$ and $v$. When it does, the relation $X_u \perp X_v \mid X_S$ is called faithful. In this paper we provide a characterization of faithful relations and then provide an algorithm to test faithfulness based only on knowledge of other conditional relations of the form $X_i \perp X_j \mid X_S$. We study two classes of separable Gaussian graphical models, namely, weakly $K$-separable and strongly $K$-separable Gaussian graphical models. Using the above test for faithfulness, we introduce algorithms to learn the topologies of weakly $K$-separable and strongly $K$-separable Gaussian graphical models with $\Omega(K\log p)$ sample complexity. For strongly $K$-separable Gaussian graphical models, we additionally provide a method with error bounds for learning the off-diagonal precision matrix entries.
BibTeX
@article{soh2019learning,
  author = {De Wen Soh and Sekhar Tatikonda},
  title = {{Learning Unfaithful $K$-separable Gaussian Graphical Models}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=zFDrvp7CRJ},
}
Figure