Node-based learning of multiple Gaussian graphical models

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

TL;DR

This paper introduces a "node-based" approach to jointly estimating multiple Gaussian Graphical Models (GGMs), moving beyond traditional edge-by-edge comparisons. By using a novel Row-Column Overlap Norm (RCON), the authors can identify shared "hub" nodes or specific "perturbed" nodes that drive network differences, offering better interpretability and performance in high-dimensional settings like genomics.

What Problem Does This Paper Address?

In many fields, we need to understand the conditional dependencies between variables—for example, how genes regulate each other or how stocks move together. These are often modeled as Gaussian Graphical Models (GGMs), where nodes are variables and edges represent direct relationships.

The challenge arises when we have data from several related conditions (e.g., healthy vs. cancerous tissue). We expect these networks to be similar but not identical. Existing "edge-based" methods (like the Fused Graphical Lasso) encourage networks to share individual edges. However, biological and social systems often change at the node level: a single "hub" gene might control many others across all conditions, or a single mutation might "perturb" a node, changing all its connections at once. This paper fills the gap by providing a mathematical framework to capture these node-level patterns.

Methods

The authors propose two new formulations based on a convex optimization framework:

  1. CNJGL (Common Hub Node Joint Graphical Lasso): Encourages the networks to share the same "hub" nodes (nodes with many connections).
  2. PNJGL (Perturbed-Node Joint Graphical Lasso): Assumes that differences between networks are driven by a few specific nodes whose entire connectivity patterns change across conditions.

The "secret sauce" is the Row-Column Overlap Norm (RCON). This penalty function encourages a matrix to have a support that is the union of a few rows and columns. Because the precision matrix in a GGM is symmetric, penalizing a row automatically penalizes the corresponding column, effectively targeting all edges connected to a specific node.

To solve these complex problems, the authors use the Alternating Direction Method of Multipliers (ADMM). Crucially, they derive a set of necessary and sufficient conditions that allow them to decompose a massive problem into smaller, independent "blocks" based on the data's structure, leading to massive computational speedups.

Datasets

The researchers evaluated their approach using:

  • Synthetic Data: Networks generated with Erdos-Renyi, scale-free, and community structures to test the ability to recover true hubs and perturbations.
  • Brain Cancer (GBM) Gene Expression: mRNA levels of 11,861 genes from 220 patients, categorized into subtypes. They focused on the "TCR signaling" and "G2/M checkpoints" pathways.
  • University Webpage Data: A dataset of word occurrences on webpages from computer science departments (Student vs. Faculty pages), used to identify terms that change context depending on the user.

Key Insights and Ideas

  • Nodes over Edges: The core "aha moment" is that penalizing rows and columns of the precision matrix is a much more natural way to model system-wide changes than looking at edges in isolation.
  • The Power of RCON: The RCON is a clever convex relaxation that makes "node-seeking" optimization tractable. It effectively says, "I want the differences between these matrices to be concentrated in just a few rows/columns."
  • Decomposition for Scale: High-dimensional GGMs are notoriously slow to compute. The authors proved that if the sample covariance matrices show certain "disconnected" patterns, the global optimization problem can be perfectly solved by solving smaller sub-problems. This turns a potentially hours-long task into one taking seconds.

Key Results

  • Superior Recovery: In simulations, PNJGL and CNJGL consistently outperformed edge-based methods (FGL and GGL) in identifying perturbed nodes and hubs, especially when the sample size ($n$) was small relative to the number of variables ($p$).
  • Biological Validation: When applied to glioblastoma data, PNJGL correctly identified PTEN—a well-known tumor suppressor gene—as a "perturbed" node, meaning its regulatory behavior significantly differs between cancer subtypes.
  • Efficiency: The ADMM algorithm combined with the block-diagonal decomposition allowed the authors to handle hundreds of variables in seconds, whereas standard interior-point solvers took hours or failed to converge.

Limitations and Future Work

  • Convergence Theory: While ADMM is efficient, the standard convergence proofs usually apply to two blocks of variables. This paper uses more, and while it works well in practice, a rigorous theoretical guarantee for this specific multi-block setup remains an open research area.
  • Ultra-High Dimensions: While the decomposition helps, scaling to the full human genome (20,000+ genes) without pre-selecting pathways still presents a massive computational hurdle.
  • Parameter Tuning: Selecting the "right" amount of penalty ($\lambda_1, \lambda_2$) is still difficult in unsupervised settings. The authors suggest stability selection as a potential path forward.

Summary updated

Abstract

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.
BibTeX
@article{mohan2014node,
  author = {Karthik Mohan and Palma London and Maryam Fazel and Daniela M. Witten and Su-In Lee},
  title = {{Node-based learning of multiple Gaussian graphical models}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=Cj2YckkSdTi},
}

Loading related content...

Figure