Ordinal Historical Dependence in Graphical Event Models with Tree Representations

Debarun Bhattacharjya, Tian Gao, Dharmashankar SubramanianAAAI 2021 · OpenReview

Abstract

Graphical event models (GEMs) capture process independence in multivariate temporal point processes. While interpretable, existing models often struggle with "parameter explosion" when accounting for the order of past events. This paper introduces a novel GEM based on a parametric tree representation to compactly model ordinal historical dependence. We demonstrate that this approach fits real-world datasets better than baselines and offers significant advantages for knowledge discovery.

Introduction

In domains ranging from finance to healthcare, event streams—sequences of time-stamped occurrences—provide critical insights into underlying dynamics. Graphical Event Models (GEMs) are standard tools for understanding dependencies between these events. However, most GEMs focus on the presence or frequency of recent events, often ignoring the specific order of occurrences. For instance, a "Government Stimulus" followed by a "Crisis" may trigger different social responses than a "Crisis" followed by a "Stimulus."

Capturing this ordinal dependence is computationally challenging. The number of possible event sequences grows super-exponentially with the number of parent events, leading to a "parameter explosion" in traditional tabular models. This makes models difficult to train and prone to overfitting.

Methodology: The Tree Ordinal Graphical Event Model (Tree OGEM)

To address these challenges, we propose the Tree Ordinal Graphical Event Model (Tree OGEM). The core innovation is the use of a tree-based representation to share parameters across different event sequences.

Figure 1: (a) A Graphical Event Model showing dependencies between event types. (b) A corresponding Parameter Tree for label P, where leaf nodes represent shared intensity rates for specific event sequences.

Tree Representation and Learning

Instead of a flat table, the model uses a tree where each node represents a partial order (e.g., "Event A happened most recently"). If the specific order of remaining events does not significantly alter the outcome, the tree stops branching, and those sequences share a single rate parameter at a leaf node. This structure captures context-specific independence, allowing the model to remain parsimonious even as the number of potential causes grows.

The model is learned using a score-based greedy algorithm that grows the tree by identifying the most informative splits in event order, guided by the Bayesian Information Criterion (BIC) to prevent over-complexity. Additionally, a window heuristic is employed to efficiently determine the optimal "look-back" period for historical events.

Experimental Results

The Tree OGEM was evaluated against standard baselines, including Multivariate Hawkes Processes (MHP) and Proximal GEMs (PGEM), across eight diverse real-world datasets such as ICEWS (socio-political events), Mimic-II (health records), and Stack Overflow (user badges).

Figure 6: Comparison of parent sets and intensity rate representations across different models. Note how OGEM-tree handles a larger set of parents with a structured tree-based table compared to the tabular OGEM-tab.

Key Findings

  • Superior Predictive Performance: Tree OGEM (and its automated window variant, OGEM-tree-W) outperformed baselines on 7 out of 8 datasets.
  • Efficiency in High Dimensions: On the Stack Overflow dataset, the model identified dependencies involving 5 or more parent events using significantly fewer parameters than a tabular model would require for just 2 parents.
  • Interpretability: Unlike "black-box" models, Tree OGEM is human-readable. In ICEWS data, it identified specific sequences (e.g., Citizen Appeal $\rightarrow$ Police Fight $\rightarrow$ Protest) that significantly increased the probability of future unrest, providing actionable insights for analysts.

Conclusion

The Tree OGEM provides a robust framework for modeling ordinal historical dependence in event streams. By leveraging tree structures to mitigate parameter explosion, it achieves a balance between complexity and interpretability. Future work will explore more sophisticated masking functions for summarizing event history and refined methods for optimizing the historical look-back window.

Summary updated

Abstract

Graphical event models are representations that capture process independence between different types of events in multivariate temporal point processes. The literature consists of various parametric models and approaches to learn them from multivariate event stream data. Since these models are interpretable, they are often able to provide beneficial insights about event dynamics. In this paper, we show how to compactly model the situation where the order of occurrences of an event’s causes in some recent historical time interval impacts its occurrence rate; this sort of historical dependence is common in several real-world applications. To overcome the practical challenge of parameter explosion due to the number of potential orders that is super-exponential in the number of parents, we introduce a novel graphical event model based on a parametric tree representation for capturing ordinal historical dependence. We present an approach to learn such a model from data, demonstrating that the proposed model fits several real-world datasets better than relevant baselines. We also showcase the potential advantages of such a model to an analyst during the process of knowledge discovery.
BibTeX
@inproceedings{bhattacharjya2021ordinal,
  author = {Debarun Bhattacharjya and Tian Gao and Dharmashankar Subramanian},
  title = {{Ordinal Historical Dependence in Graphical Event Models with Tree Representations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=4EsPtDLHSg},
}
Figure