Structural Hawkes Processes for Learning Causal Structure from Discrete-Time Event Sequences

1 Introduction

Learning causal structure among event types on multi-type event sequences is an important and challenging task, and has recently found applications in social science [Zhou et al., 2013a], economic [Bacry et al., 2015], network operation maintenance [Cai et al., 2022], etc. Existing methods, such as the multivariate Hawkes processes based methods [Xu et al., 2016; Bhattacharjya et al., 2018; Salehi et al., 2019], mostly boil down to learning the so-called Granger causality [Granger, 1969] which implicitly assumes that all events are recorded instantaneously and accurately such that the cause event happens strictly prior to its effect event (known as temporal precedence assumption). However, due to the limited recording capabilities and storage capacities, retaining event's occurred times with high-resolution is expensive or practically impossible in many real-world applications, and we usually only can access the corresponding discrete-time event sequences. For example, in large wireless networks, the event sequences are usually logged at a certain frequency by different devices whose time might not be accurately synchronized. As a result, lowresolution discrete-time event sequences are obtained and the temporal precedence assumption will be frequently violated in discrete-time event sequences, which raises a serious identifiability issue of causal discovery. For example, as shown in Fig. 1, there are three event sequences produced by three event types v1, v2, and v3, respectively. Let v1 be the cause of v2 and v3, Fig. 1(a) shows the accurate continuous-time event sequences such that each event occurred time is recorded by t1, ..., t6. However, such high-resolution sequences are usually not accessible and we can only observe the discrete-time event sequences as shown in Fig. 1(b). As a result, v1 and v2 will be considered simultaneous events due to the low-resolution, which violates the temporal precedence assumption. Consequently, many existing point process based methods will fail to capture the causal relationship v1 → v2 as only the events that occur earlier are considered as causes. In contrast, the causal relationship v1 → v3 can still be captured using the point process based method because the cause event v1 occurs before v3. However, one can imagine that as the resolution becomes lower the causal relationship between v1 and v3 might no longer be identified as they might become occurs at the same time. Thus, in this paper, we aim to answer the following two questions: 1) How to design and learn a Hawkes process that leverages the instantaneous effect in discrete time? 2) Can we identify the causal relationship in event sequences under the existence of the instantaneous effect?

∗Corresponding author.

These two questions have to do with the point processes and the causal discovery, respectively. The former question is about the design of the discrete-time Hawkes processes. The effect of discretization of Hawkes processes has been widely discussed in many ways [Foufoula-Georgiou and Lettenmaier, 1986; Kirchner, 2016; Shlomovich et al., 2022; Jacod and Todorov, 2009]. However, how to design a Hawkes process

• (b) Discrete-time event sequences.

Figure 1: Toy example of the continuous-time and discrete-time event sequences. We consider three types of event v1, v2, v3 and the causal relationship satisfying v2 ← v1 → v3. While, in continuous-time, each event's occur times (t1, ..., t6) can be observed accurately, the discrete-time event sequences have lower resolution, such that types v1, v2 will be considered as simultaneous and the Granger-based methods will fail to capture the causal relationship v1 → v2.

that leverages the instantaneous effect in discrete Hawkes process is still unknown. The latter question is related to the causal discovery [Zhang et al., 2018; Qiao et al., 2021; Cai et al., 2018a; Cai et al., 2018b; Yu et al., 2019; Yu et al., 2021; Yang et al., 2021]. Some methods have been developed for continuous-value time series with instantaneous effect. For example, the structural vector autoregression model [Swanson and Granger, 1997] is an extension of the vector autoregression model with instantaneous effect, and it has been shown that under the linear non-Gaussian model, the causal relationship is identifiable under the existence of the instantaneous effect [Hyv¨arinen et al., 2010]. However, we are not aware of any method that leverages the instantaneous effect to identify the causal relationship in event sequences with point processes. Thus, in this work, we propose Structural Hawkes Processes (SHPs) that leverage the instantaneous effect in discrete-time event sequences. We will proceed as follows. In Section 2, we review the related work. In Section 3.1, we show how to design and learn the structural Hawkes processes. In Section 4, we investigate the identification of structural Hawkes processes and theoretically show that the causal relationship among the instantaneous effect is indeed identifiable. In Section 5, we perform extensive empirical evaluations over both synthetic and real-world data.

