Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets

Jakob Runge

Source-linked AI summary

Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets

Jakob Runge

arXiv:2003.03685v2Mar 7, 2020stat.MEcs.LGstat.ML

TL;DR

Strong autocorrelation makes causal discovery less reliable, with low recall and inflated false positives. PCMCI+ extends PCMCI to contemporaneous links and improves CI-test conditioning; it is theoretically sound and complete under stated assumptions, with higher recall, controlled false positives, and faster runtime in highly autocorrelated settings. The method is intended for causally sufficient time-series graphs and does not yet account for latent confounders.

Problem
Autocorrelation can make causal discovery less reliable by contributing to false negatives, false positives, and difficult CI-test calibration.
Method
PCMCI+ extends PCMCI to contemporaneous links, separates lagged and contemporaneous conditioning phases, and optimizes conditioning sets for individual CI tests.
Results
PCMCI+ yields higher recall, controlled false positives, and faster runtime than PC for highly autocorrelated time series while maintaining similar performance for low autocorrelation.
Takeaways & Limitations
PCMCI+ can flexibly support different CI tests and variable types while exploiting sparsity in high-dimensional settings.
Takeaways & Limitations
The method assumes causal sufficiency and does not yet account for latent confounders.

Abstract

from arXiv · show

The paper introduces a novel conditional independence (CI) based method for linear and nonlinear, lagged and contemporaneous causal discovery from observational time series in the causally sufficient case. Existing CI-based methods such as the PC algorithm and also common methods from other frameworks suffer from low recall and partially inflated false positives for strong autocorrelation which is an ubiquitous challenge in time series. The novel method, PCMCI$^+$, extends PCMCI [Runge et al., 2019b] to include discovery of contemporaneous links. PCMCI$^+$ improves the reliability of CI tests by optimizing the choice of conditioning sets and even benefits from autocorrelation. The method is order-independent and consistent in the oracle case. A broad range of numerical experiments demonstrates that PCMCI$^+$ has higher adjacency detection power and especially more contemporaneous orientation recall compared to other methods while better controlling false positives. Optimized conditioning sets also lead to much shorter runtimes than the PC algorithm. PCMCI$^+$ can be of considerable use in many real world application scenarios where often time resolutions are too coarse to resolve time delays and strong autocorrelation is present.

1 INTRODUCTION

Causal discovery for time series benefits from temporal ordering but becomes less reliable under autocorrelation. PCMCI+ extends CI-based discovery to contemporaneous links while optimizing conditioning sets for autocorrelated data.

CI-based network-learning methods can use diverse CI tests and exploit sparsity for nonlinear, high-dimensional causal discovery.
Time-order helps identify directions for lagged links, but Granger causality cannot handle contemporaneous links and suffers from the curse of dimensionality.
Non-stationarity and especially autocorrelation can make causal discovery much less reliable.
PCMCI+ extends PCMCI to discover contemporaneous links in addition to lagged links.
PCMCI+ separates lagged and contemporaneous edge-removal phases and optimizes individual conditioning sets to improve calibration and detection power under autocorrelation.

2 TIME SERIES CAUSAL DISCOVERY

Time-series causal graphs represent lagged and contemporaneous dependencies under assumptions such as stationarity and acyclicity. PC learns adjacencies through conditional-independence tests, but autocorrelation can cause weak detection, false negatives, and subsequent false positives.

2.1 PRELIMINARIES: Time-series graphs represent variables across lag-times, with causal parents defined by the variables on which each variable depends.
2.1 PRELIMINARIES: The graph is considered up to a maximum time lag τmax, while causal links are assumed stationary and the graph acyclic.
2.2 PC ALGORITHM: PC first learns a skeleton by testing conditional independencies, then uses time-order for lagged orientations and collider and rule phases for contemporaneous orientations.
2.2 PC ALGORITHM: PC exploits sparsity by removing independent coupled pairs before later tests, reducing estimation dimension relative to fitting a full model on the whole past.
2.3 AUTOCORRELATION: Strong autocorrelation can make true links difficult to detect, producing false negatives that lead to false positives in later PC stages.
2.3 AUTOCORRELATION: Autocorrelation can also help orient contemporaneous links that PC would otherwise leave unoriented within a Markov equivalence class.
2.3 AUTOCORRELATION: Ill-calibrated conditional-independence tests under autocorrelation contribute to inflated false positives in PC.
2.3 AUTOCORRELATION: Time-series graphs can resolve time-delayed feedbacks even when aggregated summary graphs would contain cyclic dependencies.

3 PCMCI+

