Dynamic Representation Learning with Temporal Point Processes for Higher-Order Interaction Forecasting

Tony Gracious, Ambedkar DukkipatiAAAI 2023 · DOI

TL;DR

This paper introduces a novel approach to predict complex, multi-way interactions (hyperedges) in dynamic networks using temporal point processes. By modeling these interactions as events unfolding over time, the method offers a more realistic representation than traditional pairwise interaction models, leading to improved forecasting accuracy.

What Problem Does This Paper Address?

Real-world interactions are often more complex than simple pairwise connections. Think of a family discussing a movie, a group of researchers co-authoring a paper, or a mutual fund holding multiple stocks. These are "higher-order" interactions, often represented as hyperedges in a hypergraph. Traditional network analysis often simplifies these by projecting them into pairwise interactions, leading to significant information loss and an inability to accurately capture the true dynamics. Furthermore, these interactions evolve over time. Existing methods struggle to predict when and what type of these complex, dynamic, higher-order interactions will occur. This paper aims to fill this gap by developing a model that can forecast hyperedges in dynamic networks.

Methods

The core of this work is a Temporal Point Process (TPP) framework adapted for hyperedge forecasting. TPPs are well-suited for modeling discrete events occurring over continuous time. The authors propose a dynamic representation learning approach for nodes within this TPP framework.

Key methodological components include:

  • Hyperedge Event Modeling: Each hyperedge event is treated as a distinct event type, with a conditional intensity function predicting its occurrence. This intensity function is parameterized by dynamic node embeddings.
  • Dynamic Node Representation: Node embeddings are learned through a three-stage process:
  • Temporal Drift: Captures the evolution of a node's embedding over time between interactions.
  • History Aggregation: Uses hypergraph convolutions to incorporate information from past hyperedges.
  • Interaction Update: Updates a node's embedding based on the embeddings of other nodes involved in a hyperedge interaction, using a self-attention mechanism.
  • Self-Attention for Hyperedge Encoding: Since hyperedges can involve a variable number of nodes, a self-attention mechanism is employed to effectively encode these variable-sized interactions.
  • Bipartite Hyperedge Extension: The model is extended to handle bipartite hyperedges, where interactions occur between two distinct sets of nodes (e.g., users and items).

Datasets

The paper evaluates its proposed models on several real-world datasets for both homogeneous and bipartite hyperedge interactions.

  • Homogeneous Hyperedge Datasets: email-Enron, email-EU, congress-bills, NDC-classes, NDC-sub, CastGenre, CastKeyword, CastCrew. These datasets are standard for hypergraph analysis.
  • Bipartite Hyperedge Dataset: The Movies Dataset (from Kaggle). This dataset is used to evaluate the bipartite hyperedge variant of the model.

The paper does not introduce new benchmark datasets but rather applies its methods to existing ones.

Key Insights and Ideas

  • Hypergraphs are Crucial for Dynamic Interactions: The paper strongly argues that approximating higher-order interactions with pairwise ones leads to significant information loss, especially in dynamic settings. The example in Figure 1 vividly illustrates how different hypergraphs can project to the same pairwise graph, making it impossible to recover the original structure.
  • Temporal Dynamics Matter for Higher-Order Interactions: Just as temporal dynamics are important for pairwise interactions, they are equally, if not more, critical for understanding and predicting complex, multi-way interactions.
  • Dynamic Node Embeddings are Key: The proposed dynamic node representation, incorporating temporal drift, history aggregation, and interaction updates, is shown to be significantly more effective than static or piecewise constant embeddings.
  • Self-Attention Handles Variable Interaction Sizes: The use of self-attention is a clever way to deal with the inherent variability in the number of nodes participating in hyperedge events.

Key Results

The proposed models, Hypergraph Dynamic Hyperedge (HGDHE) for homogeneous interactions and Hypergraph Bipartite Dynamic Hyperedge (HGBDHE) for bipartite interactions, consistently outperform baseline models across various datasets and tasks.

  • Interaction Type Prediction: HGDHE shows significant gains in Mean Reciprocal Rank (MRR) compared to pairwise models (e.g., 38.4% gain for DHE vs. DE) and static hyperedge models.
  • Interaction Duration Prediction: The models achieve substantial reductions in Mean Absolute Error (MAE) for predicting interaction duration.
  • Bipartite Advantage: The bipartite models (BDHE, HGBDHE) outperform their homogeneous counterparts (DHE, HGDHE) on bipartite datasets, demonstrating the benefit of explicitly modeling bipartite structures.
  • Ablation Studies: The results highlight the importance of each component of the dynamic node representation: temporal drift, history aggregation, and interaction update all contribute to improved performance.

Limitations and Future Work

  • Computational Efficiency: The paper acknowledges that directly implementing the loss function for TPPs can be computationally inefficient due to the large number of possible hyperedges. They propose a mini-batch training procedure to address this.
  • Future Work: The authors suggest several promising directions:
  • Extending the model to handle multi-relational higher-order interactions.
  • Incorporating multi-hop information using hypergraph neural networks for better predictive performance.
  • Exploring parallel training techniques to further reduce training time.

Summary updated

BibTeX
@inproceedings{gracious2023dynamic,
  author = {Tony Gracious and Ambedkar Dukkipati},
  title = {{Dynamic Representation Learning with Temporal Point Processes for Higher-Order Interaction Forecasting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i6.25939},
}
Figure