Causal Structure Learning for Dynamical Systems with Theoretical Score Analysis

AI summary

Overview

Research area: Causal discovery for continuous-time dynamical systems, combining Gaussian Process (GP) based dynamics modeling with information-theoretic (Minimum Description Length) structure learning.

Technical level: Advanced. The paper assumes familiarity with systems of ordinary differential equations (ODEs), Gaussian Process regression, structural causal models, and algorithmic information theory (Kolmogorov complexity, Minimum Description Length).

Scope: The paper proposes CaDyT (Causal Discovery for Dynamic Timeseries), a score-based method that recovers the causal graph of a continuous-time dynamical system from regularly or irregularly sampled trajectories, supported by a theoretical analysis of the proposed MDL score.

What This Paper Is About

Real-world systems evolve in continuous time according to causal mechanisms, but existing causal discovery methods for time series usually discretize time and assume regular sampling, while dynamics-learning methods that handle continuous time generally ignore causality. The paper builds a causal discovery framework, grounded in Difference-based Causal Models (DBCM) rather than discrete-time Dynamic Bayesian Networks, that learns continuous-time dynamics using exact GP inference and searches for the causal graph by minimizing a Minimum Description Length score. The goal is to recover causal networks closer to the true underlying dynamics, including under irregular sampling.

Key Contributions

1. A novel approach for causal discovery in continuous-time dynamical systems that addresses both irregular sampling and causal structure identification, two challenges the paper states were previously tackled only in isolation.
2. Use of a Gaussian Process framework for exact inference in continuous time, enabling non-parametric modeling of system dynamics aligned with the underlying differential equation structure.
3. An end-to-end algorithm, CaDyT (Causal Discovery for Dynamic Timeseries), which combines GP dynamical system modeling for continuous-time inference with a greedy structure search, allowing exact evaluation of dynamics while recovering causal mechanisms.
4. A theoretical analysis of the proposed score: Lemma 1 and Theorem 2 show that, under two stated assumptions, the score's asymptotic upper bound behaves as a valid regularized log-likelihood score (with the same form as BIC), and Corollary 3 states that model selection using the full score is equivalent to model selection using that bound.

Main Findings

• Robustness to false positives: On a sanity check with 10 graphs made of 4 independent ODEs, CaDyT with the AB3 integrator never discovered a single spurious edge. By contrast, the baselines reported causal edges on independent data: VARLiNGAM found spurious edges 30% of the time, PcMci+ 60%, and DynoTears 100%.
• Structural accuracy (nSHD): For Erdős–Rényi random graphs with D ∈ {5, 10, 15}, on both regularly and irregularly sampled data, CaDyT consistently outperformed all baselines by a clear margin in normalized Structural Hamming Distance (nSHD, lower is better). DyNoTears and PcMci+ showed a high false positive rate, worsening their nSHD.
• Irregular sampling: All methods worsened slightly on irregularly sampled data, but CaDyT remained best by a visible margin.
• Precision and recall (F1): CaDyT was on par with baselines for variable size 5, and remained robust to false positives by maintaining high precision as network size increased; competing methods had very low precision due to frequently predicting spurious edges.
• Confidence in predicted edges (AUPRC): CaDyT's high AUPRC is reported as indicating higher confidence about correct causal edges as opposed to spurious ones.
• Effect of integrator order: On irregularly sampled data, CaDyT showed gradual improvement with higher-order Adams-Bashforth integrators for s ∈ {1, 2, 3}.
• Theoretical guarantee: Under Assumption 1 (finite-dimensional kernel) and Assumption 2 (bounded length scales, variances, and precisions), the score's asymptotic upper bound takes the form c₀ · N · log(σ̂²) + c₁ · log(N) + c₂ with constants independent of N, making it a valid regularized log-likelihood score.

Methodology in Plain English

The authors treat the system as a set of autonomous ODEs and interpret the equations as a Dynamic Structural Causal Model: each variable's trajectory is generated by a function of its direct causes. This "instantaneous gradient" view — causation flowing through time derivatives — is closer to a Difference-based Causal Model than to a Dynamic Bayesian Network, and it allows for self-loops and cyclic graphs.

