Source-linked AI summary
Learning Granger Causality for Hawkes Processes
Hongteng Xu, Mehrdad Farajtabar, Hongyuan Zha
TL;DR
Learning Granger causality for general point processes is difficult because continuous-time event sequences lack fixed time-lagged observations. This paper targets Hawkes processes by linking causality to impact functions and learning them with basis expansions and sparse regularization. Experiments on synthetic and real-world data show that the method learns both the causality graph and triggering patterns.
Problem
Learning Granger causality for general multi-dimensional point processes is difficult, particularly because continuous-time data lack fixed time-lagged observations.
Method
The paper represents Hawkes-process impact functions with basis functions and combines maximum likelihood estimation with sparse-group-lasso regularization to recover causality graphs.
Results
Experiments on synthetic and real-world data show that the method learns Hawkes-process Granger causality and triggering patterns simultaneously.
Takeaways & Limitations
The method provides a flexible Hawkes-process framework that can incorporate event-type clustering and adaptively select basis functions.
Takeaways & Limitations
The stated equivalence between Granger non-causality and a zero impact function requires the condition dNu′(t −s) > 0 for 0 ≤s < t ≤T.
Abstract
from arXiv · showhide
Learning Granger causality for general point processes is a very challenging task. In this paper, we propose an effective method, learning Granger causality, for a special but significant type of point processes --- Hawkes process. We reveal the relationship between Hawkes process's impact function and its Granger causality graph. Specifically, our model represents impact functions using a series of basis functions and recovers the Granger causality graph via group sparsity of the impact functions' coefficients. We propose an effective learning algorithm combining a maximum likelihood estimator (MLE) with a sparse-group-lasso (SGL) regularizer. Additionally, the flexibility of our model allows to incorporate the clustering structure event types into learning framework. We analyze our learning algorithm and propose an adaptive procedure to select basis functions. Experiments on both synthetic and real-world data show that our method can learn the Granger causality graph and the triggering patterns of the Hawkes processes simultaneously.
1. Introduction
The paper addresses the difficulty of learning Granger causality from continuous-time event sequences by focusing on Hawkes processes. It represents impact functions flexibly and learns causality using sparse regularization, with experiments supporting the method’s effectiveness.
- Continuous-time event data contain multiple event types and arise in applications such as television viewing and hospital records.These sequences are modeled as multi-dimensional point processes.
- Learning Granger causality for general multi-dimensional point processes is difficult because continuous time lacks fixed time-lagged observations.Existing time-series approaches commonly rely on VAR models with discrete time-lagged variables.
- The paper focuses on Hawkes processes, which model self- and mutually triggering patterns among event types and have applications across several fields.Examples include bioinformatics, social networks, and financial analysis.
- Impact functions encode Hawkes-process Granger causality, enabling a basis-function model whose coefficient group sparsity recovers the causality graph.The learning algorithm combines maximum likelihood estimation with a sparse-group-lasso regularizer and can incorporate event-type clustering.
- Experiments on synthetic and real-world data show that the method reveals Hawkes-process Granger causality and achieves superior learning performance against competitors.The method is designed for complicated event sequences in continuous time and avoids discretizing impact functions and conditional intensity.
2. Related Work
Prior work developed point-process and Hawkes-process approaches for modeling temporal dependencies, but sparse-group-lasso-based causality learning for Hawkes processes remained less explored.
- Research on point-process Granger causality includes independence tests, piecewise-constant intensity models, grouping-based network methods, diffusion inference, and marked-point-process graphical models.These approaches address different process structures and dependency settings.
- Eichler et al. connected Hawkes-process Granger causality with impact functions, while this paper applies sparse-group-lasso to learn the causality graph.The related-work discussion states that sparse-group-lasso-based Hawkes causality learning had received less attention.
- Hawkes processes have been modeled with predefined parametric impact functions and several nonparametric estimation strategies.Nonparametric approaches include ODE-based, Wiener-Hopf, and contrast-function estimators.
3. Basic Concepts
A temporal point process represents discrete events over continuous time, while a multi-dimensional process tracks multiple event types through counting processes and conditional intensities. Granger causality identifies which event histories affect a target type and represents those dependencies as directed edges.
- Temporal Point Processes: A temporal point process is a random process whose realization is a list of discrete events occurring within [0, T].It can equivalently be represented by a counting process recording the number of events before each time.
- Temporal Point Processes: A multi-dimensional point process uses one counting process for each event type, with its filtration recording the process history available up to time t.The event types form the dimensions of the process.
- Temporal Point Processes: The conditional intensity function gives the expected instantaneous rate of occurrence for an event type given the observed history.It characterizes patterns such as self-triggering or self-correcting behavior.
- Hawkes Processes: In a Hawkes process, the impact function measures how historical events of one type influence subsequent events of another type over time.The intensity combines an exogenous base intensity with endogenous peer influence.
- Granger Causality: Granger causality asks whether a target intensity depends on the histories of a selected subset of event types rather than the remaining types.The corresponding graph contains event types as nodes and directed edges for the resulting causal relations.
- Granger Causality: Learning Granger causality for general multi-dimensional point processes is difficult, motivating an efficient method specialized to Hawkes processes.The paper introduces that method in the following section.
4. Proposed Model and Learning Algorithm
The proposed method represents Hawkes impact functions with basis functions and learns Granger causality through coefficient sparsity, using an MLE-based sparse-group-lasso algorithm with optional similarity constraints. It also provides adaptive basis selection and is designed for convex, robust learning.
- Proposed Model: Hawkes Granger causality is identified by whether each destination-source impact function is identically zero.A directed edge is absent exactly when the corresponding impact function vanishes over time.
- Proposed Model: The nonparametric model represents each impact function as a linear combination of basis functions instead of a single fixed time-decay function.This addresses the inflexibility of parametric impact-function assumptions.
- Regularization: Group sparsity across basis coefficients recovers graph edges, while additional regularizers impose temporal sparsity and optional similarity among clustered event types.The model uses group-lasso for local independence, coefficient sparsity for temporal decay, and pairwise constraints when clustering information is available.
- Learning Algorithm: MLE-SGLP combines Hawkes-process maximum likelihood with sparse-group-lasso and pairwise-similarity constraints in an iterative EM-based optimization scheme.The algorithm constructs a Jensen upper bound, updates parameters, and applies soft-thresholding to shrink coefficients.
- Adaptive Basis Selection: The adaptive basis-selection procedure is founded on sampling theory and uses assumptions about impact-function integrability and band-limited approximation.The procedure estimates a frequency bound from the Fourier transform and selects basis functions accordingly.
- Properties: The proposed algorithm is convex, can achieve global optima, and has complexity at least comparable to the ODE-based alternative.Unlike the alternating ODE-based method, the proposed optimization is not prone to local optima according to the paper’s comparison.
5. Experiments
Experiments compare MLE-SGLP with alternative Hawkes-process learners on synthetic and IPTV data, showing improved likelihood, error, graph recovery, and interpretable triggering patterns.
- Experimental setup: The study compares MLE-SGLP with ODE-based, least-squares, pure-MLE, group-lasso, and sparse-regularized variants on synthetic and real-world data.Synthetic data use sine-like and piecewise-constant impact functions; IPTV data contain 7,100 users and 13 program categories.
- Synthetic data: MLE-SGLP achieves higher Loglike and lower eµ and eφ than competing methods across synthetic datasets and training-set sizes.With few training sequences, ODE-based and least-squares methods overfit by estimating too many parameters.
- Synthetic data: Regularization improves MLE results: MLE-SGLP is best when clustering structure is available, while MLE-SGL is best otherwise.MLE-SGL is slightly better than MLE-GL and MLE-S when clustering structure is unavailable.
- Synthetic data: MLE-SGLP recovers all-zero impact functions correctly, whereas pure MLE sometimes fails, even when Gaussian bases poorly fit piecewise-constant functions.The estimates of nonzero impact functions may be inaccurate, but the Granger-causality graph remains correctly recovered.
- Real-world data: On IPTV data, learned infectivity reflects strong self-triggering for all categories and stronger cross-triggering among popular categories.Diagonal infectivity values are larger and daily-periodic; non-diagonal links involving unpopular categories are small or zero.
- Real-world data: The proposed algorithm performs better than competitors on IPTV data, producing reasonable and interpretable learning results.The IPTV experiment uses the first 10 months for training and the final month for testing without pairwise sparsity.
6. Conclusion
The paper learns Hawkes-process Granger causality through impact functions and sparse-group-lasso regularization, demonstrating robustness on synthetic and real-world data while identifying general point processes as future scope.
- Conclusion: The method learns Hawkes-process Granger causality from the relationship between causality and impact functions.The approach targets the Granger-causality graph of the target process.
- Conclusion: Combining maximum likelihood with sparse-group-lasso yields an algorithm for learning the Granger-causality graph.The conclusion identifies the sparse-group-lasso combination as the central algorithmic construction.
- Conclusion: Experiments on synthetic and real-world data demonstrate the method's robustness and rationality.The conclusion reports evidence from both evaluation settings without specifying a quantitative metric.
- Conclusion: Future work will extend the analysis from Hawkes processes to general point processes.This is the stated scope boundary and planned direction.
8. Appendix
The appendix develops the optimization and adaptive basis-selection procedures, including convex subproblem updates, spectral bounds, and parameter-stability analysis.
- Optimization: Jensen's inequality supplies a lower-bound surrogate used in the optimization procedure.The surrogate satisfies QΘ|Θ(k) ≥ LΘ and equality holds at the current parameters.
- Optimization: The surrogate objective combines data fidelity with sparse, group, and clustering-related penalties on impact-function coefficients.The displayed objective includes αS, αG, and αP terms.
- Optimization: Fixing other parameters reduces coefficient updates to a convex optimization problem characterized by subgradient equations.The procedure uses majorization and soft-thresholding to obtain generalized gradient updates.
- Basis-function selection: The basis-selection procedure estimates the intensity spectrum from training sequences using a Gaussian kernel density estimator.Silverman's rule selects the bandwidth, and the resulting spectral estimate guides basis-function selection.
- Basis-function selection: Fourier analysis bounds the basis cut-off frequency using the intensity spectrum and a prescribed residual error.The intensity spectrum is a weighted sum of basis spectra, so the basis cut-off is bounded by the intensity cut-off.
- Parameter configuration: Across αP, αG, and αS values from 10^-2 to 10^4, learning results remain relatively stable, with selected values αS = 10, αG = 100, and αP = 1000.The parameter curves use 250 training sequences.