ReInc: Scaling Training of Dynamic Graph Neural Networks

1 Introduction

• Existing DGNN optimizations can rely on small graphs or partial dynamicity, while distributed training still faces communication overhead and architecture-specific partitioning trade-offs.Breaking structural or temporal dependencies can limit generalizability and incur communication overhead.Source: §1 · pp. 1–2
• REINC reuses intermediate computations and incrementally computes aggregations across snapshots, supported by a two-level cache and a DGNN-aligned caching policy.These optimizations target redundant work while avoiding assumptions about the underlying dynamic graph.Source: §1 · p. 2
• REINC places consecutive snapshot blocks across machines to preserve structural and within-sequence temporal dependencies while eliminating remote-feature access and intermediate-result redistribution.The placement also supports workload balance when combined with reuse and caching.Source: §1 · p. 2
• REINC also supports mini-batch DGNN training with locally accessible sequence data and sequence-first iteration to improve cache efficiency.Its API supports new stacked or integrated architectures with the optimizations handled under the hood.Source: §1 · p. 2
• Up to an order of magnitude performance improvement over best-performing specialized frameworks is reported for stacked and integrated DGNNs.The reported experiments cover various DGNN architectures and workloads.Source: §1 · p. 2

2.1 Dynamic Graph Neural Networks

• DGNNs combine GNN-based structural encoding with temporal models such as RNNs; they may stack these operations or integrate GNNs into GraphRNN cells.Sliding windows create overlapping input sequences, each processed as an independent training sample with gradients flowing backward across its timesteps.Source: §2.1 · p. 3

2.2 DGNN Frameworks

• Existing systems use reuse or parallelization strategies with constraints: some target integrated models or small graphs, and others assume static features or structure.Node partitioning can require remote feature access; sequence partitioning can require intermediate-output redistribution and poorly supports integrated DGNNs.Source: §2.2 · pp. 3–4

2.3 Motivation and Challenges

• Existing DGNN systems optimize for selected model groups and small graphs, leaving scalable training across diverse architectures unresolved.REINC’s consecutive-block placement preserves structural dependencies and within-sequence temporal dependencies while eliminating remote feature access and intermediate-state redistribution.Source: §2.2 · p. 4, §2.3 · pp. 4–5
• Scaling DGNN training requires addressing redundant computation, limited GPU memory, and support for both stacked and integrated models with changing graph structure and features.Sliding-window overlap and repeated aggregation add redundant work, while GPUs cannot process full snapshots of large graphs.Source: §2.3 · p. 5

3 DGNN Training with REINC

• REINC combines reuse optimizations, DGNN-aware caching, and a novel distributed training scheme to address DGNN training challenges.The three components are discussed in §§3.1–3.4.Source: §3 · p. 5
• Reuse optimizations and DGNN-aware caching form two of REINC’s three proposed components.Source: §3 · p. 5
• A novel distributed training scheme completes REINC’s proposed approach.Source: §3 · p. 5

3.1 Three Reuse Opportunities

• Integrated DGNNs can reuse feature and hidden-state aggregations across gates, while overlapping sequences enable reuse for repeated snapshots.The gate-level opportunity applies to integrated DGNNs; sequence overlap is a separate reuse opportunity.Source: §3.1 · p. 5
• Teacher forcing lets the decoder’s ground-truth snapshot aggregations be reused when those snapshots later enter encoder input sequences.Source: §3.1 · p. 5
• Reuse across sequences and between encoder and decoder applies to both stacked and integrated DGNNs, whereas gate-level reuse is specific to integrated DGNNs.Sequence and encoder–decoder reuse applies only to inputs in the first layer; that layer is especially computationally intensive because input features are typically high-dimensional.Source: §3.1 · p. 5

3.2 Incremental Aggregation

