Arrow: Accelerator for Time Series Causal Discovery with Time Weaving
Authors: Yuanyuan Yao
Yuan Dong
Lu Chen
Kun Kuang
Ziquan Fang
Cheng Long
Yunjun Gao
TIANYI LI
Venue: ICML 2025 poster (2025)
Keywords: time series
causal discovery
accelerator
Primary area: general_machine_learning->causality

Abstract: Current causal discovery methods for time series data can effectively address a variety of scenarios; however, they remain constrained by inefficiencies. The significant inefficiencies arise primarily from the high computational costs associated with binning, the uncertainty in selecting appropriate time lags, and the extensive sets of candidate variables. To achieve both high efficiency and effectiveness of causal discovery, we introduce an accelerator termed ARROW. It incorporates an innovative concept termed “Time Weaving” that efficiently encodes time series data to well capture the dynamic trends, thereby mitigating computational complexity. We also propose a novel time lag discovery strategy utilizing XOR operations, which derives a theorem to obtain the optimal time lag and significantly enhances the efficiency using XOR operations. To optimize the search space for causal relationships, we design an efficient pruning strategy that intelligently identifies the most relevant candidate variables, enhancing the efficiency and accuracy of causal discovery. We applied ARROW to four different types of time series causal discovery algorithms and evaluated it on 25 synthetic and real-world datasets. The results demonstrate that, compared to the original algorithms, ARROW achieves up to 153x speedup while achieving higher accuracy in most cases.

