Standard Graph Neural Networks (GNNs) operate through a recursive process of neighborhood aggregation. To compute a representation for a node, the model pulls features from its immediate neighbors; in the next layer, those neighbors pull from their own neighbors, and so on. While intuitive, this mechanism harbors significant structural and computational redundancies that limit scalability and expressivity.
Recent research identifies three primary forms of redundancy: message flow redundancy (backtracking), computational overlap (shared neighbors), and temporal/layer-wise repetition (re-aggregating static structures).
The Echo Chamber of Backtracking
In a standard message-passing scheme, a node $A$ sends its information to neighbor $B$. In the subsequent layer, $B$ sends its updated information—which now includes $A$'s signal—back to $A$. This "backtracking" creates a cyclic exchange where information bounces back and forth, creating an echo-chamber effect.
Seonghyun Park et al. in Non-backtracking Graph Neural Networks argue that this redundancy obscures novel signals from more distant parts of the graph. By stripping away these redundant flows, models can "see" further across the topology without being overwhelmed by local noise. Similarly, Rongqin Chen et al. propose the Redundancy-Free Graph Neural Network (RFGNN), which uses unique paths to eliminate self-loops and backtracking. This approach mitigates "over-squashing"—the bottleneck where distant information is lost—and improves the theoretical expressivity of the network.
Eliminating Computational Overlap
Beyond the logic of the message, the execution of aggregation is often redundant. Because many nodes in a graph share the same neighbors, a standard GNN will calculate the same feature combinations multiple times.
To address this, Yongan Zhang et al. introduce "islandization" in I-GCN, a technique that restructures the graph at runtime to prune redundant computations and improve data locality. In heterogeneous graphs, where nodes have multiple types of relationships, this redundancy is even more pronounced. Dengke Han et al. propose a "Thinking Like a Vertex" (TLV) paradigm in TLV-HGNN. By shifting from relation-centric to vertex-centric processing, the authors ensure that each neighbor's features are accessed exactly once, drastically reducing memory traffic and energy consumption.
Decoupling Structure from Learning
A fundamental inefficiency in GNN training is the repeated aggregation of the same neighborhood features in every epoch, even when the graph structure is static.
Seiji Maekawa et al. demonstrate in their GNN Transformation Framework that feature aggregation can be decoupled from weight learning. By precomputing the structural aggregation, the model only needs to learn the neural weights during training, allowing GNNs to scale to hundreds of millions of nodes. Hao Chen et al. take this further with Non-Recursive Graph Convolutional Networks, which use a layer-independent aggregation step to break the recursive dependency that causes computational bloat.
This decoupling is particularly effective for large-scale tasks like clustering. Yaowen Hu argues in Scalable Attribute-Missing Graph Clustering via Neighborhood Differentiation that by ensuring each neighbor's features are processed exactly once across all "views" or layers, models can bypass the memory bottlenecks that typically plague deep GNN architectures.
Domain-Specific Redundancy
In some domains, the very act of message passing may be redundant. Liang Yang et al. observe in Do We Really Need Message Passing in Brain Network Modeling? that in correlation-based networks (like brain graphs), the node features and topology are often derived from the same data. In these cases, traditional message passing simply re-aggregates information already present in the input.
Similarly, for link prediction, Wu-Jun Li et al. suggest in Asymmetric Learning for Graph Neural Network based Link Prediction that calculating complex GNN embeddings for both nodes in a pair is unnecessary. By using a GNN for one node and a simple MLP for the other, they achieve significant speedups without sacrificing accuracy, proving that "symmetry" in GNN design is often a source of wasted computation.
Key Foundational Work
I-GCN: A Graph Convolutional Network Accelerator with Runtime Locality Enhancement through Islandization (2021) — contributed 1 concept elements to this direction.
Redundancy-Free Message Passing for Graph Neural Networks (2022) — contributed 1 concept elements to this direction.
Understanding GNN Computational Graph: A Coordinated Computation, IO, and Memory Perspective (2021) — contributed 1 concept elements to this direction.