Abstract
Graph Neural Networks (GNNs) have become the standard for modeling relational data, but their computational efficiency is often limited by Sparse Matrix Multiplication (SpMM). Current deep learning frameworks typically rely on a static storage format, such as Coordinate list (COO), for all operations. This paper introduces a dynamic selection framework that utilizes an XGBoost-based predictor to choose the optimal sparse storage format at runtime. By adapting to the specific characteristics of the graph and its evolving density during training, our approach achieves an average speedup of 1.17x (and up to 3x) over standard PyTorch implementations.
Introduction
The primary computational bottleneck in GNN layers is the multiplication of a sparse adjacency matrix by a dense feature matrix. While frameworks like PyTorch and TensorFlow default to the COO format, the performance of SpMM is highly dependent on the graph's structure, including its density and neighbor distribution. Crucially, we observe that the effective density of these matrices changes as the GNN iterates, meaning a static format choice is inherently suboptimal for long-running training processes.
Methodology
We propose a dynamic selection library integrated with PyTorch that selects the best storage format (e.g., CSR, BSR, COO) for each SpMM operation. The framework consists of:
- Feature Engineering: Extraction of 19 key matrix features (e.g., density, standard deviation of non-zeros) that correlate with hardware performance.
- Predictive Modeling: An XGBoost classifier predicts the fastest format for a given input. XGBoost was chosen for its superior balance of accuracy and low inference overhead compared to MLPs or SVMs.
- Offline Training: The model is trained on 300 synthetic matrices with densities ranging from 0.1% to 70% to ensure generalization to real-world graphs.
- Runtime Integration: The library extracts features and predicts the optimal format just-in-time. The overhead of this process is minimal, accounting for less than 3% of the total kernel execution time.
Dynamic Density Analysis
A key insight of this research is that the density of the adjacency matrix effectively increases as GNNs aggregate neighborhood information across successive epochs.
This dynamic behavior confirms that a "one-size-fits-all" storage format is insufficient, as the optimal format for a sparse initial state may become a bottleneck as the representation densifies.
Performance Evaluation
The framework was evaluated across diverse datasets, including Cora, PubmedFull, and KarateClub, and various GNN architectures like GCN and GAT. The XGBoost model achieved an 89.1% prediction accuracy, capturing 89% of the performance of a theoretical "Oracle" predictor.
As shown in the results, different datasets favor different formats; for instance, BSR provides a 1.62x speedup for CoraFull, while CSR is more effective for PubmedFull. Our dynamic framework successfully navigates these variations to provide consistent end-to-end gains.
Conclusion
By moving away from static storage formats, GNN performance can be significantly improved with negligible overhead. While this study focused on multi-core CPUs, the methodology is extensible to GPUs, where specialized kernels like ELLPACK could be added to the selection library. Future work will focus on expanding the library of supported formats and optimizing the conversion costs for exceptionally large-scale graphs.
Summary updated