To model dynamics without forcing a parametric form, they use multi-step numerical integrators (Adams-Bashforth) inside Gaussian Process regression following Ensinger et al. (2024), which permits exact GP inference and evaluation of the dynamics at any point on an arbitrary timeline, including irregularly sampled ones. For each candidate variable, a GP is trained to predict that variable's dynamics from a candidate set of parents.

Scoring uses the Algorithmic Markov Condition: the true causes are those giving the simplest description of the target. Because Kolmogorov complexity is not computable, they upper-bound it with a Minimum Description Length score built from four encodings — the global model cost (integrator step size plus the first s trajectory samples), the local model cost (number of parents, which parents, and the function), the function cost (encoded via Singular Value Decomposition of the kernel matrix plus encoded length scales, variances, and eigenvalues), and the data-given-model cost (encoding Gaussian residual noise). Because scoring every possible graph is intractable (super-exponential in the number of variables), they use a three-step greedy search: rank all pairwise edges by their score gain, add the highest-gaining edge if it passes the no-hypercompression test, re-evaluate incoming edges to affected variables, and then run a backward phase to prune redundant edges.

Why This Matters

The work unifies two research threads — continuous-time dynamics learning and causal discovery — and provides a theoretical result linking its MDL score to a BIC-like regularized log-likelihood, giving score-based causal discovery for dynamical systems a firmer footing. It also shows empirically that causal structure can be recovered from irregularly sampled trajectories, which is common in practice.

Real-world applications, following from the paper's framing of continuous-time physical systems (its motivating example is an n-mass spring system where each mass's position induces forces on connected velocities):

• Physical and mechanical systems with continuous dynamics, where models are needed that respect the direction of causal influence rather than capturing spurious correlations.
• Scientific time-series data collected on arbitrary or irregular timelines, where discretization-based causal methods degrade.
• Systems modeled by differential equations where the governing equations are unknown and must be inferred from observations.
• Domains where distribution shift in an unrelated variable should not corrupt predictions of a target — a benefit the paper attributes to preserving local dependencies — with one author affiliated with the Institute for AI in medicine (IKIM).

Industry relevance: The work originates from the Bosch Center for Artificial Intelligence, and CaDyT is reported to be inherently parallelizable with an overall complexity of O(N³D³ log D), which the authors state is at least on par with existing methods.

Future Directions

• Extending the theoretical guarantees beyond the greedy search: the paper notes its guarantees hold only when scoring all graphs over the trajectory, and that the greedy procedure is a practical alternative rather than an exhaustive one.
• Broadening the kernel analysis: Theorem 2 applies to finite-dimensional kernels (Polynomial, Wendland, Buhmann, Truncated/Random Fourier, Nyström approximated kernels), while the main experiments use RBF kernels for their exact-inference capabilities despite possible over-regularization; results with Polynomial kernels are deferred to supplementary material.
• Scaling structure search to larger systems, given the super-exponential growth of the search space with the number of variables and the O(N³D³ log D) complexity.
• Determining how the approach behaves under violations of its stated assumptions — dynamic stability, causal sufficiency, μ-Markovianity and μ-faithfulness, and the sampling-rate condition Δmax ∈ (0, 1/(2φmax)).

Target Audience

Machine learning researchers working on causal discovery, particularly those interested in time-series and continuous-time systems; practitioners applying Gaussian Process dynamics models or probabilistic ODE learning; and theoretically inclined readers interested in MDL-based scoring and its connection to BIC-style regularized likelihood scores. Readers without a background in GP inference, structural causal models, and information theory will find the theoretical sections demanding.

Authors’ abstract

Real world systems evolve in continuous-time according to their underlying causal relationships, yet their dynamics are often unknown. Existing approaches to learning such dynamics typically either discretize time -- leading to poor performance on irregularly sampled data -- or ignore the underlying causality. 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. CaDyT leverages exact Gaussian Process inference for modeling the continuous-time dynamics which is more aligned with the underlying dynamical process. We propose a practical instantiation that identifies the causal structure via a greedy search guided by the Algorithmic Markov Condition and Minimum Description Length principle. 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.