Causal Discovery from Event Sequences by Local Cause-Effect Attribution

Dear Reviewer, thank you for your time and valuable feedback.

We want to follow-up on the applicability of our causal model and its implications. Mechanisms where multiple events are triggered, e.g. Hawkes processes, can still be modeled in parts by CASCADE. To this end, we supplement an experiment with a Hawkes process causal model, where we vary the expected number of effect events following a cause. We provide the results in the Table below.

We observe that CASCADE suffers only a slight decrease in accuracy in the one-to-many (large number of expected events) and many-to-one cases. In those settings, CASCADE models a subset of the true mechanism by matching the cause-effect events with highest likelihood. In general, for any causal model, CASCADE can identify causal edges as long as the fitted matching improves over the noise distribution. Expanding the causal model to many-to-one (A ∧ B => C) or suppression (A => !B) setting lies beyond the scope of this paper, but is nonetheless an interesting direction for future work, especially with regard to the identifiability of the resulting model.

With regard to your questions:

1. Multiple parents: Each individual event, e.g. “C” occurring at $t_2$, can only be caused by a cause event of a particular kind, e.g. "A" at $t_1$. However, the entire sequence of “C” events can contain events caused by different parents. For example, assume that events of type "A" and "B" trigger an event of type "C". Given two events $(A,t_1)$ and $(B,t_3)$ , which cause $(C,t_2)$ and $(C,t_4)$ respectively, the resulting sequence $S_C = \lbrace t_2, t_4 \rbrace$ contains events from multiple parents, so that $pa(C) = \lbrace A, B \rbrace$. We hope this also clarifies the real-world results.
2. Timestamps: We use the timestamps when computing the edge cost $L(i \to j)$. We match events $t_i$ and $t_j$, so that the cost of the matched delays $d = t_i - t_j$ is minimized. We will clarify and expand the algorithm description in the updated manuscript.

Dear Reviewer, thank you for your time and valuable feedback. We would like to address your concerns first.

1. Assumptions: Mechanisms where multiple events are triggered, e.g. Hawkes processes, can still be modeled in parts by CASCADE. To this end, we supplement an experiment with a Hawkes process causal model, where we vary the expected number of effect events following a cause. We provide the results in the Table below.

   Events per cause	0.4	0.7	1.0	1.3	1.6	1.9	2.3	2.6	2.8	3.1
   F1	0.69±0.13	0.89±0.11	0.86±0.10	0.80±0.12	0.79±0.12	0.76±0.09	0.75±0.11	0.75±0.12	0.75±0.11	0.74±0.11

   We observe that CASCADE suffers only a slight decrease in accuracy in the one-to-many (large number of expected events) and many-to-one cases. In those settings, CASCADE models a subset of the true mechanism by matching the cause-effect events with highest likelihood. In general, for any causal model, CASCADE can identify causal edges as long as the fitted matching improves over the noise distribution. Expanding the causal model to many-to-one (A ∧ B => C) or suppression (A => !B) setting lies beyond the scope of this paper, but is nonetheless an interesting direction for future work, especially with regard to the identifiability of the resulting model.

2. Hawkes: We will update the section on Hawkes processes to more closely show the connection to our causal model and reevaluate its proper placement in the paper.

3. Experiments: We evaluate our approach on real world data with unknown generating mechanisms. On labeled datasets (network alarms) CASCADE is far more accurate than the SOTA, whilst on the unlabeled global banks dataset we obtain a qualitatively better result than other methods. In both cases, our model is able to recover a sensible causal graph from the respective data distributions, even though it is unlikely that all of our assumptions hold.

   In addition, we conducted in a controlled setting where we generate data outside of our causal model. Here, we examine CASCADE’s behavior under delay distribution misspecification. We report the results in the table below.

   	Exponential	Poisson	Normal	Uniform
   F1	0.82 ± 0.08	0.81 ± 0.09	0.76 ± 0.08	0.75 ± 0.10
   SHD	13.8 ± 6.3	14.2 ± 6.7	18.5 ± 6.5	19.0 ± 7.8

   While we observe a decrease in accuracy under misspecification, CASCADE still remains fairly accurate in detecting causal edges in the observed event sequences, as the misspecified model still provides an improved MDL-score over the noise distribution. In general, CASCADE’s is robust to different delay distributions, causal mechanisms and noise levels, and hence performant on the variety of data generating mechanisms found in the real world datasets.

Dear Reviewer, thank you for your time and valuable feedback for the main paper as well as the Appendix. We would like to address your concerns and questions in detail.

1. Assumptions: First, we would like to elaborate on our assumptions and their implications.

   • Multiple effect events: Mechanisms where multiple events are triggered, e.g. Hawkes processes, can still be modeled in parts by CASCADE. To this end, we supplement an experiment with a Hawkes process causal model, where we vary the expected number of effect events following a cause. We provide the results in the Table below.

     Events per cause	0.4	0.7	1.0	1.3	1.6	1.9	2.3	2.6	2.8	3.1
     F1	0.69±0.13	0.89±0.11	0.86±0.10	0.80±0.12	0.79±0.12	0.76±0.09	0.75±0.11	0.75±0.12	0.75±0.11	0.74±0.11

     We observe that CASCADE suffers only a slight decrease in accuracy in the one-to-many (large number of expected events) and many-to-one cases. In those settings, CASCADE models a subset of the true mechanism by matching the cause-effect events with highest likelihood. In general, for any causal model, CASCADE can identify causal edges as long as the fitted matching improves over the noise distribution. Expanding the causal model to many-to-one (A ∧ B => C) or suppression (A => !B) setting lies beyond the scope of this paper, but is nonetheless an interesting direction for future work, especially with regard to the identifiability of the resulting model.

   • Low noise: The low noise assumption is required only to identify exclusively instant effects. In Figure 3b) we provide the results of an experiment with both instant and delayed effects where the noise level is gradually increased. There, we observe that CASCADE works well even when the added fraction of noise events is at 90%.

   • Faithfulness, Sufficiency: These assumptions are standard in causal discovery and allow us to show the fundamental identifiability of this mechanism for event sequences. For future work, it would be interesting to see if and how other MDL based approaches for confounding [1] and faithfulness [2] can be integrated into CASCADE.

   [1] Kaltenpoth, David, and Jilles Vreeken. "Causal discovery with hidden confounders using the algorithmic Markov condition." Uncertainty in Artificial Intelligence. PMLR, 2023.

   [2] Marx, Alexander, Arthur Gretton, and Joris M. Mooij. "A weaker faithfulness assumption based on triple interactions." Uncertainty in Artificial Intelligence. PMLR, 2021.

