High-Dimensional Gaussian Graphical Model Selection: Tractable Graph Families

Animashree Anandkumar, Vincent Y. F. Tan, Alan S. Willsky

Abstract: We consider the problem of high-dimensional Gaussian graphical model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples $n=\omega(J_{min}^{-2} \log p)$, where $p$ is the number of variables and $J_{min}$ is the minimum (absolute) edge potential of the graphical model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.

Introduction

Reconstructing the hidden network of relationships between thousands of variables from a limited number of observations is a fundamental challenge in modern statistics. This "High-Dimensional" problem—where the number of variables ($p$) significantly exceeds the number of samples ($n$)—is common in fields like genomics and finance. Gaussian Graphical Models (GGMs) provide a framework for this, where edges represent conditional dependencies. While methods like the Graphical Lasso are popular, they often depend on abstract "incoherence" conditions that are difficult to verify. This paper introduces a more transparent approach using the Conditional Covariance Test (CCT).

The Conditional Covariance Test (CCT)

The authors propose a greedy, local algorithm called the Conditional Covariance Test (CCT). Unlike global optimization methods, CCT focuses on local neighborhoods to determine the presence of an edge.

Algorithm 1: The Conditional Covariance Test (CCT) for structure learning using samples $\mathbf{x}^n$.

The algorithm operates by:

  1. Local Search: For every pair of nodes $(i, j)$, it examines small subsets of other nodes ($S$) within a certain range.
  2. Thresholding: It computes the empirical conditional covariance between $i$ and $j$ given $S$. If this value remains above a threshold $\xi_{n,p}$ for all subsets $S$ up to size $\eta$, an edge is added.
  3. Efficiency: By limiting the size of $S$ to a small constant $\eta$, the algorithm achieves polynomial complexity $O(p^{\eta+2})$, making it computationally tractable for high-dimensional data.

Theoretical Framework: Walk-Summability and Local Separation

The success of CCT relies on two primary conditions: walk-summability and the local separation property.

Walk-summability is a property of the model's precision matrix ensuring that correlations decay as the distance between nodes in the graph increases. This property, previously known to be important for inference (e.g., Belief Propagation), is shown here to be equally critical for structure learning.

The local separation property requires that any two non-adjacent nodes can be "separated" by a small set of nearby nodes. This ensures that a local test is sufficient to determine the absence of a direct edge.

Illustration of a local separator $\mathcal{S}(i,j)$ (shaded box) that separates nodes $i$ and $j$ in the graph.

Key Results and Insights

The paper establishes several significant theoretical results:

  • Sample Complexity: The authors prove that CCT achieves structural consistency (sparsistency) with a sample size of $n = \Omega(J_{min}^{-2} \log p)$, where $J_{min}$ is the minimum edge potential. This matches the optimal scaling of more complex global algorithms.
  • Broad Applicability: The local separation requirement is shown to hold for a wide variety of graph ensembles, including Erdős-Rényi random graphs, power-law/scale-free networks, and small-world graphs.
  • Information-Theoretic Limits: Using "typicality" concepts from coding theory, the authors derive non-asymptotic necessary conditions for the number of samples required by any algorithm, providing a benchmark for performance.
  • Inference Bridge: The paper settles a long-standing question by proving that Loopy Belief Propagation (LBP) provides asymptotically correct variances for walk-summable models on "locally tree-like" graphs.

Limitations and Future Directions

While powerful, the local approach has limitations. It fails on dense graphs where local separators become too large, making the problem computationally "hard" for this specific algorithm. Additionally, the algorithm requires an estimate of $\eta$, the maximum separator size, which may not be known a priori. Future work may extend these "typicality-based" lower bounds to other discrete models, such as Ising models.

Summary updated

Abstract

We consider the problem of high-dimensional Gaussian graphical model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples n=omega(J_{min}^{-2} log p), where p is the number of variables and J_{min} is the minimum (absolute) edge potential of the graphical model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.
BibTeX
@article{anandkumar2012high,
  author = {Animashree Anandkumar and Vincent Y. F. Tan and Alan S. Willsky},
  title = {{High-Dimensional Gaussian Graphical Model Selection: Tractable Graph Families}},
  journal = {J. Mach. Learn. Res.},
  year = {2012},
  url = {https://openreview.net/forum?id=Q7m4kbPXVYB},
}
Figure