Proximal Graphical Event Models

Debarun Bhattacharjya, Dharmashankar Subramanian, Tian GaoNeurIPS 2018 · OpenReview

Introduction

Many real-world datasets—such as server logs, financial transactions, or clinical visits—do not manifest as smooth time series. Instead, they appear as "event streams" characterized by irregular bursts of activity. To model these sequences, researchers rely on Graphical Event Models (GEMs), which describe how the occurrence of one event type influences the probability (or intensity) of another.

A major bottleneck in existing GEMs is their reliance on human experts to specify "basis functions." Essentially, users must guess the relevant time intervals for event dependencies (e.g., determining if an event happens within 5 minutes or 5 hours of its parent). Incorrect guesses lead to poor model performance, while attempting to include every possible interval renders computation intractable. To address this, researchers introduce Proximal Graphical Event Models (PGEMs), a data-driven approach that removes the human from the loop by automatically learning these critical time windows directly from the data.

Methods

The core framework of the Proximal Graphical Event Model (PGEM) posits that the rate of an event $X$ depends on a simple binary condition: has a parent event $Z$ occurred at least once within a specific "proximal" window $w_{zx}$?

Overview of PGEM: (a) event timeline, (b) graphical structure, and (c) log-likelihood surface for window optimization.

Key technical contributions of this approach include:

  • Optimal Window Learning: The authors mathematically prove that the optimal time window is not an arbitrary continuous value. Instead, it belongs to a finite set of "candidate" windows derived directly from the actual inter-event times present in the dataset.
  • Structure Learning: The model employs a Forward-Backward Search (FBS) algorithm, guided by the Bayesian Information Criterion (BIC), to discover parent-child relationships between event types.
  • Theoretical Bounds: The researchers provide a mathematical proof bounding the number of parents for any event by $O(\log N)$, where $N$ is the total number of events. This crucial bound prevents the search space from exploding as datasets grow.
  • Efficient Heuristics: To handle large-scale data, two optimized versions of the search are proposed: FBS-IW (Independent Windows) and FBS-CW (Coordinate-wise optimization).

Key Insights

The success of PGEMs relies on a few core insights. First is the "Proximal" Assumption: by assuming only the most recent occurrence of a parent matters, the model remains highly interpretable, effectively answering, "If $A$ happened recently, how much more likely is $B$?"

Second is the concept of Data-Adaptive Windows. By searching for optimal windows at the jump points of the likelihood function (the inter-event times), the model identifies the exact temporal scale of influence without requiring manual tuning. Finally, using BIC combined with derived parent-set bounds ensures strict Complexity Control, preventing the model from overfitting by adding spurious edges to the dependency graph.

Datasets and Key Results

The authors evaluated PGEMs across a mix of controlled and real-world datasets:

  1. Synthetic Datasets: Six distinct PGEM structures with varying numbers of event labels ($M=5$ and $M=10$) were used to test ground-truth recovery.
  2. Book Datasets: Word occurrences in Thomas Hobbes’ Leviathan and the Bible (treating individual words as discrete events).
  3. ICEWS (Integrated Crisis Early Warning System): A massive dataset of political events across five countries (Argentina, Brazil, Colombia, Mexico, and Venezuela).
Log-likelihood comparisons on synthetic datasets showing PGEM variants outperforming or matching baseline models.

In synthetic tests, PGEMs consistently outperformed the SIP baseline and matched or exceeded the performance of CPCIM, a state-of-the-art model that requires manual basis functions. On the real-world book datasets, PGEMs achieved significantly higher log-likelihoods than CPCIM, often by margins of several thousand points. Furthermore, in the ICEWS dataset, PGEMs outperformed competing models in 4 out of 5 countries, successfully capturing complex political dynamics without prior domain knowledge of the specific regions.

Limitations and Future Work

While highly effective, PGEMs rely on a piece-wise constant assumption. This means the influence of a parent event is strictly "on" or "off" within the learned window. Consequently, it does not naturally model decaying influences, such as those seen in a Hawkes process where an event's effect gradually fades over time.

Future work may involve extending these models to handle more complex underlying temporal distributions or exploring how these learned causal relationships adapt over time in non-stationary environments.

Summary updated

Abstract

Event datasets include events that occur irregularly over the timeline and are prevalent in numerous domains. We introduce proximal graphical event models (PGEM) as a representation of such datasets. PGEMs belong to a broader family of models that characterize relationships between various types of events, where the rate of occurrence of an event type depends only on whether or not its parents have occurred in the most recent history. The main advantage over the state of the art models is that they are entirely data driven and do not require additional inputs from the user, which can require knowledge of the domain such as choice of basis functions or hyperparameters in graphical event models. We theoretically justify our learning of optimal windows for parental history and the choices of parental sets, and the algorithm are sound and complete in terms of parent structure learning. We present additional efficient heuristics for learning PGEMs from data, demonstrating their effectiveness on synthetic and real datasets.
BibTeX
@inproceedings{bhattacharjya2018proximal,
  author = {Debarun Bhattacharjya and Dharmashankar Subramanian and Tian Gao},
  title = {{Proximal Graphical Event Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BkVet_-ObH},
}
Figure