Robust Training of Temporal GNNs using Nearest Neighbours based Hard Negatives

Shubham Gupta, Srikanta Bedathur

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.

t-SNE visualization of embedding space showing that random nodes often appear closer to the source than the actual target.

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.

Impact of the Top-K parameter on MRR and Recall@1 for Wikipedia and Reddit datasets.

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

Abstract

Temporal graph neural networks Tgnn have exhibited state-of-art performance in future-link prediction tasks. Training of these TGNNs is enumerated by uniform random sampling based unsupervised loss. 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 modified unsupervised learning of Tgnn, by replacing the uniform negative sampling with importance-based negative sampling. We theoretically motivate and define the dynamically computed distribution for a sampling of negative examples. Finally, using empirical evaluations over three real-world datasets, we show that Tgnn trained using loss based on proposed negative sampling provides consistent superior performance.
BibTeX
@inproceedings{gupta2024robust,
  author = {Shubham Gupta and Srikanta Bedathur},
  title = {{Robust Training of Temporal GNNs using Nearest Neighbours based Hard Negatives}},
  booktitle = {COMAD/CODS},
  year = {2024},
  doi = {10.1145/3632410.3632464},
}

Loading related content...

Figure