• Because consecutive snapshots often share large common parts, REINC reuses prior aggregation results instead of recomputing each snapshot from scratch.The paper notes that some DGNNs smooth snapshot differences, further reducing change ratios.Source: §3.2 · p. 5
• REINC represents edge deletions and insertions as two delta graphs and uses them to update aggregation results from the previous snapshot.Feature changes are represented as deletions from out-neighbors using previous features and insertions using current features.Source: §3.2 · p. 6
• When the delta-graph change ratio exceeds a user-defined threshold, REINC falls back to aggregation from scratch.Source: §3.2 · p. 6
• REINC focuses on edge changes because existing DGNNs assume constant matrix sizes within a sequence, though the design can be extended to node additions and deletions.Source: §3.2 · p. 6
• For max() and min(), edge deletions cannot be incrementally computed without storing old contributions, so REINC falls back to recomputation when a deleted edge contributed.REINC can store contributing edge IDs to detect this case; caching all contribution values is an optional, more memory-intensive alternative.Source: §3.2 · p. 6
• For weighted aggregations with learnable weights, REINC updates incrementally between backward passes but recomputes after each weight update.Built-in aggregation functions include sum(), mean(), max(), and min().Source: §3.2 · p. 6

3.3 Two-level Cache Store

• REINC pairs a global cache accessible across layers with a local cache designed for each layer, using a DGNN-aware policy rather than ordinary LFU or LRU eviction.Source: §3.3 · p. 6

3.3.1 Global Cache

• The global cache stores input-feature aggregations for reuse across gates, sequences, encoder and decoder, and incremental aggregation.With teacher forcing, a snapshot aggregation can be reused from decoder input when that snapshot later appears in encoder input.Source: §3.3.1 · p. 6

3.3.2 Local Cache

• Each GraphRNN layer’s local cache stores aggregations of intermediate hidden vectors and reuses them across gates.The cached inputs include hidden vectors from the previous timestep and previous layer.Source: §3.3.2 · p. 6

3.3.3 Eviction Policy

• REINC scores aggregations using future access count, imminence, and size, assigning equal weights to those factors.The policy exploits predictable future DGNN accesses rather than relying only on access history.Source: §3.3.3 · p. 7
• When an aggregation’s future access count reaches zero, REINC marks it expired and evicts it to reduce caching memory overhead.Source: §3.3.3 · p. 7

3.4.1 Graph Placement

• Consecutive snapshot blocks are assigned across machines because time dependencies occur within sequences, not between them; placement balances sequences and batches across machines.When a sequence spans machines, REINC either overlaps complete sequences if memory permits or retrieves remote snapshots as needed; it remains an in-memory system and defers out-of-core graphs.Source: §3.4.1 · p. 8

3.4.2 DGNN Execution

• For each node minibatch, REINC builds sequence computational graphs, sampling neighborhoods at the first snapshot and extracting only relevant graph changes at later snapshots.Each sample is a sequence of nodes; subsequent feature extraction supplies the minibatch inputs.Source: §3.4.2 · p. 8

3.4 Distributed Training

• Each machine executes its sample independently: GNN work requires no network communication, RNN computation stays local, and backward passes synchronize gradients at layer boundaries.REINC also uses model checkpointing to recover from failures, but does not focus on failure-recovery mechanisms.Source: §3.4 · p. 7, §3.4.2 · p. 8

3.4.3 Rethinking Mini-batch Training

• Sequence-first minibatching processes all sequences for the current node minibatch before sampling another, reducing cached aggregation memory and increasing cache hits.This replaces node-first iteration, which required caching intermediate results for all nodes in the current sequence and produced memory overhead and a low cache hit rate.Source: §3.4.3 · p. 8

3.5 REINC API

• Developers define message generation with msg_udf and neighborhood aggregation with reduce_udf, which sums the neighborhood representations.The listing uses GCRN-M2 as an encoder-decoder example.Source: §3.5 · p. 9
• The forward function passes the delta graph to msg_pass for internal incremental aggregation, then sends the intermediate output to a fully connected update layer.The example applies a linear layer followed by ReLU.Source: §3.5 · p. 9
• The integrate function combines a GCN with an LSTM to create a DGNN layer, while stack_seq_model can assemble layers into an encoder-decoder architecture.Source: §3.5 · p. 9

