PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jie Qiao, Ruichu Cai, Siyu Wu, Yu Xiang, Keli Zhang, Zhifeng Hao

arXiv:2305.05986v1cs.LGcs.AIstat.ME

TL;DR

Low-resolution discrete-time event sequences can make causes and effects appear simultaneous, a setting in which Granger-based causal learning may miss links. The paper introduces Structural Hawkes Processes to model instantaneous effects and learn causal structure; it reports identifiability results and empirical effectiveness on synthetic and real-world data.

  • Problem

    Hawkes-process causal-learning methods mostly rely on Granger causality, which assumes causes occur strictly before effects, an assumption often violated in low-resolution discrete-time sequences [Xu et al., 2016; Salehi et al., 2019].

    Source: §1 · p. 1

  • Method

    Structural Hawkes Processes incorporate instantaneous effects into discrete-time event models and use minorization-maximization with sparse causal-structure learning.

    Source: §1 · p. 2, §3.3 · p. 3, §3.4 · p. 4

  • Results

    The authors show instantaneous causal structure is identifiable and report empirical effectiveness on synthetic and real-world data.

    Source: §1 · p. 2, §6 · p. 7

  • Takeaways & Limitations

    SHPs provide an approach for learning causal structure from real-world event sequences with instantaneous effects.

    Source: §6 · p. 7

    The identifiability analysis assumes causal sufficiency—all relevant variables are observed—and instantaneous causal relations form a DAG.

    Source: §3.3 · p. 3, §4 · p. 4

Abstract

from arXiv · show

Learning causal structure among event types from discrete-time event sequences is a particularly important but challenging task. Existing methods, such as the multivariate Hawkes processes based methods, mostly boil down to learning the so-called Granger causality which assumes that the cause event happens strictly prior to its effect event. Such an assumption is often untenable beyond applications, especially when dealing with discrete-time event sequences in low-resolution; and typical discrete Hawkes processes mainly suffer from identifiability issues raised by the instantaneous effect, i.e., the causal relationship that occurred simultaneously due to the low-resolution data will not be captured by Granger causality. In this work, we propose Structure Hawkes Processes (SHPs) that leverage the instantaneous effect for learning the causal structure among events type in discrete-time event sequence. The proposed method is featured with the minorization-maximization of the likelihood function and a sparse optimization scheme. Theoretical results show that the instantaneous effect is a blessing rather than a curse, and the causal structure is identifiable under the existence of the instantaneous effect. Experiments on synthetic and real-world data verify the effectiveness of the proposed method.

1 Introduction

Learning causal structure from event sequences matters across several applications, but low-resolution discrete-time observations can violate the temporal-precedence assumption behind Granger-based methods. The paper proposes Structural Hawkes Processes (SHPs) to use instantaneous effects and studies whether causal structure remains identifiable in their presence.

Motivation

  • Existing Hawkes-process approaches to event-type causal learning mostly use Granger causality, which assumes events are recorded accurately enough to establish temporal precedence.The introduction frames this assumption as a challenge for discrete-time data collected under practical recording and storage constraints.Source: §1 · p. 1
  • Low-resolution bins can make causes and effects appear simultaneous, so Granger-based methods that require causes to occur first may miss genuine causal links.The introduction notes that links still temporally ordered at one resolution may also become simultaneous as resolution decreases.Source: §1 · p. 1

Contribution

  • SHPs leverage instantaneous effects in discrete-time event sequences; the paper studies their design, identifiability, and empirical performance on synthetic and real-world data.The authors report theoretical identifiability of instantaneous causal structure and describe empirical evaluations in Section 5.Source: §1 · p. 2

2 Related Work

Prior work on event-sequence causal learning largely builds on Granger causality, while discrete-time Hawkes models have not used instantaneous effects for causal-structure learning. Extensions that handle instantaneous effects in continuous-valued time series are described as restricted, leaving event-sequence methods challenging.

Point processes

  • Discrete-time Hawkes research has studied limit theorems and estimation, but the cited methods do not leverage instantaneous effects to learn causal structure.The passage cites,, and.Source: §2 · p. 2

