Optimizing Sparse Matrix Multiplications for Graph Neural Networks

Shenghao Qiu, You Liang, Zheng Wang

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:

  1. Feature Engineering: Extraction of 19 key matrix features (e.g., density, standard deviation of non-zeros) that correlate with hardware performance.
  2. 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.
  3. 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.
  4. 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.

Figure 2: The density of the processed matrix increases significantly over training epochs, rising from under 50% to nearly 75%.

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.

Figure 5: Speedup comparison of various storage formats for the CoraFull and PubmedFull datasets, demonstrating that the optimal format varies by graph structure.

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

Abstract

Graph neural networks (GNNs) are emerging as a powerful technique for modeling graph structures. Due to the sparsity of real-world graph data, GNN performance is limited by extensive sparse matrix multiplication (SpMM) operations involved in computation. While the right sparse matrix storage format varies across input data, existing deep learning frameworks employ a single, static storage format, leaving much room for improvement. This paper investigates how the choice of sparse matrix storage formats affect the GNN performance. We observe that choosing a suitable sparse matrix storage format can significantly improve the GNN training performance, but the right format depends on the input workloads and can change as the GNN iterates over the input graph. We then develop a predictive model to dynamically choose a sparse matrix storage format to be used by a GNN layer based on the input matrices. Our model is first trained offline using training matrix samples, and the trained model can be applied to any input matrix and GNN kernels with SpMM computation. We implement our approach on top of PyTorch and apply it to 5 representative GNN models running on a multi-core CPU using real-life and synthetic datasets. Experimental results show that our approach gives an average speedup of 1.17x (up to 3x) for GNN running time.
BibTeX
@inproceedings{qiu2021optimizing,
  author = {Shenghao Qiu and You Liang and Zheng Wang},
  title = {{Optimizing Sparse Matrix Multiplications for Graph Neural Networks}},
  booktitle = {LCPC},
  year = {2021},
  url = {https://openreview.net/forum?id=7HwP8MvnSI},
}
Figure