Learning Gaussian Graphical Models with Ordered Weighted L1 Regularization

Cody Mazza-Anthony, Bogdan Mazoure, Mark Coates

Abstract

Estimating the structure of Gaussian Graphical Models (GGMs) is a fundamental task in high-dimensional statistics, with applications ranging from genomics to finance. While standard methods like the Graphical Lasso (GLASSO) promote sparsity, they often fail to capture the inherent modular structure of real-world networks. This paper introduces two novel estimators, GOWL and ccGOWL, which utilize Ordered Weighted $\ell_1$ (OWL) regularization to simultaneously identify groups of related edges and recover the underlying network structure. Our results demonstrate that these methods offer superior accuracy and significant computational speedups compared to state-of-the-art structured estimators.

Introduction

In many scientific domains, researchers seek to estimate "precision matrices" to uncover conditional dependencies between variables. For instance, in genomics, these matrices reveal biological pathways, while in finance, they describe the interconnectedness of stock returns. Traditional approaches like GLASSO are effective at finding sparse networks but treat every potential connection independently.

However, real-world data often exhibits "structured" sparsity, where groups of edges share similar strengths due to common underlying factors. Existing methods for capturing this structure typically require pre-defined groups or rely on slow, multi-step algorithms. To address these limitations, we propose a framework that learns both the edge groupings and the network structure in a single optimization step.

Methodology: GOWL and ccGOWL

We propose two approaches based on the Ordered Weighted $\ell_1$ (OWL) norm. The OWL norm is unique because it sorts coefficients by magnitude before applying weights, encouraging coefficients to not only become zero (sparsity) but also to cluster into groups with identical values.

  1. Graphical OWL (GOWL): A likelihood-based method that applies the OWL penalty to the entire precision matrix $\Theta$.
  2. column-by-column Graphical OWL (ccGOWL): A more efficient approach that decomposes the problem into a series of regularized linear regressions, estimating the precision matrix one column at a time.
Overview of the GOWL and ccGOWL frameworks. GOWL operates on the vectorized precision matrix, while ccGOWL utilizes a column-wise regression approach for improved scalability.

The ccGOWL method is particularly advantageous as it can be easily parallelized, making it significantly more scalable than joint optimization methods.

Experimental Results

The performance of GOWL and ccGOWL was evaluated using synthetic datasets, cancer gene expression data, and S&P 500 equities data.

Synthetic Data Performance

On synthetic data with controlled sparsity and pre-defined blocks of correlated edges, ccGOWL consistently outperformed GLASSO and GOWL in terms of $F_1$ score. This advantage became more pronounced as the number of variables ($p$) increased, demonstrating the robustness of the OWL-based approach in high-dimensional settings.

F1 score comparison of GLASSO, GRAB, GOWL, and ccGOWL across various simulation settings defined by the number of variables and the proportion of edges within blocks.

Computational Efficiency

A key highlight of our work is the massive speedup achieved by ccGOWL. In timing comparisons against the state-of-the-art GRAB estimator, ccGOWL was orders of magnitude faster. For a network with 1,000 variables, ccGOWL completed the estimation in approximately 4 seconds, whereas GRAB required nearly 500 seconds.

Real-World Applications

  • Genomics: In a leukemia dataset, ccGOWL correctly grouped 49 out of 50 genes according to disease type (AML vs. ALL), providing a highly interpretable network.
  • Finance: Applied to S&P 500 data, ccGOWL successfully recovered industry sector groupings (e.g., Utilities, IT) without prior knowledge of sector labels.

Conclusion

GOWL and ccGOWL represent a significant step forward in learning structured Gaussian Graphical Models. By leveraging the grouping properties of the OWL norm, these methods provide a unified framework for simultaneous clustering and network estimation. Future work will focus on automated hyperparameter tuning and establishing theoretical consistency for these estimators.

Summary updated

Abstract

We address the task of estimating sparse structured precision matrices for multivariate Gaussian random variables within a graphical model framework. We propose two novel estimators based on the Ordered Weighted ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> (OWL) norm: 1) The Graphical OWL (GOWL) is a penalized likelihood method that applies the OWL norm to the lower triangle components of the precision matrix. 2) The column-by-column Graphical OWL (ccGOWL) estimates the precision matrix by performing OWL regularized linear regressions. Both methods can simultaneously identify groups of related edges in the graphical model and control the sparsity in the estimated precision matrix. We propose proximal descent algorithms to find the optimum for both estimators. For synthetic data where group structure is present, the ccGOWL estimator requires significantly reduced computation and achieves similar or greater accuracy than state-of-the-art estimators. Timing comparisons are presented and demonstrate the superior computational efficiency of the ccGOWL. We demonstrate the efficacy of the ccGOWL estimator on two domains - gene network analysis and econometrics.
BibTeX
@article{mazzaanthony2021learning,
  author = {Cody Mazza-Anthony and Bogdan Mazoure and Mark Coates},
  title = {{Learning Gaussian Graphical Models with Ordered Weighted L1 Regularization}},
  journal = {IEEE Trans. Signal Process.},
  year = {2021},
  doi = {10.1109/tsp.2020.3038480},
}
Figure