2 RelatedWork

This work is closely related to two topics: point processes and learning causal structure from event sequence.

Point processes. There are mainly two types of point processes for modeling the event sequence. Most existing methods focus on developing the continues-time Hawkes processes [Hawkes, 1971] which assume that the event in the past can influence the event in the future. Different variants have been developed with different types of intensity in the Hawkes processes, e.g., the parametric functions [Farajtabar et al., 2014; Zhou et al., 2013a; Rasmussen, 2013; Cai et al., 2022], the non-parametric functions [Lewis and Mohler, 2011; Zhou et al., 2013b; Achab et al., 2017], and the recent deep learning based functions [Du et al., 2016; Mei and Eisner, 2017; Shang and Sun, 2019]. Another line of research focuses on the discrete-time Hawkes processes which are more appealing for certain applications. [Seol, 2015] study the limit theorem for the discrete Hawkes processes and it has been extended to the discrete marked Hawkes processes by [Wang, 2022]. [Shlomovich et al., 2022] further discusses the estimation method for 1-dimensional discrete Hawkes processes. However, none of the above methods leverage the instantaneous effect for learning causal structure in discrete-time event sequences.

Learning causal structure from event sequences. Most approaches in learning causal structure from event sequences are based on Granger causality [Granger, 1969]. The basic idea of Granger causality is to constrain that the effect cannot precede the cause and the causal analysis can be conducted using predictability. In particular, many methods have been developed for learning Granger causality from the continuoustime event sequences based on multivariate Hawkes processes. [Xu et al., 2016] proposes a nonparametric Hawkes processes model with group sparsity regularization, while [Zhou et al., 2013a] proposes to use a nuclear and ℓ1 norm and [Id´e et al., 2021] consider an ℓ0 norm as the sparse regularization. In addition, [Achab et al., 2017] proposes to use cumulant for learning the causal structure without optimization. Recently, some deep point process based methods have been proposed, e.g., [Zhang et al., 2020] introduce an attribution method to uncover the Granger causality. However, the Granger causal relations could be misled in low-resolution which is also pointed out by [Spirtes and Zhang, 2016]. One remedy is to extend Granger causality with instantaneous effects. It has been found that in continuous-value time series, one is able to incorporate the instantaneous effect under the linear relation with non-Gaussian noise [Hyv¨arinen et al., 2010]. [Runge, 2020] further proposes to use a constraint-based method for learning the causal structure under the instantaneous effects. However, the extensions are only applicable in a restricted case and it is still very challenging to learn causal structure from event sequences with instantaneous effects.

3 Structural Hawkes Processes

We begin with a brief introduction to the general continuoustime multivariate point processes. We then develop the structural Hawkes processes that leverage the instantaneous effect in discrete-time.

3.1 Multivariate Point Processes

A multivariate point process is a random process that can be presented via a ∣V∣-dimensional counting process N = {Nv(t)∣t ∈ [0, T], v ∈ V} where Nv(t) = N((0, t]) measures the number of events that occur before time t in the event type v. Each counting process Nv(t) can be characterized by the conditional intensity function λv(t) satisfying:

where λv(t) characterizes the (conditional) expected number of jumps per unit of time, dNv(t) = Nv(t + dt) - Nv(t) measures the increment of the jump, Ft- = ⋃0≤s<t,v∈V F v s in which F v s is the canonical filtration of sub-processes Nv(t) up to time s.

In particular, Hawkes process is a counting process with an intensity function that has the following form:

where µv is the immigration intensity and ∑v′ ∈V ∫ t 0 ϕv′ ,v(t - t′ )dNv′ (t′ ) is the endogenous intensity aiming to model the influence from other event types occurring near time t [Farajtabar et al., 2014]. ϕv′ ,v(t) is a reproduction function characterizing the time variation of the causal influence from event v′ to v. Intuitively, one can imagine that events can be seen to arrive either via immigration according to µv or via reproduction from past events according to the endogenous intensity.

