High-Dimensional Gaussian Graphical Model Selection: Walk Summability\n and Local Separation Criterion

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

In high-dimensional statistics, "structure learning"—the process of identifying the underlying web of dependencies among a large set of variables—presents a significant challenge. Gaussian Graphical Models (GGMs) are a cornerstone for representing these dependencies, where an edge between two variables indicates a direct conditional dependency. However, when the number of variables ($p$) exceeds the number of samples ($n$), traditional methods often falter or rely on complex, non-intuitive conditions.

A landmark study by Anandkumar, Tan, and Willsky addresses this by introducing a simple local algorithm for structure learning. Unlike global optimization methods like the Graphical Lasso, which rely on mathematically convenient but hard-to-verify "incoherence conditions," this work proposes a method based on local conditional covariance thresholding. The authors identify a broad class of graphs where structure learning is tractable under transparent conditions: walk-summability and local separation.

The CCT Algorithm

The core contribution of this research is the Conditional Covariance Threshold (CCT) algorithm. The CCT algorithm operates on a simple principle: if two variables are not directly connected in the graph, there should exist a small set of other variables that, when conditioned upon, render the two variables nearly independent.

Algorithm 1: The Conditional Covariance Threshold (CCT) algorithm for structure learning.

As shown in Algorithm 1, the CCT test iterates through every pair of nodes $(i, j)$ in the vertex set $V$. For each pair, it calculates the empirical conditional covariance, conditioning on all possible subsets $S$ of size up to $\eta$. If the minimum absolute conditional covariance across all such subsets exceeds a predefined threshold $\xi_{n,p}$, the algorithm adds an edge between $i$ and $j$. This greedy, local approach avoids the computational burden of global optimization.

Theoretical Foundations

The success of the CCT algorithm is predicated on two key theoretical properties: walk-summability and local separation.

Walk-Summability

Walk-summability is a property of the model's precision matrix (the inverse of the covariance matrix). In a walk-summable GGM, the "weight" of all possible walks between any two nodes in the graph converges. This property is crucial because it allows the authors to bound the "long-range" influence of distant nodes. It ensures that the correlations between nodes are primarily driven by their local neighborhood, making local thresholding a viable strategy.

Local Separation Property

The second pillar is the presence of sparse local vertex separators. For any two non-adjacent nodes $i$ and $j$, there must exist a small set of nodes $S$ within a local neighborhood that "separates" them, effectively breaking their dependency.

Illustration of the local separation property where a small set $S(i,j)$ separates nodes $i$ and $j$.

Figure 1 illustrates this concept. In the graph, nodes $i$ and $j$ are separated by the set $S(i,j) = \{a, b\}$. By conditioning on this small local set, the conditional covariance between $i$ and $j$ becomes zero (or near zero in the presence of noise), allowing the algorithm to correctly identify the absence of an edge.

Analysis and Results

The authors rigorously analyze the CCT algorithm's performance, establishing both sufficient and necessary conditions for structural consistency (sparsistency).

Sample Complexity and Efficiency

The algorithm achieves sparsistency when the number of samples $n$ scales as $\Omega(J_{min}^{-2} \log p)$, where $J_{min}$ represents the minimum absolute edge potential. This logarithmic scaling with respect to the number of variables $p$ is ideal for high-dimensional settings. Computationally, the algorithm runs in $O(p^{\eta+2})$ time. For many common graph families—such as Erdős-Rényi, power-law, and small-world graphs—the separator size $\eta$ is a small constant, ensuring the algorithm remains efficient even as $p$ grows.

Information-Theoretic Limits

Beyond proving the efficacy of CCT, the paper explores the fundamental limits of structure learning. Using Fano’s inequality and the concept of typical sets, the authors derive non-asymptotic necessary conditions on the number of samples required for any algorithm to succeed. For instance, in Erdős-Rényi graphs, they show that $n$ must satisfy a specific lower bound related to the graph's parameters, providing a clear benchmark for statistical efficiency.

Conclusion

This work provides a transparent and efficient framework for learning the structure of high-dimensional GGMs. By shifting the focus from global optimization to local conditional testing, and by grounding the analysis in intuitive properties like walk-summability and local separation, the authors offer a method that is both theoretically sound and practically applicable. Future work may extend these information-theoretic techniques to non-Gaussian models and more complex graph structures, further broadening the scope of local structure learning.

Summary updated

Abstract

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