Causal Discovery from Event Sequences by Local Cause-Effect Attribution
Authors: Joscha Cüppers
Sascha Xu
Ahmed Musa
Jilles Vreeken
Venue: NeurIPS 2024 poster (2024)
Keywords: causality
causal discovery
event sequences
Primary area: causal_inference
TL;DR: We introduce a causal discovery method for event sequences, that matches individual events to individual causing events.

Abstract: Sequences of events, such as crashes in the stock market or outages in a network, contain strong temporal dependencies, whose understanding is crucial to react to and influence future events. In this paper, we study the problem of discovering the underlying causal structure from event sequences. To this end, we introduce a new causal model, where individual events of the cause trigger events of the effect with dynamic delays. We show that in contrast to existing methods based on Granger causality, our model is identifiable for both instant and delayed effects.

We base our approach on the Algorithmic Markov Condition, by which we identify the true causal network as the one that minimizes the Kolmogorov complexity. As the Kolmogorov complexity is not computable, we instantiate our model using Minimum Description Length and show that the resulting score identifies the causal direction. To discover causal graphs, we introduce the Cascade algorithm, which adds edges in topological order. Extensive evaluation shows that Cascade outperforms existing methods in settings with instantaneous effects, noise, and multiple colliders, and discovers insightful causal graphs on real-world data.

Causal Discovery from Event Sequences by Local Cause-Effect Attribution
Joscha Cüppers CISPA Helmholtz Center for Information Security j joscha. cueppers@cispa.com
Sascha Xu CISPA Helmholtz Center for Information Security sascha xu@cispa.... de
Ahmed Musa' Institute for Structural Analysis TU Dresden
Jilles Vreeken CISPA Helmholtz Center for Information Security jv@cispa.de
ahmed . wtt.:mmmsstuudrreeeeee
Abstract
Sequences of events, such as crashes in the stock market or outages in a network, contain strong temporal dependencies, whose understanding is crucial to react and influence future events. this paper, we study the problem of discovering the underlying causal structure from event sequences. To this end, we introduce causal model, where individual events the cause trigger events the effect with dynamic delays. We show that in contrast existing methods based Granger causality, our model is identifiable for both instant and delayed effects.
We base our approach on the Algorithmic Markov Condition, by which we identify the true causal network as the one that minimizes the Kolmogorov complexity. As the Kolmogorov complexity is not computable, we instantiate our model using Minimum Description Length and show that the resulting score identifies the causal direction. To discover causal graphs, we introduce the CASCADE algorithm, which adds edges topological order. Extensive evaluation shows that CASCADE outperforms existing methods in settings with instantaneous effects, noise, and multiple colliders, and discovers insightful causal graphs on real-world data.
1 Introduction
Suppose we are considering a multivariate event sequence. What caused a specific event to happen? Which variables causes of each other? Data-driven methods infer causal relationships from observed data. Existing methods for discovering causal networks from event sequence data 3 [4]. This purely predictive notion defines variable to be cause of another variable Y if the past of X helps to predict the future Y. It is relatively weak notion of causality that excludes instantaneous effects and is often unable to discover true causal dependencies; in Granger causality, baking a cake is causal to birthday.
based on Granger causality
In this paper, instead build upon Pearl's 's model of causality, which assumes the existence of an an underlying causal structure the form of directed acyclic graph (DAG) (5). In our context, such graph describes the causal relationships between types of events, such alarms in network. We propose a new causal model for event sequences based on a one-to-one matching of individual events, where model the process of one individual event of certain type possibly causing
" "Equal contribution
* TTii work done while at CISPA Helmholtz Center for Information Security
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

individual event of another type. In our model, we take into account the uncertainty of whether an event actually caused or independently generated, the uncertainty of event actually causing an effect or failing to do so, and the uncertainty of the delay between cause and effect. As we will show, our model has several advantages, such as clear notion of what event caused another and the identifiability for both instant and non-instant effects.
We base our theory on the Algorithmic Markov Condition (AMC) [6], which postulates that the true causal model achieves the lowest Kolmogorov complexity. As Kolmogorov complexity is not computable, we instantiate it via the Minimum Description Length (MDL) principle [7]. We show that our score is consistent, identifies the true causal direction for both instantaneous and delayed effects, and formally connect to Hawkes processes. discover causal networks in practice, we introduce the CASCADE algorithm,, which adds edges in topological order. Through extensive empirical evaluation, we show that CASCADE performs well practice and outperforms the state of the art by wide margin. On synthetic data, CASCADE recovers the ground truth without reporting spurious edges, and on real real-world data, returns graphs that correspond existing knowledge.
Preliminaries
We write i + when S; is cause of Sj and pa(j) for the set of parents of node j. We assume faithfulness, sufficiency, and the causal Markov condition [8]
InformationnTTherrtii Causal Discovery The Algorithmic Markov Condition (AMC) postulates that the factorization of the joint distribution according to the true causal network achieves the lowest Kolmogorov complexity [6]. The Kolmogorov complexity K (xx) of binary string is the length of the shortest program p for universal Turing machine lI that computes and halts (9. For distribution P, it is the length of the shortest program that uniformly approximates P arbitrarily well,
min (pp Vyll P(v) K ((P)=
PE0,1
The AMC states that the Kolmogorov complexity of the joint distribution P(X) is the sum of the complexities of the conditional distributions P(Xi|pa(i), of the true DAG G*, i.e.
K(P(X)) = Σ K (P((X)))))))
up constant independent of the input. Due to, among others, the halting problem, Kolmogorov complexity is not computable, but we can approximate it from above. A statistically well-founded way do so is by Minimum Description Length (MDL) 7 [0]. For fixed class of models H. MDL identifies a description length of encoding data X together with its optimal model,
L(X H))
min (L(X 11) + L(h))
KER
Next, we introduce the assumed data generating process, its corresponding model class H and encoding length function I., and show under which conditions it can be identified.
3 Theory
To be able infer causal relationships from observational data, we need to make assumptions about the underlying data-generating process (5). The key assumption we make here is that an individual event of type i at time with probability Ci.j causes an individual event of type j at time i' 2 t. To illustrate, we give toy example in Fig. which event sequence S, causes event sequence Sy. The individual events in S; occur uniformly at random. The first and third events in S, cause events in Sj, resp. with delay of 0.2 and 0.3. The other two events in S, do not cause events in Sj. denoted by a delay of oc. The final event in S, is due to noise, marked by N₁.
0.2
80
0.3
N₂
00
Sy:
Figure 1: Cause-effect matching, where St causes Sz.

---