3.2 Design of Structural Hawkes Processes

To model the instantaneous effect, we begin with extending the continues-time counting processes into the discrete-time in which the event sequences are observed or collected in T = {∆, 2∆, ...,K∆}, for K = ⌊T/∆⌋ where ∆ > 0 is the length of time interval at each observed time. Then the multivariate counting processes in discrete-time can defined as N(∆) = {N (∆) v (k)∣k ∈ {0, . . . ,K}, v ∈ V}, where N (∆) v (k) = Nv((0, k∆]) measures the number of events that occurs not later than k∆. We further let X = {Xv,t∣v ∈ V, t ∈ {0, . . . ,K}]} denote the set of observations at each time interval where Xv,t ≔ Nv(t∆) - Nv((t - 1)∆) is an analogy to dNv(t).

The discrete-time counting processes, however, as we discussed earlier, will ignore the instantaneous effect which could lead to a misleading result. To tackle this issue, we propose structural counting processes with a new type of conditional intensity function that leverages the events that occur at the same period of time.

Definition 1 (Structural counting processes). A structural counting process is a multivariate counting process N(∆) in discrete-time with the conditional intensity of N (∆) v for each v ∈ V satisfying:

where F(k-1)∆ = ⋃0≤s≤k-1,v∈V F v s∆ is the filtration with discrete-time in the past and F -v k∆ ≔ {F v′ k∆∣v′ ∈ V\v} is the filtration that except for type-v event.

Note that the exclusion in F -v k∆ is necessary since it makes no sense to use the current number of events to predict itself. Based on the structural counting processes in Definition 1, the structural Hawkes processes can be designed as follows:

Definition 2 (Structural Hawkes processes). A structural Hawkes process is a structural counting process such that for each v ∈ V, the intensity of N (∆) v can be written as:

where ϕv,v(0) ≡ 0 ensures the exclusive of type-v event at time k∆.

We can see that the intensity in Eq. (3) is not only influenced by the events that occur in the past (k-1)∆ but also the events that occur at the same period of time k∆.

3.3 Learning of Structural Hawkes Processes

The goal of this work is to identify a proper directed acyclic graph (DAG) G(V, E) among event types V such that for a type-v event, the intensity λv(t) only depends on the event from its cause Pav where Pav is the parent set of v according to the edge set E, i.e., {v′ → v∣v′ ∈ Pav} ⊆ E. Note that a DAG constraint for the instantaneous causal relation is necessary due to the lack of temporal precedence but it can be easily relaxed by taking lagged and instantaneous relations separately which we omit here for simplicity.

To learn causal structure, we parameterize the causal influence into the reproduction function ϕv′ ,v(t) = αv′ ,vκ(t) where αv′ ,v denotes the causal strength of causal relation v′ → v and κ(t) characterizes the time-decay of the causal influence which is usually set as an exponential form κ(t) = exp(βt) for t ≥ 0 with the hyper-parameter β. That is, the causal relationship can be encoded by the impact function such that for any pairs v′ , v ∈ V if ϕv′ ,v(t) = 0 we have v′ → v /∈ E.

Thus, one of the challenges of learning causal structure is to constrain the sparsity of the reproduction function. To this end, we devise the objective function with sparsity constraint using the ℓ0 norm under the likelihood framework.

Given a collection of discrete-time sequences X, the loglikelihood of parameters Θ = {A = [αv′ ,v] ∈ R∣V∣×∣V∣ , µ = [µv] ∈ R∣V∣ } of SHP can be expressed as follows:

L(G, Θ; X)

Without further constraint, the log-likelihood function will tend to produce excessive redundant causal edges. Thus, we further penalize the model with ℓ0 norm to enforce the sparsity and we obtain the objective function as follows:

where αS controls the strength of ℓ0 norm. Although there are different forms of sparse regularization for the constraint, e.g., [Xu et al., 2016] proposed to use the ℓ1 and ℓ2 norm, the ℓ0 can provide better sparsity performance and it is easy to be extended, for example, considering the directed acyclic constraint [Tsamardinos et al., 2006], as many causal structures in real-world are often directed acyclic.

