Introduction
Predicting future user activity—such as how many times a tweet will be shared, how many new followers a user will gain, or how many products a customer will buy—is a central problem in social networks and e-commerce.
Mathematically, these events are modeled as Temporal Point Processes (TPPs). The challenge is that these processes are highly stochastic (random) and history-dependent; an event happening now increases the likelihood of an event happening later, a phenomenon known as self-excitation.
The authors introduce HYBRID, a novel framework that predicts future user activity by solving a "mass transport equation." By combining traditional sampling with an analytical differential equation to track probability, HYBRID achieves the same accuracy as Monte Carlo methods while using 1,000x fewer samples—slashing computation time from over a day to just 15 minutes.
The Problem with Existing Approaches
Existing solutions for predicting TPPs usually fall into two traps:
- Heuristics and Simplification: They make rigid assumptions about the data or ignore the "randomness" of the intensity to make the math easier. This fundamentally hurts predictive accuracy.
- Brute Force (Monte Carlo): They simulate millions of possible futures and average them. While accurate, this is computationally expensive and slow because the variance of the outcomes is extremely high.
The authors sought a way to preserve the full stochastic nature of the model while making the math efficient enough for real-time applications.
The HYBRID Framework
The core innovation of this paper is the HYBRID framework, which elegantly bridges the gap between simulation and analytical calculation.
- Variance Reduction: Instead of merely averaging the number of events across simulations, the authors use a technique inspired by the Rao-Blackwell theorem. They realized that if you know the history of events up to a certain point, you can analytically calculate the probability distribution of future events much more accurately than by just counting simulated outcomes.
- The Mass Transport Equation: The authors derive a "differential-difference equation" that describes how probability mass moves between states. Imagine a series of buckets representing the number of events (0, 1, 2...). As time passes, probability "flows" from bucket $x$ to bucket $x+1$ at a rate determined by the model's intensity.
- ODE Reformulation: They transform this complex equation into a banded linear Ordinary Differential Equation (ODE). Because the matrix is "sparse" (probability only moves forward to the next bucket), it can be solved very quickly using standard numerical methods like Runge-Kutta.
- The Algorithm:
- Generate a small number of event history samples.
- For each sample, solve the mass transport ODE to get a precise probability mass function (PMF).
- Average these PMFs to get the final, unbiased prediction.
Key Insights
- Efficiency through Math: You don't need to simulate the entire future. You only need to simulate the history that determines the rate of future events, then let the mass transport equation handle the rest of the probability calculation.
- Generality: Unlike previous methods designed for specific tasks, HYBRID works for any application-dependent function. Whether predicting the mean, variance, or entropy of user activity, the framework remains the same.
- Information Utilization: Standard Monte Carlo treats two different event sequences that result in the same total count as identical. HYBRID recognizes that the timing of those events changes the future intensity, utilizing that timing data to refine the probability transport.
Key Results
The authors evaluated HYBRID on diverse real-world datasets, including Twitter (280k users), IPTV (7.1k users), Reddit (1k users), and synthetic Hawkes process data.
- Massive Speedup: To reach a relative error of 0.1 in a social link creation model, standard Monte Carlo required 1,000,000 samples and 27.8 hours. HYBRID achieved the same result with only 1,000 samples in 14.4 minutes.
- Higher Accuracy: As shown in the evaluations above, HYBRID consistently achieved a lower Mean Absolute Percentage Error (MAPE) than state-of-the-art baselines like SEISMIC, RPP, and FPE, especially when training data was sparse.
- Better Rank Correlation: In predicting which items or users would become popular, HYBRID outperformed competitors by roughly 20-30%, demonstrating a superior ability to identify "trending" content early.
Limitations and Future Work
While powerful, the ODE solver requires a maximum number of events ($M$) to be set. While the authors suggest a reliable heuristic ($M = 2 \times$ max events in samples), an extremely "explosive" process might exceed this bound. Additionally, while the paper extends the theory to multi-dimensional processes, the computational cost grows as the number of dimensions increases.
Future work will look to extend HYBRID to Marked Point Processes, where each event carries extra information (like the specific content of a tweet or the price of a purchase), requiring mass transport over more complex state spaces.
Summary updated