PaperlayerView exact revision on arXiv

Source-linked AI summary

The joint graphical lasso for inverse covariance estimation across multiple classes

Patrick Danaher, Pei Wang, Daniela M. Witten

arXiv:1111.0324v4stat.ME

TL;DR

High-dimensional data from distinct classes require graphical models that are sparse yet related without being identical. The paper proposes joint graphical lasso estimation with convex fused or group penalties, and reports more accurate simulated-network estimates, practical computation, and illustrative lung-cancer findings.

  • Problem

    Estimating separate or a single graphical model is inadequate when high-dimensional observations come from distinct but related classes with potentially different networks.

  • Method

    The joint graphical lasso jointly estimates sparse class-specific precision matrices by maximizing a penalized log likelihood with convex penalties that encourage shared edge values or sparsity patterns.

  • Results

    The proposed joint estimation methods outperform competing approaches on simulated datasets, while the algorithm is tractable for datasets exceeding 20,000 features.

  • Takeaways & Limitations

    Joint graphical lasso provides a practical way to estimate multiple related networks while separately controlling sparsity and similarity.

  • Takeaways & Limitations

    The computational speed improvements from Theorems 1 and 2 require sufficiently large tuning parameters λ1 and λ2.

Abstract

from arXiv · show

We consider the problem of estimating multiple related but distinct graphical models on the basis of a high-dimensional data set with observations that belong to distinct classes. A motivating example occurs in the analysis of gene expression data for tissue samples with and without cancer. In this case, we might wish to estimate a gene expression network for the normal tissue and a gene expression network for the tumor tissue. We expect the two gene expression networks to be similar but not identical to each other, and so more accurate estimation of these two networks may be possible using a joint approach. We propose the joint graphical lasso for this purpose. Rather than estimating a graphical model for each class separately, or a single graphical model across all classes, we borrow strength across the classes in order to estimate multiple graphical models that share certain characteristics, such as the locations or weights of nonzero edges. Our approach is based upon maximizing a penalized log likelihood. We employ fused lasso or group lasso penalties, and implement a very fast computational approach that solves the joint graphical lasso problem. In a simulation study we demonstrate that our proposed approach leads to more accurate estimation of networks and covariance structure than competing approaches. We further illustrate our proposal on a publicly-available lung cancer gene expression data set.

1. Introduction

Graphical models encode conditional dependencies through sparse inverse covariance matrices, but standard estimation struggles in high dimensions and cannot represent distinct yet related classes well. The joint graphical lasso addresses this by jointly estimating class-specific networks while encouraging shared characteristics, improving accuracy in a toy comparison.

  • Zeros in an inverse covariance matrix represent conditional independence between feature pairs in a Gaussian graphical model.
  • 10 high-dimensional maximum-likelihood estimation can fail because the empirical covariance is singular or highly variable, while estimated precision matrices remain dense.These issues arise when p exceeds or approaches n.
  • The graphical lasso adds an ℓ1 penalty to estimate sparse precision matrices, including when p ≫ n.With sufficiently large λ, some estimated precision-matrix elements become exactly zero.
  • Gene-expression observations may belong to distinct cancer and normal classes, making a single shared graphical model inappropriate because their networks may differ.
  • The joint graphical lasso jointly estimates multiple related class-specific graphical models using a penalized likelihood whose penalty encourages shared edge locations or values.
  • In a two-class toy example, joint graphical lasso estimates were more accurate than graphical-lasso estimates fitted separately to each class.Figure 1 compares true networks, separate graphical-lasso estimates, and joint graphical-lasso estimates.

2. The joint graphical lasso