4 Implementation

• The prototype uses DGL for neighborhood sampling and aggregation and PyTorch as the neural-network execution backend.The authors state that REINC’s techniques are extensible to static GNN systems because they are agnostic to the specific GNN execution implementation.Source: §4 · p. 9
• Modified DGL message-passing primitives use delta aggregations for current-timestep aggregation, supporting incremental processing with memory and computational efficiency.The implementation also adds a two-level cache store with the proposed policies for incremental processing and reuse.Source: §4 · p. 9
• REINC replaces DGL’s static-graph DataLoader with SeqDataLoader, which iterates over snapshots and creates sequence samples, transferring only data needed for incremental computation under delta mode.The implementation also uses snapshot placement and PyTorch DistributedDataParallel to synchronize and update model weights.Source: §4 · p. 9

5.1 Overall Performance

• In comparisons against two state-of-the-art DGNN systems, REINC significantly outperforms DynaGraph by 2.9-12.8× and ESDGNN by 2.8-17.7× for both stacked and integrated DGNNs over all evaluated graphs.Source: §5.1 · p. 10

5.2 Impact of Sampling

• Without sampling, REINC maintains its benefits while baselines struggle on the largest graph, OGB-Papers; the effect of removing sampling is greater on denser OGB-Products.METR-LA-LARGE averages 8 neighbors per node, compared with 25 for OGB-Products.Source: §5.2 · pp. 10–11, Figure 8 · p. 11

5.3 Impact of Reusable Computation

• Integrated DGNNs show greater speedups than stacked models, with reuse across gates delivering the greatest speedup among integrated-model optimizations.Individual optimization speedups overlap and are not additive or multiplicative.Source: §5.3 · p. 11

5.4 Cache Store Evaluation

• The cache store reduces GPU memory use without added memory overhead by reusing aggregations and automatically evicting expired ones.Memory savings are greater for integrated DGNNs because they offer more reuse opportunities.Source: §5.4 · p. 11, Figure 10 · p. 11
• With a cache-to-data size of 10%, REINC achieves a 52% cache hit rate while LRU achieves 0%; REINC reaches 100% at 60%.The DGNN-aware policy also achieves higher cache hit rate and throughput than LRU and LFU under limited cache memory.Source: §5.4 · p. 11, Figure 11 · p. 12
• Seq-first mini-batch training improves cache hit rate and throughput over node-first training as cache size grows, by reusing aggregations for current nodes across sequences.The two strategies have similar hit rates at cache-to-data sizes of 10% to 20%.Source: Figure 12 · p. 12, §5.4 · p. 12

5.5 Scaling Characteristics

• REINC scales near-linearly with larger feature and hidden dimensions and machine counts, maintains benefits as sequence length grows, and takes longer as change ratios rise.The change ratio affects incremental aggregation; real-world graphs are described as changing slowly relative to their size.Source: §5.5 · p. 12, Figure 13 · p. 12

5.6 Correctness

• On METR-LA-LARGE, REINC achieves the same test MAE as DynaGraph and ESDGNN, with speedups of 2.9× and 8.1×, respectively.Convergence curves on the other datasets align consistently with those of the baselines.Source: §5.6 · pp. 12–13, Figure 14 · p. 13

• Dynamic graph processing systems support graph algorithms and mining, but not the embedding generation required by GNNs.Source: §6 · p. 13
• Static GNN systems scale training on large graphs through single-machine and distributed approaches, including GPU-based systems and graph partitioning.Source: §6 · p. 13
• The described static GNN systems do not support efficient dynamic GNN training.Source: §6 · p. 13

• The paper identifies redundant computation and high communication overhead as obstacles to DGNN systems scaling well.Source: §7 · p. 13
• REINC is presented as a system for scalable DGNN training.Source: §7 · p. 13
• Extensive experiments show that REINC significantly outperforms the state of the art.Source: §7 · p. 13