Sparse Causal Discovery in Multivariate Time Series

Stefan Haufe, Klaus-Robert Müller, Guido Nolte, Nicole KrämerNeurIPS 2010 · OpenReview

Introduction

In fields ranging from neuroscience to economics, understanding whether one time series (e.g., activity in a specific brain region) "causes" changes in another is a fundamental challenge. The gold standard for this has long been Granger Causality, which posits that variable $A$ causes variable $B$ if the past of $A$ helps predict the future of $B$ better than $B$’s past alone.

However, applying traditional pairwise Granger Causality to multivariate systems often yields "spurious" links—false positives driven by unobserved third-party variables. While Vector Autoregressive (VAR) models can evaluate all variables simultaneously to mitigate this, they typically produce "dense" causal graphs where everything appears connected. Standard sparsity techniques like the Lasso ($L_1$ regularization) attempt to prune these connections but are "blind" to the temporal structure of the data. For instance, standard Lasso might retain a causal link at a 2-ms lag but discard it at a 1-ms lag, which is physically counterintuitive.

This paper introduces a more robust approach to mapping causal relationships by applying Group Lasso regularization to VAR models, treating all time-lagged coefficients between two variables as a single cohesive group.

Methodology

To enforce a more logical and structurally sound sparsity, the authors propose two novel approaches:

  1. Group Lasso ($\ell_{1,2}$-norm): Instead of penalizing individual coefficients independently, this method groups all coefficients representing the interaction between variable $i$ and variable $j$ across all time lags ($P$). The penalty forces the entire "block" of lags to either be zero (indicating no causality) or non-zero (indicating a causal link). This aligns with the intuitive prior that if $A$ causes $B$, the influence likely persists across multiple time steps. The optimization is solved using Second-order Cone Programming (SOCP) combined with an efficient "active set" solver.
  2. Ridge Regression + Multiple Testing: As a frequentist alternative, Ridge Regression is used to stabilize the VAR model. The authors then apply a sophisticated multiple statistical testing procedure to derive $p$-values for each coefficient, allowing them to explicitly prune non-significant links.

Experimental Setup

Because "ground truth" causal relationships are rarely known in real-world data (like fMRI scans or stock market fluctuations), the authors validated their methods using simulated multivariate time series.

The simulations featured $M=7$ time series over $T=1000$ time points, with a VAR order of $P=5$. Exactly 10 true causal interactions were randomly assigned. The models were tested under three conditions:

  • No Noise: A pure VAR process.
  • White Noise: Uncorrelated Gaussian noise added to the sensors.
  • Mixed Noise: A challenging scenario where the noise is a mixture of independent autoregressive processes, mimicking complex background interference.

Key Findings

By baking "parsimony" into the math, the proposed models become highly resistant to the noise of spurious correlations. Performance was measured using the Area Under the ROC Curve (AUC), where 1.0 indicates perfect recovery of the causal graph.

  • Superior Accuracy: Both the Group Lasso and Ridge+Testing approaches consistently outperformed standard Lasso and traditional Granger Causality.
  • Noise Resilience: In the "White Noise" scenario, Group Lasso achieved an impressive AUC of 0.971, significantly beating traditional Granger Causality (0.910). In perfectly clean data, the Ridge+Testing approach achieved a near-perfect AUC of 1.000.
  • Cleaner Causal Maps: Group Lasso produced less "dense" and more interpretable causal maps compared to standard Lasso.
Estimated causal graph using standard LASSO regularization
Estimated causal graph using Ridge regression
  • Robustness to Model Order: The methods performed well even when the true "lag" of the system was unknown (e.g., setting $P=10$ when the ground truth was $P=5$), proving robust to model over-specification.

Limitations and Future Directions

While highly effective, the Group Lasso approach relies on SOCP, which is computationally heavier than the simple coordinate descent used for standard Lasso. For massive systems, the authors suggest splitting the optimization into $M$ independent subproblems. Additionally, the VAR model inherently assumes linear interactions; highly non-linear causal dynamics might require different techniques.

Moving forward, the authors plan to transition from simulated data to real-world applications, specifically targeting the estimation of cerebral information flow in functional MRI (fMRI) datasets.

Summary updated

Abstract

Our goal is to estimate causal interactions in multivariate time series. Using vector autoregressive (VAR) models, these can be defined based on non-vanishing coefficients belonging to respective t...
BibTeX
@inproceedings{haufe2010sparse,
  author = {Stefan Haufe and Klaus-Robert Müller and Guido Nolte and Nicole Krämer},
  title = {{Sparse Causal Discovery in Multivariate Time Series}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=7iA-SEDyl3},
}
Figure