The joint graphical lasso formulates estimation across multiple related data classes as a convex penalized likelihood problem. Fused and group penalties respectively encourage shared edge values or shared sparsity patterns while retaining class-specific precision matrices.

  • K class-specific data sets share p features, with independent, identically distributed centered Gaussian observations within each class.
  • Separate maximum-likelihood precision estimates can be unstable, dense, or undefined, motivating strength borrowing across related classes.The problems are especially acute when p is close to or exceeds the class-specific sample size.
  • JGL maximizes a penalized log likelihood over positive-definite class-specific precision matrices using a convex penalty that promotes sparsity and shared characteristics.
  • Fused graphical lasso: FGL applies ℓ1 penalties to off-diagonal elements and their cross-class differences, encouraging sparse estimates with similar edge values.Large λ1 promotes sparsity, while large λ2 can make corresponding elements identical across classes.
  • Group graphical lasso: GGL applies a group lasso across corresponding elements, encouraging zeros to occur in the same locations across precision matrices.GGL therefore enforces a weaker similarity than FGL, sharing sparsity patterns rather than edge values.

3. Algorithm for the joint graphical lasso problem

The joint graphical lasso is solved with an ADMM algorithm that separates positive-definite likelihood updates from penalty updates. For fused and group lasso penalties, the resulting subproblems admit simple, efficient updates, and the algorithm converges to the global optimum.

  • ADMM algorithm: ADMM rewrites the JGL problem with auxiliary variables and alternates updates for precision matrices, penalty variables, and dual variables.The reformulation enforces positive definiteness and equality between the auxiliary and precision-matrix variables.
  • ADMM algorithm: The algorithm initializes Θ^(k)=I, U^(k)=0, and Z^(k)=0, selects ρ>0, and iterates until convergence.
  • ADMM algorithm: The final precision-matrix estimates are JGL estimates and the algorithm is guaranteed to converge to the global optimum.The positive-definiteness constraint is naturally enforced during the Θ update.
  • Computational efficiency: When p is large, block-structure results can avoid eigen decompositions of p × p matrices and solve the JGL problem efficiently.The paper reports FGL estimation for almost 18,000 features in under two minutes.
  • Penalty updates: For generalized fused lasso and group lasso penalties, the penalty update is separable or reducible to simple thresholding operations.The fused-lasso special case can be solved in O(K log K) operations, while soft-thresholding handles the two-class update.

4. Faster computations for FGL and GGL

Theorems for fused and group graphical lasso identify when the solution is block diagonal. This permits exact blockwise optimization and can substantially reduce computation for high-dimensional problems, particularly with sufficiently large tuning parameters.

  • Blockwise optimization: The JGL problem can then be solved separately within each connected component, producing exactly the same solution as optimization over all features.
  • Computational gains: Blockwise eigendecompositions reduce computational complexity from O(p^3) to a sum of costs over smaller block dimensions.With block sizes p1,...,pR, eigendecompositions are performed on matrices of dimensions p1 × p1 through pR × pR.
  • Block-diagonal conditions: Theorems 1 and 2 give necessary and sufficient conditions for block-diagonal structure in the FGL and GGL optimization problems.
  • Block-diagonal conditions: The conditions allow a partition of features to be checked quickly for disconnected blocks in the resulting network estimates.The procedure constructs an adjacency matrix and identifies connected components.
  • Scope of the speedup: The speed improvements apply only when λ1 and λ2 are sufficiently large, although the authors argue such values are common for sparse high-dimensional network estimation.Large penalties are motivated by interpretability and the limited support for estimating Kp(p + 1)/2 parameters when n ≪ p.

5. Relationship to previous proposals

The FGL and GGL proposals extend joint graphical-model estimation beyond time-ordered settings and improve on a hierarchical group-lasso precursor through convexity, computational speed, separate tuning controls, and better treatment of similar edge values.

  • Related approaches: Time-varying network methods are not easily extended to classes that lack a natural ordering.
  • Guo et al. (2011): Guo et al. (2011) can be expressed as a hierarchical group-lasso instance that encourages shared sparsity across classes.
  • Guo et al. (2011): Unlike the proposed FGL and GGL methods, the Guo et al. (2011) penalty is nonconvex, so convergence to a wrong local maximum is possible.
  • Computational comparison: The nonconvex precursor cannot use the paper’s speed improvements and is described as too slow for very high-dimensional data.
  • Penalty comparison: FGL and GGL use separate controls for sparsity and network similarity, while the precursor uses one tuning parameter.FGL is also better suited when both edge values and network structure are expected to be similar.

