PaperlayerView exact revision on arXiv

Source-linked AI summary

Node-Based Learning of Multiple Gaussian Graphical Models

Karthik Mohan, Palma London, Maryam Fazel, Daniela Witten, Su-In Lee

arXiv:1303.5145v4stat.MLcs.LGmath.OC

TL;DR

The paper tackles high-dimensional estimation of multiple GGMs for shared variables observed under distinct conditions, where networks have common structure but structured differences. It replaces edge-based assumptions with node-based models for perturbed nodes or common hubs, using convex RCON-penalized formulations solved by ADMM. The proposed methods exploit these structures and outperform comparable edge-based methods in the reported synthetic experiments, especially with fewer samples, while their computational theory has stated limitations.

  • Problem

    Estimating multiple GGMs jointly requires preserving condition-specific differences while exploiting substantial commonality across networks.

  • Method

    The paper proposes PNJGL and CNJGL, convex node-based formulations using an RCON penalty and ADMM to estimate perturbed-node and common-hub network structures.

  • Results

    PNJGL and CNJGL outperform edge-based comparators in the reported synthetic results, with larger advantages when sample sizes are smallest.

  • Takeaways & Limitations

    Node-based modeling links estimated network similarities and differences to interpretable connectivity patterns of shared, disrupted, or hub nodes.

  • Takeaways & Limitations

    The ADMM convergence theory for more than two variable groups does not cover the assumptions of CNJGL and PNJGL, and necessary and sufficient speed-up conditions have a gap.

Abstract

from arXiv · show

We consider the problem of estimating high-dimensional Gaussian graphical models corresponding to a single set of variables under several distinct conditions. This problem is motivated by the task of recovering transcriptional regulatory networks on the basis of gene expression data {containing heterogeneous samples, such as different disease states, multiple species, or different developmental stages}. We assume that most aspects of the conditional dependence networks are shared, but that there are some structured differences between them. Rather than assuming that similarities and differences between networks are driven by individual edges, we take a node-based approach, which in many cases provides a more intuitive interpretation of the network differences. We consider estimation under two distinct assumptions: (1) differences between the K networks are due to individual nodes that are perturbed across conditions, or (2) similarities among the K networks are due to the presence of common hub nodes that are shared across all K networks. Using a row-column overlap norm penalty function, we formulate two convex optimization problems that correspond to these two assumptions. We solve these problems using an alternating direction method of multipliers algorithm, and we derive a set of necessary and sufficient conditions that allows us to decompose the problem into independent subproblems so that our algorithm can be scaled to high-dimensional settings. Our proposal is illustrated on synthetic data, a webpage data set, and a brain cancer gene expression data set.

1. Introduction

The paper addresses joint estimation of multiple GGMs that share structure but differ across conditions, using a node-based rather than edge-based perspective. It proposes convex methods for perturbed nodes and shared hub nodes, with an RCON penalty and scalable ADMM algorithms.

  • Motivation: Jointly estimating condition-specific GGMs can preserve differences while exploiting shared structure, unlike fitting one pooled or entirely separate network.A pooled network can overlook cancer-versus-normal differences, whereas separate networks fail to exploit common pathways.
  • Node-based perspective: The paper models similarities and differences through nodes whose connectivity patterns are shared or disrupted across networks, rather than through individual edges.This node-based formulation is intended to provide a more intuitive interpretation of network differences.
  • Common hub nodes: CNJGL estimates networks sharing common hub nodes, such as a transcription factor that regulates many downstream genes across conditions.The motivating example uses X2 as a hub in both networks.
  • Perturbed nodes: PNJGL estimates networks whose differences arise from perturbed nodes with altered connectivity patterns across conditions.The paper illustrates this setting with X2 perturbed between two networks, potentially representing a mutated gene.
  • Optimization and computation: The row-column overlap norm encourages supports formed by unions of rows and columns, while convex formulations and ADMM provide the computational framework.The paper also derives conditions under which the optimization decomposes into independent subproblems for high-dimensional scaling.

2. Background on High-Dimensional GGM Estimation

