AI Research Portal

This paper introduces CADYT (Causal Discovery for Dynamic Timeseries), a novel method for causal discovery in continuous-time dynamical systems. CADYT addresses the challenges of irregular data sampling and causal structure identification by grounding its formulation in Difference-based causal models and leveraging exact Gaussian Process (GP) inference to model continuous-time dynamics. The core idea is to minimize a Minimum Description Length (MDL) score, which is theoretically shown to be a valid regularized log-likelihood score, via a greedy search algorithm. Empirically, CADYT outperforms state-of-the-art methods on both regularly and irregularly-sampled data, discovering causal networks closer to the true underlying dynamics.

Existing approaches to learning continuous-time dynamics typically discretize time, leading to poor performance on irregularly sampled data.
Current methods for causal discovery on time-series often ignore the underlying continuous dynamics and assume regular sampling, making them unsuitable for irregularly-sampled data.

A novel approach for causal discovery in continuous-time dynamical systems that addresses both irregular sampling and causal structure identification—two challenges previously tackled in isolation.
Leveraging the Gaussian Process framework for exact inference in continuous time, enabling nonparametric modeling of system dynamics.
An end-to-end algorithm, Causal Discovery for Dynamic Timeseries (CADYT), combining Gaussian Process dynamical system modeling methods for continuous-time inference with structure search, enabling exact evaluation of dynamics while recovering true causal mechanisms.

CADYT aims to discover the causal structure of continuous-time dynamical systems from discrete-time trajectory data, accommodating irregular sampling. The method is built around minimizing a Minimum Description Length (MDL) score, which is derived from the Algorithmic Markov Condition (AMC) principle.

Objective The method seeks to find the model M* that minimizes the total description length L(T,M) for a given trajectory T: M* = argmin L(T,M) MEM This objective is further decomposed based on the assumption of Additive Noise Models, where the observed trajectory X(t) is a sum of a deterministic process x(t) and independent Gaussian noise v(t). The objective simplifies to: argmin (L(M) + Σ(L(vi))) MEM

MDL Score Components The total MDL score L(T,M) consists of two main parts:

Model Cost L(M): This includes a global cost Lglobal(M) for storing initial samples and integrator step-size, and local model costs L(Mi) for each variable Xi.
- Lglobal(M) = log N + ra·D·s
- L(Mi) = LN(||Pai||) + ||Pai|| log D + LF(Fi)
- LF(Fi) is the cost of encoding the continuous dynamics function Fi, which is learned using Gaussian Process Regression (GPR). It involves encoding kernel matrix components, length-scale, and noise-variance parameters.
- Lp(θ) = 2||θ|| + ΣLN(|pi|) + LN ( [θi·10pi]) is used for encoding parameters.
Data Given Model L(D|M): This encodes the residual noise after the model has accounted for the underlying causal structure and data-generating process. For Gaussian noise, it is given by: L(Vi) = N/2 ln (1/(2π) + log(σ²))

Structure Search CADYT employs a three-step greedy search procedure:

Edge Scoring: Computes the gain Γij for all pairwise causal connections between Xi and Xj: Γij = L(T, M) – L(T, M⊕ij) where M⊕ij implies model M with edge Xi → Xj included. A priority queue of tuples (Γij, (Xi, Xj)) ordered by decreasing gain is returned.
Forward Search: Iteratively adds the highest-scoring edge from the priority queue, provided it passes a statistical significance test. The search terminates when no further additions improve the score.
Backward Phase: Prunes redundant edges by removing any whose deletion increases L(T, M).

