Neural Temporal Walks: Motif-Aware Representation Learning on Continuous-Time Dynamic Graphs

Ming Jin, Yuan-Fang Li, Shirui PanNeurIPS 2022 · OpenReview

TL;DR

Neural Temporal Walks (NeurTWs) is a novel framework for learning representations on continuous-time dynamic graphs. By explicitly modeling structural motifs and their evolution over time using spatiotemporal-biased random walks and Neural Ordinary Differential Equations (NODEs), NeurTWs achieves state-of-the-art performance, outperforming existing methods by up to 5% on complex real-world datasets.

The Challenge: Modeling Continuous-Time Dynamic Graphs

Many real-world systems, such as social networks, financial transaction logs, and e-commerce platforms, are best represented as Continuous-Time Dynamic Graphs (CTDGs). Unlike static graphs, these systems constantly evolve, with events occurring at irregular intervals.

Existing research faces two main hurdles when attempting to model these networks:

  1. Ignoring Motifs: Most models fail to explicitly capture "motifs"—recurring structural patterns like triadic closure. For example, if person A interacts with person B, and B interacts with C, A and C are highly likely to connect in the future. Manually extracting these is difficult, but ignoring them leaves valuable predictive signals on the table.
  2. Implicit Time Modeling: Current methods often treat time as just another static feature (via time encoding) rather than a continuous dimension. This makes it difficult to capture the underlying dynamics of events that happen at highly irregular timestamps.
Example of a dynamic law (motif) where a common neighbor leads to a future connection.

The NeurTWs Approach

To address these limitations, the authors introduce Neural Temporal Walks (NeurTWs). The framework treats motifs as the "atoms" of network dynamics and relies on three core components to extract and learn from them:

1. Spatiotemporal-Biased Random Walks

To find the most informative motifs automatically, the model performs random walks biased by three factors:

  • Recency: Preferring newer events.
  • Topology: Preferring highly connected "hub" nodes.
  • Tree Traversal: Balancing exploration and exploitation to capture meaningful structural paths.

2. Walk Anonymization

To ensure the model is inductive (meaning it can generalize to unseen nodes during inference), it replaces specific node IDs with "relative identities" based on their position in the walk. This forces the model to learn structural patterns rather than memorizing specific nodes.

The process of extracting motifs via biased walks and anonymizing them to maintain inductiveness.

3. Neural Temporal Walk Encoding

This is the core innovation of the paper. It uses a two-step process to model the extracted walks:

  • Continuous Evolution: A Neural Ordinary Differential Equation (NODE) models how the latent state of a node changes during the "empty" time intervals between interactions. This treats time as a continuous dimension of evolution.
  • Instantaneous Activation: An RNN-like cell updates the state exactly when a new interaction occurs.

To enrich the learning process, NeurTWs employs a contrastive optimization strategy. Instead of simple binary classification (predicting if an edge exists or not), the model maximizes the mutual information between interacting nodes while pushing non-interacting nodes apart in the embedding space.

Key Results

The model was evaluated on six diverse real-world datasets, including social networks (CollegeMsg, Enron), e-commerce (Taobao), education (MOOC), and bipartite interaction networks (Wikipedia, Reddit).

NeurTWs demonstrated overwhelming superiority across all benchmarks:

  • Link Prediction: It surpassed the strongest baselines (like CAWs and TGN) by approximately 3% in transductive settings and 5% in inductive settings.
  • Sparse Graphs: The performance gain was particularly notable on sparse datasets like CollegeMsg, where it achieved an AUC > 0.95 while all other baselines remained below 0.9.
  • Ablation Success: Removing the Neural ODE component led to a significant drop in performance, proving that explicit, continuous temporal modeling is vital to the model's success.

Limitations and Future Work

While highly effective, the authors identify two primary areas for future improvement:

  1. Time Normalization: Very large time gaps between events can still be challenging to model stably. While the authors use a logarithmic transformation trick, a more sophisticated normalization method could improve robustness.
  2. Computational Efficiency: Calculating spatial-biased probabilities for every neighbor is computationally expensive. Future work will focus on finding more efficient implementations to scale the framework to even larger, industry-scale graphs.

Summary updated

Abstract

Continuous-time dynamic graphs naturally abstract many real-world systems, such as social and transactional networks. While the research on continuous-time dynamic graph representation learning has made significant advances recently, neither graph topological properties nor temporal dependencies have been well-considered and explicitly modeled in capturing dynamic patterns. In this paper, we introduce a new approach, Neural Temporal Walks (NeurTWs), for representation learning on continuous-time dynamic graphs. By considering not only time constraints but also structural and tree traversal properties, our method conducts spatiotemporal-biased random walks to retrieve a set of representative motifs, enabling temporal nodes to be characterized effectively. With a component based on neural ordinary differential equations, the extracted motifs allow for irregularly-sampled temporal nodes to be embedded explicitly over multiple different interaction time intervals, enabling the effective capture of the underlying spatiotemporal dynamics. To enrich supervision signals, we further design a harder contrastive pretext task for model optimization. Our method demonstrates overwhelming superiority under both transductive and inductive settings on six real-world datasets.
BibTeX
@inproceedings{jin2022neural,
  author = {Ming Jin and Yuan-Fang Li and Shirui Pan},
  title = {{Neural Temporal Walks: Motif-Aware Representation Learning on Continuous-Time Dynamic Graphs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=NqbktPUkZf7},
}
Figure