Learning causal structure from event sequences

  • Most event-sequence causal-learning approaches use Granger causality, including multivariate Hawkes models with nonparametric, nuclear/ℓ1, or ℓ0 sparsity methods, cumulants, and deep attribution.The cited examples include [Xu et al., 2016], [Zhou et al., 2013a], [Id´e et al., 2021], [Achab et al., 2017], and [Zhang et al., 2020].Source: §2 · p. 2
  • Instantaneous-effect extensions for continuous-valued time series include structural VAR under linear non-Gaussian assumptions and a constraint-based method, but event-sequence learning remains challenging.The passage cites [Hyv¨arinen et al., 2010] and [Runge, 2020], and characterizes those extensions as restricted.Source: §2 · p. 2

3 Structural Hawkes Processes

The paper develops discrete-time Structural Hawkes Processes to represent within-interval effects and learn sparse causal graphs. Its learning procedure combines likelihood optimization with graph search under a directed-acyclic constraint for instantaneous relations.

3.1 Multivariate Point Processes

  • A multivariate point process represents event types with counting processes, while Hawkes-process intensities combine baseline immigration with influence from other event types through reproduction functions.The reproduction function describes how causal influence varies over time.Source: §3.1 · p. 3

3.2 Design of Structural Hawkes Processes

  • Structural Hawkes Processes extend discrete-time conditional intensities to include events from the same interval, while excluding a type's own current events from its prediction.The discrete-time observations are counts over intervals of length Δ; the same-period influence is the key addition.Source: §3.2 · p. 3

3.3 Learning of Structural Hawkes Processes

  • The model represents each causal influence as α_v′,vκ(t), with α_v′,v encoding causal strength and κ(t) its time decay; zero influence excludes an edge.The learning objective uses an ℓ0 penalty to discourage redundant causal edges, and instantaneous relations are constrained to a DAG.Source: §3.3 · pp. 3–4

3.4 A Minorization-Maximization-based Algorithm for Learning Causal Structure

  • The learning algorithm alternates graph search and parameter estimation with minorization-maximization, rejecting cyclic graphs and iterating until likelihood no longer increases.Graph search considers one-step edge additions, deletions, and reversals; MM updates parameters for each candidate graph.Source: §3.4 · p. 4

4 Identifiability

The section analyzes identifiability by relating discrete-time Hawkes processes to Poisson INAR processes and distinguishing temporal from instantaneous causal structure. It establishes identifiability of instantaneous structure under causal faithfulness and causal sufficiency.

4 Identifiability

  • The analysis represents discrete-time Hawkes processes through Poisson INAR processes, whose limiting connection to continuous-time Hawkes processes holds as the interval shrinks.The model assumes causal sufficiency, meaning all relevant variables have been observed.Source: §4 · pp. 4–5
  • Temporal causal structure can be identified through local independence when measurement resolution is high enough to distinguish events, while lower resolution can make causal influences instantaneous.The section focuses on this instantaneous-structure case, which it relates to Bayesian networks or structural equation models.Source: §4 · p. 5
  • Instantaneous structure can be non-identifiable in general, including under linear Gaussian structural equation models, because distinct graphs may encode the same conditional independences.The section frames identifiability as determining whether another causal structure can produce the same distribution.Source: §4 · p. 5
  • Under causal faithfulness and causal sufficiency, the multivariate instantaneous causal structure is identifiable.The proof reduces the problem to ruling out a distribution-equivalent model with a reversed causal pair.Source: §4 · pp. 5–6

5 Experiments

The experiments compare SHP with four baselines and an ablation on synthetic controls and real-world alarm data. SHP outperforms the baselines across six synthetic controls, while the supplied real-world passages describe the dataset and evaluation setup but not its results.

5.1 Synthetic Experiments

  • SHP outperforms all baseline methods in each of the six synthetic control experiments.The controls vary temporal interval, causal strength, immigration intensity, sample size, and causal structure.Source: §5.1 · p. 6
  • SHP remains best across tested time intervals, while performance declines as intervals grow and sequences become less informative.At lower temporal resolution, baseline performance decreases or is insensitive; SHP NH has lower precision and stability than SHP but can outperform baselines when instantaneous-effect information is sufficient.Source: §5.1 · p. 6
  • SHP is insensitive to causal strength and immigration intensity, whereas the baselines require reasonable values for both.In the causal-structure controls, SHP performs well and has the smallest decline as average indegree increases.Source: §5.1 · p. 6
  • All methods are robust to sample size, and 1,000 samples are sufficient for reasonable SHP performance.The sensitivity experiments use 20,000 samples by default and average results over 100 randomly generated causal structures.Source: §5.1 · p. 6

