PRES: Toward Scalable Memory-Based Dynamic Graph Neural Networks

Junwei Su, Difan Zou, Chuan Wu

TL;DR

Training Memory-based Dynamic Graph Neural Networks (MDGNNs) has long been bottlenecked by "temporal discontinuity"—the loss of chronological order when processing events in parallel batches. This paper introduces PRES (PREdict-to-Smooth), a framework that uses control-theory-inspired filtering and a novel "memory coherence" loss to allow for 4× larger batch sizes and up to a 3.4× training speedup without sacrificing accuracy.

What Problem Does This Paper Address?

Dynamic graphs—networks where nodes and edges evolve over time, such as social media interactions or financial transactions—are everywhere. MDGNNs are the state-of-the-art for modeling these networks because they maintain a "memory" for each node, effectively acting as a compressed history of its past interactions.

The catch? Training them is a sequential nightmare. To capture accurate temporal patterns, events should ideally be processed one by one in chronological order. However, to leverage modern GPUs, we process events in parallel "temporal batches." If a node appears multiple times within the same batch, the parallel update neglects the dependencies between those occurrences. This issue is known as temporal discontinuity.

MDGNN training and the challenge of temporal discontinuity.

To avoid this, researchers typically use very small batch sizes, which leads to poor hardware utilization and agonizingly slow training times. The authors set out to break this "batch size bottleneck" to make MDGNNs viable for large-scale industrial applications.

Methods

The authors propose PRES, which attacks the problem from two angles:

  1. Iterative Prediction-Correction: Drawing inspiration from control theory (similar to Kalman filters), the authors treat the memory state produced by a large, discontinuous batch as a "noisy measurement."
    • Prediction: They use a Gaussian Mixture Model (GMM) to predict what the node's memory should look like based on its previous state and the time elapsed.
  2. Correction: They then "fuse" this prediction with the actual batch update using a learnable weight, smoothing out the noise introduced by parallelization.
  3. Memory Coherence Smoothing: The authors introduce a new regularization term in the loss function. This objective encourages "memory coherence"—ensuring that the gradient directions of the "fresh" memory (processed sequentially) and the "stale" memory (from the parallel batch) are well-aligned. Mathematically, this steers the model toward parameters that are naturally more robust to the effects of pending events within a batch.

Datasets

The researchers evaluated PRES on five widely used dynamic graph benchmarks:

  • REDDIT & WIKI: User-page interactions with dynamic labels (e.g., user bans).
  • MOOC: Student actions in online courses.
  • LASTFM: Music listening histories (non-attributed).
  • GDELT: A massive dataset of global news events and social interactions.

Key Insights and Ideas

  • The Small Batch Paradox: Conventionally, we assume smaller batches are "better" for temporal data because they are closer to sequential processing. However, the authors provide a theoretical proof showing that very small temporal batches actually introduce significant variance into the gradients due to sampling noise. Larger batches are more robust, provided you can handle the discontinuity.
  • Bridging Control Theory and GNNs: The realization that parallel batching is essentially a "noise injection" process allows the use of classical filtering techniques to stabilize training.
  • Memory Coherence as a Metric: The paper formally defines "Memory Coherence" as the cosine similarity between gradients with and without pending events. This gives us a concrete way to measure how much temporal information we are losing during batching.

Key Results

The experimental results across three base models (TGN, JODIE, and APAN) demonstrate significant improvements in scalability and speed:

Performance comparison across different batch sizes showing PRES maintaining high accuracy.
  • Scalability: PRES enables training with 4× larger temporal batches than standard methods.
  • Speed: This increased parallelism translates to a 3.4× speedup in training time (specifically for TGN on the Reddit dataset).
  • Performance: Despite the much larger batches, the Average Precision (AP) remains nearly identical to (and sometimes better than) the slow, small-batch baselines. For instance, on the Reddit dataset, TGN-PRES achieved 98.0% AP compared to the baseline's 98.4%, but did so over three times faster.
  • Hardware Efficiency: The authors show that standard MDGNN training often leaves significant GPU memory underutilized; PRES allows engineers to "fill the pipe" more effectively.

Limitations and Future Work

While PRES significantly improves training efficiency, the authors note a few areas for further exploration:

  • Model Specificity: The analysis is centered on the MDGNN family. While these are highly effective, the dynamics of other time-series models might require different "coherence" definitions.
  • Complexity: While the computational overhead of PRES is linear, the storage of trackers for the GMM scales with the number of vertices. For truly massive graphs with billions of nodes, the authors suggest using an "anchor set" of nodes to reduce memory overhead.
  • Future Directions: An intriguing next step would be extending this "prediction-correction" logic to the realm of pure time-series analysis outside of graph structures.

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 4 $\times$ larger temporal batch (3.4$\times$ 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