Arrow: Accelerator for Time Series Causal Discovery with Time Weaving

We appreciate the insightful comments and our responses are detailed below.

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.

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.

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.

We appreciate the positive comments and our responses are detailed below.

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.

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.

Response to W3: The window size for handling irregular data is dynamically adjustable, based on the sparsity of the data.

Thanks for your valuable suggestions.

Response to Q1 and W1:

1. 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.

2. 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.

3. 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.

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.

Response to Q3 and W2: As 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.

Response to Q4: The 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.

Response to W3: The 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).

We appreciate the positive comments and our responses are detailed below.

Response to W1: Causal relationships rely more on trend synchronization than numerical transmission. Performance improvements come from three aspects:

• Noise Robustness – Binary encoding filters noise and highlights structural causal patterns.
• Lag Discovery – XOR operations accurately identify lagged causal relationships and optimize time lag selection.
• Pruning Strategy – Pruning reduces the search space.

Response to W2: ARROW performs well in stationary sequences and noise scenarios.

• 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.
• 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.

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.