Accelerated Hawkes Process: Scaling Event History Modeling from O(N²) to O(N)

TL;DR

Modeling sequential events in social networks—like the spread of a rumor or a series of product reviews—often relies on Hawkes Processes. While mathematically elegant, these models suffer from a "memory bottleneck" where every new event requires looking back at all previous ones. This paper introduces a recursive formulation that slashes computational complexity from quadratic to linear, enabling deep temporal modeling on datasets that were previously untouchable.

The Problem: The "History Tax" of Mutual Excitation

Hawkes Processes are "self-exciting" or "mutually exciting." This means if a user tweets about a hot topic (Event A), it increases the probability of another tweet (Event B) occurring shortly after. Mathematically, the intensity $\lambda (t)$ is the sum of a base rate plus the decaying influence of every previous event:

${\lambda }_{y_n}(t)={\mu }_{y_n}+{\sum }_{t_l<t}{\alpha }_{y_l,y_n}\kappa (t-t_l)$

As the number of events $N$ grows, the summation grows. For $N$ events, you perform roughly $N^2/2$ calculations. On a dataset with 50,000 events, this isn't just slow—it's a computational wall.

Methodology: The Recursive Breakthrough

The authors' core insight is that if we use an exponential decay kernel $\kappa (\Delta t)=\exp (-\omega \Delta t)$, we don't need to actually "look back." We can summarize the entire past into a state vector.

The State Vector ($\gamma$)

The authors maintain an $S$-dimensional vector (where $S$ is the number of labels) that stores the accumulated influence. When a new event occurs, the intensity is calculated by simply multiplying the previous state by a decay factor and adding the new influence.

Why this works: The exponential function has a unique property: $\exp (a+b)=\exp (a)\exp (b)$. This allows the "decay" to be applied to the entire sum of previous influences simultaneously, rather than calculating it for each event individually. This transforms the intensity calculation into a Constant Time O(1) operation per event.

Experimental Results: Massively Reduced Training Time

The researchers tested the "Accelerated Hawkes" against the "Standard Hawkes" across three environments:

1. Synthetic Data: 1,000x Improvement

As shown in their performance charts, the standard model's runtime grows exponentially (quadratically) while the accelerated version stays almost flat. At 5,000 data points, the runtime difference is three orders of magnitude.

2. Amazon Review Dataset: Hours vs. Days

Testing on 15,000 product reviews, the authors sought to predict rating categories (Bad, Good, Excellent).

• Standard Hawkes: 11 hours to train.
• Accelerated Hawkes: 1.46 hours.

Importantly, the Accuracy (0.65) remained identical, proving that the acceleration comes from algorithmic efficiency, not mathematical approximation.

Critical Analysis & Conclusion

Takeaway

The Accelerated Hawkes Process is a game-changer for practitioners in social media analytics and recommendation systems. By reducing the complexity to $O(N)$, it allows the use of theoretically sound probabilistic models on scale-level datasets that were previously reserved for simpler, less interpretable models.

Limitations

The primary constraint of this method is its reliance on the exponential decay kernel. In some physical systems or specific human behaviors, excitation might follow a Power Law (slower decay). The recursive trick used here does not directly apply to non-exponential kernels, which remains an open area for research in "approximate recursion."

Future Outlook

This approach paves the way for integrating Hawkes Processes into real-time streaming pipelines. Imagine a Twitter stance classifier that updates its understanding of a viral rumor's trajectory with every single millisecond-level update, without ever slowing down as the thread grows longer.