PCMCI+ optimizes conditional-independence conditioning sets by separating lagged and contemporaneous phases and using MCI tests for contemporaneous links. The resulting procedure improves detection power and false-positive control, while supporting soundness, completeness, order independence, and faster runtimes under stated assumptions.

Algorithm: PCMCI+ separates skeleton edge removal into lagged and contemporaneous conditioning phases, reducing the number of conditional-independence tests.The lagged phase tests only the strongest p adjacencies rather than all p-dimensional subsets.
Algorithm: The contemporaneous phase conditions on lagged adjacencies and uses the MCI test to improve effect size for contemporaneous links.For the initial p = 0 phase, the paper proves that the effect size is strictly larger than for the corresponding PCMCI0 test when lagged adjacencies are non-empty.
Results and scope: Higher effect size enables PCMCI+ to recover lagged and contemporaneous links while removing lagged false positives in the illustrated example.The paper cautions that formal false-positive control for nonlinear, high-dimensional settings remains beyond its scope.
Theoretical results: The first phase returns a set containing each target’s parents and, at most, lagged parents of its contemporaneous ancestors.Under standard Faithfulness, this set contains all lagged parents of contemporaneous ancestors and blocks lagged confounding paths that do not pass through contemporaneous links.
Theoretical results: PCMCI+ recovers the correct adjacency skeleton under the stated assumptions and is complete with the conservative collider rule.Under standard Faithfulness, completeness also holds with the majority or standard orientation rule.
Theoretical results: PCMCI+ is independent of variable order under the stated assumptions, although this does not remove dependence on time order.The paper also reports faster and less variable runtimes than the PC algorithm.

4 NUMERICAL EXPERIMENTS

The experiments evaluate PCMCI+ against PC, GCresPC, and LiNGAM across autocorrelation, dimensionality, sample size, and maximum lag. PCMCI+ generally provides stronger contemporaneous detection and orientation recall with better false-positive control, including under challenging autocorrelation and dimensionality.

Experimental setup: The experiments vary autocorrelation, variable count, sample size, maximum lag, noise distribution, and nonlinearity across causal-discovery benchmarks.The linear Gaussian setup uses N = 5, T = 500, a = 0.95, τmax = 5, and α = 0.01 by default.
Autocorrelation: PCMCI+ and GCresPC maintain stable contemporaneous TPR under high autocorrelation, whereas PC and LiNGAM decline strongly.PC also shows a strong decrease in lagged TPR as autocorrelation rises.
Autocorrelation: PCMCI+ controls FPR under high autocorrelation, while PC and GCresPC show inflated lagged FPR and LiNGAM shows a strong increase.PCMCI+ also shows almost no contemporaneous orientation conflicts, unlike PC at higher autocorrelation.
Number of variables: PCMCI+ has more than twice the contemporaneous recall of the other methods as N increases and is almost unaffected by higher dimensionality.FPR is well controlled only for PCMCI+ in this comparison.
Sample size: As T increases, PCMCI+ shows the highest increases in contemporaneous recall and precision, with runtime increases moderate compared with PC.Conflicts decrease as sample size grows.
Maximum lag and robustness: All methods remain relatively robust to τmax values beyond the true maximum lag of 5 at T = 500, although PC's contemporaneous FPR and runtime increase.For too-large Nτmax relative to T, GCresPC and LiNGAM sharply drop in performance.
Nonlinear settings: In nonlinear mixed-noise experiments, PCMCI+ and PC retain a similar performance difference, while GPDC performs poorly in high-dimensional, highly autocorrelated settings.GPDC runtime is orders of magnitude longer than ParCorr, especially with PC.

5 CONCLUSIONS

PCMCI+ extends PCMCI to contemporaneous causal discovery and improves CI-test reliability through optimized conditioning sets. It delivers higher recall, controlled false positives, and faster runtime under high autocorrelation while remaining flexible across CI tests and variable types.

Method and contribution: PCMCI+ extends PCMCI to discover contemporaneous links and optimizes conditioning sets to improve CI-test reliability.Its conditioning strategy differs from PC and time-series adaptations of FCI.
Empirical conclusion: Under high autocorrelation, PCMCI+ achieves higher recall, controlled false positives, and faster runtime than the original PC algorithm.Performance remains similar to PC under low autocorrelation.
Interpretation: Autocorrelation can increase contemporaneous orientation recall by creating triples that can often be oriented.Isolated links may remain undirected in the Markov equivalence class.
Scope and use: PCMCI+ is flexible across nonlinear CI tests and discrete or continuous, univariate or multivariate variables.The method is available in the tigramite Python package.