High-dimensional GGM estimation recovers conditional-dependence structure from inverse covariance matrices, but singular empirical covariance makes this difficult when features outnumber observations. Existing joint methods borrow strength across conditions, while this paper extends the comparison with a node-based formulation.

  • High-dimensional GGM estimation: A Gaussian graphical model encodes conditional dependence through the sparsity pattern of the inverse covariance matrix, with zero entries indicating conditional independence.When p > n, estimating the inverse covariance accurately is challenging because the empirical covariance matrix is singular.
  • Graphical lasso: The graphical lasso uses a convex ℓ1-penalized optimization to obtain a positive-definite, sparse estimate of the inverse covariance matrix.The estimate is positive definite for λ > 0 and becomes sparse when λ is sufficiently large.
  • Joint estimation: Joint graphical-lasso methods estimate networks for K conditions while allowing structured similarities and differences across the same features.The reviewed convex formulation uses a Gaussian likelihood with penalties applied to edges or differences between network edges.
  • Edge-based joint methods: FGL encourages identical edge values, whereas GGL encourages a shared sparsity pattern; both borrow strength across observations and can improve inference over separate estimation.These methods nevertheless remain edge-based, unlike the paper’s node-based formulation.

3. Node-Based Joint Graphical Lasso

This section develops node-based joint estimation of multiple GGMs by addressing failures of naive overlapping-group penalties and introducing the row-column overlap norm. It then formulates two convex approaches: PNJGL for perturbed nodes and CNJGL for common hub nodes.

  • Why is Node-Based Learning Challenging?: Naive group-lasso penalties fail to detect node perturbations because overlapping row and column groups produce supports corresponding to intersections rather than unions.The same overlap problem also makes naive co-hub detection challenging.
  • Row-Column Overlap Norm: The row-column overlap norm is designed to produce supports formed by the union of selected rows and columns, matching node-based sparsity patterns.It decomposes symmetric matrices into row and column components and applies an ℓ1/ℓq norm across concatenated columns.
  • Row-Column Overlap Norm: For q = 2 or q = ∞, RCON yields sparse estimates whose nonzero entries form selected rows plus selected columns, whereas q = 1 yields unstructured sparsity.The q = 1 case reduces to an ℓ1 penalty on matrix entries.
  • Node-Based Approaches for Learning GGMs: The section presents two complementary node-based approaches: one for perturbed nodes and one for co-hub nodes shared across networks.These approaches are formulated as convex optimization problems.
  • Node-Based Approaches for Learning GGMs: PNJGL encourages network differences to be attributable to perturbed nodes by applying RCON to differences among precision matrices.With q = 2 or q = ∞, its estimated support is encouraged to be a union of rows and corresponding columns.
  • Node-Based Approaches for Learning GGMs: CNJGL encourages the K networks to share common hub nodes by promoting a common node support rather than a common edge support.When λ2 > 0, shared structure is encouraged across the network estimates.

4. Algorithms

The paper develops ADMM algorithms for PNJGL and CNJGL because their overlap-based penalties make standard first-order methods difficult, then evaluates computational scaling and convergence limitations.

  • Motivation and approach: ADMM is used to solve PNJGL and CNJGL because projected subgradient and proximal-gradient methods are difficult with the RCON penalty.The RCON penalty requires non-trivial subgradient computation, and its combination with the ℓ1 norm lacks a closed-form proximal operator.
  • ADMM formulation: The algorithms decouple difficult objective terms by introducing auxiliary primal and dual variables and iteratively updating them until convergence.The formulations introduce variables such as Y, V, W, and Z to separate terms, while dual variables enforce the resulting constraints.
  • Algorithmic components: The PNJGL and CNJGL ADMM procedures use matrix decompositions and proximal operators, with Tq corresponding to the ℓ1/ℓq norm for q = 1,2,∞.The Tq operator has a simple form for these three values of q.
  • Numerical issues and run-time: O(p^3) per-iteration complexity contrasts with O(p^6) for general interior-point methods, and at p = 30 PNJGL took 0.58 seconds versus 7 minutes for the interior-point method.The O(p^3) cost is attributed to computing the SVD; the reported timing comparison was run on an Intel Xeon X3430 2.4Ghz CPU.
  • Numerical issues and run-time: ADMM solutions have average error on the order of 10^-4 relative to cvx solutions, indicating good empirical accuracy in recovering the optimal solution.The comparison uses solutions obtained by ADMM and cvx for the estimated precision matrices.
  • Numerical issues and run-time: As p increases from 100 to 500, run-times increase substantially but remain below several minutes; small λ1 favors CNJGL iterations but burdens PNJGL iterations.The different iteration behavior is attributed to identity initialization: it is poor for PNJGL at small λ1 but good for CNJGL because λ2 still induces sparsity.
  • Convergence: Convergence theory is not straightforward for these ADMM algorithms because they use more than two primal-variable groups, and general conditions remain future work.Existing convergence results require assumptions that do not hold for CNJGL and PNJGL, although modified multi-group ADMM methods provide some guarantees.

