Robust Gaussian Graphical Modeling with the Trimmed Graphical Lasso

Eunho Yang, Aurelie C. LozanoNeurIPS 2015 · OpenReview

TL;DR

The Trimmed Graphical Lasso (trim-glasso) is a new method for estimating sparse network structures (Gaussian Graphical Models) that is resistant to outliers and heavy-tailed data. Unlike previous robust approaches, it provides rigorous theoretical guarantees for consistency in high-dimensional settings and significantly outperforms standard methods on both simulated and real-world genomic data.

What Problem Does This Paper Address?

Gaussian Graphical Models (GGMs) are a staple in data science for uncovering how variables in a system—like genes in a cell or users in a social network—interact with one another. By estimating a "precision matrix" (the inverse of the covariance matrix), researchers can identify conditional dependencies: if two variables are connected in the resulting graph, they have a direct relationship that isn't explained away by other variables.

However, the standard tool for this, the Graphical Lasso (glasso), has a major "Achilles' heel": it assumes the data follows a clean multivariate normal distribution. In the real world—especially in high-dimensional biology—data is often "messy," containing outliers or "heavy tails" that deviate from normality. Even a few corrupted observations can completely distort the estimated network. While some robust alternatives existed, they often lacked mathematical proof that they would work reliably in high-dimensional scenarios where the number of variables ($p$) exceeds the number of samples ($n$).

Methods

The authors introduce the Trimmed Graphical Lasso, inspired by the "Least Trimmed Squares" technique from linear regression.

The core idea is implicit trimming:

  1. Weighting: Instead of treating every data point equally, the algorithm assigns a weight ($w_i$) to each observation.
  2. Trimming: The weights are constrained such that the algorithm must pick the "best" $h$ samples (where $h$ is a user-defined parameter representing the expected number of clean samples) and ignore the rest.
  3. Optimization: The method minimizes a weighted negative log-likelihood combined with an $\ell_1$ penalty (to ensure the resulting graph is sparse).

Because this creates a non-convex optimization problem (it's hard to pick the best samples and the best graph simultaneously), the authors developed an efficient algorithm based on composite gradient descent. Crucially, they provide a mathematical proof showing that any local optimum found by their algorithm is statistically consistent, meaning it will converge to the true underlying network as more data is provided.

Datasets

The authors evaluated their method using:

  • Simulated Data: Five different contamination scenarios (M1-M5) where "good" Gaussian data was mixed with various types of "bad" data (outliers with different means, variances, or symmetries).
  • Yeast Gene Expression Data: A real-world dataset consisting of 112 yeast samples and 126 genes involved in the cell-cycle pathway. This is a classic benchmark where the "true" network is partially known via the KEGG database.

Key Insights and Ideas

  • Local Optima are Enough: In many non-convex problems, researchers worry about getting stuck in "bad" local solutions. This paper shows that for trim-glasso, even local optima provide strong statistical guarantees, making the method practical for real-world use.
  • The Power of $h$: By tuning the parameter $h$ (the number of samples to keep), the model can adapt to different levels of data corruption. If you suspect 20% of your data is junk, you set $h$ to 80% of $n$.
  • Efficiency Matters: Robustness often comes with a massive computational tax. Trim-glasso is significantly faster than $t$-distribution-based methods (e.g., 1.58 seconds vs. 45.78 seconds in their tests), making it scalable to larger networks.

Key Results

  • Superior Accuracy: In simulations, trim-glasso consistently achieved higher sensitivity and specificity (measured via ROC curves) than the standard glasso and other robust competitors like $t$-lasso.
ROC curves comparing trim-glasso to other methods across different contamination scenarios.
  • Biological Relevance: On the yeast dataset, trim-glasso achieved an $F_1$-score of 0.41 in matching the known KEGG biological pathway, compared to just 0.23 for the standard glasso. It successfully identified key "hub" genes like CDC6 and PDS1 that standard methods missed or obscured with noise.
Yeast gene network estimated by trim-glasso and histogram showing outlier expression.
  • Robustness to "Heavy" Outliers: The method proved particularly effective when outliers were far from the mean, where standard glasso typically fails by adding many "spurious" (fake) edges to the graph.

Limitations and Future Work

  • Choosing $h$: The performance depends on choosing a good value for $h$. While the authors suggest using cross-validation, in very small datasets, picking the wrong $h$ could lead to discarding useful data or keeping too much noise.
  • Symmetry Assumptions: The theoretical analysis assumes certain structural properties of the data. While it performs well on asymmetric outliers in practice, the most rigorous guarantees are centered on symmetric distributions.
  • Future Directions: The authors suggest that this trimming framework could be extended beyond Gaussian models to other types of graphical models, such as those used for discrete or mixed data types.

Summary updated

Abstract

Gaussian Graphical Models (GGMs) are popular tools for studying network structures. However, many modern applications such as gene network discovery and social interactions analysis often involve high-dimensional noisy data with outliers or heavier tails than the Gaussian distribution. In this paper, we propose the Trimmed Graphical Lasso for robust estimation of sparse GGMs. Our method guards against outliers by an implicit trimming mechanism akin to the popular Least Trimmed Squares method used for linear regression. We provide a rigorous statistical analysis of our estimator in the high-dimensional setting. In contrast, existing approaches for robust sparse GGMs estimation lack statistical guarantees. Our theoretical results are complemented by experiments on simulated and real gene expression data which further demonstrate the value of our approach.
BibTeX
@inproceedings{yang2015robust,
  author = {Eunho Yang and Aurelie C. Lozano},
  title = {{Robust Gaussian Graphical Modeling with the Trimmed Graphical Lasso}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=S1WQhDWO-B},
}
Figure