This is an accompanying webpage to the paper:

Pathway Graphical Lasso

Maxim Grechkin, Maryam Fazel, Daniela Witten, Su-In Lee

Abstract
Structure learning of Gaussian graphical models (GGMs) from data has provided a powerful way to reveal dependencies among variables. Many approaches attempted to learn the GGM structure by obtaining a sparse estimate of the inverse covariance matrix via l_1 regularization, a method called the graphical lasso. Despite the pressing need, most algorithms for solving the graphical lasso problem do not scale to a very large number of variables. Furthermore, the learned network structure is hard to interpret. To resolve these challenges, we propose a novel GGM structure learning method that exploits the fact that for many real-world problems we have prior knowledge on the edges that are unlikely to exist. For example, in gene regulatory networks, a pair of genes that does not co-exist in the any of the putative functional units, typically referred to as pathways, is less likely to be connected. In computer vision applications in which each variable corresponds to a pixel, each variable is likely to be connected with the nearby variables. In this paper, we propose a method, called pathway graphical lasso, that learns the structure of GGMs with the pathway-based constraints. Our novel learning algorithm employs a message-passing algorithm after decomposing the network structure into smaller parts. It shows orders of magnitude improvement in run time compared to the state-of-the-art optimization methods for the graphical lasso problem when they were modified and applied to the problem with pathway-based constraints.