Node-Based Learning of Multiple Gaussian Graphical Models

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

Abstract

This paper presents a novel framework for the joint estimation of multiple Gaussian Graphical Models (GGMs) that share a common set of variables across different conditions. Unlike traditional methods that focus on edge-level similarities, we propose a node-based approach to capture structured differences and similarities. We introduce two formulations: one assuming differences are driven by specific perturbed nodes, and another assuming similarities are due to shared hub nodes. Using the Row-Column Overlap Norm (RCON), we develop convex optimization problems solved via an efficient ADMM algorithm. Our approach demonstrates superior performance in high-dimensional biological and social network data.

Introduction

Gaussian Graphical Models (GGMs) are a powerful tool for representing conditional dependencies between variables. In many real-world applications, such as genomics or finance, data is collected under multiple related conditions (e.g., different disease states or market regimes). While these conditions often share a significant portion of their underlying network structure, they also exhibit critical differences.

Traditional joint estimation methods, such as the Fused Graphical Lasso (FGL), typically encourage networks to share individual edges. However, in many biological systems, changes often occur at the node level—for instance, a single gene mutation might alter all its regulatory connections simultaneously. This paper addresses this gap by shifting the focus from edges to nodes.

Methods: A Node-Based Approach

The authors propose two primary models:

  1. Common Hub Node Joint Graphical Lasso (CNJGL): This model assumes that the networks share the same "hub" nodes—variables that are highly connected across all conditions.
  2. Perturbed-Node Joint Graphical Lasso (PNJGL): This model assumes that the differences between networks are driven by a few "perturbed" nodes, whose entire connectivity profiles change between conditions.

The mathematical foundation for these models is the Row-Column Overlap Norm (RCON). In a GGM, the precision matrix (the inverse of the covariance matrix) represents the network structure. A zero entry in the precision matrix indicates conditional independence between two variables. By penalizing the rows and columns of the precision matrix, the RCON encourages the estimated network to have a support that is the union of a few rows and columns.

Illustration of node-based structures in Gaussian Graphical Models. Figure 3 shows how specific nodes (hubs or perturbed) correspond to row-column patterns in the precision matrix.

As shown in Figure 3, the RCON allows the optimization process to "select" specific nodes. For example, in panel (a), node $X_2$ is identified as a hub, which corresponds to the shading of the second row and column in the precision matrix. This symmetry is crucial: because the precision matrix is symmetric, targeting a row automatically targets the corresponding column, effectively capturing all edges connected to that node.

Joint Learning Across Conditions

When estimating multiple networks simultaneously, the goal is to leverage shared information while allowing for flexibility.

Comparison of two related networks sharing a common hub node. Figure 5 demonstrates the core concept of joint learning where networks share structural features like hub nodes while allowing for differences.

Figure 5 illustrates this concept. In this example, two networks (a) and (b) share a common hub node, $X_2$. While the connections of $X_2$ are identical in both conditions, other parts of the network (such as the edge between $X_1$ and $X_5$ in (a) versus $X_3$ and $X_4$ in (b)) are allowed to vary. This node-centric view provides a more intuitive and biologically plausible interpretation of network evolution than edge-based methods.

Computational Efficiency via ADMM

Solving these convex optimization problems in high dimensions is computationally demanding. The authors employ the Alternating Direction Method of Multipliers (ADMM) to handle the RCON penalty. A key contribution of this work is the derivation of necessary and sufficient conditions that allow the global problem to be decomposed into smaller, independent subproblems. This block-diagonal decomposition enables the algorithm to scale to hundreds or thousands of variables, reducing computation time from hours to seconds.

Key Results and Validation

The proposed methods were tested on synthetic data, university webpage word occurrences, and glioblastoma (brain cancer) gene expression data.

  • Superior Recovery: In simulations, PNJGL and CNJGL consistently outperformed edge-based methods in identifying perturbed nodes and hubs, especially when the sample size was small relative to the number of variables.
  • Biological Validation: In the glioblastoma dataset, the PNJGL model identified the PTEN gene as a major perturbed node across cancer subtypes. PTEN is a well-known tumor suppressor, and its identification validates the model's ability to pinpoint biologically significant "master regulators."
  • Efficiency: The ADMM algorithm combined with the block-diagonal decomposition allowed the authors to handle hundreds of variables in seconds, whereas standard solvers took hours.

Conclusion

By prioritizing nodes over edges, this research provides a more robust and interpretable framework for analyzing heterogeneous datasets. The use of the RCON penalty combined with efficient ADMM solvers makes this approach a practical choice for high-dimensional network analysis in genomics and beyond. Future work will focus on theoretical convergence guarantees for multi-block ADMM and further scaling to genome-wide datasets.

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},
}
Figure