A Survey on Computational Efficiency Optimization for Graph Neural Networks on Large-Scale Graphs

Graph Neural Networks (GNNs) have become a dominant paradigm for learning from graph-structured data, yet their application to large-scale graphs remains constrained by three coupled system bottlenecks: memory, computation, and communication. This paper organizes the literature around a bottleneck-centric taxonomy that maps representative techniques, including Cluster-GCN, GraphSAINT, GraphSAGE, SGC, DistDGL, and AliGraph, to the specific constraint each primarily relieves. Three representative systems, GraphSAGE, Cluster-GCN, and DistDGL, are further analyzed as case studies and consolidated into a practical decision matrix linking graph scale, hardware budget, and structural properties to an appropriate strategy. The paper also identifies a largely unaddressed challenge: the shift toward high-dimensional, LLM-encoded node features, which is beginning to move the dominant bottleneck from computation toward memory bandwidth and I/O. The review concludes that current sampling and partitioning techniques remain vulnerable to long-tail bias, that reported near-linear distributed speedups depend on network conditions rarely disclosed in published work, and that the most promising direction for future systems lies not in a new algorithm but in adaptive schedulers that reconfigure strategy at runtime.