A Batch-Insensitive Dynamic GNN Approach to Address Temporal Discontinuity in Graph Streams

Yang Zhou, Xiaoning Ren

Abstract

In dynamic graphs, preserving temporal continuity is critical. However, Memory-based Dynamic Graph Neural Networks (MDGNNs) trained with large batches often disrupt event sequences, leading to temporal information loss. This discontinuity not only deteriorates temporal modeling but also hinders optimization by increasing the difficulty of parameter convergence. Our theoretical study quantifies this through a Lipschitz upper bound, showing that large batch sizes enlarge the parameter search space. In response, we propose BADGNN, a novel batch-agnostic framework consisting of two core components: (1) Temporal Lipschitz Regularization (TLR) to control parameter search space expansion, and (2) Adaptive Attention Adjustment (A3) to alleviate attention distortion induced by both regularization and batching. Empirical results on three benchmark datasets show that BADGNN maintains strong performance while enabling significantly larger batch sizes and faster training compared to TGN.

Introduction

Training Dynamic Graph Neural Networks (DGNNs) is a balancing act. To capture how a network evolves over time, models ideally process events sequentially. However, for the sake of computational efficiency and hardware utilization, large-batch training is preferred. This creates a "temporal discontinuity" problem: when you process a bunch of events simultaneously, the model loses the strict chronological sequence, leading to a significant drop in accuracy.

A new approach, BADGNN (Batch-Agnostic Dynamic GNN), introduces a framework designed to let researchers use massive batch sizes without sacrificing the temporal "soul" of their models. By addressing performance degradation through theoretical Lipschitz analysis and attention adjustment, it enables training with up to 11x larger batch sizes and 2x faster speeds compared to standard Temporal Graph Networks (TGNs).

The Problem: Temporal Discontinuity and Search Space Expansion

In dynamic graphs (like social networks or transaction logs), the order of events matters. Memory-based DGNNs maintain a "memory" state for each node. When we train with large batches, multiple events involving the same nodes might be processed in parallel. This leads to temporal discontinuity, where the model updates its state based on a "blurry" view of time rather than a crisp sequence.

The authors identify two main issues:

  1. Information Loss: Missing the specific gradient information that comes from sequential updates.
  2. Search Space Expansion: Through mathematical analysis, the authors prove that larger batch sizes mathematically "loosen" the model's Lipschitz bound. This effectively expands the space the model has to search to find optimal parameters, making convergence much harder and more volatile.
Conceptual comparison of standard DGNN training challenges versus BADGNN's optimization constraints and stable convergence.

Methods: The BADGNN Framework

BADGNN introduces two main components to counteract the side effects of large batches:

  • Temporal Lipschitz Regularization (TLR): Based on their theoretical derivation, the authors add a regularization term to the loss function. This term encourages orthogonality between current node representations and their neighbors. Geometrically, this "shrinks" the volume of the parameter search space, preventing the model from drifting into unstable configurations during large-batch training.
  • Adaptive Attention Adjustment (A3): Regularization and large batches can make attention weights "diffuse" or blurry. A3 acts as a corrective lens, reshaping the attention distribution using a non-uniform scaling transformation based on sequence length and feature dimensions. This forces the model to focus on the most relevant temporal features, even when the underlying batching process is messy.

Key Results and Empirical Validation

The model was evaluated on three standard dynamic graph benchmarks: Wikipedia (user-page edits), Reddit (social posts), and MOOC (student interactions). The results suggest that speed and accuracy are no longer a zero-sum game.

  • Batch Size Scaling: On the Wikipedia dataset, BADGNN maintained high performance with a batch size of 3500, which is 11.6x larger than the standard TGN setup (batch size 300).
  • Training Speedup: Thanks to these larger batches, BADGNN achieved a 2x speedup in training time on Wikipedia and a 1.4x speedup on MOOC.
  • Performance Stability: While standard TGN performance drops sharply as batch size increases, BADGNN's Average Precision (AP) remains remarkably stable across a wide range of batch sizes.
Performance stability of BADGNN (TGN+RE+AD) compared to standard TGN across increasing batch sizes, showing significantly better retention of accuracy.

Conclusion and Future Work

BADGNN represents a significant step forward for making dynamic graph learning practical for large-scale, real-world applications where training speed is just as important as accuracy. By linking batch size to the Lipschitz constant, the authors provide a robust theoretical foundation for stabilizing optimization.

While BADGNN provides a robust framework, future work may explore how these Lipschitz constraints behave in extremely sparse graphs where node interactions are rare, or how the principles can be integrated into other base architectures beyond TGN.

Summary updated

Abstract

In dynamic graphs, preserving temporal continuity is critical. However, Memory-based Dynamic Graph Neural Networks (MDGNNs) trained with large batches often disrupt event sequences, leading to temporal information loss. This discontinuity not only deteriorates temporal modeling but also hinders optimization by increasing the difficulty of parameter convergence. Our theoretical study quantifies this through a Lipschitz upper bound, showing that large batch sizes enlarge the parameter search space. In response, we propose BADGNN, a novel batch-agnostic framework consisting of two core components: (1) Temporal Lipschitz Regularization (TLR) to control parameter search space expansion, and (2) Adaptive Attention Adjustment (A3) to alleviate attention distortion induced by both regularization and batching. Empirical results on three benchmark datasets show that BADGNN maintains strong performance while enabling significantly larger batch sizes and faster training compared to TGN. Our code is available at Code: https://anonymous.4open.science/r/TGN_Lipichitz-C033/.
BibTeX
@misc{zhou2025batch,
  author = {Yang Zhou and Xiaoning Ren},
  title = {{A Batch-Insensitive Dynamic GNN Approach to Address Temporal Discontinuity in Graph Streams}},
  year = {2025},
  eprint = {2506.19282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.19282},
}
Figure