StraGCN: GPU-Accelerated Strassen's Sparse-Dense Matrix Multiplication for Graph Convolutional Network Training

Graph Convolutional Networks (GCNs) are a fundamental approach to deep learning on graph-structured data. However, they face a significant challenge in training efficiency due to the high computational cost of Sparse-Dense Matrix Multiplication (SpMM). This paper presents StraGCN, the first GPU-accelerated SpMM implementation based on Strassen’s algorithm particularly designed for GCN training. First, we propose a horizontal fusion model for GPU kernels as an alternative to the commonly used multi-stream CUDA model, significantly improving data locality of on-chip shared memory for Strassen’s SpMM. Second, StraGCN exploits the immutability of the adjacency matrix in GCNs to reuse intermediate results from submatrix operations, substantially reducing redundant computations. Third, we propose a two-stage matrix partitioning scheme to mitigate load imbalance caused by the irregular distribution of non-zero elements. We evaluate StraGCN with fifteen benchmark datasets. Experimental results show that StraGCN achieves performance speedups of 2.1 ×, 2.6 ×, and 3.3 × compared with state-of-the-art GCN frameworks–GNNA, PyG, and DGL, respectively.