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:
- Information Loss: Missing the specific gradient information that comes from sequential updates.
- 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.
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.
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