ARROW: Accelerator for Time Series Causal Discovery with Time Weaving
Yuanyuan Yao
Yuan Dong',
Lu Chen
Kun Kuang' Tianyi Li
Ziquan Fang'
Cheng Long?
Yunjun Gao
Abstract
120
2000
Current causal discovery methods for time series data can effectively address a variety of scenarios; however, they remain constrained by inefficien- cies. The significant inefficiencies arise primarily from the high computational costs associated with binning, the uncertainty in selecting appropriate time lags, and the extensive sets of candidate vari- ables. To achieve both high efficiency and ef- fectiveness causal discovery, we introduce an accelerator termed ARROW. It incorporates an innovative concept termed "Time Weaving" that efficiently encodes time series data to well capture the dynamic trends, thereby mitigating computa- tional complexity. We also propose a novel time lag discovery strategy utilizing XOR operations, which derives theorem obtain the optimal time lag and significantly enhances the efficiency using XOR operations. To optimize the search space for causal relationships, we design effi- cient pruning strategy that intelligently identifies the most relevant candidate variables, enhancing the efficiency and accuracy of causal discovery. We applied ARROW to four different types of time series causal discovery algorithms and evaluated it 25 synthetic and real-world datasets. The results demonstrate that, compared to the original algorithms, ARROW achieves up to 153x speedup while achieving higher accuracy in most cases.
Time
Time
1000
30-
500
0
20
40
60
80
100
Bins
(4) The case study of high cost binning
(b) The case study of time lag
Figure I. Case Study
Yao et al., 2024c). Causal discovery not only deepens our understanding of dynamic relationships among multiple variables (Zhao et al., 2023) but also provides scientific evidence to solve practical problems (Castro et al., 2023; Martinez-Sánchez, et al., 2024; Huang et al., 2019). For example, Alzheimer's disease research, exploring causal interactions between brain regions can help reveal patho- logical mechanisms and optimize treatment strategies (Liu et al., 2024). Furthermore, the study of causal relationships can assist downstream tasks (e.g., forecasting, anomaly de- tection, etc.) (Qiu et al., 2024; 2025; Yi et al., 2024; Xia et al., 2025; Yao et al., 2023; 2024b). By discovering causal relationships within multivariate time series, deeper feature information be provided, considerably enhancing the performance and accuracy of downstream tasks. This causal- driven analysis method is becoming one of the core tools for solving complex time series problems. Recent research in the field time series causal discovery has effectively re- vealed causal relationships under different conditions. How- ever, through case studies conducted on various methods and datasets, found that significant bottlenecks still exist in terms of efficiency due to the following limitations:
1. Introduction
High Computational Costs of Binning, Currently, most causal discovery methods (Runge, 2018; Runge et al., 2019; Martínez-Sánchez et al., 2024) rely on statistical techniques such as conditional independence testing and mutual information, often using discretization (i.e.. bin- ning) of continuous numerical data for analysis. A major issue with this approach is that the computational com- plexity of independence testing increases significantly as the binning granularity becomes finer, as shown in Fig- ure (a)) especially when dealing with large-scale time series data. Additionally, the above moniig-bbssed meth- ods struggle to capture dynamic causal structures.
Learning the causal relationships on multivariate time se- ries holds significant practical value the field of time series mining (Assaad et al., 2022; Zhou Chen, 2022:
'The College of Computer Science, Zhejiang University, Hangzhou 310027, China *College of Computing and Data Sci- ence, Nanyang Technological University, Singapore "The Depart- ment of Computer Science, Aalborg University, Denmark. Corre- spondence to: Lu Chen <luchen ej..edu.cn>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Accelerator for Time Series Causal Discovery with Time Weaving
Uncertainty in Appropriate Time Lag Selection. The selection of time lag has a significant impact on the results of most causal discovery methods (Hyvärinen et al., 2008). However, current methods Martinez-Sánchee et al.,, 2024; Gerhardus & Runge, 2020) usually rely on brute-force search, where all possible time lag values are traversed to construct the best summary graph. This approach has clear drawbacks: first, the Brute-Force search results in an unacceptable computational time when dealing with large- scale time series data as shown in Figure I(b); second, it lacks theoretical mechanism to determine the optimal time lag to generate the best summary graph, thus making the results less convincing and reliable. For example, when applying the PCMC/ algorithm to dataset with a time lag of 6, identifying the correct time lag can achieve an accuracy of up to 0.99. However, an incorrect time lag 5 may result in an accuracy drop of 49%.
intelligently selecting the most promising candidate set, rather than considering all variables in the candidate parent node set. By focusing on the variables that contribute most to causal discovery. we can effectively reduce the size of the search space, improving the efficiency and accuracy of causal relationship discovery. We applied ARROW to four different types of causal discovery algorithms. Experimental results on 25 synthetic and real-world datasets demonstrate that ARROW significantly enhances efficiency while main- taining the original performance of the algorithms.
2. Related work
Time series causal discovery algorithms. Mainstream time series causal discovery methods include constraint- based (Runge et al., 2019; Runge, 2020; Entner & Hoyer, 2010; Gerhardus & Runge, 2020), score-based (De Campos & Ji, 2011; Gao et al., 2022; Pena al., 2005; Hyvärinen et al., 2010), granger-based (Tank al., 2021; Xu et al., 2019; Marcinkevičs & Vogt, 2021; Wang et al., 2018; Xu et al., 2016), and information-theorel (Martinez-Sánchez et al., 2024; Chaves et al., 2015) approaches. Constraint- based methods constrain the causal structure using condi- tional independence tests, relying on statistical and condi- tional independence to infer causal relationships by remov- ing non-directly related edges and applying directional rules (such as d-separation (Liu et al., 2024)). Score- based meth- ods quantify model fit and complexity by defining scoring functions (Neath & Cavanaugh, 2012: Burnham & Ander- son, 2004) and use search strategies (such as greedy search) to find the optimal directed acyclic graph (DAG) in the model space. In contrast, Granger- methods utilize the lag effect in time series data, determining if one variable sig- nificantly explains the changes in another variable through linear regression or forecasting performance, thus inferring causal relationships. Information -thooreticc methods infer causal relationships by calculating the information gain or mutual information between variables, offering advantages in handling nonlinear relationships, multivariate dependen- cies. and robustness to noise. While these four types of methods can effectively address causal discovery under dif- ferent conditions, they remain constrained by inefficiencies. We aim to propose general acceleration solution that can address the current efficiency issues in causal discovery.
Extensive Sets of Candidate Variables. Current causal discovery algorithms (Martínez-Sínchezze et al., 2024; Tank et al., 2021) typically utilize different combinations of all variables to form candidate sets. As the number of vari- ables increases, the size of the candidate parent node set grows exponentially. For instance, given d variables, 2d tests are required; if T time lag needs to be determined, the number of tests increases to 2dT, The dimensional- ity explosion of the candidate set can compromise the accuracy of causal discovery by obscuring true causal relationships (Runge et al., 2019).
Our approach: To address these limitations, we propose time series causal discovery accelerator called ARROW. This accelerator can seamlessly integrate with most time series causal discovery algorithms, significantly improving efficiency without compromising the performance of the original algorithm. The key idea is to capture the contextual trends of a value in a binary tuple. Based on the binary representation, we can efficiently and effectively extract time lags and uncover causal relationships.
We first introduce time weaving, an innovative method for encoding individual time points. This method divides the data into the smallest units with contextual information by considering the trend changes between three consecutive points the time series; each unit represents the trend be- tween these three points. Here, we use 1 bit to represent the trend between two consecutive points, where indicates an upward trend and 0 represents downward trend. Based the time-weaving encoding, we analyze the patterns of trend changes between variables using XOR operations and de- rive a theorem to determine the optimal time lag ( (Yao et al., 2024a). Specificallyy when determining time lag, we first rank the potential causal relationships between variables, and then select a representative subset based on the ranking results. Finally, we propose an efficient pruning strategy. This strategy optimizes the causal relationship search by
Acceleration strategy. Current acceleration methods are mainly based on hardware acceleration, including CPU- based (Le al., 2016; 2018: Madsen et al., 2015; Schmidt et al., 2019), GPU-based (Zarebavani et al., 2019; Hagedorn & Huegle, 2021: Schmidt et al., 2018; Hu et al., 2021), and (Guo & Luk, 2022; Guo et al.. 2023b;a) ap- proaches. For instance, Par (Le et al., 2016; 2018) is the first method to implement parallel causal discovery, where the core idea is to execute conditional independence
2

---

Accelerator for Time Series Causal Discovery with Time Weaving
H
t+
For each SCM, we can construct a directed acyclic causal graph (DAG) G by associating vertex with each 2; and directing edges from each parent variable in (a();) (the causes) to the corresponding child 2; (the effect).
P
R
T
H
In the causal graph of SCM, each variable is conditionally independent of its non-effects, given its direct causes (Pearl, 2009). In other words, variable is independent of variables that do not directly influence it, once its parents (i.e., direct causes) are known. This principle is crucial for causal dis- covery as it allows the identification of causal effects from observational data. Formally, the causal Markov condition asserts that the joint distribution can be factorized as:
W
W
(a) DAG
(h) Summary graph
Figure 2. An example of DAG and Summary graph
(CI) tests in parallel. cuPC (Zarebavani et al., 2019) is the first method to accelerate causal discovery using GPUs, and it employs a lossless transformation of the PC-stable algo- rithm with two optimizations: first, if a CT test between a pair of variables returns true, cuPC immediately cancels all remaining tests; second, CT tests with the same condition- ing set are executed within the same local thread, reducing thread management costs. gpuPC (Hagedorn & Huegle, 2021) is GPU-based tool designed for discrete data, and its CI tests require auxiliary data structures (e.g., contin- gency tables), which consume substantial GPU memory. CSF (Guo & Luk, 2022) is the first FPGA-based acceler- ation method for constraint-based causal discovery, effec- tively utilizing FPGA on-chip storage and parallel process- ing capabilities while reducing communication costs. The CSF implementation achieves higher speed than cPU-based and GPU-based approaches. These hardware acceleration methods primarily address efficiency issues in CI (Runge, 2018; Spirtes et al., 2001) independence testing, but they are not universally applicable, especially for score-based methods. In contrast, the acceleration method we propose is based on data-level optimization, making it more general and applicable to all causal dis- covery methods. It can also be combined with hardware acceleration methods to further enhance efficiency.
IVI P(x) = II (z; (a;))
We study the problem of causal discovery on time series. Thus, we first define the multivariate time series below.
Definition 3.1 (Multivariate Time Series). A multivari- ate time series (MTS) X with d variables is defined as: X = {x = {(a], .r..... ................................ ,²²) TT where / repre- sents a discrete time point, T is the total length of X in the time dimension, and each x" is d-dimensional vector (zf, Z5.. <²²) at time point t. Assumption 3.2 (Markov Property). The Markov prop- erty of time series assumes that the future slice x de- pends on the current state x² but does not depend on the history .e......'"")) ), i.,, P x²,x' x!) P(x++1 xxt) (Figueiredo et al., 2018).
Definition 3.3 (Time Lag). Causal effects do not occur instantaneously, but rather unfold gradually over time for MTS (Peters et al., 2013). Given x = [x() : uu), where k represents the time lag, indicating that the impact of x; on Xj is delayed by & time points.
and Granger-
Combined with the Assumption 3.2, we focus on exploring causality in MTS with time lag k. where the current point x' is influenced by the value x Notably, different pairs of variables may exhibit distinct time lags in some cases.
3. Preliminaries and Background
A Structural Causal Model (SCM) is a graphical represen- tation that illustrates causal relationships, capturing how interventions on one or more variables affect the values of other variables within the data generation process (Pearl, 2009; Gong et al., 2023). Formally, an SCM is repre- sented as a 4-tuple (V, U, F, P(U)), where V and U denote the sets of endogenous and exogenous variables, respec- tively, P(U) represents the distribution of exogenous vari- ables, and F is the set of mapping functions. Specifically, each endogenous variable is formally defined by the model (1,..., ,IV]), where |V| denotes the number of endogenous variables, while PA(x.) repre- sents the set of parents of x; and (A(x;) C U... The function f. E F denotes a function between its structural parents PA (z:).
Definition 3.4 (Summary Graph). Let G == (V, E) be the associated summary graph of an SCM model (Peters et al., 2013). The vertex set V = X, the edge set E contains x; + xi iff x; E PA(x)).
The primary goal of time series causal discovery is to con- struct summary graph that intuitively represents the causal relationships between different variables.
Definition 3.5 (Causal Discovery from MTS). Given MTS data X, assume that causal relationships between vari- ables are given by the following structural equation model: 2y (t := (PA( PA is the set of direct parents of x t-k N₁ denotes the independent noise and can represent either measurement
x; = ((PA(():)
N.), i = {1...., d), 0 < k < T,
3

---

Accelerator for Time Series Causal Discovery with Time Weaving
noise or driving noise without losing generality. Causal discovery from MTS aims to find the Summary Graph.
time delay. This change in value effectively reflects the variable's trend. Based on this observation, we propose new concept termed Time Weaving to capture the local dynamic characteristics between time points. It encodes a specific time point via the trend changes of its preceding and succeeding points. This approach preserves the core characteristics of individual time points while integrating the local contextual relationships within the time series. We formally define Time Weaving below.
adja- cency matrix A E Zddd, The (i, (-th entry of the matrix A is if past observations of 2;; affect a/y, and 0 otherwise. We say that '2y causes zj" if Aij = 1.
Note that, the summary graph can be denoted
We propose an SCM for air quality causal discovery. The model includes three endogenous variables (i.e,, air pollution concentration P. temperature T, and hu- midity H), and two exogenous variables (wind speed W and precipitation R). The model can be represented as a 4-tuple SCM = (V,U, F, P(U)). where V = {P.T, H the endogenous variables, U = (W, R} are the exoge- nous variables, F represents the mapping functions, and P(U) is the joint distribution of exogenous variables. The air pollution concentration P is influenced by temperature, humidity, wind speed, and precipitation, with the functional relationship given by P: == (T(T H W,- R2-1); The temperature T is influenced by its own previous value and humidity, expressed T. :- (T, H,-1) 1): The hu- midity H is affected by temperature. its own previous value, and precipitation, represented as H, := (H,,1, Rt-1)- The causal relationships based on SCM are illustrated in the following directed acyclic graph (DAG) as shown in Figure 2(a), where each directed edge indicates the causal dependency between variables at different time points.
Example 1.
Definition 4.1 (Time Weaving). Given a MTS data with d variables, denoted as X (14,,25,..... ) We introduce a weaving window w and represent a (1 S isis d and w S S T -T--wi w) us- ing its trend tr relative to the values x and x; f+1w (t - w)th and (++w) timestamps, i.c., x can be encoded as (tr, - w. f), tra(t, t w)). Specifically, the trend tr, t') equals to if of > xr! otherwise ir; (1, L') = O, where / and E' are arbitrary time points. Therefore, the time weaving value Xtw of X is defined as list of tuples:
at the
Xtw = =((r (t w. 1) tr (t, 1 + +)))
(1)
where tr = (tri,...,tra tra)-
Example 2. Given MTS data X with d = 3 variables and sequence length of T 5 shown in the Figure 3(a):
0.23
2.89
2.01
2.31
1.89
X =
1.01
1.78
1.21
0.35
1.31
The summary graph depicted in Figure 2(b) represents con- densed version of the directed acyclic graph (DAG) (Vowels et al., 2022) shown in Figure 2(a). In this summary graph, the vertices correspond to the variables, while the edges capture the direct causal dependencies between them.
-..2
-0.88
0.13
1.37
0.03
Assume that the weaving window w = 1. For the value 21 2.89 at t = 1 in the first variable, its trend encoding relative to t - w = 0 and t + w = 2, and thus, it can be encoded as (1, 0), as tri (0, 1) = =1 and tri (1, = O. Similarly, for the value x2 = 1.78, its trend weaving value is (1, 0), as fr2 = and tr = O. Thus, the time weaving representation of X at = 1: X (1, (1,0), (0, 1)) The overall X of X is:
Our problem. The main focus of our paper is not on the causal discovery algorithms themselves but on addressing the efficiency challenges in MTS causal discovery, caused by the high computational cost of binning, the uncertainty in time lag selection, and the extensive sets of candidate vari- ables. Different from the hardware-level acceleration, we aim to develop a data-level acceleration framework that enhances the efficiency of any causal discovery algorithm while preserving its accuracy.
[1.0)
(0.1)
(1,0)
X Xtw =
(1,0)
(0.0)
(1,0)
(0.1)
(L.1)
(0,
Time weaving is the key component of the causal discov- ery of the time series accelerator termed ARROW. In this way, we transform the values of the time series into tuples composed of binary and 1. This transformation not only discretizes continuous time series values into 0 and 1, elimi- nating uncertainties in bucketization but also enhances the consistency and efficiency of data processing. Furthermore, after the transformation of the time-weaving, the data in- corporates contextual information, no longer representing a single value, which improves the effectiveness of causal discovery. The time weaving format can be directly used for downstream causal discovery algorithms.
4. ARROW Method
We proceed to detail our adaptive accelerator ARROW, in- cluding three components (i.e., time weaving, time lag dis- covery, and candidates pruning) as shown in Figure 3.
4.1. Time Weaving
For two variables with a causal relationship, a change in the value of one variable will directly or indirectly cause a change in the value of the other variable after certain
4

---

Accelerator for Time Series Causal Discovery with Time Weaving
1.simllan(00)
(1.0) (0.0) (1.0)
(1.0)
Xor(V,, Va) Xor(V, Va)
(0.1)
(0.1) (1.1) (0.1)
2
(0.0)
(10)
XonVV, Vá)
(1p)
(1.1) (1.1) (1.1)
candidates pruning
00
(0.1)
XOR
k=1
k-2
k-3
10.1 11
1 0.37
3.0Ifferent011100
<V2VV>>
0.21
0.16
0.23
10
30
46
30
3
0.28
<V2
0.26
0.38
0.13
(8) Time weaving
(b) Time lag discovery
(c) Candidates pruning
Figure 3. The overview of ARROW
4.2. Time Lag Discovery
covery strategy aimed at quickly and accurately identifying the specific range of time lags. This strategy effectively detects time delays in causal relationships, helping to reveal complex dynamic interactions.
We observe that if two variables exhibit significant causal relationship at time delay of i; their individual trends at specific time points must align oppose each other. Based on this observation, we need to address two key questions.
Theorem 4.2. Given two variables v and of in a MTS data X. if and v' have causal relationship in time lag k2 then either P(Xor(u, v/, k) = (0, 0)) or P(Xor(v; v', k) (1, 1)) will exceed 1 - C, where c is a value approaching O. 3
Q1: How to define the relationship between their trends?
Q2: How to use the trends to identify the time lag?
To address QI, we first define the trend of a point of us- ing the concept of time-weaving, categorizing it into three distinet states: (0,0), (1,1), and (1,0)/(0.1). As illustrated in Figure 3(b), the relationship between two points can be described by one of ten possible pairwise combina- tions: (0,0)-(0,0), (0,0)-(0,1), (0,0)-(1,0), (0,0)-(1,1), (0.1)- (1.)) (1,0)-(1.1), and (1,1)-(1,1). Here, the pairwise combination is symmetric, i.e. (0,0)-(1.0) equals to (1,0)-0,,)) When the trends of the two points are either fully aligned or completely op- posite-such as (0,0)-(0,0), (0,0)-(1,1), (0,1)-(0,1), (0,1)- (1,0), or (1,0)-(1,0) their XOR operation will yield re- sults like '00 A 00 00' or '10 A 01 = 11', which are always either '00' (indicating similarity) or '11' (in- dicating opposition). On the other hand, if the trends are only partially aligned-for example, (0,0)-(0,1), (0,0)-(1,0), or (1,1)-(1,0))thee thhii XOR operation produces results like '01 A 00 = 01' or '00 A 10 10', which are either '01' or '10' (indicating difference). Therefore, the relation- ship between two points can be classified into three distinct categories based on their XOR results:
The proof is in Appendix B. This addresses Q2, on how to use the trends identify the optimal time lag. In other words, the optimal & value makes either P(Xor(v, v', k) (0, 0)) or P(Xor(u, v', A) (1, 1)) larger than 3 e for any variable pairs with the causal relationship (we set 0.33 in our method). Leveraging the XOR results to determine causal relationships between variables highly efficient due to the use of bitwise operations. Additionally, by integrating the joint distribution with the XOR outcome, this approach accurately identifies optimal time lags, offering an effective and efficient method for uncovering causal relationships.
(0.1), (0,1)-(1,0), (0.1)-(1,1)
4.3. Candidates Pruning
Although the most likely time lag between each pair of variables can be inferred, if there is no causal relationship between e and v', the inferred time lag is likely to be incor- rect. Therefore, to minimize such errors, candidates pruning of the variables is necessary. Algorithm is designed to filter significant variable pairs based on their time-lagged re- lationships in a MTS data. It takes two inputs: X the time weaving representations of X, and Thr, pruning threshold for the percentage of valid variable pairs. The output is set of filtered variable pairs, denoted as C.
Similar (0,0): : The trends are fully aligned.
Opposite (1,1): The trends are completely reversed. Different ((0,1) or (1,0)): The trends show partial align- ment or deviation.
Step 1:
Time Lag Discovery. We first iterate over all pos- sible variable pairs (v, o') from the d variables. For each pair, it evaluates all potential time lags k ranging from to T w + 1, where T is the time series length and is the window size. For each possible lag value k. it computes the XOR operation between two variables to identify patterns in their binary representation. It then calculates the percent- ages of specific binary tuple occurrences (0,0), (1.1), and (0,1) (0,1)/(1,)) and stores them as R0(e, v', Ml. R2(u, o', M.
It solves Q1, on how to define the trend relationship Xor(u, o', k) between two variables e and of in a time lag k. where k indicates the impact of v on v' is delayed by k timestamps (cf. Def. 3.3). Here, Xor(u, of, k) at time is computed via the XOR operation on time-weaving represen- tations of - and D".
To further address Q2, we propose novel time lag dis-
5

---

Accelerator for Time Series Causal Discovery with Time Weaving
Algorithm 1 Candidates Pruning
randomly. For non-linear causal relationships, we adopt the Erdos-Renyi model (Erd6s & Rényi, 1960; Liu al., 2024) to generate the graph structure. Each non-linear SCM is EPA(.,) fijz, (t (86-ki) kay) + No, where fij is randomly chosen from {linear, sin, tanh, sqrí), kij denotes time lag and N, is also noise sampled from the same distributions as in the linear case. In addition to the syn- thetic datasets, we also conduct validation on the real-world Dream3 dataset.
Input: Time-weaving representations of MTS: wes prun-
ing threshold for variable percentage: Thr
Output: Filtered variable pairs: C
defined as: z = -
v Step I: Time lag discovery
1: for any variable pair (v, v') do
2: for any possible time lag & E [1, - w + 1] do
3: Compute (or(u,"") for time lag k
4: Calculate percentages of (0,0), (1.1), and
(0.1)/(1.0) tuples: RO(u,e', ki,, R2[0, k), RI(u, v', 5: end for
Baselines, We select representative algorithm from each of the four causal discovery approaches M for our study: the constraint-based algorithm PCMC/ (Runge et al., 2019; Runge, 2020), the Granger-based algorithm NGC (Tank et al., 2021), the score-based based algorithm VAR- LiNGAM (Hyvärinen et al., 2010), and the information- theoretic algorithm SURD Marttnez--ánchhee et al., 2024). For each algorithm, we compare the performance of the original version with its accelerated counterpart using the Arrow accelerator, focusing improvemets in both effi- ciency and accuracy. Detailed descriptions of the methods can be found in Appendix C.I.
6: end for
7: R(u, v', k] t- maxx e', R2[u, v' kl)
8: Identify (v, and k with the highest value in
Rlu, o', kl, and store as C' < {(v,e')
V Step 2: Variable candidates pruning
9:
for each candidate (v, v²) in C do
10:
if R(u, o'1 > 0.33 and |C| < Thr dl then
11:
Retain (')
12: else
13:
Remove (v, o') from C
14:
end if
Metrics, We evaluate the efficiency of causal graph gen- cration based on runtime (in seconds). Additionally, their time lag discovery and causal graph generation performance is assessed using three metrics: True Positive Rate (TPR), False Positive Rate (FPR), and Area Under the Curve (AUC). Details are shown in Appendix C.2.
15: end for
and R1 [u, v', k] (lines 1-5). For each time lag, the algo-
rithm selects the maximum value between ROju, o', k] and R2(v, v', k] R[e, v', k] (line 7). The variable pairs and their corresponding time lags with the highest Rfv, o', k] values are stored in the initial candidate set C (line 8).
Settings, We synthesized a dataset with 10 variables and a time length of 1000. The window size w for time weaving was set to 1. In addition, we conducted experiments with constant time lags and multiple time lags. For the constant time lags, the lags between variables is fixed, and can be selected from the set (3, 5, 7, 9, 15, 20). In contrast, the multiple time lags represent varying lags between variables, with the lag value being chosen from the set {3, 5, 7, 9, 15, 20} as the range for the time lags. The experiments on varying time-lagged edges are deferred to Appendix D, while in the main experiments, we set h: to (5, 15). The source code of ARROW is available
Step 2: Variable Pairs Pruning. We further filter the candidates in C. For each candidate pair (u, v'), it checks two conditions: (1) whether the value of Riu, o'] exceeds 0.33, and (2) whether the total number of candidates |C| is below the threshold Thr d2, If both conditions are met, the pair is retained in the final set; otherwise, it is removed (lines 10-14).
This algorithm analyzes time-lagged relationships in a mul- tivariate time series to filter significant variable pairs. It computes XOR values to evaluate patterns and prunes re- sults based on predefined thresholds, ensuring only the most relevant variable pairs retained in the output.
5.2. Overall Performance
Efficiency Evaluation. For MTS data with linear causal relationships, as shown in Table 1, ARROW significantly improves the efficiency of causal discovery because its ac- celeration strategy efficiently reduces the search space for time lag and variable candidates, streamlining the compu- tation process. SURD with ARROW achieves remarkable acceleration, with a nearly 70x speedup observed on the SURD dataset. This primarily due to its ability to preemp-
5. Experiments
5.1. Experimental Setting
Datasets. We generate random summary graphs to simulate causal relationships using both linear and non- non-linear struc- tural causal models (SCMs). For linear causal relationships, the SCM defined as: af = Σx, Ex,EPA( Oijzy (I kig) + N,, where 0ij is a constant, kij denotes the time lag, and N2 is noise selected from {uniform, gauss, exp, gamma}
http:///www.ssnnnpr.....//yayxxp http://gthbb.ommiiiggguuuuuunu
6

---

Accelerator for Time Series Causal Discovery with Time Weaving
Table 1. Performance the datasets with linear casual relationships
Constant Lags
Time lag
5
15
Metric
Time
Lag 1
Graph AUC f
Time J
Lag AUC t
Graph AUC 1
PCMCI
245.99+15.85
0,9350#0.053
0.916940.067
266.55#19.85
0,9275#0.033
0,9088#0.043
PCMCI+ARROW
6.673420.026
0.9775=0.018
0.9863+0.013
6.696920.021
0.9725+0.018
0.9906:0.010
SURD
424.90#1.837
0.5000#0,000
0.5038+0.000 0008
422.59+0.677
0,5000#0.000 0000
0,5200=0.017
SURD+ARROW
6.165620.013
0.9825#0.016
0.964420.013
6.187410.022
0.9700=0.042
0.963620.072
NGC
12.905+0.317 0.5000#0.000
0.7513=0.088
12.946#0.293
0.5000=0.000
0.805620.040
NGC+ARROW
0.7971=0.056 0.9750=0.027
0.9975+0.008
0.7931#0.066
0.9850=0.017
0.9906#0.018
VARLiNGAM
9.724420.439 0,9800=0.022
0.9606#0.021
9.3213#0.16 164
0,5000#0.000
0,4956+0.001
VARLINGAM+ARROW
6.2020=0.013
0.9775#0.021
0.9819#0.014
6.266410.015 0.9850=0.023
0.9281+0.062
Multiple Lags
Time lag
5
15
Metric
Time +
Lag AUC f Graph AUC
Time +
Lag AUC f
Graph AUC 1
PCMCI
388.41=83.10
0.7550
0.738110.040
441.16455.09
0.6575+0.045
0.636940.067
PCMCI+ARROW
6.4486+0.031
0.8050=0.029
0.8088#0.030
6.4285+0.029
0.9125:0.023
0.9250=0.012
SURD
425.72=00875
0.5050+0.010
0.5369H0.026
428.54+1.353
0.500010.00
0,518110.017
SURD+ARROW
6.1871+0.033
0.8925#0.016
0.9025+0.014
6.1711=0.024
0.9550=0.019
0.9394+0.023
NGC
13.043+0.339 0.5025#0.008
0.8263#0.046
13.021#0.2778
0.5025=00007
0.7688+0.031
NGC+ARROW
0.7482+0.014 0.8800#0.027
0.946920.036
0.7477+0.013
0.8775#0.028
0.9638+0.027
VARLiNGAM
9.1697=0.155 0.9925#0.016
0.9856#0.018 9.305410.129 0.610010.051
0.6100#0.051 0.829420.135
VARLINGAM+ARROW
6.2439+0.037
0.8900#0.025
0.8388#0.100 107
6.2743+0.044 0.885020.000
tively filter and prioritize candidate lags, avoiding exhaus- tive searches that slow down the original algorithm. Ad- ditionally, ARROW'S s acceleration strategy ensures greater stability compared to the original algorithm because it ap- plies the same optimization method for both constant lags and multiple lags settings, thereby minimizing variations in performance. VARLiNGAM outperforms other algorithms in terms of rumning time due to its Independent Component Analysis (ICA) strategy, but it still requires traversing the time lag range to find the optimal time lag. In contrast, VARLiNGAM with ARROW avoids the traversal to further accelerate the entire process. Note that, although ICA ac- celerates the casual discovery of VARLiNGAM, it is not a general optimization technique, which cannot be applied to other types of methods. Thus, our ARROW is a general accelerator that can significantly improve the efficiency of causal discovery on all the methods.
extensions are required, which significantly increase the computational cost.
Effectiveness Evaluation in Time Lag Discovery. As shown in Tables 1 and 2,ARROW consistently outperforms the original algorithm in terms of AUC for time lag discov- ery (i.e., Lag AUC) in most cases, when handling linear or nonlinear causal relationships across various lag sizes in both constant and multiple lags settings. This perfor- mance improvement is particularly noticeable the SURD algorithm, where the maximum improvement reaches 46%. This is because: (i) as the number of variables increases, the conditional probability distribution computed by SURD tends to dilute the relevant variable information; (ii) the brute-force search method does not guarantee the discovery of the optimal time lag if "optimal" is not well defined. In addition, VARLINGAM with Arrow performs worse than VARLiNGAM when the time lag is small, primarily because VARLINGAM is suited for data with non- Gan-Gassiinn noise, while the time weaving representation of Arrow may in- fluence the original noise distribution, affecting the perfor- mance. However, when the time lag is larger, the robustness of causal relationships between variables is enhanced, sig- nificantly reducing the interference of the time weaving
Similarly, when dealing with nonlinear causal relationships, ARROW'S acceleration strategy still demonstrates significant efficiency as shown in Table 2, especially for PCMCI. This is because PCMCI uses partial correlation for CI test, which is more suited for linear causal relationships. When han- dling non- non-linear causal relationships, additional non-linear
7

---

Accelerator for Time Series Causal Discovery with Time Weaving
Table 2. Performance on the datasets with non-linear casual relationships
Constant Lags
Time lag
15
Metric
Time L
Lag 1
Graph AUC 1
Time L
Lag AUC
Graph AUC f
PCMCI
1310.74304.4
0.9156+00,0 0.4
0.9029#0.054
996.89+182.9
0.8772+00.055
0.8595#0.051
PCMCI+Arrow
9.613243.044
0.9342+0.035
0.8999#0.037
22.925=18.55
0.9167=0.046
0.8882#0.042
SURD
424.14+0.443
0.5000=0.000
0,5000+0.000
428.09#1.220
0.5000#0.000
0,4991=0,0199
SURD+ARROW
6.3629:00059
0.9470=0.039
0.7310::.109
6.384420.145
0.931520.048
0.7642#0.060
NGC
12.980#0.318 0.5000#0.000
0.4391#0.003
12.960=0.293
0.500000.000
0.440620.001
NGC+ARROW
0.7430%0.013
0.9563#0.036
0.4485+0.033
0.7415=0.013
0.9131#0.047
0.3889#0.075
VARLINGAM
9.0475=0.171 0.9944+0.011
0.9834:0.013
9.0925#0.104
0,5000+0.000
0.4970=0.013
VARLINGAM+ARROW
6.2198+0.021
0.9133+0.057
0.897440.020
6.2424+0.021
0.9352#0.053
0.9057#0.022
Multiple Lags
Time lag
15
Metric
Time 4
Lag AUC 1
Graph AUC 1
Time +
Lag AUC 1
Graph AUC f
PCMCI
1076.7+196.8
0.655+0.068
0.6651#0.075
1368.8+222.4
0.6575+0.048
0.6368+0.067
PCRO
7.6967#1.387
0.877420.058
0.834420.059
16.591=13.15
0.915720.063
0.868020.066
SURD
426.65#11340
0.5063+0.013
0,4915=0.013
423.3420.14
0,5000#0.000
0,4840+0.010
SURD+ARROW
6.1981+0.032
0.8836+0.030
0.7108#0.046
6.2153+0.036
0.9477=0.049
0.6877+0.060
NGC
13.155+0..40 0.5000+0.000
0.437940.002
12.906#0.304
0.5000+00000
0.4398+0.003
NGC+ARROW
0.7410=0.013 0.8916#0.090
0.4382+0.004
0.7478=0.014
0.8983+0.033
0,4060#0.017
VARLINGAM
9.0378+0.129 0.9292+0.077
0.9198+0.073
9.0330+0.191
0.5549+0.054
0.560940.052
VARLINGAM+ARROW
6.2423:0.014
0.8135#0.047
0.906440.038
6.293410.026
0.8931=0.044
0.9122#0.023
representation on the original distribution.
0.75
480
Effectiveness Evaluation in Summary Graph Genera- tion. Similar to the performance in time lag discovery, the AUC for summary graph generation (i.e., Graph AUC) also outperforms the original algorithm, as shown in Tables and 2. This improvement benefits from ARROW'S strategies in time lag discovery and candidate pruning. In addition, the improvement is consistent across datasets with both con- stant lags and multiple lags settings, handling both linear and nonlinaar causal relationships, demonstrating ARROW'S 's ro- bustness and efficiency in generating reliable causal graphs.
0.60
Time (s)
420
0.45
12.
PCMCI
SURD
NGC
VARLINGAM
M
Figure 4. Causal discovery performance on Dream3
Furthermore, in terms of summary graph performance, AR- ROW successfully retains the performance of the original algorithms and even achieves better results on the VAR- LiNGAM method. This is because VARLiNGAM is suitable for datasets with non-Gaussian noise while the Dream3 dataset contains heterogeneous noise components.
5.3. Experiments on the Real-world Dataset
We validate the acceleration performance of the ARROW framework on the real-world time series dataset Dream3. The results as shown in Figure demonstrate that ARROW achieves 7x 300x speedup across various methods, with particularly remarkable performance on the SURD method. This is because the SURD method relies on a brute-force approach for time lag selection, whereas ARROW signifi- cantly improves search efficiency and accuracy through its optimized time lag mining algorithm and pruning strategy.
6. Conclusion
We propose general accelerator for time series causal dis- covery algorithms termed ARROW. First, we introduce a novel concept called "Time Weaving", which transforms
8

---

Accelerator for Time Series Causal Discovery with Time Weaving
data from single time point into a binary tuple with con- textual information. Next, we propose a time lag discovery strategy that analyzes contextual trend patterns between dif- ferent variables. We derive a theorem to find the optimal time lag and provide rigorous proofs. Additionally, we de- velop a variable candidates pruning algorithm to effectively reduce the candidate set for causal discovery, further improv- ing computational efficiency. Finally, experiments on both synthetic and real datasets demonstrate that ARROW can significantly accelerate various causal discovery algorithms while maintaining high accuracy.
De Campos, C. P. and Ji, Q. Efficient structure learning of bayesian networks using constraints. The Journal of Machine Learning Research, 12:663-689, 2011.
Entner, D. and Hoyer, P. O. On causal discovery from time series data using fei. Probabilistie graphical models, 16, 2010.
Erd6s, P. and Rényi, A. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17-61, 1960.
Figueiredo, F., Resende Borges, G., OS Vaz de Melo, P., and Assunção, R. Fast estimation of causal interactions using wold processes. Advances in Neural Information Processing Systems, 31, 2018.
Acknowledgement
This work was supported in part by the NSFC under Grants No. (62472377, 62402422). Lu Chen is the corresponding author of the work.
Gao, T., Bhattacharjya, D., Nelson, E.,, Liu, M., and Yu, Y. Idyno: Learning nonparametric dags from interventional dynamic data. In International Conference on Machine Learning, pp. 6988-7001, Pmir, 2022.
Impact Statement
Gerhardus, A. and Runge, J. High-recall causal discovery for autocorrelated time series with latent confounders. Advances in Neural Information Processing Systems, 33: 12615-12625, 2020.
This paper presents work whose goal is to advance the field of causality. There are many potential societal consequences of our work, none which we feel must be specifically high- lighted here.
Gong, C., Yao, D., Zhang, C., Li, W., and Bi, J. Causal discovery from temporal data: An overview and new perspectives. arXiv preprint arXiv:2303. /01 /2, 2023.
References
Assaad, C. K., Devijver, E., and Gaussier, E. Survey and evaluation of causal discovery methods for time series. Journal of Artificial Intelligence Research, 73:767-811 819, 2022.
Guo, C. and Luk, W. Accelerating constraint-based causal discovery by shifting speed bottleneck. In Proceedings of the 2022 ACM/SIGDA International Symposium on Field-Proc Solld-Programaable Gate Arrays, pp. 169-179, 2022.
Burnham, K. P. and Anderson, D. R. Multimodel inference: understanding aic and bic in model selection. Sociologi- cal methods & research, 33(2):261-304 2004.
Guo, C., Cupello, D., Luk, W., Levine, J., Warren, A., and Brookes, P. Fpga-accelerated causal discovery with con- ditional independence test prioritization. In 2023 33rd International Conference on Wield-Programmabe Logic and Applications (FPL), pp. 182-188. IEEE, 2023a.
Castro, M., Mendes Júnior, R., Coriano-Vargas, A., de Oliveira Werneck, R., Moreira Gonçalves, M., Lusquino Filho, L., Moura, R., Zampieri, M.. Linares, O., Ferreira, V., et al. Time series causal relationships dis- covery through feature importance and ensemble models. Scientific reports, 13(1): 1402, 2023.
Guo, C., Luk, W., Warren, A., Levine, J., and Brookes, P. Co- design of algorithm and fpga accelerator for conditional independence test. In 2023 JEEE 34th International Con- ference on application-specift. Systems, Architectures and Processors (ASAP), pp. 102-109. IEEE, 2023b.
Chaves, R., Majenz, C., and Gross, D. Information- theoretic implications of quantum causal structures. Na- ture communications, 6(1):5766, 2015.
Hagedorn C. and Huegle, J. Gpu-accelerated constraint- based causal structure learning for discrete data. In Pro- ceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 37-45. SIAM, 2021.
Cheng, Y., Yang, R., Xiao, T., Li, Z., Suo, J., He, K., and Dai, Q Cuts: Neural causal discovery from irregular time-series data, arXiv preprint 230.:23302.07555. 2023.
Hu, L., Zou, L., and Liu, Y. Accelerating triangle count- ing on gpu. In Proceedings of the 2021 International Conference on Management of Data, pp. 736-748, 2021.
Cheng, Y., Li, L.,, Xiao, T., Li, Z., Suo, J., He, K., and Dai, Q. Cuts+: High-dimensional causal discovery from irreg- ular time-series. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11525-11533, 2024.
Huang, B., Zhang, K., Gong, M., and Glymour, C. Causal discovery and forecasting in nonstationary environments

---

Accelerator for Time Series Causal Discovery with Time Weaving
with state-space models. In International conference on machine learning, pp. 2901-2910. Pmlr, 2019.
Pena, M., Björkegren, J., and Tegnér, J. Learning dynamic bayesian network models via cross-validation. Pattern Recognition Letters, 26(14):2295-2308 2005.
Hyvärinen, A., Shimizu, S., and Hoyer, P. O. Causal mod- elling combining instantaneous and lagged effects: an identifiable model based on non-gause gansssaasintt. In Proceed- ings of the 25th international conference on Machine learning, pp. 424-431, 2008.
Peters, J., Janzing, D., and Schölkopf, B. Causal inference on time series using restricted structural equation models. Advances in neural information processing systems, 26, 2013.
Hyvärinen, A., Zhang, K., Shimizu, S., and Hoyer, P. O. Estimation of structural vector autoregression model using non-gaussianity. Journal of Machine Learning Research, 1 11(5. 2010.
Qiu, X., Hu, J., Zhou, L.,, Wu, X., Du, J., Zhang, B., Guo, C., Zhou, A., Jensen, C. S., Sheng, Z., and Yang, B. Tfb: Towards comprehensive and fair benchmarking of time series forecasting methods. In Proc. VLDB Endow., pp. 2024.
Le. T. D., Hoang, T., Li, Liu, L., Liu, H., and Hu, S. A fast pe algorithm for high dimensional causal discovery with multi-core pes. IEEE/ACM transactions compu- tational biology and bioinformatics, 16(5):1433-145, 2016.
Qiu, X., Wu, X., Lin, Y., Guo, C., Hu, J., and Yang, Duet: Dual clustering enhanced multivariate time series forecasting. In SIGKDD, pp. 1185-1196, 2025.
Runge, J. Conditional independence testing based on nearest-neighbor estimator of conditional mutual infor- mation. In International Conference on Artificial Intelli- gence and Statistics, pp. 938-947. Pmlr, 2018.
Le, T. D., Xu, T., Liu, L., Shu, H., Hoang, T., and Li, Parallelpe: an I package for efficient causal exploration in genomic data. In Trends and Applications in Knowledge Discovery and Data Mining: PAKDD 2018 Workshops, BDASC, BDM, MIACyber, PAISI, DuMEMO, Melbourne, VIC, Australia, June 3, 2018, Revised Selected Papers 22, pp. 207-218. Springer, 2018
Runge, J. Discovering contemporaneous and lagged causal relations in autocorrelated nonlinear time series datasets. In Conference Uncertainty in Artificial Intelligence, pp. 3388-1397 Pmlr, 2020.
Liu, M., Sun, X., Hu, L., and Wang, Y. Causal discov- ery from subsampled time series with proxy variables. Advances in neural information processing systems, 36, 2024.
Runge, J., Nowack, P., Kretschmer, M., Flaxman, S., and Sejdinovic, D. Detecting and quantifying causal asso- ciations in large nonlinear time series datasets. Science advances, 5(11):eaau4996 2019.
Madsen, A. L., Jensen, F., Salmerón, A., Langseth, H., and Nielsen, T. D. Parallelisation of the pe algorithm. In Ad- vances in Artificial Intelligence: 16th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2015 Albacete, Spain, November 9-12, 2015 Proceedings 16, pp. 14-24. Springer, 2015.
Schmidt, C., Huegle, J., and Uflacker, M. Order- independent constraint-based causal structure learning for gaussian distribution models using gpus. In Proceed- ings of the 30th International Conference on Scientific and Statistical Database Management, pp. 1-10, 2018.
Marcinkevičs, R. and Vogt, J. F.. Interpretable models for granger causality using self-explaining neural networks. In 9th International Conference on Learning Representa- fions, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
Schmidt, C., Huegle, J., Bode, P., and Uflacker, M. Load- balanced parallel constraint-based causal structure learn- ing multi-core systems for nigh-dimensional data. In The 2019 ACM SIGKDD Workshop on Causal Discovery, pp. 59-77. PMLR, 2019.
Martinez-Sánchezz Á., Arranz, G., and Lozano-Durán, A. Decomposing causality into its synergistic, unique, and redundant components. Nature Communications, 15(1): 9296, 2024.
Spirtes, P., Glymour, C., and Scheines, R. Causation, pre- diction, and search. MIT press, 2001.
Tank, A., Covert, I., Foti, N., Shojaie, A., and Fox, E. B. Neural granger causality. IEEE Transactions Pattern Analysis and Machine Intelligence, 44(8):4267-4279, 2021.
Neath, A. A. and Cavanaugh, J. The bayesian information criterion: background, derivation, and applications. Wiley Interdisciplinary Reviews: Computational Statistics, 4(2): 199-203, 2012.
Vowels, M. J., Camgoz, N. C., and Bowden, R. D'ya like dags? a survey on structure learning and causal discovery. ACM Computing Surveys, 55(4):1-36, 2022.
Pearl, Causality. Cambridge university press, 2009.
10

---

Accelerator for Time Series Causal Discovery with Time Weaving
Wang, Y., Lin, K., Qi Y., Lian, Q. Feng. S., Wu, Z.,, and Pan, G. Estimating brain connectivity with varying-length time lags using recurrent neural network. IEEE Transactions on Biomedical Engineering, 6909):1933-193, 2018.
Zhou, W. and Chen, Q. A survey causal discovery. In China Conference Knowledge Graph and Semantic Computing, pp. 123-135. Springer, 2022.
Xia, K., Lin, I.., Wang. S., Zhang, Q Wang, S., and He, T. Prost: Prompt future snapshot on dynamic graphs for spatio-temporal prediction. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. I, pp. 1645-1656, 2025.
Xu, C., Huang, H., and Yoo, S. Scalable causal graph learning through deep neural network. In Proceedings of the 28th ACM international conference information and knowledge management, pp. 1853-1866 2019.
Xu, H., Farajtabar, M., and Zha, H. Learning granger causal- ity for hawkes processes. In International conference machine learning, pp. 1717-1726. PMLR, 2016.
Yao, Y., Li, D., Jie, H., Chen, L., Li, T., Chen, J., Wang. J., Li, F., and Gao, Y. Simplets: An efficient and universal model selection framework for time series forecasting. Proceedings the VLDB Endowment, 16(12):3741-3755 2023.
Yao, Y., Chen, L., Fang, Z., Gao, Y., Jensen, C. S., and Li, T. Camel: Efficient compression of floating- point time series. Proceedings of the ACM Management of Data, 2(6):1-26, 2024a.
Yao, Y., Dai, S., Li, Y., Chen, L., Li, D., Gao, Y., and Li, T. A demonstration of tends: Time series management system based on model selection. Proceedings of the VLDB Endowment, 17(12)433774336) 2024b.
Yao, Y., Jie, H., Chen, L., Li, T., Gao, Y., and Wen, S. Tsec: An efficient and effective framework for time series classi- fication. 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 1394-1406. IEEE, 2024c.
Yi, Z., Zhou, Z., Huang, Q. Chen, Y., Yu, L., Wang, X., and Wang, Get rid of isolation: continuous multi-task spatio-temporal learning framework. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Zarehavani, B., Jafarinejad, F., Hashemi, M., and Salehka- leybar, S. cupe: Cuda-based parallel pe algorithm for causal structure learning on gpu. IEEE Transactions on Parallel and Distributed Systems, 31(3)533--54,, 2019.
Zhao, K., Guo, C., Cheng, Y., Han, P., Zhang, M., and Yang, B. Multiple time series forecasting with dynamic graph modeling. Proceedings of the VLDB Endowment, 17(4): 753-765, 2023.

---

Accelerator for Time Series Causal Discovery with Time Weaving
A. Proofs
Theorem A.1. Given two variables and v' in a MTS data X. u and e' have causal relationship in a time lag k, then either P(Xor(e, v', k) ()) or P(Xor(u, v' k) (1, will exceed 3 - c, where is value approaching 0.
Proof. Let r ((0, 0), (0, (1, 0), (1, represent the possible tuple set resulting from the XOR operation between time weaving representation of and r' (i.c., (or(e, v')) time point with time lag k. For any tuple e T, there is corresponding tuple 7 that represents completely opposite trend (e.g., (1,0)-(,,), (0,0)-(1,1)). Then, there are three different combination results:
P(Xor(c,,',k) (0, Σ P = =T, =
P(Xor(o, (1,1))
Σ
P( = 1-k = =T)
(2)
Ter
d' {(0, 1), (1,
Σ Ter
P( ET (T,T"), =r)
where P(Xor(u, of, k) = (0,0) 0)) represents the probability that the contexts of x/, and x. exhibit similar trend, while P(Xor(e, v', k) = 1)) represents the probability of an opposite trend. P(Xor(u, v', k) {(0, (), 1), (1, represents the probability that the contexts of xt and z share some similarities or differs in others. The joint distribution P( x(==) of two variables v and r' can be factored using the conditional probability formula as:
rt-k =T) P(x = f/ = P() T) P( = T, T
P( = x. =T) P(at, = 7 -- = P(rt =T) r) T) P r 1- P))
(3)
Pl e [T,
Here, P(xt ) the marginal distribution of v, and P( k) is the conditional distribution of o' given the state zt of v.
Given 24 = T, if v has positive causal effect on v', then the probability of x = tends to be higher than that of 2 =7, where 7' E r - 7", as illustrated in Equation 4. Furthermore, the more pronounced the positive causal effect, the closer the probability of indicating an opposite trend, P(z = = = T), approaches zero.
P(zy =Tl =) P(z = = -/1 T), -'r- (T,7
(4)
P(x = To = < ED
(5)
where Co represents probability approaching 0. Note that P( r' |ott = 7) could not be zero because it may be potentially influenced by other external factors, such noise other variables in SCM.
Therefore, given x = r, the sum of the probabilities for all possible contextual trends of a ( (the similar trend, opposite trend, or other cases) must equals to as shown in Equation Based on Equations 5 and 6, we can further derive Equation 7.
P( T/ =-
=T)
Σ
Play =' = =) + Playe = 19 =))
(6)
F'ET [T,79}
P(1.. = 7|2 T) +
Σ
P( T = 1-
TEE
Given Equation& 4, we can infer that given ..6 т, the conditional probability of xt, greater than the average of the
12

---

Accelerator for Time Series Causal Discovery with Time Weaving
probabilities for all other possible trends indicated in Equation 8.
Σ
P(ay 7|26 7) > Plzye = T) + P(xye = T/|2, + P - =
111-2 P(ay, = 1/ - = -))
P(r. 7|00/ r) >
1
(P(x)) -| = +)+ +
E
r
('Er-(r)e)
1
>
r 1 (1 - cu)
1
6 c=
3 co
(8)
Due to Eter P( = 1, we can infer the Equation 9.
P(Xor(u, o' (0,
Σ
P( = =
TET
Σ
P(ay = -| T) P( = =T)
1
E)
Σ
Play r)
3
In general, if v has positive causal effect on v/, P(Xor(v, vf, k) = (0, 0)) should be greater than 3 Similarly, if v has a negative causal effect on v', P( v', k) = (1, 1)) should be greater than 1/ - e. It also proves why the threshold selected (i.e., 0.33) in the Algorithm slightly smaller than J.
B. Discussions
Our acceleration framework is compatible with various causal discovery algorithms, supports irregular time series data input, and enables efficient concurrent causal discovery.
10
10
6
4
2
2
10 11 1314
2
7
8
9
10 12
(a) Imputation with mean value
(b) Imputation with time weaving
Figure Imputation for irregular MTS
Adaptive irregular MTS. Most causal discovery algorithms typically handle irregular time series by imputing the missing values using imputation methods (Liu et al., 2024; Cheng al., 2024; 2023), such as imputation by mean value as illustrated in Figure 5(a). However, this approach may alter the original distribution of the data, especially when too many consecutive missing values exists. In contrast, ARROW adopts time- weaving representations instead of imputation, effectively preserving the original data distribution, as illustrated in Figure 5(b). For any two variables v and o' in irregular multivariate time series (MTS) data X, v contains 6 time points (1, 3, 3,4, 6, 8, 12), while contains 8 different time points (1,2,45 4, 5, 8, 10, 11, 14). ARROW constructs the union of their time points, T < v, >= T, U Ter, resulting in a complete time set 11, 2, 4, 5, 6, 8, 10, 11, 12, 14).
13

---

Accelerator for Time Series Causal Discovery with Time Weaving
Next, the values of the variables are transformed using the time-weaving transformation. For any time point in the union set (T < U, r' > -T T v,,'z ) where variable has missing values, the missing values are filled based on the trend between adjacent time points. For example, for variable e, the missing value at = 5 is filled using the trend between t t= 4 and t = 6. Similarly, for variable v', the missing values at t = 6 and t = 7 are filled using the trend between t = 5 and = 8.
Compared to traditional imputation methods, ARROW preserves the original trends and distribution of the data through time-weaving representations, avoiding the bias introduced by imputation assumptions. It naturally handles data with irregular time points and better adapts the complexity of multivariate time series data.
Adaptive to parallel acceleration. In causal discovery algorithms, CUDA-based parallel computation strategies can significantly enhance computational efficiency, particularly when exploring causal relationships between variables. CUDA leverages the parallel processing capabilities of GPUs to accelerate logical operations such as AND, OR, and NOT, which are commonly applied to 0/1 data. The inherent simplicity and low memory consumption of 0/1 data make it well-suited for parallel computation, enabling CUDA to process large-scale datasets efficiently and dramatically reduce computation time, thereby improving scalability and real-time performance.
Specifically, in the case of ARROW, the original data is discretized into 0 and values, making it particularly compatible with CUDA acceleration. This discretization reduces memory and bandwidth overhead, while the simplicity of logical operations on binary data allows CUDA to perform parallel computations more effectively. As a result, ARROW benefits from both the data transformation and parallel processing, providing an efficient solution for causal discovery tasks, especially in lcage-scale and complex time series data analysis. This combination of data discretization and CUDA parallelism significantly enhances the computational performance and processing speed of causal discovery algorithms.
C. Experimental Setting
C.1. Baselines description
In our experiments, we selected four representative algorithms for detailed study: the constraint-based algorithm PCMCI, the information-theorede algorithm SURD, the Granger-based algorithm NGC, and the score-based algorithm VARLINGAM.
PCMCI is a constraint- based causal discovery algorithm that improves the original PC algorithm for application to time series data, aiming to uncover causal relationships between variables in time series data. The algorithm combines conditional independence tests with machine learning methods. The key idea behind PCMC/ is to use "post-effects" (Post-Nonlinear) in time series data to capture potential nonlinear causal relationships. In the experiment, we implemented the PCMCI algorithm based the open-source code 3. PCMCI can generate causal graphs for all candidate time lags, and we determine the time lag and final causal graph by selecting the densest time lag set.
SURD is an iheoreiiion-theoreiiic causal discovery method that uses the principle of uncertainty reduction in information theory to infer causal relationships. The algorithm infers the causal relationships between variables by calculating the information gain between them. SURD focuses on discovering causal relationships by reducing the system's 's entropy (i.e., uncertainty), making it effective in handling nonlinear and multivariable dependencies in complex systems. We implemented the SURD algorithm based on the open-source code and implemented CUDA acceleration. We determine the optimal time lag and summary graph using the brute-force search method usned in the SURD.
NGC is an algorithm based on granger causality, specifically designed for causal discovery in time series data. The Granger causality test assumes that if variable X has causal relationship with variable Y, then past values of X can help predict future values of The NGC algorithm extends the traditional granger causality test to capture nonlinear causal relationships between variables. This is achieved by performing granger causality testing on component-wise MLP model, thereby enhancing the ability to model complex dynamic systems. We implemented the NGC algorithm based on the open-source code NGC can directly return the time lag and summary graph.
VARLINGAM is acore-based causal discovery algorithm that combines the Vector Autoregressive (VAR) model with the Linear Non-Gaussian Acyclic Model (LiNGAM). This method uses the VAR model to describe the temporal dependencies between variables and performs causal discovery based on the linear non Con-Gaussian assumption. VARLINGAM assumes that the error terms of the variables follow a non-Gaussian distribution, enabling it to distinguish between causal relationships.
hattss//gthubbcom/jkooouuggggggu hhtpss//gihuuhcco//oomuaaatttttt Turbuulence-GrouupSUURRD htttss//gituuh.co//hhjpppiiii
14

---

Accelerator for Time Series Causal Discovery with Time Weaving
We implemented the VARLiNGAM algorithm based on the open-source code 9 VARLINGAM outputs set of candidate causal graphs, and obtain the final causal graph by averaging these candidates. Based the contribution of each candidate graph, we use the time lag with the highest contribution as the optimal time lag for each position.
C.2. Metric details
In experiments, not only evaluated the efficiency of the algorithms but also assessed the effectiveness of causal discovery, including the performance of summary graph generation and time lag discovery.
To evaluate the performance of different algorithms in generating causal graphs, the following metrics are commonly used. Let the inferred edge probability from the algorithm be P(Aig), with a threshold Uhre E (0, 1). The set of edges in the ground truth causal graph is Er, and the set of missing edges is Em. The definitions of metrics are as follows:
TPRG = [(i,)) P(A;)) 2 thre) Er!
Erl
(10)
FPRG H(i.)): P(Ay)) 2 thre} Es
[Esl
TPR (True Positive Rate) represents the proportion of correctly identified edges to the total number of true edges, serv- ing measure of the algorithm's ability to recognize true edges- the higher, the better. FPR (False Positive Rate) indicates the proportion of incorrectly identified edges to the total number of missing edges, reflecting the algorithm's tendency to misjudge non-existent edges- the lower, the better. The ROC curve is constructed by plotting the rela- tionship between TPR and FPR, while AUROC (Area Under the ROC Curve) measures the area under this curve, i.e., AUC - (FPR FP.,) (TPR) 1 (TPR)) It is a key metric for assessing the overall performance of algorithm.
The closer the AUROC value is to 1, the better the algorithm performs.
To evaluate the performance of time lag discovery, we also use the three metrics TPR, FPR, and AUC. Let P(Asj, k) represent the probability of an edge between and j at time lag k with the maximum time lag denoted as Max. The time lag in the true edges is represented by TLy, while the time lag in the missing edges is represented by TL The definitions of the time lag discovery metrics are as follows:
K(i,)): max [1.Max] P(Aig, k) 0.33] NTLT
TPRTL.
[TTT]
(11)
FPRTL ((i,5): max Max] P(Asg, k)> 0.33) nTLs
TLsl
where max P(Asj, k:) indicates iterating over all i values (from Max) and selecting the maximum probability for each (i,5) pair. P(Aij, k) 0.33 signifies selecting edges where the maximum probability value for the corresponding (i,5) pair exceeds 0.33. TPR represents the proportion of edges with actual delays that are correctly detected, while FPR represents the proportion of edges without delays that are incorrectly identified as having delays.
C.3. Experimental environment
All methods executed machine equipped with an Intel(R) Core(TM) i9- 10900K CPU, boasting 10 cores and clock speed of 3.70GHz. The system also features NVIDIA GeForce RTX 3090 graphics card, equipped with 24GB of video memory.
D. Extensive Experiments
D.1. Efficiency Evaluation
We do extensive experiments on the four algorithms with ie selected from the set of (3, 5, 7,9, 15, 20). The recorded time includes both time lag detection and causal graph discovery time, except for NGC, which learning method using training
methods index/Causal
15

---

Accelerator for Time Series Causal Discovery with Time Weaving
Table 3. Comparison causal discovery time
Linear+Constant Lags
Time lag
3
5
7
9
15
20
PCMCI
240.31=19.47
245.99115.8
244.87=19.75
258.45423.13
266.55=19.83
288.10#24.52
PCMCI+ARROW
6.6506#0.031
6.673420.026
6.6722=0.021
6.696620.026
6.6969=0.021
6.6868+0.021
SURD
424.00#2.001
424.90#1.837
425.34+2.04)
423.98
422.59=0.677
421.91+0.228
SURD++RROW
6.1697=0.026
6.1656+0.013
6.168120.011
6. 180020.0166
6.187420.022 0.222
6.168720.015
NGC
12.918#0.324
12.905=0.317
12.844#0.273
12.88948. 293
12.946#0.22
12.898+0.299
NGC+ARROW
0.7608#0.045
0.7971#0.056
0.7949:0.055
0.795240.058
0.7931=0.066
0.7484+0.013
VARLINGAM
9.5531 9.7244#0.430
9.2401#0. 137
9.2190#0. 129
9.3213#0.
9.5007+0.319
VARLINGAM+ARROW
6.2040+0.013
6.2020+0.013
6.219240.020
6.230540.016
6.266420.015
6.2882+0.039
Lunear+ Lags
Time lag
5
15
20
PCMCI
306.21+38.92
388.41483.10
416.26436.11 13
442.87485.53
441.16255.00
491.77+95.44
PCMCI+ARROW
6.6167:0.540
6.448620.031
6.498240.026
7.2986+2.375
6.4285=0.029
6.477820.034
SURD
427.9242.212
425.72+0.875
427.58#0.336
428.81#0.336
428.54#1.355
425.71+0.931
SURD+ARROW
6.2240+0.120
6.1871#0.033
6.1442+0.016
6.1598#0.014
6.171120.024
6.1761#0.034
NGC
15.10844.023
13.043#0.339
13.010#0.273
13.059#0.289
13.021#0.278
13.039#0.273
NGC+ARROW
0.7432+0.013
0.7482+0.014
0.7473:0.014
0.746620.013
0.7477=0.013
0.7462+0.013
VARLINGAM
8.8738#0. 104
9.1697#0. 155
9.2141#0.133
9.2228+0. 110
9.3054
9.2058+0. 126
VARLINGAM+ARROW
6.2325+0.025
6.243940.037
6.252640.037
6.252240.420
6.2743+0.044
6,2668+0.026
Non-Linear+Constall Lags
Time lag
3
5
7
15
20
PCMCI
1160.8+287.2
1310.74304.4
1338.4
1014.724231.6
196.9
1287.8+264.2
PCMCI+ARROW
1.546
9.613243.044
13.056+5.052
28.265+18.342
22.925=18.55
65.774457.08
SURD
424.08=0.478
424.14=0.423
424.3640.256
424.15+0.194
428.0941. 1.220
428.9440.
SURD+ARROW
6.468020.324
6.362940.059
6.382240.071
6.366720.028
6.384420.145
6.4870+0.129
NGC
12.895+0.281
12.980#0.318
12.855+0.308
12.89940.22 290
12.960+0.25 293
12.832+0 292
NGC+ARROW
0.7406:0.015
0.743040.013
0.739020.013
0.740620.013
0.741520.013
0.7328+0.057
VARLiNGAM
9.1115+0.133 132
9.0475+0.171
9.053140. 102
9.065340.106
9.0925#0.104
9.0630#0.095
VARLINGAM+ARROW
6.2116:0.013
6.2198+0.021
6.2297:0.012 6.2448+0.024
6.242410.021
6.2322+0.017
Non-Liinerr-Multiplee Lags 7
Time lag
5
9
15
20
PCMCI
1139.34277.2
1076.7+196.8
1175.64357.1
1185.74262.1
1368.8+222.4
1033.2+263.3
PCMCI+ARROW
7.6503+1.325
7.6967+1.387
9.290014.339
10.727014.502
16.591+13.154
29.738+19.92
SURD
428.54#0.185
426.65=1.340
425.38+1.422
123.40#0.133
423.34=0. 141
425.50+0
SURD+ARROW
6.2758+0.087
6.198140.032
6.205140.039
6.196740.039
6.2153+0.036
6.1909#0.028
NGC
13.246+0.326
13.155+0.340
12.973+0.275
12.96420.312
12.906#0.304
12.985+0.306
NGC+ARROW
0.739020.016
0.741010.013
0.743940.013
0.746240.011
0.7478+0.014
0.748240.014
VARLiNGAM
8.801440. 196
9.0378+0. 129
8.991040. 136
9.019740.137
9.0330+0.19
9. 9.1033+0.19
VARLINGAM+ARRON
6.2102+0.018
6.2423+0.014 6.2769=0.019
6.279620.016
6.293420.026
6.2852+0.016
time for each 100 epochs. Our method achieves up 153x, 69x, 20x, and 1.57x speedup compared with PCMCI, SURD. NGC, and VARLiNGAM among synthetic datasets with linear and non-linear causal relationships shown in Table 3, demonstrating favorable accelerating effect.
Specifically, PCMCI with ARROW performs more stably across both linear and non-linear datasets, while PCMCI is significantly slower on non-linear datasets than linear ones. This because CI tests on non-linear dependency between variables use more complicated calculations. Equipped with ARROW, MTS data is discretized into a binary representation, simplifying the CI tests and thus achieving a swift and stable performance.
SURD takes the longest time compared other algorithms, and its time increases rapidly the time lag range expands. This is because SURD uses brute-force traversal method to detect the optimal time lag and calculates the joint and conditional
16

---

Accelerator for Time Series Causal Discovery with Time Weaving
distributions for each variable and its candidate set. However, SURD with ARROW maintains approximately 6 seconds regardless of the time lag value. This is due to ARROW'S pruning strategy, which significantly reduces the candidate set for each variable, exponentially decreasing the number of conditional distribution calculations.
NGC with ARROW spends less time per 100 epochs compared to the NGC. This is because the size of convolution kernel is set according to the time lag size. NGC requires the max time lag range, whereas ARROW only to set it to k: identified by the time lag discovery strategy, which is much smaller than the max value.
VARLiNGAM outperforms other algorithms in terms of efficiency due to its ICA, linear models, and recursive regression. However, it still requires traversing the time lag range find the optimal lag. In contrast, VARLINGAM with ARROW avoids the traversing, further speeding up the discovery. Note that, although ICA and other optimization techniques accelerate the casual discovery of VARLiNGAM, they are not general, and cannot be applied to other types of methods. To sum up, our ARROW is general accelcrator that can significantly improve the efficiency of causal discovery on all the methods.
D.2. Effectiveness Evaluation in Time Lag Discovery
As shown in the Figures 6 and 7, the time lag discovery strategy of ARROW outperforms almost all the baselines.
PCMCI performs better on the dataset with constant lags than those with multiple lags. This is because PCMCI returns summary graphs for each possible time lag, and does not provide an internal implementation of selecting the best time lag for each variable. In addition, PCMC/ with ARROW is more stable than PCMCI and performs better on the dataset with multiple lags. This is because the time lag discovery strategy of ARROW can adapt to datasets with different types of relationships.
SURD exhibits performance similar to that of random classifier on both constant and multiple lags datasets, while SURD with ARROW is able to select much more accurate lag graph. This is because: i) SURD assumes the lags among variables be equal, which makes it fail to find the optimal lag graph on datasets with multiple lags; ii) the real causation can be diluted when the size of candidate sets becomes too large. However, ARROW can select the most appropriate time lag for each variable pair the candidate set by time lag discovery and candidate pruning strategies.
NGC with ARROW achieve better time lag discovery performance than NGC on all datasets, and VARLINGAM with ARROW is better than VARLiNGAM when the time lag exceeds 10. This is because both NGC and VARLINGAM deduce the optimal lag graph by selecting the lag that contributes the most to the final summary graph, which ignores the contextual information in the original input data. In contrast, ARROW improves time lag discovery accuracy by preserving the contextual information of each data point through time weaving. In addition, the performance of VARLiNGAM slips sharply as the time lag exceeds 10, due to the non-gaus non-gaussianity of the data distribution being obscured in cases of long lags.
D.3. Effectiveness Evaluation in Summary Graph Generation
As shown in Figures 8 and 9, the accuracy of the summary graph generated by the original algorithm equipped with ARROW much better than that of the original method on most datasets.
PCMCI with ARROW performs better than PCMCI, especially on the dataset with multiple lags. This is because PCMCI does not support multi-lag causation discovery, thus encountering a performance drop from constant-lagged to multiple-lagged datasets, while ARROW can effectively handle causality relationships with multiple lags.
SURD has a worse performance on deducing the summary causal graph because that is constructed on the wrongly-inferred lag graph. Moreover, the pruning strategy imported by However, if given the correct lag graph and pruned parent set inferred by ARROW, SURD can achieve a performance burst of at most 94%. This is because ARROW concentrates the conditional distribution on the potentially important subset of variables out of the entire, focusing the algorithm on more significant causal relationships for each pair of variables.
Both NGC and NGC with ARROW exhibit poor performance non-linear datasets. This is because the items on the leading diagonal tends to be kept during the simplification of the initially fully connected causal graph. However, our synthetic Erdos-Renyi graph would not have its diagonal element to be 1, leading to the poor performance on our non-linear datasets.
VARLINGAM with ARROW exhibits comparable excellence with VARLINGAM when the time lag is small. However, their performance significantly declines as the lag increases, exhibiting a similar pattern and underlying reasons observed in the time lag discovery.
17

---

Accelerator for Time Series Causal Discovery with Time Weaving
Lag!
M-ARRCW (Constant Lag)
MA-ARROW (Multpic Lag)
M-ARROW (Mutppl Lag!
1.0
1.0
1.0
1.0
0.9
0.8
0.9
0.9
0.8
0.8
9 0.8
0.8
0.7
0.7
0.8
0.5
0.5
21
k
8
A
POMCI
SURD
(c) NGC
VARLINGAM
1.0
1.0
0.8
0.8
0.8
0.8
0.6
0.6
0.4
4
0.2
0.2
02
0.2
0.0
(e) M: POMCI
(0) Ar: SURD
(g] M: NGC
(hi M: VARLINGAM
0.10
0.05
0.05
E. 0.05
0.05
0.00
0.00
3
6
12
15
18
21
3
6
12
15
18
21
12
15
18
21
12
15
16
21
k
(i) Ar: PCMCI
())
[K) M: NGC
A:: VARLINGAM
Figure 6. Time lag discovery performance on the dataset with linear causal relationships
(Constant
(Constant Lag)
AA-AROOW (Mutsple Lag)
MEAAROOW (Mutiple Log)
1.0
1.0
1.0
1.0
0.9
0.9
0.9
0.9
08
2 0.8
0.8
0.8
0.7
0.7
0.7
0.8
06
0.5
0.5
21
k
PCMCI
M: SURD
NGC
VARLINGAM
1.0
0.8
0.8
0.8
0.8
g: 0.8
0.8
0.6
0.2
0.2
0.2
0.2
0.0
(e) M: POMCI
(i) M:: SURD
(g) M: NGC
(h) M: VARLINGAM
0.10
0 0.00
0.05
0.05
8.00
0.00
6
12
15
18
21
3
6
12
15
18
21
3
15
18
21
12
1.5
18
21
k
()) PCMCI
()) SURD
[K] NGC
0) VARLINGAM
Figure 7. Time lag discovery performance on the dataset with non-linear causal relationships
18

---

Accelerator for Time Series Causal Discovery with Time Weaving
(Constamt Lag)
M-ARROW (Constant Lag)
AARARO (Mutiple Log)
M-ARROW (Multple Lag)
09
0.9
0.9
0.9
0.
0.8
0.8
207
07
0.7
0.7
08-
0.5
PCMCI
SURO
(c)
VARLINGAM
1.0
1.0
1.0
1.0
08
0.8
0.6
g
0.6
0.5
0.6
0.4
0.2
0.2
02
0.2
12
15
(e) PCMCI
(f M: SURD
(g) M: NGC
(h) M: VARLINGAM
0.3
0.2
0.2
0.1
EPP.
FPR
0.0
0.0
0.0
5
6
12
15
18
12
15
18
21
15
18
21
15
21
k
(i) PCMCI
(i) SURD
(k) M: NGC
(1) VARLINGAM
Figure 8. Summary graph performance on the dataset with linear causal relationships
(Constant
M-ARROW (Constant Lag)
MA-RROWW (Muliple Lag)
M-AAROWW (Muliple Lag)
1.0
1.0
1.0
0.6
08
9
2
0.5
0.8
0.7
0.7
0.7
0.6
0.8
0.5
0.
0.5
0.3
0.5
3
6
12
15
18
9
12
15
18
21
12
15
18
21
12
15
18
21
k
PCMCI
M: SURD
NGC
VARLINGAM
1.0
1.0
0.5
1.0
0.9
0.4
0.9
0.8
0.6
0.8
0.4
0.5
0.0
0.5
12
15
12
18
(e) M: POMCI
(i) M:: SURD
(g) M: NGC
(h) M: VARLINGAM
0.3
0.2
2 0.10
0.1
0.4
FPR
0.155
0.05
0.0
3
9
12
15
18
21
3
6
9
12
15
18
21
3
6
9
12
15
18
21
3
6
12
15
18
21
k
k
PCMCI
() SURD
[K).M: NGC
(): VARLINGAM
Figure 9, Summary graph performance the dataset with non-linear causal relationships
19


Reviews:
[{"review_id": "XyU4qZ6sTc", "reviewer": "Reviewer_t36X", "summary": "The paper investigates the computational efficiency of causal discovery in multivariate time series. Existing methods face high computational costs when applied to large-scale data, primarily due to issues such as data binning, time lag selection, and candidate set explosion. To address these challenges, the authors propose ARROW, a method designed to accelerate time series causal discovery. ARROW optimizes time lag selection using time weaving encoding and XOR operations while reducing computational overhead through a pruning strategy. Experimental results demonstrate that ARROW significantly improves efficiency while maintaining the accuracy of causal discovery.\n\n## Update after rebuttal: I have read the rebuttal and I think my concerns are well addressed, I will keep my score this time (for acceptance).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the positive comments and our responses are detailed below.\n\n**Response to W1**: Causal relationships rely more on trend synchronization than numerical transmission. Performance improvements come from three aspects:\n* Noise Robustness – Binary encoding filters noise and highlights structural causal patterns.\n* Lag Discovery – XOR operations accurately identify lagged causal relationships and optimize time lag selection.\n* Pruning Strategy – Pruning reduces the search space.\n\n**Response to W2**: ARROW performs well in stationary sequences and noise scenarios.\n* In stationary sequences, binary encoding of temporal weaving stabilizes, and XOR results remain similar, preventing the pruning. Note that, causal discovery relies on the downstream inference, and ARROW does not impact the accuracy of downstream algorithm.\n* Temporal weaving filters high-frequency noise, but in high-noise environments (e.g., outliers), pre-processing is needed to reduce interference and improve causal identification accuracy.\n\n**Response to W3**: We have included different data sizes, including synthesized datasets with 10 variables and 1000 time points, Dream3 dataset with 10 genes and 84 time points.", "claims_and_evidence": "Yes. The claims made in the submission are supported by clear and convincing evidence, particularly through experiments on synthetic and real-world datasets across various time lag scenarios.", "methods_and_evaluation_criteria": "Yes. The proposed methods and evaluation criteria are suitable for addressing the problem and validating the approach.", "theoretical_claims": "Yes. The theoretical proof regarding the time lag selection strategy has been checked, with a rigorous logic that effectively validates Theorem 4.2.", "experimental_designs_or_analyses": "Yes. The experiment validates ARROW using synthetic and real-world datasets across different time lag scenarios, which is quite convincing.", "relation_to_broader_scientific_literature": "Building on prior constraint-based, score-based, granger-based, and information-theoretic methods, ARROW enhances time series causal discovery by introducing time weaving encoding and XOR-based analysis to optimize time lag selection and reduce candidate set complexity, significantly improving efficiency without compromising accuracy.", "essential_references_not_discussed": "The author provides a comprehensive and thorough review of related work.", "other_strengths_and_weaknesses": "S1. The proposed acceleration framework ARROW has significant value and partially addresses the efficiency bottleneck in causal discovery.\n\nS2. The paper introduces time weaving representation, which represents trends between three consecutive points using a compact binary format, reducing discretization costs and capturing dynamic time series features.\n\nS3. To optimize time lag selection, it leverages XOR operations to analyze trend patterns, eliminating brute-force search and improving efficiency and reliability.\n\nS4. A pruning strategy for candidate sets is proposed to select only the most causally relevant variables, mitigating candidate set explosion and enhancing scalability.\n\nS5. The experiment is robust, thoroughly examining various time lag scenarios and validating the approach on both synthetic and real-world datasets.\n\nW1. Since time weaving encoding retains only trend information while discarding exact numerical changes, it requires further explanation for the observation that our causal discovery performance in the experiment surpasses the original algorithm.\n\nW2. The authors need further clarification whether ARROW's time weaving representation might perform poorly on stationary sequences or high-noise data.\n\nW3. The experimental setting does not explicitly mention the data scale. It would be better to see the impact of different dataset sizes on the performance of the ARROW method.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please See W1, W2, W3.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethics_expertise_needed": ["Other expertise"], "ethical_review_concerns": "NA."}}, {"review_id": "jQy2MsUWLn", "reviewer": "Reviewer_yPiC", "summary": "This paper presents ARROW, an acceleration framework for causal discovery in time series data. ARROW aims to improve the efficiency of causal discovery algorithms by reducing computational complexity through three sequential steps: Time Encoding with Time Weaving transforms time series into binary tuple representations to capture local trend dynamics. Time Lag Discovery via XOR Analysis identifies optimal time lags by analyzing trend patterns using XOR operations, ensuring efficient and accurate selection. Candidate Pruning Strategy reduces the search space by filtering out irrelevant variable pairs, improving efficiency without compromising accuracy. ARROW successfully accelerates four time series causal discovery algorithms by up to 153x on 25 synthetic and real-world datasets while improving accuracy in most cases.\n\n################################\nAdded after rebuttal period:  I checked the authors' response, but I still believe that the assumption in Theorem 4.2 of the paper is too strong. As the authors mention, the method is effective in scenarios with monotonic causal relationships, but in more complex systems, such as financial markets, climate, where there are multi-variable interactions, the relationship between two variables is likely to be influenced by other variables, non-stationarity . This could cause the numerical trend consistency to disappear, rendering the ARROW method ineffective. The authors claim that there are no specific requirements for data construction, but if two variables, A and B, only have a dependency in the first 1/5 of the time and the dependency disappears afterward, I believe it would be difficult for ARROW to detect a significant cooperative positive/negative trend that exceeds the set threshold in this case. In summary, I think the core assumption in Theorem 4.2 has certain limitations, so I keep my original score.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable suggestions.\n\n**Response to Q1 and W1**: \n\n1. **Response to the assumption of Theorem 4.2:** Our method is well-suited for scenarios with monotonic causal relationships, as assumed in Theorem 4.2, where trend changes show consistent positive or negative correlations in most consecutive periods. Many real-world datasets (e.g., NetSim[ICLR23], DREAM3, NetSIM[ICLR20], Turbulence[Nature24]) exhibit monotonic causal relationships, making our method applicable to practical scenarios. Additionally, we incorporate nonlinear relationships in our experiments (Table 2), with results further validating the robustness of our approach.\n\n3. **Response to a variable is often influenced by multiple other variables.** Our method filters variable pairs without strong correlations to accelerate downstream causal discovery. The downstream casual discovery method can support either the case when a variable is influenced by multiple other variables or the case when a variable is influence by one variable, which is not our focus. In situations where the impact of one variable is offset by others, ARROW will not incorrectly prune the edges in most cases. For example, in the case of 2A(t-1) = C(t) and -2B(t-1) = C(t), with A and B being functions of y=x, the effects of A and B cancel each other out, making C always 0. Here, A’s time weaving encoding is {1, 1, 1}, B’s is {0, 0, 0}, and C’s is {0, 0, 0}, so A XOR C always gives {0, 0, 0, 0}, and A XOR B gives {1, 1, 1, 1}. According to Theorem 4.2, both edges will be retained, with causal relationships determined by downstream algorithms. However, in complex scenarios challenging for downstream algorithms, ARROW may misprune, reflecting a trade-off between accuracy and efficiency. Our method performs well on both synthetic datasets and real-world datasets, which involve multiple variable influences, as shown in Tables 1 and 2 in the paper.\n\n4. **Response to noise.** Our datasets include both synthetic datasets and real-life datasets used in experiments incorporate the noise. In the synthetic datasets, we set the noise standard deviation to 0.1. In this rebuttal, we further validate the impact of different noise levels on ARROW by setting the noise standard deviations in the nonlinear causal relationship dataset to 0.1, 0.5, and 1. The results below demonstrate that noise has a minimal effect on performance. Additionally, the acceleration efficiency remains stable across these noise levels.\n\n| Parameter | Graph AUC | Lag AUC | Time(s) |\n|-----------|-----------|---------|---------|\n| 1         | 0.842    | 0.895  | 7.166  |\n| 0.5       | 0.870    | 0.911  | 7.047  |\n| 0.1       | 0.846    | 0.894  | 7.055  |\n\n\n**Response to Q2**: The hidden variable problem remains a significant challenge in causal discovery[CSUR23]. Our method focuses on accelerating causal mining algorithms, while handling hidden variables is determined by downstream algorithms (e.g., SURD supports hidden variables, but PCMCI does not). When hidden variables exist, we accelerate the discovery only based on observed variables, thus the acceleration process for observed variables remains unchanged regardless of the number of latent variables. This rebuttal further validates ARROW on a synthetic dataset with 10 observed and 4 hidden variables. The results below confirm its improvements in time lag discovery, causal graph accuracy, and up to 70x speedup.\n\n| Metric        | SURD+ARROW    | SURD          |\n|-------------|---------------|---------------|\n| Graph AUC  | 0.645       | 0.484       |\n| Lag AUC    | 0.869        | 0.502        |\n| Time(s)     | 6.219        | 426.206      |\n\n**Response to Q3 and W2:**\nAs an accelerator for causal mining, ARROW makes no specific assumptions about the dataset; these are determined by downstream methods. For instance, LiNGAM assumes linear data generation, non-Gaussian disturbances, and no unobserved confounders, while PCMCI assumes causal sufficiency, faithfulness, and the Markov condition.  For datasets with insufficient causality, ARROW does not prune indirect variables that still show lagged correlations with other observed variables, allowing downstream algorithms to make the final decision.\n\n\n**Response to Q4:**\nThe pruning threshold is set based on the sparsity levels in real-world scenarios. Currently, the threshold is set to 0.25, which is set based on experience. A larger threshold retains more edges, reducing efficiency, while a smaller threshold may prune important correlations, impacting accuracy.\n\n**Response to W3:**\nThe datasets we generated in our experiments have sparsity levels of 0.2 and 0.4, while the real-world datasets, including the Dream3 dataset, have sparsity levels ranging from 0.1 to 0.25, and the NetSim dataset has a sparsity level of 0.14 (see the table below).\n\n| Dataset        | Sparsity |\n|--------------------|----------|\n| Dream3-Ecoli1      | 0.11     |\n| Dream3-Yeast2      | 0.25     |\n| Netsim             | 0.14     |", "claims_and_evidence": "The authors' claims in this paper are theoretically supported, specifically by Theorem 4.2. However, this theorem assumes that if a variable v has a causal effect on v′, then their trends are more likely to be either positively or negatively correlated. I believe this assumption is overly idealized, as real-world systems often involve multiple interacting variables, where the effect of one variable may be offset or influenced by others, making the overall trend less predictable.Under the authors' assumptions, the proposed methods and evaluation criteria are reasonable. However, their applicability to real-world scenarios remains uncertain.", "methods_and_evaluation_criteria": "Under the authors' assumptions, the proposed methods and evaluation criteria are reasonable. However, their applicability to real-world scenarios remains uncertain.", "theoretical_claims": "I checked the proof of Theorem 4.2, and under the assumptions proposed by the authors, the proof seems to be correct. However, I believe that the assumptions may not hold in real-world scenarios. The theorem assumes that if a variable v has a causal effect on v′, their trends should be either positively or negatively correlated. While this might be reasonable in a simplified setting with a single influencing variable, real-world systems are often influenced by multiple interacting factors, making the actual trend relationships more complex.", "experimental_designs_or_analyses": "The experiments include both synthetic and real-world experiments. The synthetic experiments consider multiple scenarios and appear to be relatively comprehensive. However, I do not get the information of the number of variables and the edge density in each synthetic dataset from the paper. Additionally, the real-world dataset is not specifically described in detail in the paper. It is also unclear whether the synthetic experiments effectively validate the hypotheses proposed in the paper.", "relation_to_broader_scientific_literature": "This proposed method is based on existing time series causal discovery methods by introducing a candidate variable selection step and a time lag determination strategy. These steps reduce the number of variable pairs that need to be tested, effectively accelerating the causal discovery process.", "essential_references_not_discussed": "I do not see any major issues with the related work. The paper cites relevant prior research in time series causal discovery and acceleration techniques, providing sufficient context for its key contributions.", "other_strengths_and_weaknesses": "Strength: \n1. The paper is clearly written and presents its methodology in an understandable way.\n\nWeaknesses: \n1. I believe the proposed method may not be well-suited for real-world scenarios, as a variable is often influenced by multiple other variables in general. The impact of one variable may be offset by the effects of others, meaning that trend changes do not necessarily exhibit a strictly positive or negative correlation, which contradicts the assumption of Theorem 4.2.\n\n2. The authors do not specify the specific conditions under which their method is applicable, such as whether it assumes stationarity or causal sufficiency. Clarifying these assumptions would help better understand the method’s limitations and applicability.\n\n3. Although the authors claim that their method is not a causal discovery approach but rather a data-level acceleration framework applicable to most causal discovery methods, I believe it fundamentally serves as a causal discovery pre-filtering step. It leverages trend-based analysis to determine whether a time series is a potential causal candidate for another variable. However, I believe this trend-based approach is prone to misclassification. While it may be beneficial in sparse causal graphs, its effectiveness could diminish as the relationships between variables become more complex.", "other_comments_or_suggestions": "1.  Provide more details on the synthetic datasets, including the number of variables and the density of causal graphs, to enhance the transparency of the evaluation.\n2.  Clarify the description of the real-world dataset, particularly the specifics of the DREAM3 dataset, to better assess the method’s applicability.\n3.  Further discuss the limitations of the approach, especially its potential challenges in unobserved confounders.", "questions_for_authors": "1. Theorem 4.2 suggests that if variable v has a causal effect on v′, the probability of the XOR operation results being (0,0) or (1,1) is higher than (0,1) or (1,0), implying that the trends tend to be either consistently similar or consistently opposite. Is there any evidence to support this claim? How do you account for the influence of other variables and noise in this process?\n\n2. Does this method apply to scenarios with hidden variables? Since hidden variables are common in real-world data, I believe they may affect the ARROW process, potentially excluding the correct variables and reducing the effectiveness of the subsequent causal discovery methods.\n\n3. Is there a stationarity assumption in your approach? I believe non-stationary time series could disrupt the ARROW process and affect its performance.\n\n4. How is the pruning threshold in the final step determined? Is there a theoretical basis for it, or is it purely empirical?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NStMOVzJu6", "reviewer": "Reviewer_YSzU", "summary": "This paper presents ARROW, an accelerator for time series causal discovery that overcomes the efficiency bottleneck of existing causal discovery methods. The concept of time weaving is introduced, along with an XOR-based time lag discovery strategy, which leverages theoretical derivations to rapidly determine the optimal time lag, significantly improving computational efficiency. Additionally, a pruning strategy is designed to optimize the search space. The experimental results demonstrate that ARROW significantly accelerates the causal discovery process.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the positive comments and our responses are detailed below.\n\n**Response to W1**: Calculating time lag is the same for both constant and multiple lags, with no additional complexity for multiple lags. Our pruning strategy reduces the time dimension and variable count, while binary computation improves the efficiency.\n\n**Response to W2**: In the rebuttal, we add a comparison experiment on the hyperparameter w, evaluating the SURD algorithm on a nonlinear dataset with w set to {3, 9, 15, 21}. The results below indicate that larger w values slightly accelerate ARROW without significantly affecting time lag discovery or causal graph accuracy, further highlighting its effectiveness in handling irregular time series data.\n\n| w | Graph AUC | Lag AUC | Time(s) |\n|-----------|-----------|---------|---------|\n| 3         | 0.745     | 0.923   | 6.273   |\n| 9         | 0.686     | 0.886   | 6.253   |\n| 15        | 0.746     | 0.941   | 6.173   |\n| 21        | 0.716     | 0.912   | 6.030   |\n\n**Response to W3**: The window size for handling irregular data is dynamically adjustable, based on the sparsity of the data.", "claims_and_evidence": "Yes. This paper proposes a general accelerator for time-series causal discovery algorithms. Its effectiveness is validated through theoretical analysis and empirical evaluation across four different types of causal discovery methods.", "methods_and_evaluation_criteria": "Yes. To improve the efficiency of temporal causal discovery, the paper introduces the concept of time weaving and an XOR-based sequence analysis method, leveraging bit-level operations to accelerate the process. Additionally, the pruning strategy ensures the accuracy of time lag identification. The paper evaluates the performance of both time lag discovery strategy and causal graph construction, demonstrating the method's reliability and effectiveness in causal discovery tasks.", "theoretical_claims": "Yes. I carefully reviewed the proof section in the appendix, which thoroughly demonstrates Theorem 4.2, and provides an explanation for why the threshold value is set to 0.33 in the pseudocode.", "experimental_designs_or_analyses": "Yes. The experimental design and analysis are highly reasonable. To validate the effectiveness of the proposed method, the authors conducted tests on both synthetic and real-world datasets using four different causal discovery algorithms. Additionally, they set up both constant time lags and multiple time lags for the varying relationships between variables in multivariate scenarios. Extensive evaluations demonstrate that ARROW can achieve stable and efficient causal discovery across most causal discovery algorithms.", "relation_to_broader_scientific_literature": "Currently, most causal discovery research focuses on causal discovery strategies in different scenarios, lacking a general accelerator framework to improve the efficiency of causal discovery. This paper primarily addresses the efficiency problem in time series causal discovery and can be applied to most existing causal discovery methods.", "essential_references_not_discussed": "I believe that the paper has sufficiently discussed the works related to its research.", "other_strengths_and_weaknesses": "S1. The proposed accelerator, ARROW, effectively addresses the efficiency bottleneck of existing causal discovery methods. ARROW is with broad applicability and practical value.\nS2. The paper introduces a novel concept of \"time weaving\" and leverages XOR technology for sequence analysis, offering an elegant approach that greatly enhances computational efficiency.\nS3. The paper designs an efficient and effective pruning strategy that accurately identifies the most relevant candidate variables, reduces the search space, and quickly determines the optimal time lag. Additionally, the paper provides strong theoretical support.\nS4. Experimental results fully validate the effectiveness of the accelerator, demonstrating it superior performance in computational efficiency.\n\nW1. In cases when different time lags exist between multivariate variables, calculating the time lag pairwise may increase the complexity. Would this affect the overall efficiency?\nW2. The paper introduces the time weaving concept with a hyperparameter w. It would be better to experimentally verify the impact of this parameter on both efficiency and effectiveness.\nW3. The description of handling irregular data is not very clear. If there is a lot of missing data, should the window size be fixed or variable?", "other_comments_or_suggestions": "1. In the sentence \"their time lag discovery and causal graph generation performance is assessed using three metrics,\" \"is\" should be \"are.\"", "questions_for_authors": "{W1, W3}", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X6O6bSjrg8", "reviewer": "Reviewer_vSZc", "summary": "The authors proposed an accelerator framework named ARROW to address the efficiency bottleneck in multivariate time series causal discovery. By introducing time weaving encoding (capturing contextual trends between time points), an optimal time lag determination theorem based on XOR operations, and an intelligent pruning strategy, ARROW significantly improves causal discovery efficiency without compromising the performance of the original algorithms. Experiments demonstrate that the method is adaptable to various causal discovery algorithms and shows significant improvements in efficiency.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the insightful comments and our responses are detailed below.\n\n**Response to W1**: Our method is better suited for monotonic causal relationships and less applicable to purely nonlinear ones. Future work should explore trend patterns in nonlinear relationships, such as periodicity. In complex scenarios, some nonlinear relationships don't affect overall monotonicity, and thus, our method remains effective. This is validated by our experiments on synthetic datasets with nonlinear causal relationships, as shown in Table 2 of the paper.\n\n**Response to W2**: GPU-based acceleration provides hardware-level acceleration. In contrast, ARROW is the first data-level acceleration solution, particularly suited for high-dimensional time series data, and can be used alongside GPU acceleration.\n\n**Response to W3**: Nonlinear datasets pose challenges for the downstream causal discovery algorithms. However, by identifying time lags and pruning variables in advance, our approach enhances time lag discovery, causal graph accuracy, and causal mining efficiency.", "claims_and_evidence": "Yes. The claims made in the submission are supported by clear and convincing evidence, including rigorous experimental results, comparative analyses with four different types of methods, and theoretical justifications, all of which collectively validate the effectiveness and efficiency of the proposed ARROW framework.", "methods_and_evaluation_criteria": "Yes. The proposed methods and evaluation criteria, including synthetic datasets and metrics, are well-suited for the problem of causal discovery in multivariate time series. They also demonstrate that ARROW can effectively address computational efficiency and accuracy issues in real-world applications.", "theoretical_claims": "Yes. The correctness of the theoretical claims, including the proofs for the XOR-based time lag determination theorem (Appendix A), appears to be well-supported by logical reasoning and empirical validation, ensuring their validity within the proposed framework.", "experimental_designs_or_analyses": "Yes. The experimental designs and analyses in the paper are well-founded and reliable, supported by thorough comparisons with baseline methods in different cases, and consistent results across various datasets, showcasing the robustness and reliability of the proposed approach.", "relation_to_broader_scientific_literature": "The paper's key contributions are deeply connected to the broader scientific literature by addressing efficiency bottlenecks in causal discovery, introducing innovative encoding and optimization techniques, and demonstrating practical value through empirical validation, thereby advancing the field and its real-world applications.", "essential_references_not_discussed": "No. The related work section in the paper is comprehensive and thorough.", "other_strengths_and_weaknesses": "**Strengths**\n\nS1. The proposed accelerator, ARROW, aims to achieve high efficiency for various existing causal discovery methods. \n\nS2. Experimental results demonstrate that the proposed accelerator, ARROW, successfully addresses the efficiency bottlenecks of existing causal discovery methods, achieving a maximum speedup of 153 times. ARROW is a research with significant practical implications.\n\nS3. The paper is well written.\n\n**Weaknesses**\n\nW1. The paper mentions using XOR operations to determine the optimal time lag, but is the XOR operation applicable to all types of time series data? Are there certain data distributions or causal relationship patterns that could cause the XOR operation to fail?\n\nW2. Compared to existing high-performance causal discovery methods (such as those based on GPU acceleration), what are the advantages of ARROW?\n\nW3. From the experimental results, it appears that ARROW shows more significant acceleration and performance improvement for nonlinear causal relationships. Please provide a detailed explanation.", "other_comments_or_suggestions": "None", "questions_for_authors": "Answer W1, W2, W3.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper received four reviews, of which three were highly positive and one leaned negative. The paper explores the computational efficiency of causal discovery in multivariate time series. Reviewers generally found the proposed acceleration framework, ARROW, to be valuable and well-supported by robust experiments. However, one reviewer raised concerns about the applicability of the method to real-world scenarios. The authors have addressed these concerns in their rebuttal.

As the AC, I agree with the majority of the reviewers. The paper tackles an interesting and important problem, and proposes a convincing and well-executed solution. I therefore recommend acceptance.
Decision: Accept (poster)