Optimizing Sparse Matrix Multiplications for Graph Neural Networks

• URL: http://arxiv.org/abs/2111.00352v1
• Date: Sat, 30 Oct 2021 22:08:51 GMT
• Title: Optimizing Sparse Matrix Multiplications for Graph Neural Networks
• Authors: Shenghao Qiu, You Liang and Zheng Wang
• Abstract summary: 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 operations. This paper investigates how the choice of sparse matrix storage formats affect the GNN performance.
• Score: 8.080228311931261
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• SpanGNN: Towards Memory-Efficient Graph Neural Networks via Spanning Subgraph Training [14.63975787929143]
  Graph Neural Networks (GNNs) have superior capability in learning graph data. Full-graph GNN training generally has high accuracy, however, it suffers from large peak memory usage. We propose a new memory-efficient GNN training method using spanning subgraph, called SpanGNN.
  arXiv  Detail & Related papers  (2024-06-07T13:46:23Z)
• Graph Neural Networks and Applied Linear Algebra [1.8749305679160366]
  Graph neural networks (GNNs) are an approach suitable to sparse matrix computations. This paper provides an introduction to GNNs for a numerical linear algebra audience. Concrete examples are provided to illustrate how many common linear algebra tasks can be accomplished using GNNs.
  arXiv  Detail & Related papers  (2023-10-21T18:37:56Z)
• SENSEi: Input-Sensitive Compilation for Accelerating GNNs [7.527596018706567]
  We propose SENSEi, a system that exposes different sparse and dense matrix primitive compositions based on different matrix re-associations of GNN computations. SENSEi executes in two stages: (1) an offline compilation stage that enumerates all valid re-associations leading to different sparse-dense matrix compositions and uses input-oblivious pruning techniques to prune away clearly unprofitable candidates. On a wide range of configurations, SENSEi achieves speedups of up to $2.012times$ and $1.85times$ on graph convolutional networks and up to $6.294times$ and $16.274
  arXiv  Detail & Related papers  (2023-06-27T02:24:05Z)
• RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations [56.59168541623729]
  Training graph neural networks (GNNs) is time consuming because sparse graph-based operations are hard to be accelerated by hardware. We explore trading off the computational precision to reduce the time complexity via sampling-based approximation. We propose Randomized Sparse Computation, which for the first time demonstrate the potential of training GNNs with approximated operations.
  arXiv  Detail & Related papers  (2022-10-19T17:25:33Z)
• DNN Training Acceleration via Exploring GPGPU Friendly Sparsity [16.406482603838157]
  We propose the Approximate Random Dropout that replaces the conventional random dropout of neurons and synapses with a regular and online generated row-based or tile-based dropout patterns. We then develop a SGD-based Search Algorithm that produces the distribution of row-based or tile-based dropout patterns to compensate for the potential accuracy loss. We also propose the sensitivity-aware dropout method to dynamically drop the input feature maps based on their sensitivity so as to achieve greater forward and backward training acceleration.
  arXiv  Detail & Related papers  (2022-03-11T01:32:03Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  We propose the Neighbor2Seq to transform the hierarchical neighborhood of each node into a sequence. We evaluate our method on a massive graph with more than 111 million nodes and 1.6 billion edges. Results show that our proposed method is scalable to massive graphs and achieves superior performance across massive and medium-scale graphs.
  arXiv  Detail & Related papers  (2022-02-07T16:38:36Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  We propose textitVersaGNN, an ultra-efficient, systolic-array-based versatile hardware accelerator. textitVersaGNN achieves on average 3712$times$ speedup with 1301.25$times$ energy reduction on CPU, and 35.4$times$ speedup with 17.66$times$ energy reduction on GPU.
  arXiv  Detail & Related papers  (2021-05-04T04:10:48Z)
• Adaptive Filters and Aggregator Fusion for Efficient Graph Convolutions [11.769185588579488]
  We present state-of-the-art performance with lower memory consumption and latency, along with characteristics suited to accelerator implementation. Our proposal uses memory proportional to the number of vertices in the graph, in contrast to competing methods which require memory proportional to the number of edges. We propose aggregator fusion, a technique to enable GNNs to significantly boost their representational power, with only a small increase in latency of 19% over standard sparse matrix multiplication.
  arXiv  Detail & Related papers  (2021-04-03T20:54:36Z)
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
  We present a unified GNN sparsification (UGS) framework that simultaneously prunes the graph adjacency matrix and the model weights. We further generalize the popular lottery ticket hypothesis to GNNs for the first time, by defining a graph lottery ticket (GLT) as a pair of core sub-dataset and sparse sub-network.
  arXiv  Detail & Related papers  (2021-02-12T21:52:43Z)
• Binary Graph Neural Networks [69.51765073772226]
  Graph Neural Networks (GNNs) have emerged as a powerful and flexible framework for representation learning on irregular data. In this paper, we present and evaluate different strategies for the binarization of graph neural networks. We show that through careful design of the models, and control of the training process, binary graph neural networks can be trained at only a moderate cost in accuracy on challenging benchmarks.
  arXiv  Detail & Related papers  (2020-12-31T18:48:58Z)
• Model Fusion via Optimal Transport [64.13185244219353]
  We present a layer-wise model fusion algorithm for neural networks. We show that this can successfully yield "one-shot" knowledge transfer between neural networks trained on heterogeneous non-i.i.d. data.
  arXiv  Detail & Related papers  (2019-10-12T22:07:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.