S1 Definitions

The supplementary definitions assume causal sufficiency, Faithfulness, and a time-series graph whose variables and relevant parent lags are observed. The Causal Markov Condition requires each variable to be independent of its non-descendants given its parents.

Causal sufficiency assumes that all variables in the underlying structural causal model are observed.
τmax must be at least as large as the maximum time lag of any parent in the structural causal model.
The Causal Markov Condition states that each variable is independent of its non-descendants conditional on its parents.
For the structural causal model with independent noise terms, the Causal Markov Condition is automatically fulfilled.
Adjacency Faithfulness is formulated as a conditional-independence requirement for disjoint variable pairs and conditioning sets.

S2 Proofs

The proofs establish soundness, completeness, and order-independence properties for PCMCI+ under the stated assumptions. They also show why its staged conditioning strategy recovers lagged and contemporaneous structure while improving conditional-independence test reliability.

Lagged-parent discovery: Lemma S1 shows that Algorithm 1 returns a superset of the lagged parents under the assumptions.
Lagged-parent discovery: Algorithm 1 removes non-parent lagged variables through iterative conditional-independence tests, using Faithfulness to justify retained dependencies.
Soundness: Theorem 1 establishes that the estimated graph skeleton equals the true time-series graph skeleton under the assumptions.
Consistency: PCMCI is consistent under the weaker Adjacency Faithfulness Condition when contemporaneous causal links are absent.
Orientation and completeness: Under the conservative collider rule, PCMCI+ correctly identifies separating sets and marks triples as ambiguous when only Adjacency Faithfulness holds.
Order-independence: Order-independence follows from the PC-stable implementation and ambiguity marking for inconsistent separating sets.
Effect-size analysis: The oracle analysis uses conditional mutual information and the chain rule to compare conditioning sets for contemporaneous links.

S3 Further pseudo code

The supplementary pseudocode specifies PCMCI+ collider and orientation phases, including conservative, majority, and no-collider-rule variants. It also records ambiguous and conflicting structures during orientation.

Collider phase: Algorithm S2 requires a graph, separating sets, a collider rule, data, a significance threshold, and a conditional-independence test.
Collider phase: The collider phase iterates over nonadjacent triples and uses separating-set membership to determine collider orientations.
Collider phase: The conservative rule orients a triple as a collider only when no separating subset contains the middle variable.
Collider phase: The majority rule orients a triple as a collider when fewer than half of its separating subsets contain the middle variable.
Orientation phase: Algorithm S3 repeatedly applies rules R1–R3 to orient unambiguous triples, avoid cycles, and mark conflicting orientations.

S4 Implementation details

The implementation evaluates PCMCI+ against PC and other causal-discovery approaches with linear and nonlinear conditional-independence tests. Comparator implementations include residual-based GCresPC and VARLiNGAM, with explicit procedures for estimating and updating lagged and contemporaneous links.

Experimental comparisons: Linear experiments compare PCMCI+ and PC using ParCorr, while nonlinear experiments use GPDC for both methods.
Experimental comparisons: Linear experiments additionally evaluate GCresPC and an autoregressive VARLiNGAM implementation.
VARLiNGAM: VARLiNGAM uses a common τmax across methods and adaptive LASSO regularization with BIC-based hyperparameter selection.
GCresPC: GCresPC first fits a VAR model, applies PC to residuals, then updates lagged and contemporaneous graph components.
GCresPC: The residual-based contemporaneous graph does not use triples containing lagged adjacencies, and its third step removes spurious lagged links caused by contemporaneous parents.

S5 Further numerical experiments

Further numerical experiments evaluate linear Gaussian and linear mixed-noise setups across autocorrelation, dimensionality, sample size, and maximum time lag. The experiments use significance levels α = 0.01 and α = 0.05, with additional nonlinear mixed-noise overview results.

Experiments cover linear Gaussian, linear mixed-noise, and nonlinear mixed-noise setups.The overview varies autocorrelation strength, number of variables, sample size, and maximum time lag.
Linear Gaussian experiments vary autocorrelation strength, number of variables, sample size, and maximum time lag.Figure S1 summarizes these four factors, while Figures S4–S15 provide further experiments.
The experiments compare significance levels α = 0.01 and α = 0.05.The left and right columns represent the two significance levels in the detailed figure panels.
Detailed panels examine increasing autocorrelations and, depending on the figure, fixed or varying N, T, and τmax.Rows depict increasing autocorrelation in several experiments, while other figures vary N, T, or τmax directly.