Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions

Salar Fattahi, Somayeh SojoudiJMLR 2019 · OpenReview

TL;DR

This paper establishes a theoretical equivalence between the computationally expensive Graphical Lasso (GL) and a simple thresholding method for learning sparse Gaussian graphical models. Crucially, it derives explicit closed-form solutions for GL under certain conditions, significantly outperforming existing methods in speed and scalability for large-scale problems.

What Problem Does This Paper Address?

Learning the structure of high-dimensional graphical models is essential for understanding complex systems in fields like neuroscience and finance. The Graphical Lasso (GL) is a popular method for this, but it's computationally intensive, especially for large datasets. A simpler, faster alternative is to threshold the sample covariance matrix. However, the conditions under which these two methods yield the same structure (i.e., are equivalent) were not well-understood and often depended on solving the GL itself. This paper aims to bridge this gap by providing verifiable conditions for GL-thresholding equivalence and, more importantly, deriving explicit closed-form solutions for GL, making it practical for much larger problems.

Methods

The authors introduce novel concepts of "sign-consistent" and "inverse-consistent" matrices to analyze the relationship between GL and thresholding. They derive sufficient conditions for their equivalence, which are directly verifiable from the sample covariance matrix. Building on this, they prove that GL has an explicit closed-form solution when the thresholded sample covariance matrix has an acyclic structure. This result is then generalized to arbitrary sparse graphs, providing an approximate closed-form solution. The approximation error is shown to decrease exponentially with the length of the minimum cycle in the graph's support structure. They also propose a warm-start algorithm that leverages these closed-form solutions to accelerate existing GL solvers.

Datasets

The paper evaluates its methods on:

  • Synthetic data.
  • Real-world functional MRI data (134 samples from 140 brain regions).
  • Transportation network traffic flow data (1049x1049 sample covariance matrix).
  • Massive randomly generated datasets, including a case with 80,000 dimensions and 20,000 samples.

Key Insights and Ideas

  • Equivalence Beyond Intuition: The paper provides rigorous conditions for when a simple thresholding of the sample covariance matrix yields the same graph structure as the complex Graphical Lasso. This is a significant theoretical contribution.
  • Closed-Form Solutions for GL: The most impactful insight is the derivation of explicit, closed-form solutions for GL, particularly for acyclic graph structures. This bypasses the need for iterative optimization, drastically improving computational efficiency.
  • Approximation Guarantees: For general sparse graphs, the authors provide an approximate closed-form solution and quantify its error based on graph properties (cycle length), offering theoretical backing for its accuracy.
  • Scalability Breakthrough: The derived closed-form solutions enable GL to be applied to problems orders of magnitude larger than previously feasible, as demonstrated by their performance on massive datasets.
  • Warm-Start Advantage: The closed-form solutions serve as excellent initial points for existing GL solvers, significantly speeding up their convergence.

Key Results

  • The proposed closed-form solution significantly outperforms state-of-the-art methods (QUIC, GLASSO) in terms of runtime, being on average 6, 36, and 951 times faster than elementary, QUIC, and GLASSO methods, respectively, for large-scale problems.
  • For problems with d=40,000 and d=80,000, existing methods failed to converge within 4 hours, while the proposed method obtained accurate solutions in under 30 minutes.
  • The approximation error of the closed-form solution decreases exponentially with the length of the minimum cycle in the graph, leading to high accuracy in practice.
  • The warm-start algorithm, using the closed-form solution, achieved speedups of up to 2.35x for QUIC and 4.45x for GLASSO, and doubled the size of solvable instances for GLASSO.
  • The accuracy (measured by Frobenius norm difference and similarity degree) of the closed-form solution is shown to be very high, often achieving similarity degrees greater than 0.98.

Limitations and Future Work

  • The paper notes that its results may not be directly applicable in the high sampling regime where the number of samples is large relative to the dimension, as the thresholded sample covariance matrix becomes dense.
  • The theoretical conditions for equivalence and closed-form solutions are sufficient but not always necessary.
  • Future work could involve tightening the approximation error bounds and exploring the application of these methods to other graphical model structures or problem types. The warm-start algorithm's effectiveness is also highlighted as a direction for further investigation.

Summary updated

BibTeX
@article{fattahi2019graphical,
  author = {Salar Fattahi and Somayeh Sojoudi},
  title = {{Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=Rq-IEDo5Ru},
}
Figure