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:
- 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.
- 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.
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.
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:
- 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.
- 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