Dynamic Group Link Prediction in Continuous-Time Interaction Network

Shijie Luo, He Li, Jianbin HuangIJCAI 2023 · DOI

TL;DR

This paper introduces CTGLP, a novel method for predicting future relationships between individuals and groups in dynamic, continuous-time networks. It addresses the limitations of existing methods by incorporating fine-grained temporal information and a new graph neural network (CTGNN) that captures both neighborhood features and temporal dynamics, outperforming state-of-the-art approaches.

What Problem Does This Paper Address?

Link prediction, the task of forecasting future connections between entities in a network, is crucial for understanding network evolution and has applications in areas like knowledge graph completion and recommendation systems. While significant progress has been made in predicting links between individual nodes, a more complex and realistic scenario involves predicting relationships between individuals and groups. This "group link prediction" is vital for understanding how individuals might join or interact with existing groups, such as in social networks or community formation.

Existing group link prediction methods often fall short in dynamic, continuous-time settings. They tend to focus on predicting missing links rather than future ones, assume static group structures, or inadequately leverage the rich temporal information inherent in real-world interactions. Furthermore, they often neglect the influence of an individual's neighborhood and the varying importance of members within a group, leading to suboptimal predictions. This paper aims to bridge this gap by proposing a method that effectively handles continuous-time dynamics and incorporates these crucial contextual factors.

Methods

The proposed method, CTGLP, is built upon three core components:

  1. Individual Representation Learning (CTGNN): This component uses a novel Graph Neural Network (GNN) called CTGNN to learn latent embeddings for individuals. A key innovation here is a continuous-time neighbor sampling strategy. Unlike traditional GNNs that might sample neighbors irrespective of time, CTGNN ensures that sampled neighbors always exist before the central node's current time, preserving the temporal causality. Additionally, CTGNN employs a biased aggregation function (CTAgg). This function assigns higher weights to neighbors that have interacted more recently with the central node, reflecting the intuition that recent interactions are more indicative of current preferences.
  2. Importance-based Group Modeling: Traditional methods often simply sum the embeddings of group members to represent a group. CTGLP introduces an importance-based group modeling function that accounts for the fact that not all members contribute equally to a group's identity or formation. It calculates an "importance factor" for each member based on their link time to the group, giving more weight to recent members. This weighted sum of member embeddings then forms the group's latent representation.
  3. Prediction: Finally, the learned group embeddings are fed into a Multi-Layer Perceptron (MLP) followed by a Softmax activation function to generate a probability distribution over potential individuals who might link to the group. The individual with the highest probability is predicted as the target.

Datasets

The paper evaluates CTGLP on three datasets:

  • MovieLens-100K (ML100K): A dataset of user ratings for movies.
  • MovieLens-25M (ML25M): A larger version of the MovieLens dataset.
  • CiaoDVD: A dataset containing DVD ratings.

For each dataset, two versions were used: one with all data and another specifically designed to test performance on unseen nodes (nodes not present during training). This "unseen node" scenario is crucial for evaluating the generalizability of the models.

Key Insights and Ideas

  • Temporal Dynamics Matter: The paper strongly emphasizes that simply treating interactions as static or only considering recent snapshots is insufficient for dynamic networks. Capturing the precise timing of interactions is key to understanding evolving relationships.
  • Recency Bias in Aggregation: The idea that more recent interactions are more predictive of future behavior is a powerful heuristic. Applying this to GNN aggregation (CTAgg) significantly improves individual representations.
  • Member Importance Varies: Not all members of a group are equal. Recognizing and quantifying the differential impact of members on a group's identity (Importance-based Group Modeling) leads to more accurate group representations.
  • Unseen Nodes are a Real Challenge: Performance drops significantly when models encounter nodes they haven't seen during training, highlighting the need for robust generalization capabilities.

Key Results

CTGLP consistently outperforms state-of-the-art baselines across various metrics (Hit Ratio@K, NDCG@K, MRR@K) on both datasets with and without unseen nodes.

  • On datasets with unseen nodes, CTGLP achieved average gains of 13.4% and 13.2% across metrics.
  • Specifically, on ML100K, it showed average gains of 7.3%, 31.9%, and 43.9% in HR, NDCG, and MRR, respectively.
  • On ML25M, average gains were 11.45%, 14.7%, and 11.1%.
  • The ablation study confirmed the importance of both the CTAgg (neighbor aggregation) and Importance-based Group Modeling components, with their removal leading to significant performance degradation.
  • The paper also demonstrates that CTGLP has a competitive training and inference time compared to other advanced methods.

Limitations and Future Work

  • Computational Complexity: While CTGNN's neighbor sampling helps manage computational cost, handling very large-scale, dense continuous-time networks can still be challenging.
  • Hyperparameter Sensitivity: The performance of CTGLP is influenced by hyperparameters like hidden state dimension, group vector dimension, and neighbor sampling size, requiring careful tuning.
  • Future Work: The authors suggest exploring more sophisticated temporal aggregation mechanisms and investigating CTGLP's applicability to other dynamic network tasks beyond group link prediction. Further research into how to better model the evolving nature of group memberships and individual roles within groups could also be beneficial.

Summary updated

BibTeX
@inproceedings{luo2023dynamic,
  author = {Shijie Luo and He Li and Jianbin Huang},
  title = {{Dynamic Group Link Prediction in Continuous-Time Interaction Network}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/248},
}
Figure