Fast and Scalable Learning of Sparse Changes in High-Dimensional Graphical Model Structure

Abstract

We focus on the problem of estimating the change in the dependency structures of two p-dimensional Gaussian Graphical models (GGMs). Previous studies for sparse change estimation in GGMs involve expensive and difficult non-smooth optimization. We propose a novel method, DIFFEE for estimating DIFFerential networks via an Elementary Estimator under a high-dimensional situation. DIFFEE is solved through a faster and closed-form solution that enables it to work in large-scale settings. Notice that GGM assumes data are generated from a Gaussian distribution. However, the Gaussian assumption is too strict and can not be satisfied with all the real-world data generated from a complex process. Therefore, we further extend DIFFEE to NPN-DIFFEE by assuming that data are drawn from the nonparanormal distribution (a large family of distributions) instead of a multivariate Gaussian distribution. Thus, NPN-DIFFEE is applicable to more general conditions. We conduct a rigorous statistical analysis showing that surprisingly DIFFEE achieves the same asymptotic convergence rates as the state-of-the-art estimators that are much more difficult to compute. Our experimental results on multiple synthetic datasets and one real-world data about brain connectivity show strong performance improvements over baselines, as well as significant computational benefits.

Jiaqi Zhang

PhD Student at Computer Science

My research interests include machine learning and bioinformatics.