An Expectation Conditional Maximization approach for Gaussian graphical models

Zehang Li, Tyler H. McCormick

This paper presents a new way to map out the complex web of dependencies between variables in high-dimensional datasets. By combining the strengths of Bayesian "spike-and-slab" priors with the speed of deterministic optimization, the authors provide a tool that is both more accurate than standard frequentist methods and significantly faster than traditional Bayesian approaches.

TL;DR

The authors introduce EMGS (EM Graph Selection), a deterministic algorithm that uses an Expectation Conditional Maximization (ECM) approach to estimate sparse Gaussian graphical models. It provides the accuracy and flexibility of Bayesian "spike-and-slab" priors—including the ability to incorporate prior knowledge—without the massive computational burden of MCMC sampling.

What Problem Does This Paper Address?

In modern data science, we often want to understand the "conditional independence" between variables—for example, does a specific symptom directly indicate a disease, or is it just a byproduct of another symptom? We represent these relationships using graphical models, where variables are nodes and their relationships are edges. Mathematically, this involves estimating a precision matrix (the inverse of the covariance matrix), where a zero entry means two variables are independent given all others.

However, two major hurdles exist:

  1. High Dimensionality: When the number of variables ($p$) is much larger than the number of observations ($n$), standard statistical methods fail.
  2. The Bias-Speed Tradeoff: Frequentist methods like the Graphical Lasso (GLasso) are fast but use a "one-size-fits-all" penalty that often shrinks real signals too much (high bias). Bayesian methods are more flexible and handle prior information well, but they usually rely on Markov Chain Monte Carlo (MCMC), which is agonizingly slow for large datasets.

Methods

The core innovation is EMGS, which treats the problem as a missing data task.

  • Spike-and-Slab Prior: The model assumes every potential edge in the graph comes from a mixture of two distributions: a narrow "spike" centered at zero (representing no connection) and a wide "slab" (representing a real connection).
  • The ECM Algorithm: Instead of sampling the whole distribution (MCMC), the authors use a deterministic Expectation-Maximization approach to find the "most likely" graph (the posterior mode).
  • E-step: Calculates the probability that each potential edge belongs to the "slab" versus the "spike."
    • CM-step: Updates the precision matrix. Crucially, this step uses an adaptive ridge penalty. Unlike GLasso, which penalizes all edges equally, EMGS learns to apply smaller penalties to large, certain signals and larger penalties to noise.
  • Copula Extension: The authors extend the model to non-Gaussian data (like binary or ordinal data) using a "latent Gaussian" framework and a stochastic version of the algorithm (SAEM).
  • Structured Priors: The algorithm can incorporate "block-wise" information, allowing researchers to tell the model that certain groups of variables (e.g., symptoms related to the same organ system) are more likely to be connected.

Datasets

The authors evaluated EMGS using:

  • Simulated Data: Various graph structures including AR(1), AR(2), random graphs, and clustered graphs to test accuracy and bias.
  • Seattle Traffic Data: Hourly bike and pedestrian counts from the Burke Gilman Trail (96 variables). This tested the model's ability to learn temporal patterns and predict missing values.
  • Verbal Autopsy (VA) Surveys: A dataset of 7,841 records containing binary indicators of symptoms leading to death. This tested the "copula" version of the model on messy, real-world categorical data with high missingness.

Key Insights and Ideas

  • Adaptive Penalization is Key: The "aha moment" is that by using the EM framework, the algorithm naturally creates an adaptive penalty. This allows it to identify true edges quickly while keeping the estimates of those edges nearly unbiased—a feat GLasso struggles with.
  • Natural Handling of Missing Data: Because it is an EM-based algorithm, handling missing values is "baked in." During the E-step, the model simply estimates the missing values based on the current state of the graph.
  • Prior Knowledge Matters: The "Structured Prior" results show that if you know variables belong to certain groups, you can significantly reduce "false positive" edges between unrelated groups, leading to a much cleaner and more interpretable graph.

Key Results

  • Lower Bias: In simulations, EMGS consistently showed lower bias (measured by the Frobenius norm) compared to GLasso and other popular selectors like RIC and StARS.
  • Better Discovery: EMGS achieved higher Area Under the Curve (AUC) for graph recovery, meaning it was better at distinguishing real edges from noise.
  • Superior Prediction: On the Seattle traffic data, EMGS outperformed GLasso in predicting missing values, achieving a Mean Squared Error (MSE) of 0.28 compared to GLasso’s 0.42.
  • Real-World Discovery: On the VA symptom data, the model successfully clustered related symptoms (e.g., pregnancy-related symptoms, or the link between stroke and paralysis) even when data was sparse.

Limitations and Future Work

  • Point Estimates vs. Uncertainty: Because EMGS is deterministic, it provides a single "best" graph but doesn't automatically provide the "uncertainty" or confidence intervals that a full Bayesian MCMC would.
  • Local Optima: Like all EM algorithms, EMGS can get stuck in "local modes" depending on where it starts. The authors used GLasso to initialize the algorithm, but they note that better initialization heuristics could be explored.
  • Multimodality: The "spike-and-slab" landscape is often bumpy with many peaks. The authors suggest that future versions could incorporate "perturbations" to help the algorithm explore multiple possible graph structures.

Summary updated

Abstract

Bayesian graphical models are a useful tool for understanding dependence relationships among many variables, particularly in situations with external prior information. In high-dimensional settings, the space of possible graphs becomes enormous, rendering even state-of-the-art Bayesian stochastic search computationally infeasible. We propose a deterministic alternative to estimate Gaussian and Gaussian copula graphical models using an Expectation Conditional Maximization (ECM) algorithm, extending the EM approach from Bayesian variable selection to graphical model estimation. We show that the ECM approach enables fast posterior exploration under a sequence of mixture priors, and can incorporate multiple sources of information.
BibTeX
@article{li2019expectation,
  author = {Zehang Li and Tyler H. McCormick},
  title = {{An Expectation Conditional Maximization approach for Gaussian graphical models}},
  journal = {Journal of Computational and Graphical Statistics},
  year = {2019},
  doi = {10.1080/10618600.2019.1609976},
}
Figure