Abstract
Temporal graph neural networks (TGNNs) have exhibited state-of-the-art performance in future-link prediction tasks. Training of these TGNNs is typically driven by an unsupervised loss based on uniform random sampling. During training, in the context of a positive example, the loss is computed over uninformative negatives, which introduces redundancy and sub-optimal performance. In this paper, we propose a modified unsupervised learning approach for TGNNs, replacing uniform negative sampling with importance-based negative sampling. We theoretically motivate and define a dynamically computed distribution for sampling negative examples. Finally, using empirical evaluations over three real-world datasets, we show that TGNNs trained using loss based on the proposed negative sampling provide consistently superior performance.
Introduction
Temporal Graph Neural Networks (TGNNs) are essential for predicting dynamic interactions in evolving graphs, such as user-item interactions or social network activity. To train these models without explicit labels, researchers rely on unsupervised loss functions that contrast positive interactions with negative ones.
The standard approach uses uniform random sampling to select negative nodes. However, this often results in "easy" negatives that provide little signal for the model to learn precise boundaries. As shown in Figure 1, t-SNE visualizations reveal that random nodes are frequently closer to a source node in the embedding space than the actual target node is. This proximity makes it difficult for the model to achieve high precision in recommendation and prediction tasks.
Methodology
To address the limitations of random sampling, we propose Importance-based Negative Sampling. Our approach is grounded in the theoretical finding that models converge more effectively when negative samples are chosen in proportion to their gradient norm—focusing on examples where the model is "most wrong."
Since computing exact gradients for all nodes is computationally prohibitive, we use the dot product (or cosine similarity) between node embeddings as a proxy for loss. Our algorithm identifies the top-K nearest neighbors of a source node in the current latent space and samples negatives from this "hard" pool. To maintain computational efficiency, we introduce two hyper-parameters:
- Periodicity ($P$): The frequency of refreshing global node embeddings.
- Frequency ($F$): The frequency of recomputing the top-K nearest neighbor lists.
Experimental Evaluation
We evaluated our method on three real-world temporal datasets: Wikipedia Edits, Reddit Posts, and Twitter Retweets. These datasets capture diverse interaction patterns and include rich node and edge features.
Our results indicate that the proposed method consistently outperforms standard TGNN architectures like TGN and TGAT across all primary metrics, including Mean Reciprocal Rank (MRR) and Recall@K. For instance, on the Wikipedia dataset, the MRR increased from 0.615 with standard TGN to 0.733 using our hybrid hard negative approach.
Results and Discussion
A key insight from our experiments is that "hardness" in temporal graphs is dynamic. Static heuristics, such as selecting nodes with many common neighbors, actually performed worse than random sampling. This suggests that effective hard negatives must be derived from the model's own evolving embedding space.
The best performance was typically achieved using a hybrid strategy (TGN + UN + HN), which combines one uniform negative for global context with one hard negative for local refinement. Furthermore, our method proved robust enough to outperform PINT, a more complex state-of-the-art architecture, demonstrating that optimizing the training strategy can be more impactful than increasing model complexity.
As illustrated in Figure 6, the performance of the model is sensitive to the choice of $K$. The optimal size of the neighbor pool varies by dataset, with $K=5$ performing best for Wikipedia and $K=20$ for Reddit.
Conclusion
This paper demonstrates that importance-based negative sampling significantly enhances the robustness and accuracy of TGNNs. While the nearest neighbor search introduces some training overhead, optimizations in refresh frequency ($F$) allow for substantial performance gains with manageable computational costs. Importantly, this method has no impact on inference speed. Future work will explore the use of approximate nearest neighbor libraries like Faiss to scale this approach to even larger graphs and investigate its impact on the "cold start" problem for new nodes.
Summary updated