Predicting User Activity Level In Point Processes With Mass Transport Equation

Yichen Wang, Xiaojing Ye, Hongyuan Zha, Le SongNeurIPS 2017 · OpenReview

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:

  1. 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.
  2. 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.

The HYBRID framework process
  1. 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.
  2. 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.
  3. 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.
  4. The Algorithm:
    • Generate a small number of event history samples.
  5. For each sample, solve the mass transport ODE to get a precise probability mass function (PMF).
  6. 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.

Predictive performance (MAPE) comparisons
  • 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

Abstract

Point processes are powerful tools to model user activities and have a plethora of applications in social sciences. Predicting user activities based on point processes is a central problem. However, existing works are mostly problem specific, use heuristics, or simplify the stochastic nature of point processes. In this paper, we propose a framework that provides an unbiased estimator of the probability mass function of point processes. In particular, we design a key reformulation of the prediction problem, and further derive a differential-difference equation to compute a conditional probability mass function. Our framework is applicable to general point processes and prediction tasks, and achieves superb predictive and efficiency performance in diverse real-world applications compared to state-of-arts.
BibTeX
@inproceedings{wang2017predicting,
  author = {Yichen Wang and Xiaojing Ye and Hongyuan Zha and Le Song},
  title = {{Predicting User Activity Level In Point Processes With Mass Transport Equation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=BJeKq8bOWB},
}
Figure