IncAgg: Efficient Memory-Enhanced Graph Learning via Incremental Aggregation

Scaling Graph Neural Network (GNN) training to large graphs commonly relies on mini-batch sampling, but incomplete neighborhoods can degrade approximation quality and training stability. Memory-enhanced methods mitigate this issue by reusing historical node embeddings to approximate full-neighborhood aggregation; however, they reconstruct pseudo full-neighborhood messages inside every training iteration, repeatedly fetching out-of-batch memories and aggregating over large neighborhoods. In this work, we identify this under-examined inner-loop bottleneck and propose IncAgg, an efficient memory-enhanced GNN training framework based on incremental aggregation. IncAgg periodically pre-aggregates historical embeddings into a global memory baseline, and during mini-batch training propagates only the current in-batch residual before fusing it with the stored global context. This design preserves historical full-neighborhood information at a configurable refresh frequency while avoiding per-iteration out-of-batch memory fetching and aggregation, without modifying the underlying GNN architecture. We provide theoretical analyses showing that IncAgg reduces gradient-carrying aggregation and memory-access costs while retaining the residual-based stability principle of memory-enhanced estimators. Extensive experiments on four large-scale benchmarks and four representative GNN backbones show that IncAgg matches or improves the accuracy of strong memory-enhanced baselines while achieving substantial training acceleration, with up to $18.6\times$ speedup in individual settings and up to $13.8\times$ geometric-mean speedup on large graphs.