Dynamical Systems: Modeled as systems of autonomous Ordinary Differential Equations (ODE) of the form X(t) = F(X(t)) with F : RD → RD.
Gaussian Processes: Assumed to have a zero-mean Gaussian process prior F ~ N(0,kθ(x, y)). GPR is used to estimate the dynamics function F(X*|Pat1:tN) ~ N(µpost(X*), Σpost(X*)).
Kernels: RBF-Kernel is used for experiments, with Polynomial kernels also mentioned.
Integrators: Multi-step integrators, specifically Adams-Bashforth (AB) integrators of order s ∈ {1,2,3}, are used for exact GP inference and to approximate trajectory points X(n+s) using a weighted sum of past points.
Causal Models: Grounded in Difference-based Causal Models (DBCM) and Dynamic Structural Causal Models (DSCM).
Assumptions: Causal sufficiency, µ-Markovian, µ-faithful, instantaneous gradient assumption, dynamic stability, finite dimensions (Assumption 1), and bounded hyperparameters and precision (Assumption 2).
Optimization: Greedy search algorithm (edge scoring, forward, backward search).
Computational Complexity: O(N³ D³ log D), where N is the number of trajectory points and D is the number of variables. The method is inherently parallelizable.
Precision: Parameters are encoded up to a user-specified precision p, with p = 2 used for considering the first two digits.

Datasets:
- Synthetic data: Diamond structure (4 variables) and Erdős–Rényi random graphs with and without cycles for D ∈ {5, 10, 15}.
- Simulated systems: 2-mass spring system, Rössler Oscillator.
- Real-world system: Double-linear system.
Metrics:
- Structural Hamming Distance (SHD), normalized as NSHD (divided by D²). Lower NSHD is better.
- F1 score. Higher F1 is better.
- Area Under Precision Recall Curve (AUPRC). Higher AUPRC indicates higher confidence.
Baselines:
- PCMCI+ (Runge 2020) using non-parametric Kernelized independence test.
- DYNOTEARS (Pamfil et al. 2020).
- VARLINGAM (Hyvärinen et al. 2010).
Numeric Results:
- NSHD (Figure n: 2): CADYT consistently outperforms all baselines by a clear margin on both regularly and irregularly sampled data for D ∈ {5, 10, 15}.
- F1 score (Figure n: 3): CADYT is on-par with baselines for D=5 and maintains high precision as network size increases, outperforming competing methods which have very low precision.
- AUPRC (Figure n: 3): CADYT performs well across benchmarks, indicating high confidence about high-confidence edges.
- AUPRC for specific systems (Table n: 1):
  - DblMass: DYNOTEARS 0.22, PCMCI+ 0.24, VARLINGAM 0.39, CADYT (ours) 0.79
  - DblLinear: DYNOTEARS 0.59, PCMCI+ 0.30, VARLINGAM 0.44, CADYT (ours) 0.79
  - Rössler: DYNOTEARS 0.34, PCMCI+ 0.22, VARLINGAM 0.30, CADYT (ours) 0.55
- Effect of Integration Order (Figure n:4): Higher-order integrators (AB2/AB3) generally outperform AB1 on irregular timelines.
- False Positives: CADYT with AB3 never discovered a single spurious edge for 4 independent ODEs. Baselines reported spurious edges (VARLINGAM 30%, PCMCI+ 60%, DYNOTEARS 100%).
Runtime/Training Cost: CADYT has an overall computational complexity of O(N³ D³ log D).

The greedy graph search and Adams-Bashforth integrators used in CADYT are not claimed to be optimal choices; alternate search strategies or integrators might yield better performance.
The current approach, while allowing for both regular and irregular-sampled trajectories, is known to be sensitive to high amounts of noise.
CADYT currently assumes causal sufficiency, which could be relaxed by searching for instantaneous edges where both directions give a high score, potentially pointing to a hidden confounder.
CADYT assumes ODEs can be well-modeled by a GP regression under a noisy observation model.

Method evidence: "We propose CADYT, a novel method for causal discovery on dynamical systems addressing both these challenges. In contrast to state-of-the-art causal discovery methods that model the problem using discrete-time Dynamic Bayesian networks, our formulation is grounded in Difference-based causal models, which allow milder assumptions for modeling the continuous nature of the system." (section: Abstract)
Result evidence: "Our experiments show that CADYT outperforms state-of-the-art methods on both regularly and irregularly-sampled data, discovering causal networks closer to the true underlying dynamics." (section: Abstract)
Limitation evidence: "First, we used greedy graph search and the Adams-Bashforth integrators as the two main components for CADYT. We do not, however, claim that these to be optimal choices. It is possible that alternate search strategies resp. integrators yield better performance and we aim to investigate such alternative approaches." (section: 7 Discussion and Conclusions)

Causal Structure Learning for Dynamical Systems with Theoretical Score Analysis

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures