Eliminating Redundant Computation in Graph Neural Networks

This direction is split into other directions: neighborhood aggregation redundancy. Its last version stays readable and citable here.

Version 1 of 1105 papers135 conceptsfrozen 2026-10-04

Graph Neural Networks (GNNs) are notoriously difficult to scale, not just because of the sheer size of modern datasets, but because of a fundamental structural property: overlap. In a typical social or biological network, nodes are not isolated; they share neighbors, form dense clusters, and participate in repeated motifs like triangles.

When a standard GNN processes these graphs, it often treats every node's neighborhood as an independent sub-problem. This leads to a massive amount of redundant work. If two nodes share 90% of their neighbors, a naive implementation will fetch, transform, and aggregate those same neighbors twice. As Meng Wu and colleagues note in A Comprehensive Survey on GNN Characterization, identifying and eliminating these redundant calculations can reduce the total aggregation workload by over 80%.

The Neighborhood Explosion and Execution Redundancy

The most visible symptom of this redundancy is the "Neighborhood Explosion Phenomenon." As Muhammed Fatih Balin and Ümit V. Çatalyürek explain in Layer-Neighbor Sampling --- Defusing Neighborhood Explosion in GNNs, recursive sampling causes the number of nodes to grow exponentially with depth. Because traditional mini-batching treats samples as independent, the system repeatedly fetches and processes the same vertex embeddings across different batches.

This redundancy isn't just a software inefficiency; it's a hardware bottleneck. Hengrui Zhang and Guohao Dai argue in Understanding GNN Computational Graph that redundant computation is coupled with inefficient memory IO. When neural operations are applied to every edge, the same vertex data is processed repeatedly because multiple edges share the same source or destination.

Layer-Wise Materialization and Reuse

To solve this, researchers have moved away from "node-wise" execution toward "layer-wise" or "redundancy-aware" materialization.

In DGI: Easy and Efficient Inference for GNNs, Peiqi Yin and James Cheng propose a system that translates standard code into a format where intermediate node embeddings are calculated once per layer and then reused. This eliminates the need to recalculate the same embeddings for overlapping neighborhoods, achieving speedups of up to 1,000x for inference.

A similar logic applies to heterogeneous graphs. Kun Wu and Israt Nisa introduced Hector (Hector: An Efficient Programming and Compilation Framework...), which uses "redundancy-aware materialization." By identifying unique source-node and edge-type combinations, the framework computes intermediate results once and reuses them across all relevant edges, drastically reducing the memory footprint.

Exploiting Temporal and Structural Stability

Redundancy also exists across time and frequency. In dynamic graphs, the structure often changes minimally between snapshots. Saumia Singhal and Anand Padmanabha Iyer developed REINC (ReInc: Scaling Training of Dynamic Graph Neural Networks), which shifts from "recompute everything" to an incremental approach. By caching and reusing results from static portions of the graph, they avoid re-aggregating neighborhoods that haven't changed.

Even in static training, some nodes are more "stable" than others. Kezhao Huang and Minjie Wang introduced FreshGNN (ReFresh: Reducing Memory Access...), which identifies node embeddings that have already converged. By caching these "stable" embeddings, the system skips redundant fetches and computations, speeding up training on massive graphs with negligible impact on accuracy.

Coordinated and Cooperative Computation

In distributed environments, the challenge is coordination. If two GPUs independently sample overlapping subgraphs, they will both fetch and compute the same data.

Muhammed Fatih Balin and Dominique LaSalle proposed Cooperative Minibatching (Cooperative Minibatching in Graph Neural Networks), where multiple GPUs work together on a single large batch. This allows them to share the results of sampled nodes, eliminating redundant work and saving significant interconnect bandwidth.

For hypergraphs, where multiple nodes are connected by a single hyperedge, the redundancy is even more pronounced. Hui Yu and Jin Zhao developed RHGNN (An efficient high throughput system of hypergraph neural network...), which groups hyperedges based on topological similarity. This "load once, compute many" strategy allows the system to fetch vertex features once and reuse them across multiple overlapping hyperedges, eliminating over 80% of redundant data operations.

Intuition: From Vertex-Centric to Cluster-Centric

The shift in the field can be summarized as moving from vertex-centric to cluster-centric processing.

In a vertex-centric model, each node is an island. In a cluster-centric or redundancy-aware model, the system recognizes that nodes exist in a shared context. As Paolo Sylos Labini and Flavio Vella demonstrate in their work on epidemic models (Scaling Expected Force...), identifying unique transmission clusters once and updating all constituent nodes simultaneously is far more efficient than processing overlapping neighborhoods one by one. By treating the graph as a collection of shared structures rather than independent points, these methods turn the "curse" of graph density into an opportunity for reuse.

Papers in this version

Showing 60 of 105 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_eliminating_redundant_computation_in_gra_5233c319,
  title = {Eliminating Redundant Computation in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/eliminating-redundant-computation-in-graph-neural-networks/rdr_5233c3192f8d4d7f929727e382eda096},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_eliminating_redundant_computation_in_gra_5233c319_v1,
  title = {Eliminating Redundant Computation in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/eliminating-redundant-computation-in-graph-neural-networks/rdr_5233c3192f8d4d7f929727e382eda096/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}