Introduction
Graph Neural Networks (GNNs) have become the standard for learning on graph-structured data. However, their computational efficiency is often hampered by a "neighbor tax": the redundant aggregation of features from shared neighbors. In clustered real-world graphs, nodes frequently share large portions of their neighborhoods. Standard GNN implementations re-calculate these shared aggregations independently for each node, leading to significant overhead in both floating-point operations and data movement.
This paper introduces Hierarchically Aggregated computation Graphs (HAGs), a novel representation that identifies and reuses these shared intermediate results. By transforming the flat aggregation process into a hierarchical structure, HAGs can significantly boost training and inference speeds without compromising model accuracy.
Hierarchically Aggregated computation Graphs (HAGs)
The core innovation of this work is the HAG abstraction. Instead of performing a direct aggregation for every node, the system identifies common subsets of neighbors across different nodes and computes their sum once.
The construction of a HAG involves several key components:
- Aggregation Nodes: Intermediate nodes are introduced to represent the results of partial aggregations (e.g., the sum of features for a common pair of neighbors).
- Greedy Search Algorithm: Since finding the optimal hierarchy is NP-hard, the authors employ a greedy algorithm that iteratively merges the most frequent pairs of nodes being aggregated.
- Theoretical Foundations: The authors demonstrate that this greedy approach is globally optimal for sequential aggregations (like LSTMs) and provides a $(1 - 1/e)$ approximation for set-based aggregations (like GCNs).
- Cost-Aware Optimization: The algorithm uses a cost function that accounts for both computational complexity and the overhead of data movement between memory and GPU cores.
Experimental Evaluation
The HAG framework was evaluated across five diverse datasets: BZR (chemical compounds), PPI (protein interactions), REDDIT (social media), and IMDB/COLLAB (collaboration networks). These datasets represent a wide range of graph densities and clustering coefficients.
Key Results
The implementation of HAGs yielded substantial performance improvements across all tested scenarios:
- Throughput Gains: As shown in Figure 4, HAGs achieved end-to-end training speedups of up to 2.8× and inference speedups of up to 2.9×.
- Efficiency: The number of binary aggregations was reduced by up to 6.3× (in the BZR dataset), while data transfer volume saw reductions of up to 5.6×.
- Zero Accuracy Loss: Because HAGs are mathematically equivalent to the original GNN computation graphs, the optimization is "lossless"—it provides speedups with no impact on model performance.
Discussion and Future Work
The results suggest that current GNN implementations suffer from massive hidden redundancies. By making the computation graph model-agnostic, HAGs can be applied to various architectures, including GCN, GraphSAGE, and Tree-LSTMs. Furthermore, the memory overhead for maintaining these intermediate nodes is negligible (approximately 0.1%).
However, some challenges remain. The current HAG generation process is designed for static graphs; dynamic graphs would require frequent re-optimization. Future research could focus on faster heuristic-based search algorithms for massive-scale graphs or developing specialized hardware kernels to further optimize HAG traversal.
Summary updated