PRES: Toward Scalable Memory-Based Dynamic Graph Neural Networks

Junwei Su, Difan Zou, Chuan Wu

Abstract

Memory-based Dynamic Graph Neural Networks (MDGNNs) leverage memory modules to capture long-term temporal dependencies in evolving graphs. However, training these models at scale is hindered by "temporal discontinuity"—a phenomenon where parallel batch processing ignores chronological dependencies within a batch. This paper introduces PRES, an iterative prediction-correction scheme with a memory coherence learning objective. PRES enables training with significantly larger temporal batches, achieving up to a 3.4x speedup without sacrificing generalization performance.

Introduction: The Scalability Bottleneck

Dynamic graphs, representing time-evolving relationships in social media or finance, are increasingly modeled using MDGNNs. These models maintain a persistent "memory" state for each node, updated as new events occur. While effective, they are notoriously difficult to scale.

The primary obstacle is temporal discontinuity. In a dynamic graph, events must ideally be processed sequentially to maintain chronological integrity. However, modern GPU training relies on large-scale parallelism via batching. When a batch contains multiple events involving the same node, parallel processing neglects their internal order, leading to "blurred" memory states. To maintain accuracy, practitioners often resort to small batch sizes, which underutilize hardware and slow down training.

MDGNN training workflow and the illustration of temporal discontinuity.

Methodology: The PRES Framework

To address this, we propose PRES (PREdict-to-Smooth), which combines two key innovations:

1. Iterative Prediction-Correction

Inspired by control theory, PRES treats the memory state resulting from temporal discontinuity as a noisy measurement. It employs a Gaussian Mixture Model (GMM) to predict the expected memory change based on historical patterns. A correction step then fuses this prediction with the actual batch update, yielding a more accurate state estimate.

2. Memory Coherence Smoothing

We introduce the concept of Memory Coherence, measuring the alignment between gradients of "fresh" memory and "past" memory. By adding a coherence regularization term to the loss function, PRES encourages the model to produce updates that are robust to the noise introduced by large batches.

Experimental Results

We evaluated PRES on five large-scale benchmarks (WIKI, REDDIT, MOOC, LASTFM, GDELT) using three state-of-the-art architectures: TGN, JODIE, and APAN.

Performance comparison between standard MDGNNs and PRES-enhanced versions across different batch sizes.

The results demonstrate that PRES allows for up to 4x larger temporal batches, translating to a 3.4x training speedup. Crucially, as shown in the performance plots, PRES maintains or improves Average Precision (AP) even as batch sizes increase, whereas standard models typically see a performance drop. Furthermore, PRES significantly improves hardware efficiency by allowing models to utilize more GPU memory.

Conclusion and Future Work

PRES provides a rigorous foundation for scaling MDGNNs by mitigating temporal discontinuity. While currently focused on the MDGNN family and requiring some memory overhead for GMM tracking, it opens new avenues for applying control-theory principles to time-series graph learning. Future work will explore extending these insights to memory-less dynamic GNNs and other sequential data domains.

Summary updated

Abstract

Memory-based Dynamic Graph Neural Networks (MDGNNs) are a family of dynamic graph neural networks that leverage a memory module to extract, distill, and memorize long-term temporal dependencies, leading to superior performance compared to memory-less counterparts. However, training MDGNNs faces the challenge of handling entangled temporal and structural dependencies, requiring sequential and chronological processing of data sequences to capture accurate temporal patterns. During the batch training, the temporal data points within the same batch will be processed in parallel, while their temporal dependencies are neglected. This issue is referred to as temporal discontinuity and restricts the effective temporal batch size, limiting data parallelism and reducing MDGNNs' flexibility in industrial applications. This paper studies the efficient training of MDGNNs at scale, focusing on the temporal discontinuity in training MDGNNs with large temporal batch sizes. We first conduct a theoretical study on the impact of temporal batch size on the convergence of MDGNN training. Based on the analysis, we propose PRES, an iterative prediction-correction scheme combined with a memory coherence learning objective to mitigate the effect of temporal discontinuity, enabling MDGNNs to be trained with significantly larger temporal batches without sacrificing generalization performance. Experimental results demonstrate that our approach enables up to a 4x larger temporal batch (3.4x speed-up) during MDGNN training.
BibTeX
@inproceedings{su2024pres,
  author = {Junwei Su and Difan Zou and Chuan Wu},
  title = {{PRES: Toward Scalable Memory-Based Dynamic Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=gjXor87Xfy},
}
Figure