Learning Causal Structure of Time Series using Best Order Score Search

Imagine you are a detective trying to figure out the cause-and-effect relationships in a bustling city. You have a security camera feed (your data) showing thousands of people moving around every second. Your goal is to draw a map showing who influences whom: Does the traffic light turning red cause the cars to stop? Does a sudden rainstorm cause people to open umbrellas?

In the world of data science, this is called Causal Discovery. But when the data is a Time Series (a continuous stream of events over time), it gets tricky. Things happen in a sequence, and what happened a second ago often influences what happens right now. This "temporal dependence" confuses many standard detective tools.

This paper introduces a new detective tool called TS-BOSS (Time Series - Best Order Score Search). Here is how it works, explained through simple analogies.

The Problem: The "Frozen Frame" vs. The "Movie"

Most old methods for finding causes treat data like a stack of frozen photos. They look at a snapshot and ask, "If A and B happen together, did A cause B?"

But time series data is a movie. In a movie, the frame at 1:00 PM depends heavily on the frame at 1:01 PM. If you treat a movie like a stack of photos, you get confused. You might think the car stopping caused the light to turn red, because they happen at the same time in the video, even though the light actually came first.

The Solution: TS-BOSS

The authors took a powerful tool called BOSS (which was great at solving the "frozen photo" mystery) and upgraded it to handle the "movie" format. They call the new tool TS-BOSS.

Here is the secret sauce of how TS-BOSS solves the mystery:

1. The "Ordering Game" (Permutation Search)

Imagine you have a group of suspects (variables) and you need to figure out the order in which they acted.

Old way: Try every possible combination of who did what. This is like trying every possible seating arrangement for a dinner party. If you have 20 guests, the number of arrangements is so huge it would take a lifetime to check them all.
TS-BOSS way: It plays a smart game of "Ordering." It asks: "If I assume Suspect A acted before Suspect B, does the story make more sense?" It uses a clever trick called Grow-Shrink Trees.
- The Analogy: Think of building a family tree. Instead of drawing the whole tree from scratch every time you add a new person, TS-BOSS keeps a "scratchpad" (the tree) where it remembers the work it already did. If it needs to check if "Grandma" is related to "Grandson," it doesn't re-calculate the whole family history; it just looks at its scratchpad. This makes it incredibly fast.

2. The "Time Travel" Rule

Since this is a time series, TS-BOSS has a strict rule: You cannot change the past.

In the game, it forces the "lagged" variables (things that happened in the past) to always come before the "contemporaneous" variables (things happening right now).
The Analogy: Imagine a line of dominoes. You can rearrange the order of the dominoes standing up right now, but you can never move a domino that has already fallen to the front of the line. This ensures the cause always comes before the effect.

3. The "Scorecard"

How does TS-BOSS know if its map is correct? It uses a Scorecard (called BIC).

It tries to draw a map that explains the data perfectly but uses as few lines (connections) as possible.
The Analogy: Imagine you are trying to explain a complex magic trick. You want the simplest explanation that fits all the facts. If you say "The magician used a hidden wire, a mirror, and a secret assistant," that's a complex explanation. If you say "The magician used a hidden wire," and that explains everything, that's a better score. TS-BOSS looks for the simplest, most accurate map.

Why is this a big deal? (The Results)

The authors tested TS-BOSS against other famous detective tools (like PCMCI+). They found something surprising:

The "High Autocorrelation" Problem: In some movies, the action is very repetitive. The cars move slowly, the rain falls steadily. In these "highly repetitive" scenarios, the old tools (which rely on checking if things are independent) get confused and fail. They think everything is connected to everything else because the patterns are so similar.
TS-BOSS Wins: Because TS-BOSS looks at the order of events and uses its "scratchpad" to score them, it stays calm and accurate even when the data is repetitive. It found the correct connections (edges) much more often than the other tools, especially when the data was "sticky" (highly autocorrelated).

The Bottom Line

TS-BOSS is a new, super-fast, and smart way to figure out cause-and-effect in time-based data.

It treats time like a movie, not a photo.
It uses a "scratchpad" to save time and energy.
It follows the rule that the past must always come before the future.
It is particularly good at solving mysteries where the data is repetitive and predictable, a scenario where other tools usually get stuck.

In short, if you want to understand the hidden rules of a dynamic system (like weather patterns, stock markets, or brain activity) without getting lost in the noise, TS-BOSS is the new detective you want on your team.

Here is a detailed technical summary of the paper "Learning Causal Structure of Time Series using Best Order Score Search" by Irene Gema Castillo Mansilla and Urmi Ninad.

1. Problem Statement

The paper addresses the challenge of causal structure learning from observational multivariate time series data. While causal discovery is well-established for static (i.i.d.) data, time series settings introduce significant difficulties:

Temporal Dependence: Observations are not independent and identically distributed (i.i.d.), violating standard assumptions for many statistical procedures.
Complexity: The search space involves both contemporaneous relationships (variables at the same time step) and lagged relationships (variables at previous time steps).
Limitations of Existing Methods:
- Constraint-based methods (e.g., PCMCI+) rely on conditional independence (CI) tests, which can be ill-calibrated in time series due to strong autocorrelation and sample dependence.
- Score-based methods (e.g., GES, NOTEARS) often struggle with scalability or lack specific theoretical guarantees for the dynamic setting.

