Temporal point processes (TPPs) are the mathematical bedrock for modeling events that occur irregularly in continuous time. They are widely used to capture the dynamics of retweets cascading through a social network, high-frequency stock trades, or neural spike trains. Among these, self-exciting processes—such as the Hawkes process—are exceptionally powerful because they capture how past events trigger future ones.
However, this expressive power comes with a severe computational penalty: a quadratic scaling bottleneck ($O(N^2)$) relative to the number of events $N$. To compute the network's "intensity" (the instantaneous likelihood of a new event occurring) at any moment, a standard Hawkes process must look backward and sum up the decaying influence of every single historical event. If a dataset contains millions of interactions, calculating this history for each new event becomes computationally intractable. As noted by Shuang Yang et al. in Mixture of Mutually Exciting Processes for Viral Diffusion, this quadratic complexity prevents these models from scaling to planetary-scale data.
Furthermore, when events are "marked" (categorized into $M$ distinct types or nodes, such as users in a network), the problem compounds. Tracking how every event type influences every other type introduces an additional matrix scaling bottleneck, making real-time inference on massive graphs nearly impossible (Hongyuan Zha et al. in Learning Social Infectivity in Sparse Low-rank Networks Using Multi-dimensional Hawkes Processes).
To solve these scaling challenges, researchers have developed several distinct strategies to bypass the quadratic bottleneck.
Timeline Discretization and Precomputation
One intuitive way to break the $O(N^2)$ bottleneck is to decouple the computational cost from the raw number of events by discretizing the timeline. Instead of calculating exact pairwise continuous-time intervals between every historical event, models can map events onto a fine-grained temporal grid.
In FaDIn: Fast Discretized Inference for Hawkes Processes with General Parametric Kernels, Guillaume Staerman et al. demonstrate that by combining timeline discretization with clever precomputations, the inference cost can be made entirely independent of the number of events. This allows researchers to use complex parametric kernels without suffering from the typical scaling penalty.
Similarly, Emilia Siviero et al. leverage discretization alongside finite-support kernels and a least-squares loss function in Numerically Efficient Parametric Inference for Learning Space-Time Hawkes Processes. This combination achieves linear scalability ($O(N)$), unlocking the ability to model complex, non-separable spatiotemporal interactions that were previously computationally prohibitive.
Shortening Memory via Markovian Processes
If the quadratic bottleneck stems from the "long memory" of Hawkes processes—where an event from days ago still technically exerts a mathematical pull on the present—an alternative solution is to change the underlying process to one with shorter memory.
Wold processes offer an elegant alternative. Unlike Hawkes processes, a Wold process possesses a Markovian property: its intensity depends only on the most recent inter-event times rather than the entire history. As a result, the computational complexity per event drops to a constant $O(1)$.
Jalal Etesami et al. exploit this property in A Variational Inference Approach to Learning Multivariate Wold Processes, providing a scalable variational framework that sidesteps the long-memory computational trap. For causal network discovery, Flavio Figueiredo et al. introduce the GRANGER-BUSCA algorithm in Fast Estimation of Causal Interactions using Wold Processes. By swapping out the computationally heavy Hawkes process for a Wold process, the authors achieve massive speedups and superior accuracy on datasets that were previously too large to process.
Low-Rank Approximations and Tensor Factorization
When modeling high-dimensional event streams (e.g., millions of users interacting with millions of items), the challenge shifts from the number of events to the cardinality of the interaction network. Tracking every potential "who-triggers-whom" pair requires optimizing an $M \times M$ matrix, which quickly becomes intractable.
To resolve this, researchers turn to low-rank approximations. In Multivariate Hawkes Processes for Large-Scale Inference, Rémi Lemonnier introduces Scalable Low-Rank Hawkes Processes (SLRHP). By approximating the interaction kernels using a low-rank structure, the author slashes the computational complexity from quadratic to linear ($O(Md)$) with respect to the number of event types, enabling non-parametric inference on web-scale data.
For higher-order interactions (such as a user buying a specific item at a specific store at a specific time), Zhimeng Pan et al. propose a scalable nonparametric factorization framework in Scalable Nonparametric Factorization for High-Order Interaction Events. Their approach balances the depth of temporal history with the massive scale of multi-dimensional tensor data by leveraging Bayesian nonparametrics.
Re-engineering Likelihood and Simulation
Beyond modifying the model structure, scalability can be achieved by changing how we train and simulate these processes. Standard maximum likelihood estimation (MLE) requires evaluating a "survival term"—an integral over the intensity function across the entire observation window. For complex or neural TPPs, this integral lacks a closed-form solution and must be approximated numerically, creating a massive bottleneck.
To bypass this, Hongyuan Mei et al. adapt Noise-Contrastive Estimation (NCE) to continuous-time event streams in Noise-Contrastive Estimation for Multivariate Point Processes. By training the model to distinguish true events from artificially generated noise events, the authors eliminate the need to compute the expensive survival integral entirely.
On the simulation side, traditional thinning algorithms scale quadratically because they require recalculating the maximum intensity after every event. Modern frameworks instead utilize queued thinning algorithms, which sync the thinning process with model time to dramatically accelerate large-scale simulations (Extending JumpProcesses.jl for fast point process simulation with time-varying intensities).
Key Foundational Work
Mixture of Mutually Exciting Processes for Viral Diffusion (2013) — contributed 1 concept elements to this direction.
Learning Social Infectivity in Sparse Low-rank Networks Using Multi-dimensional Hawkes Processes (2013) — contributed 1 concept elements to this direction.
MCMC for continuous-time discrete-state systems (2012) — contributed 1 concept elements to this direction.