Accelerating Graph Neural Networks with a Novel Matrix Compression Format
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916380739108864 |
|---|---|
| author | Alves, João N. F. Moustafa, Samir Benkner, Siegfried Francisco, Alexandre P. Gansterer, Wilfried N. Russo, Luís M. S. |
| author_facet | Alves, João N. F. Moustafa, Samir Benkner, Siegfried Francisco, Alexandre P. Gansterer, Wilfried N. Russo, Luís M. S. |
| contents | The inference and training stages of Graph Neural Networks (GNNs) are often dominated by the time required to compute a long sequence of matrix multiplications between the sparse graph adjacency matrix and its embedding. To accelerate these stages, we first propose the Compressed Binary Matrix (CBM) storage format to succinctly represent the binary adjacency matrix of an unweighted graph. Then, we show how to generalize this representation to normalized adjacency matrices of unweighted graphs which arise in the context of GNNs. Finally, we develop efficient matrix multiplication kernels based on this compressed representation. The matrix multiplication kernels proposed in this work never require more scalar operations than classic sparse matrix multiplication algorithms. Experimental evaluation shows that the matrix multiplication strategies proposed outperform the current state-of-the-art implementations provided by Intel MKL, achieving speedups close to 5$\times$. Furthermore, our optimized matrix-multiplication strategies accelerated the inference time of a GNN by up to $3\times$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_02208 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Accelerating Graph Neural Networks with a Novel Matrix Compression Format Alves, João N. F. Moustafa, Samir Benkner, Siegfried Francisco, Alexandre P. Gansterer, Wilfried N. Russo, Luís M. S. Data Structures and Algorithms The inference and training stages of Graph Neural Networks (GNNs) are often dominated by the time required to compute a long sequence of matrix multiplications between the sparse graph adjacency matrix and its embedding. To accelerate these stages, we first propose the Compressed Binary Matrix (CBM) storage format to succinctly represent the binary adjacency matrix of an unweighted graph. Then, we show how to generalize this representation to normalized adjacency matrices of unweighted graphs which arise in the context of GNNs. Finally, we develop efficient matrix multiplication kernels based on this compressed representation. The matrix multiplication kernels proposed in this work never require more scalar operations than classic sparse matrix multiplication algorithms. Experimental evaluation shows that the matrix multiplication strategies proposed outperform the current state-of-the-art implementations provided by Intel MKL, achieving speedups close to 5$\times$. Furthermore, our optimized matrix-multiplication strategies accelerated the inference time of a GNN by up to $3\times$. |
| title | Accelerating Graph Neural Networks with a Novel Matrix Compression Format |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.02208 |