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.
The algorithm operates by:
- Local Search: For every pair of nodes $(i, j)$, it examines small subsets of other nodes ($S$) within a certain range.
- 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.
- 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.
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