GPU-Accelerated Sparse Matrix-Dense Matrix Multiplication for Graph Neural Networks: A Comprehensive Survey
TL;DR
It is found that no single kernel dominates across all graph structures and that effective Tensor Core utilization reaches only 5–20% on irregular GNN matrices, while graph reordering is broadly beneficial, yielding gains of up to $43\times $ when it enables Sparse Tensor Core execution.
Abstract
Sparse Matrix-Dense Matrix Multiplication (SpMM) is a dominant computational bottleneck in Graph Neural Network (GNN) inference and training. Representative studies report that SpMM consumes roughly 30% of the execution time in some Graph Convolutional Network (GCN) settings and over 80% in full-batch GraphSAGE training. Despite the rapid growth of GPU SpMM optimization techniques, spanning CUDA core kernels, Tensor Core acceleration, adaptive hybrid execution, autotuning, graph reordering, and framework integration, no dedicated survey has focused on this subfield. This paper presents the first such survey, covering 52 GPU-accelerated SpMM methods for GNN workloads published between 2019 and 2026. We constructed the corpus from IEEE Xplore, the ACM Digital Library, USENIX, arXiv, and Google Scholar, screening the studies first by title and abstract and then by full text. We included GPU-based SpMM kernels and GNN aggregation systems and excluded CPU-only, non-SpMM, abstract-only, and duplicate-version papers. We organize the literature into six technique categories and compare the methods using a ten-dimensional framework. Representative dimensions include sparse format, hardware target, parallelism strategy, load balancing, preprocessing cost, and open-source availability. We find that no single kernel dominates across all graph structures and that effective Tensor Core utilization reaches only 5–20% on irregular GNN matrices. Graph reordering is broadly beneficial, yielding gains of up to $43\times $ when it enables Sparse Tensor Core execution. Because the surveyed literature is overwhelmingly based on CUDA and Tensor Cores, our analysis is NVIDIA-centered. Nevertheless, we distinguish architecture-level insights that generalize to AMD and Intel accelerators from vendor-specific implementation details. We conclude with eight open challenges, including the no-single-winner problem, the Tensor Core utilization gap, standardized benchmarking, and graph-to-kernel compilation.