5.2 Real World Experiments

  • The real-world evaluation uses eight months of alarms from 55 network devices, with 18 alarm types and domain-expert causal ground truth.The authors report significant results by Wilcoxon signed-rank test and manually vary temporal resolution, but these supplied passages do not state the outcomes.Source: §5.2 · p. 7

6 Conclusion

Structural Hawkes processes use instantaneous effects to learn causal structure in discrete-time event sequences, and the paper reports that this structure is identifiable.

  • Structural Hawkes processes leverage instantaneous effects to learn causal structure among event types in discrete-time event sequences.The paper describes this as its first causal-structure-learning method for event sequences with instantaneous effects.Source: §6 · p. 7
  • Theoretical results show that the instantaneous causal structure in structural Hawkes processes is identifiable.Source: §6 · p. 7
  • The authors plan to extend the work to general point processes with a more general intensity function.Source: §6 · p. 7

A Derivation of minorization-maximization algorithm

The appendix derives the proposed minorization-maximization algorithm by developing a likelihood objective for the causal graph and parameters.

B Proof of Theorem 2

Theorem 2 addresses identifiability of an instantaneous causal structure by considering whether a backward model can match the forward model.

  • Theorem 2 is examined through two proofs, one from the likelihood and one from the distribution of Y.Source: B Proof of Theorem 2 · p. 11
  • The theorem takes X → Y as the correct causal direction and rules out a backward model admitting the stated equation.Source: B Proof of Theorem 2 · p. 11
  • The forward setup uses Poisson variables ξ_i, ε, and X, while the reverse setup uses corresponding hatted variables and Y.Source: B Proof of Theorem 2 · p. 11

B.1 Proof by Likelihood Function

The appendix gives two arguments against a distribution-equivalent reverse causal model: one based on likelihood differences and one based on the probability generating function of Y.

B.1 Proof by Likelihood Function

  • The likelihood proof compares the forward and reverse models by taking first and second differences of the log-likelihood with respect to X.The equations imply a condition that must hold for all x and y, leading to the contradiction.Source: §B.1 · pp. 11–12
  • The likelihood proof assumes a reverse model with the same likelihood, then derives a necessary condition that contradicts αX,Y ≠ 0.The derived condition requires αX,Y = 0.Source: §B.1 · pp. 11–12

B.2 Proof by Probability Generating Function

  • The probability-generating-function proof shows that Y cannot be Poisson under the stated nonzero-effect model, ruling out the reverse model’s required distribution.The necessary matching condition would require µX = 0 or αX,Y = 0, each contrary to the model assumptions.Source: §B.2 · p. 12

C Proof of Theorem 3

Under causal faithfulness and causal sufficiency, the multivariate instantaneous causal structure is identifiable. The proof rules out an alternative causal direction by comparing likelihoods for a graph with one reversed causal pair.

  • Theorem 3 establishes identifiability of the multivariate instantaneous causal structure under causal faithfulness and causal sufficiency.Source: C Proof of Theorem 3 · p. 12
  • Because likelihood decomposes by graph, the proof tests whether a graph with one reversed causal pair can match the correct graph’s likelihood.If the pairwise reversal is ruled out, the full likelihood admits no alternative graph in the Markov equivalent class.Source: C Proof of Theorem 3 · p. 12
  • The proof assumes equal likelihoods for the correct and reversed graphs, then compares their second-order differences to derive a necessary condition.Source: C Proof of Theorem 3 · pp. 13, 16
  • That condition requires every reversed node’s causal influence to be zero, contradicting the assumption that those influences are nonzero.The contradiction rules out equal likelihoods for the two directions.Source: C Proof of Theorem 3 · pp. 12, 16

D Additional Experiments

The additional experiments report precision, recall, and Structural Hamming Distance (SHD) for sensitivity experiments, complementing F1 scores and baseline results shown in the main paper.

Loading 2305.05986v1…