2. Theorem 2: We decompose the total number of events $n_j$ into those that were caused by variable $i$, i.e. $n_{i,j}$, and the remaining ones as $n_j - n_{i,j}$, which is the term that is canceled, i.e. $n_j = n_j - n_{i,j} + n_{i,j}$. We show that the entropy relation in (l.491) holds, since $\alpha_{j,j} n_j = n_{i,j}$ we can just replace $\alpha_{j,j}$ with $n_{i,j}/n_j$. We will clarify these steps in the updated manuscript.

3. Colliders: CASCADE is able to find collider structures on real world datasets. We provide the learned DAG of the Network Alarms dataset (Section 6.3) as Figure 1 in the rebuttal PDF. On this real world benchmark, CASCADE discovers many ground-truth collider structures. Additionally, we expanded the experiment from Section 6.2 to include graphs with multiple colliders (see Figure 2 in PDF). This setting too provides no problem for CASCADE, showing that our individual cause-effect matching correctly assigns effects to causes from different parents.

   # Colliders	5	7	10	15	20
   F1	0.97±0.01	0.95±0.01	0.91±0.01	0.87±0.02	0.82±0.01

4. Global banks dataset: Figure 8 shows the results of THP, which does not find any colliders at all, whereas CASCADE obtains a graph with causal edges from large to small banks with subgraphs representing geographical regions. We think, that the lack of collider structures stems from the fact that most crashes propagate on the same day. Hence, it is sufficient in most cases to have a causal singular causal parent, which is reflected in the graph we obtain in Figure 4. We agree that some of the assumptions are unlikely to hold, especially the DAG assumption and consider it an interesting future research direction to allow cyclic graphs.

Regarding the detailed list of typos and misc suggestions, we thank you for reviewing our paper at this level of detail! We will adopt all proposed changes in the updated manuscript.

Dear Reviewer, thank you for your time and valuable feedback. We would like to address your concerns and questions in detail.

1. Assumptions: Mechanisms where multiple events are triggered, e.g. Hawkes processes, can still be modeled in parts by CASCADE. To this end, we supplement an experiment with a Hawkes process causal model, where we vary the expected number of effect events following a cause. We provide the results in the Table below.

   Events per cause	0.4	0.7	1.0	1.3	1.6	1.9	2.3	2.6	2.8	3.1
   F1	0.69±0.13	0.89±0.11	0.86±0.10	0.80±0.12	0.79±0.12	0.76±0.09	0.75±0.11	0.75±0.12	0.75±0.11	0.74±0.11

   We observe that CASCADE suffers only a slight decrease in accuracy in the one-to-many (large number of expected events) and many-to-one cases. In those settings, CASCADE models a subset of the true mechanism by matching the cause-effect events with highest likelihood. In general, for any causal model, CASCADE can identify causal edges as long as the fitted matching improves over the noise distribution. Expanding the causal model to many-to-one (A ∧ B => C) or suppression (A => !B) setting lies beyond the scope of this paper, but is nonetheless an interesting direction for future work, especially with regard to the identifiability of the resulting model.

2. Scalability: Scalability is an important aspect for application of causal discovery in real-world settings. In our experiments, we run with up to 200 variables (collider-experiment Figure 3 (c) ), which takes on average 62 minutes (single threaded), whilst the competitors closest in accuracy take 2.7 hours (CAUSE) and 3.6 hours respectively (THP). In the experiment with Hawkes processes, we process event sequences with 500k total events in 99 minutes. To obtain further speedup, the edge addition and pruning steps of CASCADE are fully parallelizable, which would allow our method to scale to extremely large problem sizes.

3. Parameter sensitivity: CASCADE does not require pre-specified parameters. The cause probability and delay parameters are fitted by minimizing the MDL score. CASCADE is sensitive to the decision which parametric model to adopt. Here, we choose the commonly used class of exponential distributions. To examine CASCADE’s behavior under misspecification, i.e. when the distribution is different, we conduct a further experiment. We report the results in the table below.

   	Exponential	Poisson	Normal	Uniform
   F1	0.82 ± 0.08	0.81 ± 0.09	0.76 ± 0.08	0.75 ± 0.10
   SHD	13.8 ± 6.3	14.2 ± 6.7	18.5 ± 6.5	19.0 ± 7.8

   While we observe a decrease in accuracy under misspecification that is worse for distributions of a different shape (normal, uniform), CASCADE still remains quite accurate. In fact, CASCADE is able to detect causal edges in the observed event sequences, if the misspecified model still provides an improved MDL-score over the noise distribution.

4. Noise: Lastly, we would like to answer your question on the effect of noise on our method. The low noise assumption is only required to identify exclusively instant effects. For instant and delayed effects, Section 6.2 contains an experiment where the additional noise fraction of events is increased up to 90%. As summarized in Figure 3b), CASCADE copes well with noise and outperforms the SOTA on all noise levels.