Next, we formally describe the causal mechanism. We differentiate between source and effect nodes.
Source nodes nodes in G with empty parent set pa(i). For source nodes assume that the events S; occur uniformly at random with a rate of A events per time unit. This mechanism, commonly known as homogeneous Poisson process, is used, for example,
model for accident rates requiring hospital admission [[]]. In this work, we focus on the delay times between individual events, denoted dy for the delay t f and Aioi [d& for the sequence. For Poisson process, the delay times are independently and exponentially distributed. Thus, we model source event sequence S, as
k Σ
S, = [tt])i where &
dis
A {ds: ~ Exp(Ai)
(1)
Effect nodes are nodes) j G with at least one parent pa(i). For each effect node j. the individual events in Sj are either caused by individual event in an S; with i E pa(j) due to noise. That is, reasoning from the causing node i, every event ty E S, may trigger an event of the effect S with probability of os.j. .. If triggered, an individual event in S, will occur after random delay dg. drawn from cause-effect specific delay distribution P. parameterized by 0.g. c.g. the rate À of an exponential distribution, and az. If no event is triggered, then model the delay infinite, iee d = oc. The sequence delays Di-t from S: + Sj is modeled as
(d)(d) -1 (1-acs (p(d 0z.)) oii
d = 0c else
A و = {dx h km
dg ~ & Pi 0o.g) itd
(2)
where di.j (d) denotes the density of the delay distribution. Thus, given the sequence S, of the cause and delays A;-jj the individual events in Sj caused by S; are obtained by adding the delays dy to the time stamps la of the individual cause events, with the reconstruction function f as
fig Ai-,)) [tx + du d2 + 0o), for k = 1,...,
In addition, individual events in Sy can also be due to noise. Like for source nodes, we assume these Poisson process as per Eq. ( with rate Ay. i.c. N2 Poisson(Ay). Putting this together, given causal structure G" an effect event sequence Sj is generated by taking the union of the individual delays from the causal parents pa(j) and the time stamps due noise N,,
S₁ = ( fas (S,, Ai.))) UN,, (Epa(i)
(3)
Next, we instantiate MDL score for this causal model and consider its identifiability.
3.1 Minimum Description Length Instantiation
We now develop a score for our causal model using MDL. 77 consists of the cost of the data given the model, T(S (), i.e. the negative log-likelihood of the data, and the cost of the model, i.e. that of the parameters, (e), and that of the graph, [G)), all measured in bits.
Data Cost
The cost of data in bits directly corresponds to its negative log-likelihood, i.e. the likelihood of each delay as per Eq. (2) over all the event sequences corresponding to the parents of node j and that of the noise events. Formally, we have
L (S, Spa(t) θ) = Σ Σ - -log(or +
Σ di diEA,
log (d)))
iEpa(j) deEA
The first term encodes those events that caused by the parent S; through the delays A Here, we use a Shannon-optimal coding that requires log((r,, (dx)) bits per sample [7] In the second term, we encode all remaining events noise using the delay distribution of Poisson process. For source events, i.e. variables without any parents, only the noise term is present.
The cost of all sequences is then simply L(S G, ΣEEp) L(S, Spa(t), 9).
3

---

Parameter Cost Next, we define the costs of the DAG, L(G), and that of the parameters, L()). We encode the DAG in topologiaal order. Per node we encode its number of parents [pa(i)] and identify which those are, i.e. L(G)= = Ei=o (log(k) log &
Depending on their type, we encode the parameters f E O For parameters 8 E N we use Ln. the MDL-optimal encoding for integers [12 It defined as Lg (2)
log" + log Co where log" is the expansion, log 2 log log = +... in which we only include positive terms. To ensure this is valid encoding, i.e. one that satisfies the
Kraft inequality, we set Co 2.865064 [2]. For parameters 0 E R. we use (0) = I (d) + LN( 1) + as the number of bits needed to encode a real number up to user-specified precision [7]. For an edge i + j. the parameters are the trigger probability os.j and those of the delay distribution 6. For the cost of an edge we hence have L(i + j) Lg(0),)) Eoco., L(0). For O as whole,
we have [())= =
-i-jea L(i + j).
The overall MDL score then
L G + L(0))
3.2 Identifiability
We now study the identifiability guarantees of our model and score, i.e. under what conditions we can identify from given pair which is the cause and which the effect. Consider pair of event sequences S, and Sj. where S; + S, and the cause S; is a source event while S, is an effect event.
Instant Effects We begin with the case of instant effects only. Instant effects are observed when the sampling frequency of the data, e.g. a daily time scale, is insufficient to pick up a difference in time, such financial crash that can spread across the globe within hours. It is well-known that Granger causality cannot identify the causal direction for instant effects [13]. In Pearl's causal framework, on the other hand, the causal direction between two binary variables is identifiable [4 We can build upon these results and show that our causal model and MDL-based score can identify the causal direction for non-deterministic instant effects.
Theorem 1. Let Sy be an event sequence generated by a Poisson process as per Eq. ① and S be an effect of St as per Eq. B with, low noise X; < (1 - (iis) )as and a trigger probability 0s.j < 1. In the case of exclusively instant effects, i.e. &he (d) = 5(d), where 5(d) is the Dirac delta function, the MDL score in the true causal direction is lower than in the anti-causal direction, ie..
lim L(S, 1 |S, + L(S, 01) < L(S, 02) + L(S, O2)
We provide the full proof in the Appx. A.I the general idea is under non-deterministic trigger mechanism, i.c. 0i, < 1. Then, in the causal direction, we can fully explain S with St, but not vice-versa, as the cause is generated by a Poisson process. If a, = 1, i.c. the process is deterministic, we always observe cause and effect together, making them indistinguishabl.
Delayed Effects Next, we consider the case of exclusively delayed effects. Here, there is an
inherent asymmetry in the benefit of knowing the cause versus the effect. As shown by Didelez [17] for marked point processes, and later used by Xu et al. [.. Eichler et al. [18] for Granger causality in Hawkes processes, the intensity of observing the cause after an event of the effect is unchanged. That
is, the future of the cause is independent of the past of the effect, while if cause triggers effect, the intensity of the effect is increased by the cause. We have the following identifiability guarantee.
Theorem Let S be an event sequence generated by a Poisson process as per Eq. ① and S, be an effect of S; as per Eq. 3,, such that H (63.) > Hp(; ((p(:)0))))))))))))))())))))(( + o. (B(az,)) + ai H (B(a,,)). where denotes the entropy and the Bernoulli distribution.
Then the matching in the anti-causal direction Á of the effect Sj to the cause S; has a worse MDL score than the true matching Ai-s i.e.
L(S; 0,,,) + L(S; O;) < L(S, Sj.
0,)) 1
We provide the full proof in the Appx. A.2 In the anti-causal direction S - S,, the delay times follow the same exponential distribution of Exp(A:), leading to gain in score compared to the

---

self-delay encoding. On the other hand, in the true causal direction, knowing the times of the cause leads better knowledge of the delay and hence a lower cost, long as the delay distribution (i.j provides a better description than treating it as noise. This requirement is closely related to the algorithmic Markov condition, which postulates that the shortest description of variable is given through its parents.
3.3 Connection to Hawkes Processes
Hawkes processes 19 analytically convenient and well-suited for modeling real-world processes where events trigger further events, e.g. earthquakes triggering aftershocks. Consequently, the majority of methods focusing on Granger causality are based on Hawkes processes [T33]. The Hawkes process extends the Poisson process by incorporating the influence of past events on the intensity, i.e. the rate of occurrence future events. This is done by means of excitation functions vt.((t fx), ), which increase/inhibit the intensity of future events based on past events. The intensity function of Hawkes process under a DAG structure is given by
(t(t) = u Σ Σ
Vit (t - [x)
SEpa(j) EE,
Each event 1 S; increases the intensity of seeing an effect by vi.5(( - (x). The main difference between our model and a Hawkes process is our direct trigger model from cause to effect. In a Hawkes process, an event of type increases the intensity and, therewith, the probability of effect events occurring. That is, contrary to our framework. in Hawkes process there is no explicit one-to-one relationship between causing and effect events, i.e. no one event can be attributed solely to causing another. Nonetheless, in Appendix A.5 we show how to identify S; as parent of S, by constructing a sequence of delays مر- with the most-influential past event and therewith Φz.j- If Φs.j fulfills Theorem 2 we can identify S, as a parent of Sy. Hence, should the data be generated by Hawkes process, our method can still pick up the causal relationship between the two event classes, so long as there sufficiently many events where S; is the primary cause.
4 Algorithm
With our model in place, we now turn to the problem of discovering the underlying causal structure from observed sequence of events. In recent years, several methods that find and proceed on a topological ordering of the true graph have been introduced (20-22), which outperform other score-based frameworks such as GES (23 in terms of accuracy. We here propose the CASCADE algorithm that instantiates this idea for iooormation-thhorede scores. We prove that in the limit, it recovers not only the correct topological ordering but also the correct parent set of each node.
CASCADE derives its guarantees from the gain in bits of adding an edge + j to the model, i.e
g(i +) L(S,) SmaG); θ L(S, Spa(jjui, θ J ( + L(i + +)
The edge cost L(i + j) is constant and independent of the number of samples n4. In the limit n4 - 00, the gain inherits the identifiability guarantees from Sec. 3.2 such that g(i + j θ) > g(j + θ) if S, is true ancestor of Sj. In other words, the gain of an edge is greater in the causal than in the anti-causal direction.
4.1 High Level Overview
CASCADE initializes the model θ with an empty graph G and without any causal edges. During the search, we maintain a set of nodes C' [p], from which we remove nodes in a topological order of G* We iterate over the following four steps until C is empty.
1. Source Node Selection: Select that node E C' with minimal gain for any edge + i,
j C. i.e.
JEC arg min max g(j + () g(i - 1 iEC
(4)
2. Edge Adding: Add all outgoing edges from j. C, to G that improve our score.
3. Edge Pruning: Remove all incoming edges j from G that harm score.
5

---

4. Node Set Update Remove i from C.
Each iteration, CASCADE selects that node i, which has the minimal achievable gain when adding any edge j + the current graph G, expressed in Eq. 4 below, we will show that under our causal model this node is guaranteed to be true source of the graph G*. We then add all edges from i nodes j C that improve our score; provided that all true causal edges i + j were added, there is now at least one node j E C' whose parents are all accounted for, that in the next iteration can be identified as a source. We remove edges j + from G to remove shortcuts. By repeating this process, CASCADE proceeds in topological order of the true graph G". In total, CASCADE requires p iterations, leading to an overall cubic complexity (p²))
Source Node Selection. To identify a source node in the graph, we can use the identifiability guarantees from Sec. 3.2 They show that the gain g + j b) correctly orients the edge i - j in the unconfounded bi-variate case. We additionally require that the edge gain is pathwise oracle, i.e. it can identify the direction of the path from to k.
Theorem 3. Given event sequence S generated by causal structure G let St be source node of G and S. be a descendant of Si, where there exists a path + - ... -+ 1 in G".
Then, the gain in the causal direction of the path g(i + () g(v + i () is greater.
We provide the proof in Appx.A..3 We can now show that the criterion in Eq. selects nodes in topological ordering of G Initially, CASCADE has to identify a true source of G", i.e. node i without parents. For that node i, all other nodes j are either ancestors or independent
If is an ancestor of j. then oi + i )) g(i j +) < 0, i.e. the gain in the anti-causal direction is lower. If i is independent of j. then ز( + i () = 0 and g(i + j () = O. Hence, the maximum achievable gain for node without parents is zero.
Now consider a node y which does have a parent. For this node, there exists an ancestor u which is a true source. Hence, for that pair g(u - v () g(v + u () > O. Consequently, the maximum achievable gain is positive, whilst for a source node, we can maximally achieve zero, allowing us to identify true sources with Eq.
In the next step, add all outgoing edges from the source i G that improve the score. As G* is DAG, we are now guaranteed to have another node j, whose incoming edges are all accounted for in G. Then, as per the causal model from Eq. (3). the only events that remain are those of the noise Nj. Hence, j is now source node for which the guarantees from above apply. By repeating this process, CASCADE thus follows a topological order of G*.
Edge Addition Given a source i, CASCADE adds all outgoing edges i - that improve the score. We restrict the set to nodes j C' from the candidate set only, i.e. to nodes further down the topological order. By the Algorithm Markov Condition, the description length of the true set of parents of a node j is smaller than the description length of any other set of parents, and hence the gain of the true edge is positive in the limit of n; 0o.
When adding an edge i + j. where there is already edge - j. we use an Expectation Maximization approach to attribute all events to their respective cause. That is, we first find the bi-variate alignment Âi-i using all events in Sj. Now, is very likely that there are conflicts between Ai-ej and A as the same event can be attributed to both and v. In those cases, we choose that event where the density / is higher and the delay to infinity in the other matching. After ce-assigning all events, we refit the delay distribution function Φi,j using the new matching.
Edge Pruning Lastly, we deal with removing any shorteuts that have been added in the previous iteration. With the previous two steps, we are guaranteed have a superset of all true causal edges incoming to i. Fortunately, we can prune such edges directly with MDL by removing any incoming edge + j that does not improve the MDL score. In the chain graph + j + v, we would remove i + v as the edge - v is sufficient to explain the data. In practice, given the current set of parents of in G, we search for the true set of parents by starting with the empty set and greedily adding only those edges that improve the score.
V
Figure 2: Causal chain
As we show in Appx. A.3 shorteut always has lower gain than the true edge and hence will not be

---

re-added. In this manner, we are asymptotically left with only the true causal parents. We can now finally show the consistency of CASCADE.
Theorem 4. Given an event sequence S, where each individual subsequence S, was generated as per Eq. (3 by an underlying causal graph G*. Assuming all Âi-j are the true causal matchings. Under the Algorithmic Markov Condition, CASCADE recovers the true graph G for n + 0o.
We postpone the proof to Appx. A.7 In the experiment section, we show that CASCADE recovers the true DAG even in challenging settings and works well on real-world data.
5 Related Work
Causal discovery on observational data is an active research topic. Two main research directions exist: constraint-based [5] and score-based [23 24 methods. Our approach belongs the latter and is based on the Algorithmic Markov Condition 6 While Kolmogorov complexity is uncomputable, Marx and Vreeken [0] formally showed that if we instantiate the AMC with two-part MDL 77]. we, expectation, achieve the same results. MDL has been successfully used for bivariate causal 26 causal discovery [27]. identifying hidden confounding [28]. identifying
inference [25 13
mechanisms shifts [29] and identifying selection bias [30]
In this paper, consider point processes. Particularly close our method are Hawkes processes 31 as a way to model the influence of past events onto future events. As such, our work is also related the concept of transfer entropy [32], which measures the influence in terms of Shannon entropy. Budhathoki and Vreeken B3 proposed an MDL-based method for bivariate causal inference on event sequences, which unsuitable for learning a global causal structure.
Existing methods for discovering causal graphs from event sequence data focus on different instan- tiations of Granger causality and mostly be categorized by different intensity functions. Most common are parametric approaches with different regularizing [34] [. ADM4 (34] uses the nuclear matrix norm in combination with lasso, THP 2 uses BIC for regularization. The method MDLH by Jalaldoust et al. (3] is most closely related, as they also use MDL for regularization. NPHC 35 takes porammrmetriiic approach by using a moment matching method fit second and third-order integrated cumulants. A recent development is neural point processes. Mei and Eisner (36) propose a deep neural network that learns the dependeneies (36), which Xiao al. [37] extended include attention mechanisms. Zhang et al. (38) first learn neural point process and then use feature importance attribution method obtain weight matrix of pairwise variable influence.
6 Experiments
We evaluate CASCADE both synthetic and real-world data. CASCADE is implemented in Python. We provide the source code, along with the synthetic data generator and the used real-world datasets online[] We compare
method to four of state of the methods: THP 2 representative for the regularized parametric approaches, CAUSE (38 as representative for the neural point processes and NPHC (35) as a representative non-parametric approach, and MDLH [39] who also rely on MDL, as our most closely related competitor. CAUSE and NPHC do not return a graph but rather a weight matrix where the weight indicates the strength of the causal relation. On synthetic data, we can obtain a graph by thresholding such that we optimize the F1 score.
6.1 Evaluation
We evaluate the estimated graphs in terms of structural similarity by the Structural Hamming Distance (SHD) 40), in terms of causal similarity by the Structural Intervention Distance (SID) [41], and predictive performance by Fl score. To compare graphs of different sizes, we report the scores normalized by the maximally achievable SHD/SID and show the unnormalized scores in Appendix B
NPHC, CAUSE, and MDLH can and often do return cyclic graphs. As SID is strictly only defined for acyclic graphs, we omit these methods from the SID evaluation.
https://eda.rg wwwpeeddrrr...pp....o.oooo Tatspa.io/pp/// cispa..o//pr//cccccae
7

---

0.5
0.003
0.4
SHI
NPHC
0.2
0.1
10
1.5
20
90
100
.0004
.0003
STD
S1D
0002
0.2
.0011
90
100
0.8
0.6
7
E
4
11_
0.2
8:
0.9
0.8
0.7
0.6
0.5
# Event Types
Noise level
# Event Types
(a)
(b)
(c)
Figure 3: DAG recovery in different settings. We show normalized SHD, normalized SID, and Fl score, the Y-axis are truncated for better visualization. In (a) we vary the number of event types, on the SID score we observe that the graph reported by CASCADE is casually, the most similar to the true DAG. In (b) we decrease the noise, CASCADE does recover close causal graph, even under high noise. Finally, in (c) we increase the number parents collider, we observe that a high number of parents does not pose problem for CASCADE.
6.2 Synthetic Data
We begin by comparing all methods on data with known ground truth. To this end, we generate synthetic data. We generate both data within and outside our causal model and vary aspects such as noise intensity, number of event types and the number parents of a variable, We describe the full data-generating process in Appendix B
Sanity Check We start with a sanity check on data without any structure over 20 variables, CASCADE correctly does report any causal edge. THP reports in 45% of the cases at least one spurious edge. We omit the results of CAUSE and NPHC as is unclear how to choose a meaningful, non-trivial threshold, this setting. MDLH did terminate within 96 hours.
Scalability We evaluate how well each method scales under an increasing number of variables. We vary the number of nodes, which correspond to the number of unique event types, from to 50 and report the results in Fig. Bal As MDLH did not terminate within 96 hours for 15 variables, from here on out. For a lower number of nodes, both CASCADE and THP obtain far better results than NPHC and CAUSE. With increasing event types, all methods SID and Fl scores decrease. Amongst all methods, CASCADE scales best with an increasing number of nodes, whereas Granger causality based methods such THP and NPHC find many spurious edges of connected but not causal variables. On the other hand, CASCADE is the most accurate method for a higher number of nodes, showing the efficacy of its causal model and MDL-based approach.
omit
Noise Next, we assess the impact of noise, which are events that is not caused by any parent. To this end, we vary the 'cause" probability and the fraction of events due additive noise. We do so by varying noise parameter adding an additional n; a events to S; (additive noise), and by setting the 'cause" probability a
a, i.e. we decrease additive noise and increase trigger probability. We show the results in Fig. 3b We observe that CASCADE does quite well for high noise and that for noise levels of a = 0.7 and lower, it (mostly) recovers the true DAG. All other methods perform considerably worse.
8

---

Matching an effect event to the correct parent, resp. modeling the correct excitation, becomes increasingly challenging for a larger number of parents. We test this through a setting where half ( (1 the variables converge into a collider, and the other half ( - are independent. We vary the total number of variables, P and we show the results in Fig. 3c We observe that CASCADE achieves almost perfect results. THP is robust, but with an increasing number of nodes, starts to miss edges. Beyond 100 variables, it does not terminate within 24 hours. To validate that our method can recover structures with multiple colliders, we repeat the same experiment where 10% of nodes are colliders. That is, for 50 event types, 5 are colliders and 23 direct causes of all 5 colliders. The remaining 22 are independent. Resulting in an F1 score of 0.97 for 50 event types, slightly decreasing to 0.82 for 200 event types; as such CASCADE can deal well with multiple colliders.
Colliders
Instantaneous Effects Next, evaluate performance under instantaneous effects. First, consider data with exclusively instant effects. CASCADE achieves an average unnormalized SHD of 32.8. The second best-performing method, NPHC, achieves 46.85. Next, we generate a setting where 90% of the effects are instantaneous and the others occur with a small delay, CASCADE improves to an SHD of 19.45, while NPHC achieves the second lowest average with 47.5. We provide all results in the Appendix B
Finally, evaluate how effecttivlly CASCADE recovers the true DAG on data generated by a Hawkes process. We vary the intensity of the excitation function, i.e, the expected number of events generated per cause. We show the results in Figure 4 We observe that CASCADE performs best when our assumptions hold, when there is one effect per cause fewer, but still demon- strates strong performance across all settings.
Hawkes Processes
E
0.5
0.4 0.7 1.0 1.3 1.6 1.9 2.2 288 3.1 Expected Events per Cause
Figure 4: DAG recovery on data gener- ated by a Hawkes process.
6.3 Real- World Data
We evaluate CASCADE on three distinct datasets of real-world event sequences. We begin by evaluating CASCADE on dataset of network alarms, where the causal structure is known.
Network Alarms This data was provided by Huawei for the NeurlPS 2023 CSL-competitior/ and consists of data from simulated network of devices in which alarms can cause other alarms. We run all methods and get an (unnormalized) SHD score of 42 for CASCADE, 127 for THP, 214 for NPHC, and 1564 for CAUSE. As the network connectivity structure is known, during the search. THP supports this natively, CASCADE can be trivially constrained to only consider the given edges. CASCADE correctly identifies 142 out of 147 causal edges, THP 20. Neither method reports spurious edges. We show the full recovered graph in Appendix B.5
take it into account
Global Banks Second, we run CASCADE on daily return volatility dataset 42), we follow the preprocessing Jalaldoust al. (3, specifically we turn the time series into an event sequence by rolling one year window over the data and register an event if the last value is among the top 10%. The dataset includes the 96 world's s largest publicly traded banks. We show the largest discovered subgraph in Fig. [ In addition, three unconnected sub-graphs are discovered, one covering two banks in Australia and two others connecting banks in Japan, which we provide in Appendix B.5
Daily Activities We run CASCADE on a dataset of recorded daily activities [43] Our method reports plausible causal connections such as Sleeping End -+ Showering Start + Showering End - Breakfast Start + Breakfast End, etc. We show the complete graph in the Appendix [B.5] This result reinforces the suitability of our causal model and CASCADE for real-world data, and illustrates the potential of our method to discover causal structures in a wide range of applications.
Conclusion
We studied the problem of causal discovery from event sequences, we propose cause-effect matching approach to learn fully directed acyelic graph (DAG). To this end, we introduced a new causal model

---

Auda Europe
Australaa
Crigruup
10 Bunks
Milayan Banking Berhad
Americai
Wide
11. Brosog
Sundan
Starts
Ngoond
Smifrol
Ameek
BBAT Ciry
jesoiga Clace
Bank of Amrrica
State Strvet Corportiin
BMO
Melho
Credi Eenn
Suioo
KB
Eonde Apaloee
ING
Cloyke
Norioa
Commerzbbnk
Danite
Sverola
UNBS ASA
CIBC
ANZ
Regios Fanrca
R15
Dom bop
Goldear
Fajjois Bank
Group Bank
RBC
Figure 5: Result of CASCADE on the Global Banks dataset, we show the largest subgraph, we highlight the 10 largest, by assets, banks. We clearly CASCADE recovers locality and that larger banks have a strong influence on the market, both information not provided in the input.
and an MDL based score. We proposed the CASCADE algorithm discover causal graphs through topological search from observational data. Finally, we evaluated CASCADE on synthetic and realistic data. On synthetic data, we find that CASCADE is either the best or close to the best-performing method across all settings, both within and outside our causal model. In particular, whenever conditions get challenging, e.g. due to noise or with multiple colliders, CASCADE outperforms all other methods by significant margin. We examined how CASCADE performs on real world event sequences, where the true sata-geenrating process may lie outside our causal model. We found that CASCADE recovers meaningful graphs that match with common understanding of the world.
Limitations As is necessary, we have make causal assumptions. The most prominent in our work is the direct matching between cause event and an effect event - which precludes modeling of a single event causing multiple other events, as well multiple events jointly causing single effect event and that we only consider excitatory effects which precludes modeling the absence of events due to cause. Our proof of identifiability for instantaneous effects depends on the strengths of the trigger resp. noise probabilities. The identifiability of the model seems provable via the independence of these, but how to operationalize this into an effective score and search algorithm are open questions.
Future Work Currently, our structural equations are 'or' relations over the parent's variables. An interesting future direction would be to explore 'and' relations, c.g., and together cause C. This raises several questions, like how close to each other A and B have to occur or if the order matters. Another interesting future direction event, where each parent could have caused the event. This would allow us to answer counterfactual questions, such as if causing event had not occurred, would we nevertheless observe its effect? This strongly relates to the firing squad example by Pearl (5), where multiple guards shoot a prisoner at the same time; if one guard did not shoot, the prisoner would still have died.
allow matching of multiple causing events one
10

---

References
[1] Hongteng Xu, Mehrdad Farajtabar, and Hongyuan Zha. Learning granger causality for hawkes processes, In International conference machine learning, pages 1717-1726. PMLR, 2016.
[2] Ruichu Cai, Siyu Wu, Jie Qiao, Zhifeng Hao, Keli Zhang, and Xi Zhang. Thps: Topological hawkes processes for learning causal structure on event sequences. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[3] Amirkasra Jalaldoust, Kateñina
Sarriükkvv--Schinlle and Claudia Plant. Causal discovery in hawkes processes by minimum description length. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6978-6987, 2022.
[4] Clive WJ Granger. Investigating causal relations by econometric models and cross-spectral methods. Econometrica; journal of the Econometric Society, pages 224-438, 1969.
[5] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, 2nd edition, 2009.
[6] Dominik Janzing and Bernhard Schölkopf. Causal inference using the algorithmic markov condition. IEEE Transactions on Information Theory, 56(10):5 16855519,,,,, 2010.
[7] Peter Grünwald. The Minimum Description Length Principle. MIT Press, 2007.
[8] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[9] Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, volume 3. Springer, 2008
[10] Alexander Marx and Jilles Vreeken. Formally justifying mdl-based inference of cause and effect. In AAA/ Workshop Information-Theoreel Causal Inference and Discovery (IT'C'222) 2022.
[11] Donald C Weber. Accident rate potential: An application of multiple regression analysis of a poisson process, Journal of the American Statistical Association. 66(334):285-288. 1971.
[12] Jorma Rissanen. A universal prior for integers and estimation by minimum description length. 11(2):41-431,, 1983.
[13] Jonas Peters, Dominik Janzing, and Bernhard Schlkopf. Elements of Causal Inference: Founda- tions and Learning Algorithms. The MIT Press, 2017. ISBN 0262037319.
[14] Jonas Peters, Dominik Janzing, and Bernhard Scholkopf. Causal inference on discrete data using additive noise models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(12):243--2500 2011.
[15] Kailash Budhathoki and Jilles Vreeken. Accurate causal inference on discrete data. In Proceed- ings of the IEEE International Conference on Data Mining (ICDM' 18). IEEE, 2018
[16] Murat Kocaoglu, Alexandros Dimakis, Sriram Vishwanath, and Babak Hassibi. Entropic causal inference. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
[17] Vanessa Didelez. Graphical models for marked point processes based local independence. Journal of the Royal Statistical Society Series B: Statistical Methodology, 70(1):245-25) 2008.
[18) Michael Eichler, Rainer Dahlhaus, and Johannes Dueck. Graphical modeling for multivariate hawkes processes with nonparametric link functions. Journal of Time Series Analysis, 38(2): 225-242, 2017.
[19] Alan G Hawkes. Spectra of some self-exciting and mutually exciting point processes. Biometrika, 58(1):33-99 1971.
[20] Peter Bühlmann, Jonas Peters, and Jan Ernest. Cam: Causal additive models, dime-aimensional order search and penalized regression. The Annals of Statistics, 42(6))2526-2555 2014.
11

---

[21] Paul Rolland, Volkan Cevher, Matthäus Kleindessner, Chris Russell, Dominik Janzing, Bernhard Schölkopf, and Francesco Locatello. Score matching enables causal discovery of nonlinear additive noise models. In International Conference on Machine Learning, pages 18741-18753. PMIRR 2022.
[22] Spencer Compton, Kristjan Greenewald, Dmitriy Katz, and Murat Kocaoglu. Entropic causal inference: Graph identifiability. In International Conference on Machine Learning, pages 4311-4343. PMLR, 2022.
[23] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-55) 2002.
[24] Joseph Ramsey, Madelyn Glymour, Ruben Manchez-Romero, and Clark Glymour. A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images. Interna- tional journal of data science and analytics, 3:121-129, 2017.
[25] Alexander Marx and Jilles Vreeken. Telling cause from effect using mdl-based local and global regression. In 2017 IEEE international conference on data mining (ICDM), pages 307-316. IEEE, 2017.
[26] Sascha Xu, Osman Mian, Alexander Marx, and Jilles Vreeken. Inferring cause and effect in the presence of heteroscedastic noise. In Proceedings of the International Conference on Machine Learning (ICML). PMLR, 2022.
[27] Osman A Mian, Alexander Marx, and Jilles Vreeken. Discovering fully oriented causal networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8975-8988 2021.
[28] David Kaltenpoth and Jilles Vreeken. Nonlinear causal discovery with latent confounders. In Proceedings of the International Conference on Machine Learning (ICML). PMLR, 2023.
[29] Sarah Mameche, David Kaltenpoth, and Jilles Vreeken. Learning causal models under indepen- dent changes. In Proceedings of Neural Information Processing Systems (NeurIPS). PMLR, 2023.
[30] David Kaltenpoth and Jilles Vreeken. Identifying selection bias from observational data. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). AAAI, 2023.
[31] Alan G Hawkes. Spectra of some self-exciting and mutually exciting point processes. Biometrika, 58(1):83-90, 1971.
[32] Thomas Schreiber. Measuring information transfer. Physical review letters. 85(2):461, 2000.
[33] Kailash Budhathoki and Jilles Vreeken. Causal inference on event sequences. In Proceedings of the 2018 SIAM International Conference on Data Mining, pages 55-63. SIAM, 2018.
[34] Ke Zhou, Hongyuan Zha, and Le Song. Learning social infectivity in sparse low-rank networks using multi-dimensional hawkes processes. In Artificial Intelligence and Statistics, pages 641-649, PMLR, 2013.
[35] Massil Achab, Emmanuel Bacry, Stéphane Gaïffas, Iacopo Mastromatteo, and -ean-FFannois Muzy. Uncovering causality from multivariate hawkes integrated cumulants. Journal of Machine Learning Research, 18(1 1--12))1-228 2018.
[36] Hongyuan Mei and Jason M Eisner. The neural hawkes process: A neurally self-modulating multivariate point process. Advances in neural information processing systems, 30, 2017.
[37] Shuai Xiao, Junchi Yan. Mehrdad Farajtabar, Le Song, Xiaokang Yang, and Hongyuan Zha. Learning time series associated event sequences with recurrent point process networks. IEEE transactions neural networks and learning systems, 30(10):3 2019.
[38] Wei Zhang, Thomas Panum, Somesh Jha, Prasad Chalasani, and David Page. Cause: Learning granger causality from event sequences using attribution methods. In International Conference on Machine Learning, pages 11235-11245. PMLR, 2020.
12

---

[39] Amirkasra Jalaldoust, Kateñina Swwwaäkkvv-Schhindle and Claudia Plant. Causal discovery in hawkes processes by minimum description length. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6978 6987,
[40] Markus Kalisch and Peter Bühlman. Estimating high-dimensional directed acyclic graphs with the pe-algorithm. Journal of Machine Learning Research, 8(3), 2007.
[41] Jonas Peters and Peter Bühlmann. Structural intervention distance for evaluating causal graphs. Neural computation, 27(3):771-799, 2015.
[42] Mert Demirer, Francis X Diebold, Laura Liu, and Kamil Yilmaz. Estimating global bank network connectedness. Journal of Applied Econometrics, 33(1):1-15, 2018.
[43] Feo Javier Ordónez, Paula De Toledo, and Araceli Sanchis. Activity recogmition using hybrid generative/diseriinattv models on home environments using binary sensors. Sensors, 13(5): 5460-5477, 2013.
[44] Dominique MA Haughton. On the choice of model to fit data from exponential family, The annals of statistics, pages 342-355, 1988.
13

---

A Theory
A.1 Proof Identifiability on Instant Effects
Theorem 1. Let S; be an event sequence generated by a Poisson process as per Eq. 1 and Sj be an effect of St as per Eq. (3) with, low noise X3 (1 (4. Aa, and trigger probability az < 1. In the case of exclusively instant effects, i.e. ) = 8(d), where 5(d) is the Dirac delta function, the MDL score in the true causal direction is lower than in the anti-causal direction, i.e.
lim L(S, St θ1) + L(S. 11) L(S, S,. 02) + L(S) (2)
D2 +00
Proof.
Let ny be the number events in S; and n, the number of events in Sy. As n, + oo
L(S,) (o.,), L(S)(S,) - (B(a,,))))))
where B is the Bernoulli distribution. In the reverse direction, we have
L(S,) H(55))
L(S](S)) = n, (B((,((),))) + (n+ (di.))
To show
T(S.) + ((S)SS)) < ((S,) ((),S,) n. ( (B(()() < ny H + n,H (B(as.))) + (n; - (()))((b))))))
since every event that does not cause can not be explain by j in the reverse direction, Oijj 0s (5, hence
(0:.) + + (n: n ((i.))
(HH() <n.HH(0))=+n.(000))-))))))
[.H() < + ((o)))
(oi)) < (n,ll(05s)
H(dr,) < H())))
For ((r,) < H(05.) to hold n, > ng.
n4 di
n₂ x asij2tt t2
>; > anidii + Aj
X - a X1
(1 air)di>> Aj
directly follows that ((b,)) < H(65s), and hence for nı - 0
L(S,|8., 01) + ((S,Or) S(S θ2) + L(S)
A.2 Proof Identifiability on Delayed Efffett
Theorem 2. Let Sy be an event sequence generated by a Poisson process as per Eq. and S, be an effect of S; per Eq. 33. such that H (dis) > H(p(; - H (B(o.,)) + 0 H (B(aga)), where H denotes the entropy and B the Bernoulli distribution.
Then the matching in the anti-caused direction Az-s of the effect S, to the cause S; has worse MDL score than the true matching Ai-3 i.e.
L(S, S, 0,,)) + L(S, O2) < L(S,) S,, 9G-r) + L(S, O,))
14

---

We will show that the delays between S; itself. i.e.A, and the delays between Sy to St. i... As-j- are equivalent.
Proof. We consider a source event S; with exponentially distributed delays, i.e. A:-i exp(A:). Consider any event la E Sj. then the intensity of observing an event in S; at time > la is given by d₁- The distribution of the delay the next event in S; exponential with A3. Thus, the difference between
[(S)(S)) L(S,) = Σ
log(As) dz/As
Σ diEAi
log(A:) + di/A; =0
de deEAi-j
remains show that the likelihood in the causal direction is better when conditioning effect on the cause, i.e. [(S)(S:) < L(S)).
Gain by i j For to cause has to provide information about j. that the cost selecting which i events cause j, and with what dealys. Additional it has to ofset the cost which events do have be encoded as a self delay. Formally this is,
n: (B(((()))) + nh (p(::cn)) + n, (BI (is))
ni ((ojs)
ni
where ni,j are the number events in caused by i, and H Hp(: (sg)) the entropy of distribution described by the pdff
As 00.
- n. = H(5j))
L(S][S:) n.H(dss) (mg= ((
To show,
L(S,) L(S)(S))
n n,H(o n. ((()))) - [
ni.j ((s.s) + b,)=
n4. ((,H(() > 1,
we can substitute n; n:H(d.))) = m.j H(p(
ni n 0 (. + n n2
Now, note that the number of caused items an n.j and igj n4.j then it follows
ni. H()))) n..j H(p(: 0, + Ri.j (B((,,,))
ni.j H(B(ags))
a:j
1 ((((a,)))
H(O)a) Hp(: ()) HB((a))))
aij
ajj
Hence, we show that + j is identifiable.
A.3 Proof Path Identifiability
Theorem Given an event sequence S generated by causal structure G*, let St source node of G and S, be descendant of S,, where there exists path + v in G*.
Then, the gain in the causal direction of the path gli u () - g( + () is greater.
Proof. We begin by proving that the path identifiability holds for triplet of nodes i + j v. by constructing a new alignment from + u.
From Ai-z and A jo we can construct A,- For each da E Ai-ij- there is corresponding di E Ay- i.e. the trigger time of the triggered event. construct Aç- we consider the following cases:
15

---

1. If d2 3o for d2 E A.-j, then dy E A,-v, is set to de oc.
2. Let di E Ar- be the delay of event a of type j where a has been caused by delay dę. If
du + oo for d2 Di-j and di = oo then then dę E Ai-so is set to 2c.
3. Let di E A, be the delay of event of type j where has been caused by delay dg. If dx # xo for d A.-s and di * oo then then dy E A is set to d3 = dy + dl.
As Ai is another valid alignment, and remains a source node, the guarantees of Theorem I and hold, i.e. the path is identifiable. This extends a path of arbitrary length. Consider an additional edge + then we construct the alignment A by considering the delays of Ai-v and A A-tw- Furthermore,
show that the true path v has a better gain than the shortcut - v, that can remove the shortcut in the pruning stage. (1) Since + and j - v are independent processes, it follows either Var(ór,)) > Var(03..); OKi, Oj," and by that a more costly description of
(2) j v á G we can construct a new function fú, = S3,o Ar-)) U Nj, Ay-r) by
Theorem 2 follows that edge
improves score.
(3) Assume + E G then each individual v event that is matched by already matched to by + and from (I) we know it does so cheaper, hence we get no gain by adding the shortcut i +
A.4 Consistency
Proof. Here we will show that L(S", "iss", θ) asymptotically behaves like BIC.L(S, Q) directly corre- sponds the log likelihood, which we rewrite log (OS" G) Our approach can be instantiated with arbitrary delay distribution, to show consistency we have to upper bound the number of param- eters by (log n)), this trivially holds for the parametric setting we focus on in this paper, because [pa(t)] (log n) (27]. The encoding of the graph G is independent of n, i.e. fixed for given network, hence in (1). Finally this results at,
pggp(S" O G) + clogn n + O(1)
set 5 where is the number of free parameters, arriving the BIC score.
From Haughton 44 and Chickering (23] we know that BIC identifies a Markov equivalence class of the true DAG. For the identifiability of undirected edges we refer to Theorem and
A.5 Connection to Hawkes Processes
The key difference between linear Hawkes process and model is the assumption of direct triggers, that is the mechanism of one event and one event only causing another. In a linear Hawkes process 'cause events' increase the intensity and therewith the probability of events occurring. However, one can generally not label for a specific event another as the 'cause', as each event is the result of a multitude of causes.
In this section, we are going to explore under which conditions we can identify a Hawkes process under our causal model.
Given an event sequence S, [t*) generated by linear Hawkes process,
(t) uj Σ
Σ
Vi,s (t t+)
(Epa() ba E...EE
We construct a set of primary causes for each event tx E Sg as
C c-- (t,ittt)) -
arg max (i.t), (e where we consider as primary cause of an event that past event with the highest influence at time point from a causal parent i E pa(j). Using these delays, we construct an alignment (mapping of delays) as
Sj, (i,tx)
Piz(t - tx)
16

---

[t 1 B(xx)
Vig(( tx) > Uj
A,-, (B(4x) l E Si)
0c
else
where t arg S33
We consider t E S2 cause of an event & Sy if it is the primary cause of and & has stronger influence any other event of Sy. Finally, the influence has to be stronger than that of the base intensity of Sy-
Pty(t te) if it, 1,t)) Cj then B((x)
To be able to identify a causal edge between S; and Sj the improvement gained by this alignment must outweigh the edge cost L(i j). For this, there are two conditions: firstly, the number of primary cause events from to j. i.e. those instances where influence on an event from S,, must be large enough. This is the case as long as ارزز increases with nj. i.e. the total number of events of Sj. Then, in the limit n + oo the number of primary cause events is large enough to offset the constant edge cost.
event from S; has the maximum
The achievable score gain is obtained by constructing a delay distribution from | as
Oiijj (i.((d) (Pa.., (d) oij else
if d == 0
where atj P(A o0)
this density (d) fulfills the conditions of Theorem limit of ny 00.
we can identify S; as parent of Sj in the
In conclusion, CASCADE can identify causal pair generated under Hawkes process, there exist sufficiently many events from S; - Sj. where Vs (t) has the strongest influence on (t) for some of the t. By aligning the delays of these events, we can identify the causal edge and recover the underlying causal structure.
A.6 Empirical Evaluation
[From main paper] To empirically evaluate how effectively CASCADE recovers the true DAG on data generated by Hawkes process, we generate synthetic data using the tick library We vary the intensity of the excitation function, i... the expected number of events generated cause. We show the results in Figure 6 We observe that CAS- CADE performs best when our assumptions hold, when there one effect per cause or fewer, but still demonstrates strong performance across all settings.
E
0.5
0.7 1.0 1.6 1.9
Expected Evenis per Cause
Figure 6: DAG recovery data gener- ated by a Hawkes process.
A.7 Consistency of Algorithm
Theorem 4. Given an event sequence S, where each individual subsequence S, was generated as per Eq. 33 by underlying causal graph G*. Assuming all Ai-j are the true causal matchings. Under the Algorithmic Markov Condition, CASCADE recovers the true graph G for n + Do.
Proof. We begin by proving that the first step, CASCADE identifies true source node of G*. We denote the parents of in the true causal graph G" as pa(i), whilst write for the parents in the graph maintained by CASCADE as pa' (i, G).
Let [p) be node of G* without parents, i.e. a source. By Theorem 3 for path i ... the gain in the causal direction g(i + v +) is greater than the gain the reverse direction g(v + O).
G*
For all nodes u [p], v # v either an descendant of unrelated.
1. If is descendant of then the gain of g(i + () is greater than the gain of g(v + +).
2. If v unrelated to i, then the gain in both sides is 0.
https://2xdattainitiaatet github. io/tick/
17

---

Hence it follows, that for a node where pa(i) 0,
max
s(i + - () - -g(i + =0 JEC
On the other hand, consider a node i with parents pa(i) * 0. Then, as G is a DAG, there exists an ancestor of i, where v source node, i.e. pa(v) = 0. For that v, holds that the gain from to is greater than the gain from i to v. Hence, for node with parents, it holds that
max g(j - () - g + () > 0. jEC
Therefore, by taking the argmin over all nodes, CASCADE identifies the true source node of G i.e.
arg min max s(j + θ g + j| () = pa(() nc nc== = 0 sEC
JEC
Edge Addition Now, we show that CASCADE always identifies a true causal edge for n, - co. First, note that given source node i, there do not exist any incoming causal edges in the graph G*,
pa(i) nc 0 Bj
Hence, by fitting outgoing edges only, we test all possible edges for i and never add false oriented edge.
Vj CjECii+jer
= j-+i
Finally, we recall that the true causal graph G the graph that minimizes the description length of the data per the Algorithm Markov Condition. Hence, adding true causal edge to the graph will result lower description length, i.e.
Vj C,i+j L[SS))Sp 01) LSS pa (G:C)u O'U0;s)
Edge Removal Consider the node i, where pa(i) n 0, and given graph G where all true causal edges have been added, i.e.
VjeC:Vj-i - :j-
Then, for i it holds that
Vj ma) :1 : -i-
It follows, that pa' G) P (i). By the Algorithm Markov Condition, the shortest description length of the data is achieved by the true causal graph G*, Hence, superset of the true parents of will result in a higher description length, and it holds that
L(S (1), 0²) > L(S (a)(), 9)
Therefore, by testing that subset of the parents of results in a lower description length, CASCADE identifies the true parents of i.
Overall Consistency For n, + oo, note that in each step for the node i it holds that
1. has no parents in the candidate set pi()) nc = 0.
2. We add no false oriented edges to the graph, as pa(i) nc = 0 = tiE
3. We add all true edges i + j to the graph G, i.e. Vj C₁ + i G L(S, Spe' O') L(S)|Spen pua e' (.,g))
4. For i, the current graph G contains a superset of all true parents, i.e. (i. G) 2 pa(i). while the description length of the data is minimized by the true graph SSm 0¹) L(S θ).
Hence, by repeating the edge addition and pruning in topological order, in the limit of oo under our causal model and by the Algorithm Markov Condition, CASCADE identifies the true causal graph G
18

---

B Experiments
In this section we provide additional detail on the synthetic data generation and the experiment setup. Additional provide further metrics the synthetic experiments. For the real-world data provide additional results.
B.1 Synthetic Experiments
We generate synthetic data according to our causal model. We discretize the timestamps to million unique timestamps. Throughout the experiments vary the following parameters:
Variables: Number of unique events types p.
Edges: The total number edges in the generating causal graph G+.
Delay Distribution: For all synthetic experiments we generate delays according to geometric distribution (as a discretize instantiation of the exponential).
Delay Distribution Parameter: For each causal edge we sample the uniformly from specified range.
Cause probability: For each causal edge we sample uniformly from specified range.
# Source Events: Number of events sampled for source nodes (variables without any parents in the DAG).
Additive noise parameter: percentage of additional added events to the caused events, also applies to source nodes, where # Source Events are considered as 'caused'.
Instant effect: Except for the 'Instant Effect' experiments no instant effects are created.
For all experiments, unless otherwise stated a random DAG is generated. And for each parameteriza- tion 20 independent samples are generated.
Sanity Check We set the number of types to 20 and generate 100 root events per source node (in this every node is source node).
Increase of Event Types In this experiment we increase the number event types p from 5 to 40, We set the number of edges to (d2 - d)/(2 * 5). that is 20% of all possible edges. To avoid overly many events in the colliders we set the number of root events to 20, for 40 variables this results in up to z 30.000 events. We do not include any additive noise and set 1. For the delay distribution, we sample À from a range between of [0.3, 1].
this experiment we increase the probability of a, and decrease the fraction of additive noise. We set the number of variables to 20 and set the number of root events to 100. We sample from a range of [0.1, 0.4]
Decrease of Noise
Distribution Misspecification To further evaluate robustness of CASCADE we test recovery on generated data where the actual distribution does not match the assumed distribution. To this end, change the assumed distribution of CASCADE and use the same setup as the previous experiment (Increase of Event Types) with 20 unique events. For the, true, exponential we observe average Fl score of 0.82, for the Poisson 0.81, with Normal distribution 0.76, and uniform 0.75. While recovery is best when assumed and generating distribution match CASCADE still performs well under misspecification.
Multiple Parents For this experiment we specify DAG, where [ are direct parents and n-1 are independent, the n node is the collider. We plant 30 events per root cause and increase the number of variables from 50 200. We add 30 % of additive noise and set the cause probability randomly between 0.9 and 0.6. We repeat the same experiment where 10% of nodes are colliders. That is, for 50 event types, 5 are colliders and -p-57 direct causes of all 5 colliders. The remaining 5 are independent. We show the results in Table
19

---

F1
Number of Colliders
0.97 #0.01
0.96 #0.01
0.95 #0.02
0.93 #0.01
0.92 #0.02
10
0,91 #0.01
15
0.88 +0.02
20
0.82 +0.01
Table 1: Average F1 score on Multiple Parents experiment with multiple colliders.
Fl
SHD
SID
SHD-Norm
SID-Norm
Method
CASCADE
0.74
19.45
104.10
0.05
0.27
CAUSE
0.19
264.50
NaN
0.69
NaN
NPHC
0.57
47.50
NaN
0.12
NaN
THP
0.23
64.20
180.70
0.16
0.47
Table Average results on 90% instant data
Instant Effects For the instant effects experiments we again use 20 variables with 100 events, we shift the geometric delay distribution and set À = 0.9, such that 90% of the events are generated the same timestamp. We randomly sample the trigger probability between 0.7 and 0.5. For the exclusively instant effects we set = 1. We show the full results in Table and
B.2 Method Parameterization
We set the precision parameter for all experiments to For all synthetic experiments consider events potential causes of most 100 timestamps. For all experiments consider geometric distribution, which we shift back to cover instant effects.
CASCADE
MDLH For the results of the Increase event types experiment set the maximum degree to the true maximal degree and set =10000. In an effort to reduce runtime with higher number of types (i.e. nodes), we tested it with T=100, where it also did not terminate within 96 hours.
the sparse version, where
Other For all other competing methods used the default parameters.
B.3 Compute Recourses
All experiments where executed on internal cluster on compute nodes equipped with AMD EPYC 7773X 64-Core Processor (2.2 GHz; Turboboost: 3.5 GHz), with TB of RAM, while in practice fraction of that was necessary. We provide the average runtimes below.
F1
SHD
SID
SHD-Norm
SID-Norm
Method
CASCADE
0.55
32.80
216.05
0.08
0.56
CAUSE
0.19
249.60
NaN NaN
0.65
NaN
NPHC
0.57
46.85
0.12 NaN
Table 3: Results instant effects, we omit the results of T'PP as it only reports empty DAGs
20

---

# Event Types
CASCADE
CAUSE
NPHC
THP
MDLH
5
2.05
6.50
4.30
2.35
3,00
10
2.80
9.50
4.25
3.55
16489.00
15
7.10
16.75
4.40
13.80
NaN
20
35.20
42.95
4.15
40.90
NaN
30
362.65
225.70
4.75
305.50
NaN
40
1957.65
890.45
4.85
1984.60
NaN
Table 4: Mean runtime, in seconds, Increase Event Types Experiment
Noise
CASCADE
CAUSE
NPHC
THP
0.10
147.85
231.50
4.55
97.20
0.50
66.85
176.85
4.40
71.45
0.60
42.75
142.30
4.50
61.55
0.70
25.20
113.30
4.40
51.35
0.80
14.05
76.75
4.25
41.65
0.90
7.55
48.60
4.45
32.95
Table 5: Mean runtime, in seconds, under increasing Noise.
B.4 Network Alarms
In the provided dataset each event happens specific device. In addition to the event sequences topology T over the devices is provided. event can cause an event on each neighboring device, in addition to the device where the event occurred. To support this we can include a matching for connected devices. That is if {a, b} T we include A (a.6) and A (b.a) iajs we include both directions
since events a can cause events on and events can cause events a. For all devices include the self loop A |
B.5 Real World Experiment
In this section we provide Causal Graphs reported by CASCADE and for the Globul Banks dataset additionally the result of THP.
Event Types
CASCADE
CAUSE
NPHC
THP
50
45.80
323.65
6.30
587.45
60
79.60
536.75
6.10
1596.55
70
131.30
904.50
5.90
3175.30
80
196.80
1129.00
6.45
5393.70
90
283.90
1513.60
6.95
8295,25
100
392.55
1941.80
7.20
12923.50
150
1479.60
4694.75
10.05
NaN
200
3736.70
9736.05
16.95
NaN
Table 6: Mean runtime, seconds, of Increase Event Types (Collider Experiment)
21

---

250
300
200
MULH
THP
CAUSE
200
SUD
100
150
NPHC CASCADE
100
100
50
0
-...
50
60
70
80
90
100
150
200
10
50
1,000
800
SID
600
150
4000
10000
200
50
60
70
80
90
100
250
10
15
20
30
40
0.8
0.8
0.8
0.6
0.6
E
0.6
0.4
0.4
0.2
8
6
0.2
0:
0.2
0,9
0.8
0,7
0.6
0.5
50
60
70
80
90
100
150
200
# Event Types
Noise
Types
Figure 7: SHD, SID, and Fl score for the synthetic experiments
Spare Time/TV end
Sleeping end
Leaving end
Leaving start
Lunch end
Lunch start
Spare
Showering start
Groopaing start
Toileting start
Steeping start
Snack stast
Time/TV
start
Showering end
Grooming end
Toileting end
Snack end
(a)
Spare Time/TV cnd
Sleeping end
Dinner end
Dinner start
Leaving end
Leaving start
Lunch end
Lunch start
Breakfast start
Toilebing start
Smück start
Sheeping start
Showering start
Breakfast end
Faileting eird
Snack
Showering end
end
Spare Time/TV
Growqiin
Grooming end
(b)
Figure 8: Recovered Causal Graphs on the two Daily Activities datasets.
22

---

Correctly Recovered
15
13
Not Recovered
24
28
29
30
31
52
38
40
49
Figure 9: Recovered Causal Graph on Network Alarms dataset.
Asia Furepe America
Australia
Clignup
Jayon
Malayan Banklng Berfad
Top in Banks
Deutsche
Well
Busoup
Sundanf
Natsoal
Carab
BB&T Comp
JPMoggu
Bank of Chuse
America
State Stocet Copporatoo
Bao
Mellid
Chedf Sun
KBC
Grest
Arsool
So
10104
ING
Lloyh
Nonta
Commertbni
Danke
CIBC
ANZ
Regions
Flnachl
LNSI
Eouaa Croup Bank
Nove Sosiia
Bartons
Goldioas Santa
Suppick
BAVA
RBC
Mizuto
Westpac Banking
Bank
Minubosti
Commonweallh Bank of Australia
Bank UX
Yokohuem
Chiba
Fuluooka
Figure 10: DAG reported by CASCADE on the Global Banks dataset 42 nodes for clarity.
We omit unconnected
23

---

BNP
Deutsche Pank
Bank of America
Citigroup
BB&T Corp
Bank Of
Tokohama
Paribus
BMO
Resona
ING
Morsan Stanley
BNY Mellon
PNC
HSBC
Lloyds
Commerzbank
SoeGen
Credit
Suisse
JPMorgan
National
Bank off Canada
SunTrust
U.S.
Вancorp
TD Bunk
RBC
Sumitomo
Capital
Fifth
Third
Chiba Bank
National
Australia
ANZ
American Express
Fukuoka
Figure 11: DAG reported by THP the Global Banks dataset 42
We omit unconnected nodes for
clarity.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims made in the abstract and introduction are supported by the findings and the main body of the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations and assumptions the conclusion.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We clearly state all theorems and proof them in the appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our results can be fully reproduced, we provide all the data and code online.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the full code along with the synthetic data generator. All used dataset are publicly available.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide experiment setup description in the appendix. We did not do any hyperparameter tuning. Our method does not require data splitting.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We show Box-Plots for all (synthetic) experiments.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: Yes, provide detailed description of the compute recourse in the appendix.
25

---

9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://pww..............o..aaaaa
Question:
Answer: [Yes]
Justification: Our research complies with NeurIPS Code of Ethics, we do not expect any harmful consequences resulting from our research.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We provided citations sources for all datasets.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We use only already publicly available datasets, and do not introduce any new. 14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No Human Subjects where involved.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
26


Reviews:
[{"review_id": "1EduMfmguG", "reviewer": "Reviewer_hRgg", "summary": "The paper introduces a method for identifying causal relationships in event sequences. The authors presents a causal model that handles both instantaneous and delayed effects, contrasting it with existing methods like Granger causality. This algorithm is evaluated on both synthetic and real-world datasets.", "questions": "1. How sensitive is the CASCADE algorithm to the choice of parameters for the delay distribution and cause probability?\n\n2. What are the practical limits of the CASCADE algorithm in terms of the number of event types and the size of the datasets?\n\n3. How does the algorithm handle high levels of noise in the data, and are there specific noise thresholds beyond which performance degrades significantly?", "limitations": "The authors discussed the limitation in the Conclusion section. The identifiability of instantaneous effects relies on the strengths of the trigger and noise probabilities, which may be challenging to estimate accurately in practice.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The theoretical foundation based on the AMC and MDL principle is provided.\n\n2. The proposed CASCADE algorithm is evaluated through extensive experiments.\n\n3. The paper is well-organized, with clear explanations of the proposed model, theoretical underpinnings, and algorithmic steps. The use of illustrative examples and detailed proofs enhances understanding.", "weaknesses": "1. The paper acknowledges assumptions such as the direct matching between cause and effect events and the focus on excitatory effects. However, it could provide more discussion on the impact of these assumptions and potential ways to address them.\n\n2. Scalability and computational complexity: The paper demonstrates the algorithm's performance on datasets with a moderate number of variables and events. An evaluation of its scalability to very large datasets, which are common in real-world applications, is less emphasized. The computational complexity of the algorithm, particularly for large datasets with many event types, is a concern. The quadratic complexity in the number of event types may limit its applicability to very large-scale problems.\n\n3. Parameter sensitivity is not provided: How sensitive is the CASCADE algorithm to the choice of parameters for the delay distribution and cause probability?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your time and valuable feedback. We would like to address your concerns and questions in detail.\n\n1. **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.\n\n   | Events per cause | 0.4       | 0.7       | 1.0       | 1.3       | 1.6       | 1.9       | 2.3       | 2.6       | 2.8       | 3.1       |\n   |-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|\n   | 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 |\n\n   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.\n   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.\n\n2. **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.\n3. **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. \n\n   |     | Exponential | Poisson     | Normal      | Uniform     |\n   |-----|-------------|-------------|-------------|-------------|\n   | F1  | 0.82 ± 0.08 | 0.81 ± 0.09 | 0.76 ± 0.08 | 0.75 ± 0.10 |\n   | SHD | 13.8 ± 6.3  | 14.2 ± 6.7  | 18.5 ± 6.5  | 19.0 ± 7.8  |\n\n   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.\n\n\n4. **Noise**: Lastly, we would like to answer your question on the effect of noise on our method.\nThe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "FqUTUFTqWi", "reviewer": "Reviewer_T6V6", "summary": "In their work, the authors are concerned with recovering causal relations, where cause and corresponding effects occur in varying temporal distances. The authors leverage information theoretic formulations and properties of the algorithmic Markov condition to recover the causal graph via minimum description length principled. To this end, the authors present the 'CASCADE' algorithm, which recovers the topological ordering of the causal structure and proof identifiability results. The algorithm is evaluated on multiple synthetic data setups to examine the algorithm's performance under different varying noise, event type, and collider settings. Lastly, the algorithm is tested on a banking and daily activity data set to demonstrate robust performance on real-world data.", "questions": "My questions mainly concern the weaknesses mentioned above. I would kindly like to ask the authors to comment on the following:\n\n1) How realistic are the assumptions made in the paper (e.g., low noise in real-world settings)? How would one test for them to hold true? How robust would the algorithm be in the presence of other event types, such as suppressing events or multi-effect events?\n\n2) Proof Thm. 2: Could the authors provide further details regarding the proof of theorem 2 - in detail, the derivation of the final step?\n\n3) Regarding my comments above, could the authors give further insights on the algorithm's performance with an increased number of colliders?\n\n4) Figures. 4, 6 and 8 seem to feature few colliders. This seems unreasonable to me, especially for the global banking data set, which I assume to be highly interconnected (possibly violating the DAG assumptions). Could the authors comment on this possible bias? Is it a result of the assumptions made, and how could it be reduced?", "limitations": "Limitations with regard to the applicability of the algorithm are discussed. Assumptions required for identifiability of the considered causal models are stated explicitly but might be hard to check in real-world settings. The work might be improved by discussing societal impacts from applying the algorithm under possible assumption violations in real-world settings.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and introduces the problem setup and formalisms intuitively. The authors consider the challenging problem of modeling causal event sequences. The information-theoretic treatise and causal modeling of the event-generating process via minimum description length encodings are well described and follow common notation from related work. While I am not an expert on the topic of time series event causality, relevant related work seems to be sufficiently discussed and compared to.\n\nThe overall intuition on all proofs is well described. To the best of my knowledge, proofs of theorems 1, 3 and 4 seem to be correct. (Please see minor comments on Thm. 2 below). The presented CASCADE algorithm seems to be sound and its robustness is evaluated via multiple real-world and synthetic experiments, varying the noise and number of event types.", "weaknesses": "While the authors present strong theoretical identifiability results, these guarantees are tied to a restrictive set of assumptions (faithfulness, sufficiency, low noise) and hold only for a specific type of event process (single excitation, no suppressing effects). While the authors state all assumptions explicitly, the paper could be improved by discussing the possible implications and reasonability of real-world applications.\n\n\nProof of Theorem 2 (Sec. A.2; second line of l. 496): As all other terms seem to be taken over from the line above, it is unclear to me where the canceled term on the left side of the inequality is coming from. (Since all terms are positive, I believe the transformation to be still correct.) Furthermore, it is not obvious to me how the equation following l.497 and the noise ratio of $n_{i,j}/n_j$ leads to the desired result. The paper could be improved by providing a more detailed explanation of this step.\n\n\nThe experiments seem to demonstrate consistently better results compared to related algorithms. However, from the experimental description in B.1, it seems that the experiment on the especially challenging identification of colliders --due to unclear parent assignment-- only considers a setting with a single collider. The authors might want to demonstrate algorithm performance for settings where multiple colliers exist, to better examine the algorithm's robustness regarding unclear EM assignments.\n\n\nMinor:\n* It would be helpful to mention the definition of H() in Sec. A.1 as the entropy, which is only mentioned afterward in A.2.\n* Typos in the Proof of Thm. 2 (sec. A.2 l.490): \"dealys\", \"ofset\"; and the Conclusion (l.340) \"discovers\" -> \"discover\".\n* In Sec. 4.1 l.201 text and formula disagree on the complexity: \"[...] leading to an overall quadratic complexity $O(p^3)$\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n1. **Assumptions**: First, we would like to elaborate on our assumptions and their implications.\n   - *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.\n\n      | Events per cause| 0.4       | 0.7       | 1.0       | 1.3       | 1.6       | 1.9       | 2.3       | 2.6       | 2.8       | 3.1       |\n      |-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|\n      | 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 |\n\n     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.\n   - *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%.\n   - *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. \n\n   [1] Kaltenpoth, David, and Jilles Vreeken. \"Causal discovery with hidden confounders using the algorithmic Markov condition.\" Uncertainty in Artificial Intelligence. PMLR, 2023.\n\n   [2] Marx, Alexander, Arthur Gretton, and Joris M. Mooij. \"A weaker faithfulness assumption based on triple interactions.\" Uncertainty in Artificial Intelligence. PMLR, 2021.\n\n2. **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}$.\nWe 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.\n\n3. **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.\n\n   | # Colliders | 5        | 7        | 10       | 15      | 20       |\n   |-----|-----------|-----------|-----------|-----------|-----------|\n   | F1  | 0.97±0.01 | 0.95±0.01 | 0.91±0.01 | 0.87±0.02 | 0.82±0.01 |\n\n4. **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.\n\n\nRegarding 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "V2Gyb0GEFU", "reviewer": "Reviewer_WfU1", "summary": "The article employs the Algorithmic Markov Condition alongside Kolmogorov\ncomplexity for causal discovery from event sequences. It focuses on a specific scenario in\nwhich the sequence of events is divided into source and effect variables. The principal\ncontribution of this study is its innovative application of Pearl's causality model with\ncombination of AMC method, in contrast to the traditional Granger causality approach,\nenabling the identification of both instantaneous and delayed effects.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Originality: The author employs Pearl's model of causality, diverging from\ntraditional Granger causality, to innovatively incorporate instantaneous effects\ninto the analysis of sequential events for causal relationship discovery.\n2. Quality: The article is with good quality and honest about its strength and\nlimitation on their work.\n3. Clarity: The article presents its algorithm with well-defined logic and\nsubstantiated proofs.\n4. Significance: The article offers an innovative approach to integrating\ninstantaneous effects into the causal discovery of sequential events, proposing a\npotential method to enhance causal discovery techniques under such conditions.\nHowever, it imposes strict limitations on the scenarios involving event sequences.", "weaknesses": "1. Significance: As mentioned in the limitation section by the author, strict\nassumptions like direct matching between a cause event and an effect event leads\nto challenges and possible violations in practical application, and it lacks\nflexibility.\n2. Section 3.3, which discusses the connection to Hawkes Processes, might be better\nplaced in an appendix or in a section dedicated to comparing different\nmethodologies. Its current placement in the theoretical part of the paper is\nsomewhat abrupt, especially since there is no direct focus on these processes in\nyour model.\n3. The experimentation section lacks depth. It would be beneficial to evaluate and\nreport on the robustness of your model when its assumptions are challenged\nduring real-world applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your time and valuable feedback. We would like to address your concerns first.\n\n1. **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.\n\n   |Events per cause | 0.4       | 0.7       | 1.0       | 1.3       | 1.6       | 1.9       | 2.3       | 2.6       | 2.8       | 3.1       |\n   |-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|\n   | 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 |\n\n     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.\n\n3. **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.\n4. **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.\n\n   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. \n\n   |    | Exponential | Poisson     | Normal      | Uniform     |\n   |-----|-------------|-------------|-------------|-------------|\n   | F1  | 0.82 ± 0.08 | 0.81 ± 0.09 | 0.76 ± 0.08 | 0.75 ± 0.10 |\n   | SHD | 13.8 ± 6.3  | 14.2 ± 6.7  | 18.5 ± 6.5  | 19.0 ± 7.8  |\n\n   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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "ylNPJNriQ8", "reviewer": "Reviewer_e9Hj", "summary": "This paper introduces a new causal model in which individual events of the cause variable trigger events of the effect variable with dynamic delays. The authors propose a cause-effect matching approach to learn a fully directed acyclic graph, named the CASCADE algorithm. The algorithm performs a topological search on observational data.", "questions": "**1.** \nAssuming ``an individual event ... causes an individual event'' in Line 64, and in Line 88: Equation 2.\nDo these indicate that an effect event can only be caused by a single cause event? If so, the use of $pa(*)$ later in the manuscript is confusing. Can an effect event be caused by more than one event?\n\nIn the results of real experiments, there is an event that is caused by more than one event, which contradicts the assumption. How are the results obtained?\n\n\n**2.**\nAre timestamps in events erased during actual use?\nAs far as I can see, the algorithm proposed in the manuscript does not use timestamps.", "limitations": "The authors discuss in detail the limitations and applicability of their algorithm.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a comprehensive theory and algorithm, and conducts extensive experiments, particularly with real data, to validate the effectiveness of the proposed method. The analysis and the algorithm are presented in a logical way.", "weaknesses": "The proposed method is the direct matching between a cause event and an effect event, which precludes modeling a single event causing multiple other events, as well as multiple events jointly causing a single effect event.  This limits the applicability of the algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your time and valuable feedback.\n\nWe 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.\n\n|Events per cause | 0.4       | 0.7       | 1.0       | 1.3       | 1.6       | 1.9       | 2.3       | 2.6       | 2.8       | 3.1       |\n|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|\n| 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 |\n\nWe 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.\n\nWith regard to your questions:\n\t\n1. **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. \n2. **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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We thank the reviewers for their detailed and thoughtful comments. All reviewers appreciate the proposed causal model with “theoretical foundation based on the AMC and MDL”, with “strong theoretical identifiability results”. In particular the identifiability of instant effects, which Granger causality based method can not identify, is recognized. Finally, the proposed CASCADE algorithm, with which “extensive experiments [...] to validate the effectiveness of the proposed method” were conducted, was well received across the board. 

The reviews ask for clarification with regard to CASCADE’s performance in aspects regarding causal model, different data distributions and structure, and noise levels. We would like to respond to each question individually.
- **Causal model**: A commonly raised concern was the performance of CASCADE under a differing causal model, e.g. where one event causes multiple. To this end, we supplement an experiment with data generated by a Hawkes process, 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.

- **Distribution misspecification**: In CASCADE, we fit exponential distributions to the matched cause-effect delays. We additionally test our method on generated data where the actual distribution is different and 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 |

   While we observe a decrease in accuracy under misspecification, CASCADE still remains accurate in detecting causal edges in the observed event sequences, as the misspecified model still provides an improved MDL-score over the noise distribution.

- **Multiple 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 (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 |

- **Strong noise**: 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 is increased up to 90%. As summarized in Figure 3b) of the paper, CASCADE copes well with noise and outperforms the SOTA on all noise levels.

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. Expanding the causal model to the 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. We will update the manuscript with the provided experiments, as well as add a discussion about the implications of our assumptions to the paper.

Meta-review: This paper advances the state-of-the-art in modeling event sequences as a way to gain insights into causation.  The reviewers are extremely consistent in their opinions.  The paper has a nice mixture of theoretical and empirical justification for its claims.  There was great discussion with the authors about questions around the following potential issues (1) assumptions (are they too strong?), (2) model misspecification, (3) multiple colliders, and (4) noise.  The authors gave additional empirical results, and these should be included in the final paper.  These better showed that the method had good robustness to different data distributions, structure, and noise levels.  They also showed the method could in fact handle situations where one event can influence multiple downstream events.  The reviewers seemed satisfied with the author replies although did not further revise their scores.  The authors should take into account reviewer comments and their own commitments in the replies to make clarifying additions in the final version.
Decision: Accept (poster)