3.4 AMinorization-Maximization-based Algorithm for Learning Causal Structure

However, estimation of the parameters by maximizing the likelihood in Eq. (5) has two obstacles. First, the likelihood of the point processes model is known as flat making the optimization unstable and computationally intensive [Veen and Schoenberg, 2008]. Second, learning DAGs from observational data is a combinatorial problem and, without any assumption, it has been shown to be NP-hard [Chickering et al., 2004]. To tackle the issues above, following [Lewis and Mohler, 2011; Chickering, 2002], we propose to use minorization-maximization (MM) based optimization [Hunter and Lange, 2004] with a two-step causal structure learning algorithm.

For the first step, the parameters are estimated given a fixed causal graph using the MM algorithm which leverages the additive structure in Eq. (4) to apply Jensen's inequality similar to the EM algorithm and obtain the following lower bound:

λ(j) v (k∆) is the conditional intensity function with parameters Θ(j) in the j-th iteration. Then, by setting ∂Q(Θ∣Θ(j) ) ∂µv = 0,

∂Q(Θ∣Θ(j) ) ∂αv′ ,v = 0, we obtain the close-form iteration formulas:

With the MM algorithm, we then search the causal structure by using a Hill-Climbing-based algorithm as shown in Algorithm 1. It mainly consists of two phases. First, we perform a

Algorithm 1 Learning causal structure using SHP

Input: Data set X

Output: G∗ , Θ∗

• 1: G′ ← empty graph, L∗p ← -∞
• 2: while L∗p(G∗ ,Θ∗ ;X) < L′p(G′ ,Θ′ ;X) do
• 3: G∗ ,Θ∗ ←G′ ,Θ′ with largest L′p(G′ ,Θ′ ;X)
• 4: for every G′ ∈ V(G∗ ) do
• 5: Update Θ′ via iteration in Eq. (7)
• 6: Record score L′p(G′ ,Θ′ ;X)
• 7: end for
• 8: end while
• 9: return G∗ ,Θ∗

structure searching scheme by taking one step adding, deleting, and reversing the graph G∗ in the last iteration, i.e., in Line 4, V(G∗ ) represents a collection of the one-step modified graph of V(G∗ ). Furthermore, the acyclic constraint is implemented by eliminating all cyclic causal graphs in V(G∗ ). Second, by fixing the graph G′ , we optimize the log-likelihood using the MM algorithm in Line 5. Iterating the two steps above until the likelihood no longer increases.

4 Identifiability

In this section, we aim to answer the question that whether we can identify the causal relationship under the existence of the instantaneous effect. In answering this question, one will need to explore the property of Hawkes processes in discrete-time. Based on the discrete-time likelihood in Eq. (4), each interval is modeled by conditional Poisson distribution with the linear structure in Eq. (3). As such, one may alternatively represent the relation by integer-valued autoregressive (INAR) processes according to [Kirchner, 2016] for analyzing the identification of structural Hawkes Processes. Furthermore, we assume that the causal sufficiency holds, i.e., all relevant variables have been observed [Spirtes et al., 2000]. Following [Kirchner, 2016], the INAR(∞) processes can be defined as follows:

Definition 3 (INAR(∞)). For θk ≥ 0, k ∈ N0, let ϵt i.i.d. ∼ Pois(θ0), t ∈ N, and ξ (t,k) i ∼ Pois(θk). An Integer-valued autoregressive time series of infinite order (INAR(∞)) process Xt, t ∈ N is defined by

where ◦ is a reproduction operator given by θk ◦ Xt-k ≡ ∑Xt-k i=1 ξ (t,k) i with ξ (t,k) i be a sequence of i.i.d. non-negative integer-valued random variables that depends on the reproduction coefficients θk, {ϵt}t∈N is an i.i.d. integer-valued immigration sequence that are independent of {ξ (t,k) i }, and Xt-k is independent of ϵt for all k.