5. Algorithm-Independent Computational Speed-Ups

The paper derives conditions under which PNJGL and CNJGL estimates become block-diagonal, enabling their optimization problems to split into independent subproblems. These conditions support substantial computational speed-ups for high-dimensional settings.

  • Block-diagonal decomposition: Necessary and sufficient conditions characterize when PNJGL and CNJGL precision estimates share a block-diagonal structure.The conditions depend on sample covariance matrices and regularization parameters; sufficient conditions apply to a broader class of regularizers.
  • Condition tightness: When q = 1 and K = 2, the PNJGL necessary conditions are also sufficient, whereas a gap remains for q > 1 and λ2 > 0.For λ2 = 0, the conditions reduce to graphical-lasso results.
  • Block-diagonal decomposition: The sufficient conditions can be checked in O(p^2) operations by testing whether a constructed matrix is block-diagonal up to permutation.The resulting feature partition identifies independent blocks for subsequent optimization.

6. Simulation Study

The simulation study evaluates PNJGL and CNJGL on synthetic networks containing perturbed and common hub nodes. Across network structures, the proposed node-based methods outperform their edge-based counterparts, especially with fewer samples.

  • Design: Synthetic networks contain common nodes, two perturbed nodes, and two co-hub nodes across Erdos-Renyi, scale-free, and community settings.Performance is assessed through support recovery, node detection, and Frobenius error metrics.
  • Perturbed-node networks: PNJGL outperforms FGL and GL for suitable λ2 values by identifying more true positives, detecting more perturbed nodes, and reducing Frobenius error.Its relative advantage is greatest at the smallest sample sizes.
  • Common-hub networks: CNJGL outperforms GGL and GL for suitable λ2 values, with a larger margin when the number of samples is smallest.CNJGL performs best in this setting because it exploits the presence of common hub nodes.
  • Regularization behavior: Large λ2 in CNJGL necessarily induces sparse network estimates, preventing dense estimates even when λ1 is small or zero.This behavior differs from PNJGL, whose sparsity is induced only by λ1.
  • Additional network structures: Across scale-free and community simulations with n = 50, PNJGL and CNJGL substantially outperform the edge-based approaches on the three evaluation metrics.The reported metrics cover support recovery, node detection, and estimation error.

7. Real Data Analysis

The paper applies PNJGL and CNJGL to glioblastoma gene-expression and university-webpage data. The analyses identify condition-specific connectivity patterns and several regulator or perturbed-node candidates.

  • Data sets: The real-data analyses use gene-expression and university-webpage data to evaluate PNJGL and CNJGL.The GBM data include 11,861 genes across 220 tissue samples, while the webpage data contain 544 student and 374 faculty webpages.
  • Webpage analysis: For webpage data, PNJGL and FGL achieve comparable log-likelihood values, but PNJGL outperforms FGL at a fixed number of non-zero edges.The comparison uses five-fold cross-validation of log-likelihood.
  • GBM gene-expression analysis: In the GBM G2/M-checkpoints analysis, CNJGL identifies four regulator genes: CDC6, MCM6, CCNB1, and CCNB2.The pathway contains 38 genes, including 15 previously identified regulators.
  • Webpage analysis: A selected PNJGL solution identifies advisor, high, construct, email, applic, fax, and receiv as perturbed webpage nodes.The solution uses λ1 = 27 and λ2 = 381 and overlays student and faculty precision matrices.

8. Discussion

The paper develops node-based learning for multiple GGMs through two convex formulations and discusses extensions, computational decomposition, limitations, and implementation resources.

  • The paper proposes perturbed-node and cohub-node joint graphical lasso formulations for node-based learning of multiple GGMs.
  • The row-column overlap norm encourages supports expressible as unions of a few rows and columns, while ADMM solves the resulting convex problems.
  • Necessary and sufficient regularization conditions can make the optimization problems block diagonal up to row-column permutation, enabling independent subproblems.
  • Future work includes generalizing the RCON penalty to other structured sparsity patterns, such as jointly activated or perturbed gene pathways.
  • The authors identify open issues involving tuning-parameter selection, ADMM convergence and practical performance, scalability, and a gap between decomposition conditions.
  • Adaptive or iteratively reweighted penalties may improve the PNJGL and CNJGL proposals, and Matlab implementations are available online.

