The Multiple Quantile Graphical Model

Alnur Ali, J. Zico Kolter, Ryan J. TibshiraniNeurIPS 2016 · OpenReview

Introduction

Most traditional methods for learning the structure of sparse graphical models—identifying "who is connected to whom" in a dataset—rely on the Gaussian Graphical Model. Methods like the popular Graphical Lasso (GLasso) assume that if two variables are related, that relationship manifests in their conditional mean.

However, real-world data is rarely that well-behaved. It is often non-Gaussian (featuring heavy tails or skewness), heteroskedastic (variance changes depending on the value of another variable), and non-linear. In these cases, looking only at the mean is like trying to understand a landscape by only looking at the average elevation; you miss the peaks, valleys, and complex terrain.

The Multiple Quantile Graphical Model (MQGM) addresses this gap. By modeling a range of conditional quantiles instead of just the conditional mean, MQGM captures complex, non-linear dependencies that standard methods miss, while still providing theoretical guarantees for exact structure recovery in high-dimensional settings.

Methodology

The MQGM extends the "neighborhood selection" approach. Instead of performing a single sparse regression for each variable, it performs Multiple Quantile Regression.

  • Quantile Modeling: For every variable, the model estimates several quantiles (e.g., the 5th, 50th, and 95th percentiles) as a function of all other variables. This allows the model to detect "tail dependencies"—connections between variables that only appear during extreme events.
  • Additive Basis Expansion: To handle non-linearity, MQGM uses basis functions (like splines). This allows the model to capture complex, "curvy" relationships rather than just linear ones.
  • Sparsity and Smoothness: Similar to the Lasso, penalties are applied to ensure the resulting graph is sparse, identifying only the most important connections.
  • Non-crossing Constraints: To prevent "quantile crossing" (e.g., predicting a 90th percentile that is lower than the 10th), structural constraints are incorporated into the optimization.
  • Efficient Optimization: The authors developed a custom algorithm using the Alternating Direction Method of Multipliers (ADMM) to solve this complex optimization problem efficiently.

Because MQGM defines conditional distributions rather than a single joint distribution, the authors utilize Gibbs Sampling to draw samples from the implied joint distribution, allowing them to visualize the "learned" world. Furthermore, the paper provides theoretical proofs showing that MQGM can achieve exact structure recovery. Even if the number of variables is much larger than the number of samples, the model will correctly identify the edges of the graph with high probability.

Key Results

The authors evaluated MQGM on both synthetic benchmarks (Multivariate Normal, heavy-tailed Student-t, Autoregressive data) and real-world datasets. In terms of edge detection (Area Under the Curve), MQGM consistently outperformed or matched state-of-the-art methods, particularly excelling when the data was non-Gaussian.

The Ring Test

In a synthetic "Ring" experiment, variables were related by a circular, highly non-Gaussian constraint. MQGM was the only method among several baselines (including GLasso and SpaceJam) that correctly identified the dependency between the coordinates. Standard methods saw the "average" relationship as zero and failed to find the edge.

Comparison of MQGM and baseline methods on the synthetic Ring dataset.

Flu Epidemic Modeling

The authors also applied MQGM to US Flu Epidemic Data (weekly flu incidence reports from the CDC across 10 US regions). This data is naturally heteroskedastic and spatiotemporal. MQGM successfully identified "bellwether" regions (like Region 6) that act as early indicators for flu spread in other regions, and correctly captured how the previous week's data influences the current week.

MQGM applied to US Flu Epidemic data, highlighting regional dependencies and quantile predictions for Region 6.

Limitations and Future Work

While powerful, MQGM comes with trade-offs:

  • Computational Complexity: Despite the efficient ADMM algorithm, MQGM is computationally heavier than simpler methods like GLasso because it solves for multiple quantiles and uses basis expansions.
  • Hyperparameter Sensitivity: The model requires tuning multiple penalty parameters across different quantile levels, which can be time-consuming.
  • Joint Distribution Consistency: As with many pseudolikelihood methods, the set of conditional distributions might not strictly define a single, valid joint probability distribution. While Gibbs sampling provides a practical workaround, the theoretical implications of this inconsistency remain a known challenge.

Summary updated

Abstract

We introduce the Multiple Quantile Graphical Model (MQGM), which extends the neighborhood selection approach of Meinshausen and Buhlmann for learning sparse graphical models. The latter is defined by the basic subproblem of modeling the conditional mean of one variable as a sparse function of all others. Our approach models a set of conditional quantiles of one variable as a sparse function of all others, and hence offers a much richer, more expressive class of conditional distribution estimates. We establish that, under suitable regularity conditions, the MQGM identifies the exact conditional independencies with probability tending to one as the problem size grows, even outside of the usual homoskedastic Gaussian data model. We develop an efficient algorithm for fitting the MQGM using the alternating direction method of multipliers. We also describe a strategy for sampling from the joint distribution that underlies the MQGM estimate. Lastly, we present detailed experiments that demonstrate the flexibility and effectiveness of the MQGM in modeling hetereoskedastic non-Gaussian data.
BibTeX
@inproceedings{ali2016multiple,
  author = {Alnur Ali and J. Zico Kolter and Ryan J. Tibshirani},
  title = {{The Multiple Quantile Graphical Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=BJV4CPbdWB},
}
Figure