mlsanityData to 13 Oct 2026

Scalable Time-Series Causal Discovery with Approximate Causal Ordering

arXiv 2409.05500 ↗First posted 9 Sep 2024cs.LG cs.DC cs.PFcited by 0

Not on the map. Why?

Abstract (arXiv)

Causal discovery in time-series data presents a significant computational challenge. Standard algorithms are often prohibitively expensive for datasets with many variables or samples. This study introduces and validates a heuristic approximation of the VarLiNGAM algorithm to address this scalability problem. The standard VarLiNGAM method relies on an iterative search, recalculating statistical dependencies after each step. Our heuristic modifies this procedure by omitting the iterative refinement. This change permits a one-time precomputation of all necessary statistical values. The algorithmic modification reduces the time complexity from O(m3n) to O(m2n + m3) while keeping the space complexity at O(m2), where m is the number of variables and n is the number of samples. While an approximation, our approach retains VarLiNGAM's essential structure and empirical reliability. On large-scale financial data with up to 400 variables, our algorithm achieves a 7--13x speedup over the standard implementation and a 4.5x speedup over a GPU-accelerated version. Evaluations across medical imaging, web server monitoring, and finance demonstrate the heuristic's robustness and practical scalability. This work offers a validated balance between computational efficiency and discovery quality, making large-scale causal analysis feasible on personal computers.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Builds on 14 of its 55 references that are in the map. First posted on arXiv 9 Sep 2024.

Builds on

14 of 55 references.

References · 14

  1. 2017Detecting causal associations in large nonlinear time series datasetscited by 242
  2. 2020DYNOTEARS: Structure Learning from Time-Series Datacited by 199
  3. 2021Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Gamecited by 159
  4. 2015A fast PC algorithm for high dimensional causal discovery with multi-core PCscited by 45
  5. 2023Causal Recurrent Variational Autoencoder for Medical Time Series Generationcited by 45
  6. 2024CausalFormer: An Interpretable Transformer for Temporal Causal Discoverycited by 17
  7. 2013Structural Intervention Distance (SID) for Evaluating Causal Graphscited by 14
  8. 2023Case Studies of Causal Discovery from IT Monitoring Time Seriescited by 14
  9. 2018cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPUcited by 12
  10. 2013Score-based Causal Learning in Additive Noise Modelscited by 8
  11. 2021Interactive Causal Structure Discovery in Earth System Sciencescited by 6
  12. 2022Granger Causal Chain Discovery for Sepsis-Associated Derangements via Continuous-Time Hawkes Processescited by 6
2 more
  1. 2024AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUscited by 4
  2. 2021ParaLiNGAM: Parallel Causal Structure Learning for Linear non-Gaussian Acyclic Modelscited by 3

Built on by

Not cited yet.