ITPD holds F1 near 0.99 and runs 40.9× faster than PCMCI at 2,000 nodes

Time Series Structure Learning with Local Causal Parent Discovery

Jacqueline Maasch, Shu Wan, Hank Zhu, Huan Liu, Zhiguang Wang

cs.LG, stat.ML

2026-11-19

ITPD finds each node's parents in time order on series whose causal links can change. At 2,000 nodes it is 40.9× faster than PCMCI, with F1 near 0.99.

What problem this solves

Constraint-based causal discovery deletes edges with conditional independence tests: given some other variables, are two variables still associated? Multivariate time series makes those tests harder. Observations are autocorrelated, causal links can change over time, and a larger conditioning set needs exponentially more samples.

PCMCI and DYNOTEARS assume causal stationarity. A link at a fixed lag repeats at every time, so a long series collapses into a window graph. Figure 1 shows what that assumption costs. The true object is a full time graph whose edges change. A stationary window with maximum lag 2 uses the wrong parents after time 3.

The main experiments target repeated trajectories whose edges can still change, and they learn a separate parent set for every node.

Method

ITPD walks forward in time, finds the parents of each variable, and assembles a DAG. Parents already stored in the adjacency list become conditioning sets for later tests, which replaces high-order tests with lower-order ones.

Parents are restricted to the past. The lag-1 self-loop is treated as a known parent, and the candidate set starts there. Variables at the same time do not point to each other. After the first time step there is no latent confounding; the first step itself may be a root under unobserved history. The distribution is faithful to an acyclic graph and satisfies the Markov condition. Causal stationarity can fail.

Each target has two phases. A deletion in Phase I does not come back, so the threshold is loose: α is 0.01, γ is 0.2, and κ is 50. With few candidates the level is 0.2; with many it does not fall below 0.01, and κ limits how many non-parents enter the set. Earlier variables are scanned from newest to oldest, at most three tests each. A variable with no ancestral tie to the current set and marginally independent of the target is dropped. A variable already independent given the current set is also dropped, once. A variable that stays dependent given its previously learned parents is kept. That last check is the local Markov condition: given its parents, a variable is independent of its nondescendants, so the conditioning set is those learned parents, far smaller than the entire past.

Phase II tightens the superset from oldest to newest at threshold α/m, a Bonferroni correction. A candidate that remains dependent after it is removed from the set is kept as a parent.

Newest-to-oldest is the order kept after ablation. Extra partition tests for mediators and instruments stayed correct under an oracle, but the conditioning set shrank little and the tests increased, so they were removed. The naive baseline IPaDL calls PaDL on every leaf, and its conditioning sets are much larger.

Under an independence oracle the parent set is exact, and induction over time yields the full graph. If each test runs in polynomial time, the number of tests on replicate trajectories is O(N²T²). Sixty-one Lean theorems check that oracle claim.

Results

Across 32 oracle settings and 4,240 graphs, with N from 20 to 80 and T from 16 to 50, both ITPD and IPaDL recovered the true graph. At N=20, T=16, lag 1, and 200 graphs per cell, unique tests per candidate at in-degree d=1 are 1.23 for ITPD, 6.02 for IAMB, and 1.76 for IPaDL, while FullCI always uses 1. At d=8, ITPD stays at 1.26 and IAMB rises to 17.67. Mean conditioning-set size at d=1 is 0.7 for ITPD, 5.6 for IAMB, 21.7 for IPaDL, 206 for FullCI, and 4.2 for PCMCI. IPaDL's largest conditioning set is 22.9× to 52.2× ITPD's.

The finite-sample main setting is linear-Gaussian, nonstationary, N=20, T=16, and Fisher-z, with 20 graphs per cell.

SettingITPDIAMBPCMCIDYNOTEARS
M=500, d=20.9920.9940.2050.045
M=500, d=50.9610.9720.3640.062
M=2000, d=20.9970.9980.2070.038
M=2000, d=50.9910.9990.3960.055