6. Tuning parameter selection

The paper recommends selecting JGL tuning parameters with an approximate AIC and a grid search, while recognizing that practical interpretability and stability may require more deliberate model-size control.

  • AIC-based selection: An approximate AIC can select λ1 and λ2 by grid-searching for the pair that minimizes AIC(λ1, λ2).
  • AIC-based selection: Simulation results suggest that this criterion tends to select models with low Kullback–Leibler divergence from the true model.
  • Large-scale selection: When p is very large, the authors suggest a dense search over λ1 followed by a quick search over λ2 to reduce computational burden.
  • Practical considerations: For exploratory analysis, AIC, BIC, and cross-validation may select networks too large to remain useful.
  • Practical considerations: Practical model selection should consider interpretability, stability, and a low false discovery rate.

7. Simulation study

Simulations compare FGL and GGL with separate graphical lasso and related joint methods across tuning parameters, sample sizes, and dimensions. FGL often provides stronger differential-edge control, lower dKL, and substantially faster computation than Guo et al. (2011)’s method.

  • Simulation set-up: The study evaluates FGL and GGL against graphical lasso and Guo et al. (2011)’s method on simulated multi-class networks.The main three-class simulations use p = 500 features, n = 150 observations per class, and power-law subnetworks with shared and class-specific structure.
  • Simulation results: At many similarity-penalty settings, FGL dominates the competing methods for identifying true edges while controlling false edges.GGL performs as well as Guo et al. (2011)’s method at some settings, whereas the joint methods dominate separate graphical lasso fits.
  • Simulation results: FGL and GGL attain SSE values as low as Guo et al. (2011)’s method while estimating much larger networks.The convex penalties tend to overshrink edge values toward zero; the authors suggest refitting selected edges with smaller penalties when simultaneous selection and estimation are desired.
  • Simulation results: FGL yields fewer false-positive differential edges because it shrinks between-class edge differences to zero.GGL and Guo et al. (2011)’s method are not designed to shrink edge values toward each other and do not outperform graphical lasso on this measure.
  • Simulation results: At most λ2 values, FGL has the lowest dKL, while graphical lasso performs worst; FGL and GGL are much faster than Guo et al. (2011)’s method.Graphical lasso is fastest overall, but the computational gains for FGL and GGL arise from block-structure results; FGL is especially fast with two classes.
  • Simulation results: Increasing n from 50 to 200 substantially improves covariance estimation, while further increasing n to 500 yields only marginal dKL improvement.Edge-detection sensitivity improves slightly and FDR decreases dramatically across the sampled sample sizes; differential-edge detection remains harder, with FGL performing well.

8. Analysis of lung cancer microarray data

The authors apply FGL to lung-cancer and control airway gene-expression data to infer normal and tumor-specific dependency networks. The analysis identifies biologically coherent shared and tumor-specific subnetworks, including a large tumor-specific network linked to ribosome activity and cancer-related genes.

  • Data and preprocessing: FGL is applied to gene-expression measurements from 97 lung-cancer patients and 90 controls after filtering and within-class normalization.The data contain 22,283 microarray-derived measurements and are publicly available through Gene Expression Omnibus accession GDS2771.
  • Network structure: The inferred networks contain many shared two-gene subnetworks, several small subnetworks, and one large tumor-specific subnetwork.Figure 3 distinguishes common edges from tumor-specific and normal-specific edges across 17,772 genes; 278 genes have nonzero edges in at least one network.
  • Biological interpretation: Forty-five percent of edges connect multiple probes for the same gene, while many others connect genes with known biological relationships.Examples include TUBA1B–TUBA1C, HLA-B–HLA-G, and SERPINB3–SERPINB4, supporting the use of the inferred networks for generating biological hypotheses.
  • Biological interpretation: The normal network connects HBA2 and HBB probes, whereas those between-gene connections are absent in tumor cells.Within-gene probe connections are preserved in tumor cells, making the class-specific pattern a possible direction for future investigation.
  • Biological interpretation: A 104-node tumor-specific subnetwork covering 84 unique genes includes many ribosome-related genes and the RAS-family genes RAB1A and RAB11A.Its connections between ribosome activity and RAS-family genes may indicate a relationship relevant to an important subset of cancers.

