Research map / Probabilistic and scientific modeling / Causal discovery
Arrow: Accelerator for Time Series Causal Discovery with Time Weaving
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ARROW, a data-level accelerator for time series causal discovery that binarizes series via "time weaving", uses XOR-based time lag discovery and candidate pruning, and speeds up four existing algorithms (PCMCI, NGC, VARLiNGAM, SURD).
Problem
Time series causal discovery is slow due to costly binning for independence tests, brute-force time lag search with uncertain lag selection, and an exponentially large candidate parent set as the number of variables grows.
Approach
Encode each time point as a binary trend tuple relative to its neighbors at a weaving window (time weaving), then use XOR of trend codes between variable pairs to rank lags via a theorem-based threshold (1/3) and prune candidate variable pairs, making any causal discovery algorithm faster as a plug-in accelerator.
Key results
- ARROW gives up to 153x speedup over the original algorithms while achieving higher accuracy in most cases (abstract).
- On linear SCM data, SURD with ARROW runs in about 6.2 s versus about 425 s for SURD (nearly 70x speedup).
- On the real-world Dream3 dataset, ARROW achieves 7x to 300x speedup across methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add ARROW to PCMCI | PCMCI · Linear SCM, constant lag 5 | Time (s): 245.99±15.85 -> 6.6734±0.026 | Helped |
| add ARROW to SURD | SURD · Linear SCM, constant lag 5 | Time (s): 424.90±1.837 -> 6.1656±0.013 | Helped |
| add ARROW to NGC | NGC · Linear SCM, constant lag 5 | Graph AUC: 0.7513±0.088 -> 0.9975±0.008 | Helped |
| add ARROW to VARLiNGAM | VARLiNGAM · Linear SCM, constant lag 5 | Graph AUC: 0.9606±0.021 -> 0.9819±0.014 | Helped |
| add ARROW to PCMCI | PCMCI · Nonlinear SCM, constant lag 5 | Time (s): 1310.7±304.4 -> 9.6132±3.044 | Helped |
| add ARROW to PCMCI | PCMCI · Nonlinear SCM, constant lag 5 | Graph AUC: 0.9029±0.054 -> 0.8999±0.037 | Hurt |
| add ARROW to SURD | SURD · Nonlinear SCM, constant lag 5 | Graph AUC: 0.5000±0.000 -> 0.7310±0.109 | Helped |
| add ARROW to VARLiNGAM | VARLiNGAM · Nonlinear SCM, constant lag 5 | Graph AUC: 0.9834±0.013 -> 0.8974±0.020 | Hurt |
Surprising findings
- VARLiNGAM with ARROW performs worse in lag AUC than VARLiNGAM when the time lag is small, attributed to time weaving altering the noise distribution.
- The original SURD baseline reaches only about 0.50 lag AUC in many settings, indicating chance-level lag discovery.
Limitations
- Accuracy drops on some nonlinear settings (e.g., graph AUC for SURD and NGC with ARROW are below originals in some cases).
- Time weaving may distort original noise distributions, hurting methods that rely on non-Gaussian noise such as VARLiNGAM at small lags.
Experimental setup
Datasets: synthetic linear SCM time series (10 variables, length 1000) synthetic nonlinear SCM time series Dream3
Benchmarks: synthetic linear SCM datasets synthetic nonlinear SCM datasets Dream3
Metrics: runtime (s) TPR FPR AUC (lag AUC and graph AUC)
Baselines: PCMCI NGC VARLiNGAM SURD
Builds on: PCMCI NGC VARLiNGAM SURD
Closest papers by meaning
- CausalRivers - Scaling up benchmarking of causal discovery for real-world time-series (ICLR 2025 · similarity 0.90)
- CausalTime: Realistically Generated Time-series for Benchmarking of Causal Discovery (ICLR 2024 · similarity 0.89)
- CUTS+: High-Dimensional Causal Discovery from Irregular Time-Series (AAAI 2024 · similarity 0.87)
- SPACETIME: Causal Discovery from Non-Stationary Time Series (AAAI 2025 · similarity 0.86)
- Learning Causal Relations from Subsampled Time Series with Two Time-Slices (ICML 2024 · similarity 0.86)
- Discovering Mixtures of Structural Causal Models from Time Series Data (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.