In these cells ITPD's F1 is higher than Lasso, PCMCI, CD-NOD, and DYNOTEARS. Against IAMB it wins 2 of 12 settings, ties 4, and loses 6, with gaps from -0.042 to +0.004. FullCI is higher only when d is 3 or 5 and M=2000, by at most 0.007.

When 5% of edges are redrawn at each step, ITPD's F1 stays from 0.984 to 0.994, while PCMCI, DYNOTEARS, and CD-NOD fall to 0.562 to 0.808. In all 16 settings with d of 2 or 5 and M of 500 or 2000, IAMB beats ITPD by 0.003 to 0.064. With nonlinear mechanisms and a generalized covariance test, ITPD ranks first or second in 6 of 8 settings.

At 2,000 nodes ITPD is 2.3×, 9.1×, and 40.9× faster than iterative IAMB, DF-PC, and PCMCI, and it sits on the Pareto frontier of F1 versus wall-clock time. From 1,000 to 2,000 variables it is the fastest method, with F1 of 0.997 to 0.998 at M=2000. Across 76 finite-sample settings it uses 0.10× to 0.86× as many unique tests per candidate as IAMB.

Conditioning-set size flips on finite samples. At M=2000 and d=2, the mean set is 8.2 for ITPD and 2.3 for IAMB, and the maximum is 33 versus 7.

On resimulated DREAM4 networks 3 and 5, ITPD beats IAMB in all 6 settings, but against the best baseline in each setting it loses 4, ties 1, and wins 1. At M=200 the window-graph methods are higher in every comparison, and that F1 covers only early time steps. On network 3 at M=200, DYNOTEARS scores 0.689, CD-NOD 0.681, PCMCI 0.609, and ITPD 0.518. At M=500, ITPD's 0.683 is the highest in that cell.

Removing lag-1 self-loops, from a fraction of them up to all of them, leaves ITPD at F1 0.997. When half the edges sit inside a time step, F1 on the remaining lag-1 edges drops to 0.527, against 0.574 for FullCI.

Why it matters

On repeated panel measurements whose mechanism changes, a window graph is the wrong model. Raising M in the main experiment still leaves PCMCI near F1 0.2 and DYNOTEARS near 0.05. ITPD and time-ordered IAMB do not require links to repeat, so that gap comes from the problem definition.

Against iterative IAMB, ITPD runs fewer tests, is faster past a thousand nodes, and has a polynomial bound on the number of tests. F1 stays in the same range and is often slightly lower. The implementation is public.

In the main setting it matches or beats the other methods once M passes about 100. A single nonstationary series with no replicates sits outside this guarantee.

Limitations

Two gaps are stated directly. No setting is a uniform win, and there is no public real-world benchmark in the regime where ITPD should help, so the evaluation stays on simulations and resimulated gene networks. Latent confounding after the first time step, and same-time edges, are still out of reach.

The 40.9× figure is against PCMCI, whose F1 is about 0.2 on the nonstationary main experiment. Iterative IAMB, the closer task, is 2.3× slower and often slightly more accurate. The largest speedup stacks a misspecified baseline together with a faster search.

Lower-order tests are offered as the reason to expect better sample efficiency. At M=2000 and d=2, IAMB's mean conditioning set is 2.3 and ITPD's is 8.2. The smaller oracle conditioning sets do not survive Fisher-z on finite samples.

γ and κ were fixed by F1 on linear-Gaussian graphs. At N=100 and T=20 the largest conditioning set is 27 to 37; a fixed Phase I level of 0.2 pushes it to 134 to 156. F1 across 16 settings moves by at most 0.001.

F1 stays at 0.997 after the lag-1 self-loops are removed, and the text does not say whether those loops enter the F1 denominator. Development, ecology, and climate rarely supply clean replicates of one structural model. The Lean proofs check parent sets only under an oracle.

Terms

Source

Related papers

All paper explainers