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.
- Graphical OWL (GOWL): A likelihood-based method that applies the OWL penalty to the entire precision matrix $\Theta$.
- 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.
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.
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