9. Discussion

The discussion emphasizes the joint graphical lasso’s scalability, flexibility, and ability to borrow strength across related classes. It also identifies extensions and tuning choices that broaden its use.

  • The ADMM algorithm handles convex penalties, with explicit efficient solutions for fused lasso and group lasso variants.The authors report tractability on datasets exceeding 20,000 features and convergence in seconds for smaller 500-feature problems.
  • Class contributions can be weighted equally by omitting the n_k term, preventing the largest class from dominating network estimation.In the default formulation, each class’s contribution is weighted by its sample size.
  • FGL and GGL use two tuning parameters, allowing similarity and sparsity to be varied separately.This contrasts with a competing proposal whose single parameter controls both properties.
  • The method may extend to classification by shrinking multiple precision matrices toward each other between QDA and LDA.The discussion also mentions use in the maximization step of an unsupervised model, although the supplied passage is truncated.
  • An R package implementing FGL and GGL was planned for release on CRAN.

Appendix 1: Modifying JGL to work on the scale of partial correlations

The appendix describes extending fused and group lasso approaches from shared precision matrices to shared partial correlations. The construction uses estimated diagonal precision elements to rescale the penalty.

  • The extension targets shared partial correlations rather than shared precision matrices.The authors state that a similar extension can be made for GGL.
  • Partial correlations are related to precision-matrix entries through the diagonal precision elements.The supplied expression identifies ρ_ij as the true partial correlation and σ_ij as an entry of the true precision matrix.
  • The FGL algorithm can be modified to apply a generalized fused lasso penalty after rescaling by estimated diagonal precision elements.The estimates may be obtained by fitting the graphical lasso to all K datasets together, under shared diagonal elements.

Appendix 2: Proofs of Theorems 1 and 2

The appendix proves conditions governing solutions of the joint graphical lasso, including when variable groups are disconnected across all estimated networks. The proofs use KKT conditions and equivalent subgradient formulations.

  • The proofs begin by characterizing JGL solutions through necessary and sufficient Karush-Kuhn-Tucker conditions.
  • The proof concludes the two-class result via Lemma 9.1 and the general result via Lemma 9.2.The supplied text states that the necessary condition for K > 2 is simple and omitted.
  • For multiple classes, the appendix derives an equivalent condition using scalars a_ij,k to characterize complete disconnection between variable sets.The condition is stated as necessary and sufficient for variables in C1 and C2 to be disconnected in every resulting network estimate.

Appendix 3: Additional simulations for two-class datasets

Additional two-class simulations evaluate FGL and GGL on both disconnected-subnetwork and single-network power-law structures. Across these settings, the methods were superior to or competitive with the alternatives.

  • Two-class simulations used p = 500 features in ten equally sized unconnected power-law subnetworks, with 150 observations per class.Eight subnetworks shared structure and edge values, while two appeared in only one class; class 1 had 490 edges, 94 absent from class 2.
  • Figure 4 compares FGL, GGL, Guo et al. (2011)’s method, and graphical lasso on the disconnected-subnetwork simulations.
  • A separate simulation generated two 500-feature single-component power-law networks differing by a missing branch in class 2.Class 1 had 499 edges, 104 absent from class 2; results averaged 100 datasets with 150 observations per class.
  • Figure 5 compares the same four methods on the single-large-network simulations.The results were similar to the earlier simulations, with FGL and GGL superior to or competitive with the other methods.
  • The three-class simulation network encoded shared edges in black, class-1-and-2 edges in green, and class-1-only edges in red.
Loading 1111.0324v4…