The authors aim to develop a score-based causal discovery method specifically for time series that maintains scalability, handles high autocorrelation effectively, and provides theoretical guarantees for correctness.

2. Methodology: TS-BOSS

The authors propose TS-BOSS (Time Series - Best Order Score Search), an extension of the static BOSS algorithm (Andrews et al., 2023). TS-BOSS combines permutation-based search with efficient caching via Grow-Shrink Trees (GSTs).

Core Adaptations for Time Series

Window Causal Graph ( $G_W$ ):
- Instead of learning the infinite time series graph directly, TS-BOSS targets a Window Causal Graph.
- It assumes a maximum time lag $\tau_{max}$ . The time series is "unrolled" into a window $W = [t-\tau_{max}, t]$ .
- Under the assumption of stationarity, learning the structure of this finite window graph allows for the reconstruction of the entire time series causal graph (ts-DAG).
Restricted Permutation Search:
- Temporal Ordering Constraint: Permutations must respect time order. Lagged variables ( $X_{t-\tau}$ ) must always precede contemporaneous variables ( $X_t$ ) in the permutation order.
- Search Space Reduction: The permutation search is restricted only to the contemporaneous variables ( $X_t$ ). Lagged variables are treated as fixed predecessors (candidate parents) that cannot be reordered relative to the current time slice.
Two-Phase Algorithm:
- Phase 1 (Permutation Search & Grow-Shrink):
  - Iteratively finds the best permutation of contemporaneous variables.
  - Uses Grow-Shrink Trees (GSTs) to cache intermediate score computations, avoiding redundant calculations when variables are added or removed from parent sets.
  - Constructs a TS-DAG (Time Series Directed Acyclic Graph) based on the optimal permutation.
- Phase 2 (TS-BES - Backward Equivalence Search):
  - Applies a backward search to delete edges that do not improve the score, ensuring the resulting graph is the most minimal representation (Markov Equivalent Class) of the data.
Scoring:
- Utilizes the Bayesian Information Criterion (BIC) as the scoring function, which balances goodness-of-fit and model complexity.

3. Key Contributions

Theoretical Contributions

Soundness Guarantees: The authors provide theoretical proofs (Theorems 5, 6, and 7) establishing that TS-BOSS is sound in the large sample limit.
- They prove that the permutation-induced window graph satisfies the Window Markov Property and is window subgraph minimal.
- They extend classical results (Verma & Pearl, 1990; Raskutti & Uhler, 2018) regarding sparsest permutations to the dynamic (time series) setting.
Assumptions: The method relies on standard assumptions: Time Series Local Markov Property, Faithfulness, Causal Sufficiency (no latent confounders), Stationarity, and a known finite maximum time lag.

Algorithmic Contributions

TS-BOSS Algorithm: A novel adaptation of BOSS that enforces temporal constraints within a permutation-based search, leveraging GSTs for efficiency.
Handling Autocorrelation: The method is specifically designed to remain effective in high-autocorrelation regimes where constraint-based methods often fail due to the difficulty of calibrating conditional independence tests.

4. Experimental Results

The authors evaluated TS-BOSS on synthetic data generated from multivariate linear time-series SCMs, comparing it against:

TS-BOSS (i.i.d.): A baseline where data is sampled independently to test the algorithm's core logic without temporal dependence.
PCMCI+: A state-of-the-art constraint-based method for time series.

Key Findings:

High Autocorrelation Regime: TS-BOSS significantly outperforms PCMCI+ in terms of Adjacency Recall when autocorrelation is high. PCMCI+ struggles to detect edges in these regimes, while TS-BOSS remains stable.
Precision vs. Recall: While PCMCI+ often achieves slightly higher precision (fewer false positives), TS-BOSS consistently achieves higher recall (fewer false negatives) at comparable precision levels.
Scalability: TS-BOSS is substantially faster than PCMCI+, especially as the number of nodes ( $N$ ) and graph density increase. The permutation search scales more favorably than the exponential growth of conditional independence tests required by constraint-based methods.
Sample Size: Performance improves with larger sample sizes ( $T$ ), but TS-BOSS maintains its advantage in recall even with moderate sample sizes.

5. Significance and Impact

Bridging Theory and Practice: The paper provides a principled bridge for extending sparsity-based, permutation-driven causal learning theory from static settings to dynamic time series.
Alternative to CI Tests: It demonstrates that score-based permutation search is a viable and often superior alternative to constraint-based methods (which rely on CI tests) for time series, particularly when data exhibits strong temporal dependence.
Scalability: By utilizing Grow-Shrink trees and restricting the permutation space to contemporaneous variables, TS-BOSS offers a scalable solution for high-dimensional time series causal discovery, a critical need in fields like neuroscience, economics, and Earth system science.
Future Directions: The work highlights the need for further theoretical guarantees regarding score consistency in sliding-window settings (non-i.i.d. data) and suggests that permutation-based methods may offer better parallelization opportunities for large-scale systems.

In summary, TS-BOSS represents a significant advancement in time series causal discovery, offering a robust, scalable, and theoretically grounded approach that excels in high-autocorrelation environments where traditional methods falter.