Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study

• URL: http://arxiv.org/abs/2409.11129v1
• Date: Tue, 17 Sep 2024 12:28:02 GMT
• Title: Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study
• Authors: Nikolai Merkel, Pierre Toussing, Ruben Mayer, Hans-Arno Jacobsen,
• Abstract summary: Graph neural networks (GNNs) are capable of learning on graph-structured data. The sparsity of graphs results in suboptimal memory access patterns and longer training time. We show that graph reordering is effective in reducing training time for CPU- and GPU-based training.
• Score: 13.354505458409957
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Graph neural networks (GNNs) are a type of neural network capable of learning on graph-structured data. However, training GNNs on large-scale graphs is challenging due to iterative aggregations of high-dimensional features from neighboring vertices within sparse graph structures combined with neural network operations. The sparsity of graphs frequently results in suboptimal memory access patterns and longer training time. Graph reordering is an optimization strategy aiming to improve the graph data layout. It has shown to be effective to speed up graph analytics workloads, but its effect on the performance of GNN training has not been investigated yet. The generalization of reordering to GNN performance is nontrivial, as multiple aspects must be considered: GNN hyper-parameters such as the number of layers, the number of hidden dimensions, and the feature size used in the GNN model, neural network operations, large intermediate vertex states, and GPU acceleration. In our work, we close this gap by performing an empirical evaluation of 12 reordering strategies in two state-of-the-art GNN systems, PyTorch Geometric and Deep Graph Library. Our results show that graph reordering is effective in reducing training time for CPU- and GPU-based training, respectively. Further, we find that GNN hyper-parameters influence the effectiveness of reordering, that reordering metrics play an important role in selecting a reordering strategy, that lightweight reordering performs better for GPU-based than for CPU-based training, and that invested reordering time can in many cases be amortized.

Related papers

• Faster Inference Time for GNNs using coarsening [1.323700980948722]
  coarsening-based methods are used to reduce the graph into a smaller one, resulting in faster computation. No previous research has tackled the cost during the inference. This paper presents a novel approach to improve the scalability of GNNs through subgraph-based techniques.
  arXiv  Detail & Related papers  (2024-10-19T06:27:24Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training [13.354505458409957]
  Graph neural networks (GNNs) have gained much attention as a growing area of deep learning capable of learning on graph-structured data. In this paper, we study the effectiveness of graph partitioning for distributed GNN training. We find that high-quality graph partitioning is a very effective optimization to speed up GNN training and to reduce memory consumption.
  arXiv  Detail & Related papers  (2023-08-29T19:47:31Z)
• Cached Operator Reordering: A Unified View for Fast GNN Training [24.917363701638607]
  Graph Neural Networks (GNNs) are a powerful tool for handling structured graph data and addressing tasks such as node classification, graph classification, and clustering. However, the sparse nature of GNN computation poses new challenges for performance optimization compared to traditional deep neural networks. We address these challenges by providing a unified view of GNN computation, I/O, and memory.
  arXiv  Detail & Related papers  (2023-08-23T12:27:55Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. We propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon.
  arXiv  Detail & Related papers  (2022-10-27T16:00:45Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Adaptive Kernel Graph Neural Network [21.863238974404474]
  Graph neural networks (GNNs) have demonstrated great success in representation learning for graph-structured data. In this paper, we propose a novel framework - i.e., namely Adaptive Kernel Graph Neural Network (AKGNN) AKGNN learns to adapt to the optimal graph kernel in a unified manner at the first attempt. Experiments are conducted on acknowledged benchmark datasets and promising results demonstrate the outstanding performance of our proposed AKGNN.
  arXiv  Detail & Related papers  (2021-12-08T20:23:58Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  We consider the problem of learning a graphon neural network (WNN) by training GNNs on graphs sampled Bernoulli from the graphon. Inspired by these results, we propose an algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training.
  arXiv  Detail & Related papers  (2021-06-07T15:05:59Z)

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.