Appendix B. Proof of Theorem 4

Appendix B derives optimality conditions for PNJGL and uses symmetry, subgradient bounds, and support restrictions in the proof of Theorem 4.

  • The PNJGL optimality conditions combine ℓ1-norm subgradients with a subgradient of the overlap penalty on Θ1 − Θ2.
  • Symmetric solutions imply that their inverse matrices share the same support, allowing the proof to restrict attention to a common support set T.
  • Summing the optimality equations and applying the derived inequalities establishes the theorem’s stated conclusion.
  • The proof bounds subgradient terms using elementwise ℓ∞ control, Hölder’s inequality, and the maximal absolute entries of matrices.

Appendix C. Proof of Theorem 7

Appendix C proves Theorem 7 for CNJGL using symmetric subgradients, support restrictions, norm bounds, and the sufficient condition for decomposition.

  • CNJGL optimality conditions use ℓ1 subgradients and a K-tuple subgradient of the overlap penalty applied to off-diagonal precision matrices.
  • The proof may assume symmetric subgradients because symmetrizing them preserves the subgradient property established by Lemma 11.
  • Assuming all solution matrices and their inverses are supported on T permits the argument to control terms outside T.
  • Triangle-inequality and subgradient bounds control the ℓ1 contributions, while Lemma 11 bounds the overlap-penalty contributions by column norms.
  • Combining the intermediate inequalities with the sufficient condition proves the theorem.

Appendix E. Connection Between RCON and Obozinski et al. (2011)

Appendix E connects the RCON penalty to the overlap norm by representing symmetric matrices through overlapping row-column groups and triangular decomposition.

  • For K = 1 and q = 2, the RCON penalty is derived from the overlap norm of Obozinski et al. (2011).
  • A symmetric matrix Θ is represented as Θ△ + Θ△T, where Θ△ is upper triangular with half diagonal entries.
  • The construction defines p overlapping groups, with each matrix element for k ≤ l belonging to both the kth and lth groups.
  • The overlap norm is rewritten using matrices supported on these groups and Frobenius norms corresponding to column ℓ2 norms.
  • The resulting RCON penalty accommodates row and column groups of a symmetric matrix in an elegant and convenient form.

Appendix F. Derivation of Updates for ADMM Algorithms

The appendix derives ADMM updates for the PNJGL and CNJGL convex formulations. It updates primal variables with the others fixed, applies dual ascent, and notes coupling or omitted derivations where relevant.

  • ADMM update derivations: The PNJGL and CNJGL formulations are addressed through augmented-Lagrangian ADMM update derivations.The appendix introduces augmented Lagrangians for both formulations and derives their primal-variable updates.
  • ADMM update derivations: Each ADMM iteration updates one primal variable while holding the others fixed, then updates dual variables using dual ascent.
  • PNJGL updates: The PNJGL derivation uses the Expand operator, soft-thresholding, and soft-scaling operators for specific variable updates.The text explicitly references these operators while deriving updates for Θ2, Z2, and related variables.
  • Derivation scope: Some updates are omitted when they are easy to derive or closely parallel previously presented derivations.The update for W is skipped, while other CNJGL updates follow the PNJGL treatment.
  • CNJGL updates: For CNJGL, the updates for ˜V 1 through ˜V K are coupled and therefore derived simultaneously.Other CNJGL primal-variable updates are described as similar to the PNJGL derivations and are omitted.

Appendix G. Additional Simulation Results

Additional simulation results for n = 25 show that PNJGL identifies the two perturbed nodes, with related metrics exhibiting similar behavior. The displayed results are robust to the tuning-parameter choices used for evaluation.

  • Perturbed-node identification: The two perturbed nodes in the n = 25 simulation are identified as perturbed by PNJGL.
  • Metric behavior: PPC is relatively insensitive to the threshold ts because perturbed and non-perturbed columns have a large gap in their norms.Similar results apply to TPPC, PCC, and TPCC.
  • Robustness: The Figure 16 results were robust to the choice of tuning parameter despite using values selected for best node identification.
Loading 1303.5145v4…