In general, INAR is a discrete analogy of the continuous autoregressive model. Note that the distribution of the independent variables in INAR could be different and different choices of the distribution would lead to different INAR models [Guerrero et al., 2022]. Here, we use the Poisson choice to adopt the conditional Poisson distribution in Eq. (4), and it has been shown that such INAR(∞) model will converge to the continuous-time Hawkes processes as the time interval ∆ → 0:

Theorem 1 ([Kirchner, 2016]). Let N be a Hawkes process with immigration intensity µ and let ϕ ∶ R → R+0 be a reproduction intensity that is piecewise continuous with ϕ(t) = 0, t ≤ 0 and ∫ ϕ(t)dt < 1. For ∆ ∈ (0, δ), let (X(∆) t ) be an INAR(∞) sequence with immigration parameter ∆µ and reproduction coefficients ∆ϕ(k∆), k ∈ N. From the sequences (X(∆) t )∆∈(0,δ) , we define a family of point processes by

where B ≔ B(R) is the Borel set in R. Then, we have that

Theorem 1 implies that the properties of INAR can be utilized for analyzing the Hawkes processes in discrete-time. Intuitively, the reproduction function ϕ in the discrete-time Hawkes processes can be represented by a series of reproduction coefficients θk for each time period, and the immigration intensity µ in the discrete-time Hawkes processes can be represented by the immigration parameters of ϵt.

Specifically, given the property of INAR processes, the analysis of the identifiability of structural Hawkes processes can be typically performed in two folds-the identifiability of the temporal structural Hawkes processes and the instantaneous structural Hawkes processes [Hyv¨arinen et al., 2010]. For the former, the temporal resolution of the measurement that is high enough to capture the former and latter relationship of the events, the identifiability can be derived by local independence, which has been well explored by [Mogensen and Hansen, 2020]. For example, in Fig. 1, the causal relationship v1 → v3 can be simply identified by the independence. Thus, in this work, we are more interested in the instantaneous structural Hawkes processes-the measurements have lower time resolution such that the causal influences are instantaneous. In such a case, one can use a model in which the influences are instantaneous, leading to Bayesian networks (BNs) or structural equation models (SEMs), e.g., the causal relationship v1 → v2 in Fig. 1 belong to this class.

Thus, to analyze the identification of SHP, based on the INAR model, we consider the instantaneous causal structure in the structural Hawkes process:

Definition 4 (Instantaneous causal structure in structural Hawkes process). Let ϵv,t i.i.d. ∼ Pois(µv), and ξ (v′ ,v) i ∼ Pois(αv′ ,v). The instantaneous causal structure in the structural Hawkes process consists of a set of equations of the form

where αv′ ,v > 0 for v′ ∈ Pav and αv′ ,v = 0 for v′ /∈ Pav, with αv′ ,v ◦ Xv′ ,t ≡ ∑Xv′ ,t i=1 ξ (v,v′ ) i , and µv > 0 if v is a root variable i.e., the variable whose parent set is empty Pav = ϕ. The random variables Xv′ ,t, ξ (v,v′ ) i , and ϵv are independent of each other.

The identifiability of the instantaneous causal structure, however, is much more difficult compared with the temporal causal relationship and most of them suffer from lack of identifiability. For example, without any constraint, the instantaneous causal structure may not be identified due to the Markov equivalence class [Pearl, 2009] in which all graphs in the equivalence class encode the same conditional independence. In such a case, different model with different causal graph and parameter, M1 = (G1,Θ1), M2 = (G2,Θ2) will produce the same distribution. Such non-identifiability also exists even considering an additional constraint, e.g., the linear Gaussian SEM is also non-identifiable [Spirtes et al., 2000].

Thus, an essential goal of this work is to investigate the identifiability of the instantaneous causal structure, i.e., whether there exists another causal structure that entails the same distribution to the underlying causal model. Such identifiability basically boils down to bivariate cases that whether there exists a backward model that is distribution equivalent to the causal direction. It can be easily extended to multivariate cases by incorporating the conditional independent constraint in the causal structure with the causal faithfulness assumption, i.e., the causal graph faithfully displays every dependency [Pearl, 1988]. Specifically, let X be the cause variable and Y be the effect variable, and surprisingly, the following theorem shows that the bivariate instantaneous causal pair is indeed identifiable:

Theorem 2. Let X → Y be the correct causal direction that follows

where ξi ∼ Pois(αX,Y ), ϵ ∼ Pois(µY ), X ∼ Pois(µX). Then, there does not exist a backward model that admits the following equation:

where ˆ ξi ∼ Pois(ˆαY,X), ˆ ϵ ∼ Pois(ˆµX), Y ∼ Pois(ˆµY ).

To better understand the identifiability, we provide two alternative proofs for this theorem. The details of the proofs are given in the supplementary material [Qiao et al., 2023]. The first proof shows that it is impossible to have a backward model that the probability distribution of the two directions is equivalence. While the second proof shows that the distribution of Y must not admit the Poisson distribution and therefore the distribution is not equivalent. We also provide an empirical study of the identifiability for the bivariate causal pair in Section 5. Finally, we generalize the result of Theorem 2 to the multivariate causal structure and show that the multivariate instantaneous causal structure is also identifiable:

Theorem 3. With the causal faithfulness assumption and causal sufficiency assumption, the multivariate instantaneous causal structure is identifiable.

The main idea behind the proof is that for any causal structure (G,Θ). there does not exist another causal structure

( ˆ G, ˆΘ) that is distribution equivalent. Specifically, with the causal faithfulness and causal sufficiency assumption, the Markov equivalent class is identified. Since all Markov equivalent classes share the same skeleton, we only need to show that each causal pair will not admit another causal structure that has the revered causal direction while having the same likelihood (i.e., distribution equivalent).

5 Experiments

In this section, we test the proposed SHP and the baselines on both synthetic and real-world data. The baseline methods include ADM4 [Zhou et al., 2013a], NPHC [Achab et al., 2017], MLE SGL [Xu et al., 2016], and PCMCI Plus [Runge et al., 2019]. We further develop SHP NH, an ablation study of SHP that removes the hill-climb based searching scheme and uses a threshold to determine the causal structure following the work of ADM4 and MLE SGL. In all following experiments, Recall, Precision, and F1 are used as the evaluation metrics. The results of recall and precision are provided in the supplementary material.

5.1 Synthetic Experiments

In this part, we design extensive control experiments using synthetic data to test the correctness of the theory and the sensitivity of sample size, length of time interval, number of event types, and different ranges of α and µ. In the sensitivity experiment, we synthesize data with fixed parameters while traversing the target parameter as shown in Fig. 3. The default settings are listed below, sample size=20000, time interval=5, number of event types=20, range of α ∈ [0.3, 0.5], range of µ ∈ [0.0005, 0.0001]. All experimental results are averaged over 100 randomly generated causal structures.

The generating process proceeds as follows: 1) randomly generate a directed causal graph G with a certain average in degree; 2) generate the events according to randomly generated parameters αv′ ,v, µv from G, and 3) aggregate the number of counts at each interval for each event according to the length of time interval to synthesize the discrete-time process.

Two-variable case. We first conduct a simple two-variable experiment to verify the identifiability in Theorem 2, by computing the likelihood difference between the causal direction and the reversed direction on a simulated causal pair with different causal influence αX,Y . That is, we simulated data using the model Yt = αX,Y ◦ Xt + ϵt with Xt ∼ Pois(µx) and ϵt ∼ Pois(µy). Each experiment is conducted 100 times with random causal pairs. As shown in Fig. 2, we can see that the likelihood difference is always greater than zero which means that it is always identifiable unless the degenerate cases and it verifies the correctness of Theorem 2. In addition, as the causal influence αX,Y decreases, the likelihood difference also decreases and tends to zero. This is reasonable as the causal influence becomes zero, and the two variables will also become independent making the model non-identifiable. Moreover, the level of immigration intensity also would affect the likelihood difference, which is reasonable as the lower the µx, the weaker the causal relation. Similarly, the higher the µy, the stronger the noise making the causal relation weaker. The more general multivariate case experiments will be implied in the following sensitivity analysis.

