Exact Hybrid Covariance Thresholding for Joint Graphical Lasso

Qingming Tang, Chao Yang, Jian Peng, Jinbo Xu

Abstract

This paper considers the problem of estimating multiple related Gaussian graphical models from a $p$-dimensional dataset consisting of different classes. Our work is based upon the formulation of this problem as group graphical lasso. This paper proposes a novel hybrid covariance thresholding algorithm that can effectively identify zero entries in the precision matrices and split a large joint graphical lasso problem into small subproblems. Our hybrid covariance thresholding method is superior to existing uniform thresholding methods in that our method can split the precision matrix of each individual class using different partition schemes and thus split group graphical lasso into much smaller subproblems, each of which can be solved very fast. In addition, this paper establishes necessary and sufficient conditions for our hybrid covariance thresholding algorithm. The superior performance of our thresholding method is thoroughly analyzed and illustrated by a few experiments on simulated data and real gene expression data.

Introduction

Estimating relationships between high-dimensional variables across multiple conditions—such as gene interactions in healthy versus diseased cells—is a critical task in modern data science. The Joint Graphical Lasso (JGL) is a powerful framework for this, as it allows models to share information across related classes, assuming they possess similar network structures. However, JGL is computationally intensive, particularly as the number of variables ($p$) and classes ($K$) increases.

Existing acceleration techniques often use "screening" to identify zero entries in the precision matrix early, allowing the problem to be decomposed into smaller, independent blocks. A major limitation of these methods is their reliance on uniform thresholding, which forces all classes to share the same block structure. If even one class contains a unique connection, the entire matrix remains coupled, creating a significant computational bottleneck.

Methods: Hybrid Covariance Thresholding

The authors introduce Hybrid ADMM (HADMM), which leverages a non-uniform thresholding approach to overcome the limitations of uniform partitioning.

Non-Uniform Partitioning

Unlike traditional methods, HADMM allows each class's precision matrix to be partitioned differently. This flexibility means that variables might be grouped together in one class but separated in another, allowing for a much finer decomposition of the global optimization problem.

Comparison of uniform (left) vs. non-uniform (right) partitioning schemes.

The Hybrid Criterion

The algorithm identifies zero entries by evaluating two distinct conditions: class-specific thresholding (analyzing individual sample covariance) and global thresholding (analyzing aggregated covariance across all classes). By combining these criteria, the hybrid approach can "shatter" a large matrix into many tiny, independent sub-problems that are far easier to solve than the original monolithic problem.

Comparison of Global, Class-specific, and Hybrid partitioning on a 3-node graph.

Mathematical Exactness and Parallelization

The authors provide theoretical proofs (Theorems 2 and 3) demonstrating that this pre-processing step yields the exact same solution as solving the full JGL problem. Once decomposed, these sub-problems are solved in parallel using the Alternating Direction Method of Multipliers (ADMM), leading to massive performance gains.

Experimental Results

The method was evaluated on synthetic datasets with up to 10,000 variables and 10 classes, as well as a real-world gene expression dataset with 10,726 features and 3 classes.

  • Performance Gains: On synthetic data ($p=1000$), HADMM was consistently orders of magnitude faster than both Global ADMM (GADMM) and Local ADMM (LADMM).
  • Scalability: For the 10,000+ feature gene dataset, HADMM completed the estimation in 3.46 to 8.23 hours. Competing methods either failed to finish within a 20-hour window or were significantly slower.
  • Accuracy: Experimental validation confirmed that HADMM converges to the same objective function value as standard ADMM, ensuring that speed is achieved without sacrificing mathematical precision.

Conclusion

The core contribution of this work is the realization that joint estimation does not necessitate joint partitioning. By breaking the "uniform" constraint, the hybrid thresholding method effectively isolates independent components in high-dimensional, sparse settings. Future work may explore "dynamic" thresholding, where partitions are updated during optimization, and extending the hybrid logic to other penalties like the Fused Graphical Lasso.

Summary updated

Abstract

This paper considers the problem of estimating multiple related Gaussian graphical models from a $p$-dimensional dataset consisting of different classes. Our work is based upon the formulation of this problem as group graphical lasso. This paper proposes a novel hybrid covariance thresholding algorithm that can effectively identify zero entries in the precision matrices and split a large joint graphical lasso problem into small subproblems. Our hybrid covariance thresholding method is superior to existing uniform thresholding methods in that our method can split the precision matrix of each individual class using different partition schemes and thus split group graphical lasso into much smaller subproblems, each of which can be solved very fast. In addition, this paper establishes necessary and sufficient conditions for our hybrid covariance thresholding algorithm. The superior performance of our thresholding method is thoroughly analyzed and illustrated by a few experiments on simulated data and real gene expression data.
BibTeX
@inproceedings{tang2015exact,
  author = {Qingming Tang and Chao Yang and Jian Peng and Jinbo Xu},
  title = {{Exact Hybrid Covariance Thresholding for Joint Graphical Lasso}},
  booktitle = {ECML/PKDD},
  year = {2015},
  url = {https://openreview.net/forum?id=rCfWIpOf6-9},
}

Loading related content...

Figure