Learning Causal Structure of Time Series using Best Order Score Search

Irene Gema Castillo Mansilla, Urmi Ninad · 2026

Read Learning Causal Structure of Time Series using Best Order Score Search by Irene Gema Castillo Mansilla, Urmi Ninad (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05370.txt.

Introduction

Irene Gema Castillo Mansilla and Urmi Ninad introduce TS-BOSS, a Best Order Score Search extension. Causal learning from observational data matters despite temporal dependence. TS-BOSS searches dynamic Bayesian networks by permutation, caching scores via grow-shrink trees. Guarantees establish TS-BOSS soundness and dynamic subgraph minimality. Synthetic experiments show TS-BOSS excels in high auto-correlation regimes, with higher recall than constraint-based methods. TS-BOSS offers scalable time series causal discovery, bridging sparsity-based, permutation-driven theory to dynamic settings.

Catalog record

CREATORIrene Gema Castillo Mansilla, Urmi Ninad
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46982
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.05370

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Causal Structure of Time Series using Best Order Score Search Irene Gema Castillo Mansilla, Urmi Ninad Abstract Causal structure learning from observational data is central to many scientific and policy domains, but the time series setting common to many disciplines poses several challenges due to temporal dependence. In this paper we focus on score-based causal discovery for multivariate time series and introduce TS-BOSS, a time series extension of the recently proposed Best Order Score Search (BOSS) ( 1 ) . TS-BOSS performs a permutation-based search over dynamic Bayesian network structures while leveraging grow–shrink trees to cache intermediate score computations, preserving the scalability and strong empirical performance of BOSS in the static setting. We provide theoretical guarantees establishing the soundness of TS-BOSS under suitable assumptions, and we present an intermediate result that extends classical subgraph minimality results for permutation-based methods to the dynamic (time series) setting. Our experiments on synthetic data show that TS-BOSS is especially effective in high auto-correlation regimes, where it consistently achieves higher adjacency recall at comparable precision than standard constraint-based methods. Overall, TS-BOSS offers a high-performing, scalable approach for time series causal discovery and our results provide a principled bridge for extending sparsity-based, permutation-driven causal learning theory to dynamic settings. \arxivauthor University of Potsdam, Potsdam, Germany and Department of Computer Science, University of Potsdam, Potsdam, Germany keywords Causal discovery, score-based methods, time series, BIC score 1 Introduction Learning the causal structure underlying observational data is fundamental across a wide range of disciplines, from policy-relevant fields such as economics and epidemiology to natural sciences including neuroscience and Earth system science. Causal structure learning methods can be broadly categorized into constraint-based and score-based methods. The former make use of conditional independence constraints learned from the data to infer causal relationships, while the latter optimize a consistently-defined score defined over the space of directed acyclic graphs (DAGs). Further methods exist such as restricted structural causal model (SCM) framework which employs assumptions on functional relationships and noise distributions to uncover causal relationships. See 19 ; 28 ; 20 for details on the different approaches and 8 ; 29 for a review. Often, the observational data take the form of time series, with observations at each time point influenced by past observations. The challenges specific to time series causal structure learning, or time series causal discovery , have been discussed at length ( 24 ; 5 ) . For instance, in the setting of a single multivariate time series, temporal dependence violates the i.i.d. assumption, thereby limiting the theoretical guarantees of causal discovery methods and statistical procedures more generally. Several methods spanning the different approaches for causal discovery have been proposed for the time series setting ( 11 ; 26 ; 17 ) , see 2 for a survey. In this work, our focus will be the score-based approach to causal discovery, while presenting experimental comparisons to constraint-based approaches. Recently, best order score search (BOSS), a score-based method for structure learning, was introduced ( 1 ) . BOSS performs a permutation-based search over DAGs and leverages a novel data structure—grow–shrink trees (GSTs)—to cache intermediate computations. BOSS was shown to achieve high accuracy and state-of-the-art performance while maintaining scalability to a large number of nodes. We propose a time series extension of BOSS for causal discovery over multivariate time series data named TS-BOSS . We provide theoretical results for the soundness of TS-BOSS and ablation studies that compare TS-BOSS to the constraint-based method PCMCI+ ( 26 ) for time series causal discovery. Interestingly, our studies illustrate that TS-BOSS outperforms PCMCI+ in the high auto-correlation regime, and generally maintains higher adjacency recall at similar precision. This establishes TS-BOSS as a high-performing and scalable time series causal discovery method. We also provide an intermediate result ( Theorem 5 ) that extends the result of 30 (Theorem 2 and Corollary 2) to the time series (i.e. dynamic bayesian network) setting. This result implies that sparsest permutation-based methods for causal discovery ( 22 ) can be extended to the time series setting under suitable stationarity assumptions. The remainder of this paper is organized as follows: In Section 2 we present the related work, and in Section 3 we provide the general background for the time series causal discovery problem. In Section 4 we present our algorithm TS-BOSS and in Section 5 we provide theoretical results that guarantee soundness of TS-BOSS. In Section 6 we present a simulation study on synthetic data and conclude with a discussion in Section 7 . 2 Related work Greedy Equivalence Search (GES) was an influential early method in score-based causal discovery which leveraged Meek’s conjecture to search greedily over equivalence classes of DAGs ( 6 ) . Causal discovery was presented as a search problem over permutations that yield the sparsest DAG in 22 with the sparsest permutation (SP) algorithm. 27 ; 12 proposed greedy score-based approaches for the permutation search over DAGs and 1 proposed an efficient algorithm within the same class of methods using Grow-Shrink trees. 33 algorithm presented the search over space of DAGs as a continuous optimization problem, and 17 extended this work to the dynamic setting. Several other continuous optimization-based methods and perspectives thereon have been proposed since then ( 4 ; 23 ; 16 ) . Recently, 32 proposed a discrete-search based method using a modified grow-shrink procedure that provides significant speed-up as graph size increases. In the dynamic setting, 26 proposed a constraint-based causal discovery algorithm for time series using a modified conditional independence (CI) test to mitigate the effects of ill-calibrated CI tests in the single multivariate time series setting while allowing for contemporaneous edges. In 13 , a hybrid constraint and score-based method for time series causal discovery with latent confounders was introduced, that uses GES as a model selection step. 3 Time Series Causal Discovery 3.1 Preliminaries and Problem Setup Let \mathbf{X}_{t}=(X_{t}^{1},\dots,X_{t}^{m}) denote a vector of m random variables observed at discrete time points t\in\mathbb{Z} . The collection (\mathbf{X}_{t})_{t\in\mathbb{Z}} is called a multivariate time series . We assume that dynamical processes that are representable as multivariate time series can be modeled as a time series SCM (or ts-SCM): X^{j}_{t}:=f^{j}(\text{Pa}(X^{j}_{t}),\eta^{j}_{t})\qquad\forall\ X^{j}_{t}\in\mathbf{X}_{t}\ \text{ and }\ \forall\ t\in\mathbb{Z}\ , (1) with ‘ := ’ denoting structural assignments. Here, each f^{j} denotes the causal mechanism corresponding to X^{j}_{t} that models each X^{j}_{t} in terms of the parents of X^{j}_{t} , denoted by \text{Pa}(X^{j}_{t}) , and the random variable \eta^{j}_{t} which is the noise associated to X^{j}_{t} . For each t\in\mathbb{Z} , the noises \bm{\eta}_{t}=(\eta_{t}^{1},\dots,\eta_{t}^{m}) are assumed to be jointly independent. Furthermore, for each i\in[m] , the noises \bm{\eta}^{i}=(\eta_{t}^{i})_{t\in\mathbb{Z}} are assumed to be i.i.d.. The time series SCM Eq. 1 entails a time series graph with nodes X^{i}_{t} for all i\in[m] and for all t\in\mathbb{Z} , and directed edges from a node X^{i}_{t} to a node X^{j}_{t^{\prime}} if and only if X^{i}_{t}\in\text{Pa}(X^{j}_{t^{\prime}}) , for all i,j\in[n] and t,t^{\prime}\in\mathbb{Z} such that (i,t)\neq(j,t^{\prime}) . The condition (i,t)\neq(j,t^{\prime}) excludes self-cycles in the time series graph, and we additionally exclude general directed cycles. The resultant graph is referred to as a time series directed acyclic graph or a ts-DAG ( 7 ) . The concept of d-separation of two disjoint sets of vertices given a third extends naturally to ts-DAGs

Read the complete text