Sensitivity analysis. As shown in Fig. 3, we conduct six different control experiments for SHP. In general, our proposed SHP method outperforms all the baseline methods in all six control experiments.

In the control experiments of time interval given in Fig. 3(a), as the time interval controls the temporal resolution of the measurement sequence, the larger the time interval, the lower the temporal resolution, and the more instantaneous causal influences will occur leading to the decrease or insensitive of performance of the baseline methods. In the contract, SHP keeps giving the best results at all intervals. We also notice that the performance will decrease as the time interval increase because it reduces the sample size and the sequence become less informative. In addition, the performance of SHP NH stresses the effectiveness of the searching algorithm which has lower precision and stability than SHP but also outperforms the baseline methods if the event sequences contain sufficient information on the instantaneous effect, which also verifies the ability to capture the instantaneous effect in SHP.

For the controlled experiments of causal strength and immigration intensity in Fig. 3(b) and Fig. 3(c), we can see that a reasonable causal strength and immigration intensity are required for the baseline methods while SHP is insensitive to both of them which shows the robustness of SHP.

In the sample size controlled experiments given in Fig. 3(d), all methods are robust to the sample size, and in particular, a 1000 sample size is enough to produce a reasonable performance for SHP, which demonstrates the practicality of SHP.

For the causal structure controlled experiments given in Fig. 3(e) and Fig. 3(f), SHP performs well in both experiments, and the average indegree is also important as it increases the performance of most methods decreases but SHP has the smallest decline.

5.2 Real World Experiments

We also test the proposed SHP on a very challenging realworld dataset 1 from real telecommunication networks. The

1 https://competition.huaweicloud.com/informations/mobile/ 1000041487/dataset

• (e) Sensitivity to Num. of Event Types

Figure 4: Real-world experiment on different temporal resolutions.

dataset records eight months of alarms that occurred in a real metropolitan cellular network. The alarms are generated by fifty-five devices in the metropolitan cellular network, which consists of eighteen types of alarms. Our goal is to learn the causal structure among the alarm types. Note that the causal impact among alarms is not deterministic but probabilistic in this system, which is similar to our model setting. All experiments have been conducted with different random seeds and the results are significant according to Wilcoxon signed-rank test. In addition, the ground truths of the causal relationships among alarm types are provided by domain experts.

As shown in Fig. 4, we conduct the real-world experiments by manually setting different temporal resolutions of the observed sequence (i.e., from one second to nine seconds) and the original temporal resolution is one second. Interestingly, as the time interval increases, the performance of our method also increases instead of decreasing, while the baseline methods all decrease. The reason is that in the real-world scenario, there exists a communication latency in the logging system such that the recorded timestamp might be not fully accurate, and this error can be mitigated by decreasing the temporal resolution. In contrast, after decreasing the temporal resolution, other methods fail to capture the causal relationship under the instantaneous effect. This verifies the effectiveness of SHP and stresses the importance of the instantaneous effect.

6 Conclusion

In this work, we study how to model and leverage the instantaneous effect for learning causal structure in discrete-time event sequences. We propose structural Hawkes processes that leverage the instantaneous effects and a practical algorithm for learning the causal structure among event types. Theoretical results show that the instantaneous causal structure in structural Hawkes processes is indeed identifiable. To the best of our knowledge, this is the first causal structure learning method for event sequences with instantaneous effects. The success of SHP not only provides an effective solution for learning causal structure from real-world event sequences but also shows a promising direction for causal discovery from the discrete-time event sequences. In future, we plan to extend our work to a point process with a more general intensity function.

(d) Sensitivity to Sample Size

• (f) Sensitivity to Avg. Indegree

Acknowledgements

This research was supported in part by National Key R&D Program of China (2021ZD0111501), National Science Fund for Excellent Young Scholars (62122022), Natural Science Foundation of China (61876043, 61976052), the major key project of PCL (PCL2021A12). We appreciate the comments from anonymous reviewers, which greatly helped to improve the paper.