Distributed Graph Neural Network Training with Periodic Historical Embedding Synchronization

• URL: http://arxiv.org/abs/2206.00057v1
• Date: Tue, 31 May 2022 18:44:53 GMT
• Title: Distributed Graph Neural Network Training with Periodic Historical Embedding Synchronization
• Authors: Zheng Chai, Guangji Bai, Liang Zhao, Yue Cheng
• Abstract summary: Graph Neural Networks (GNNs) are prevalent in various applications such as social network, recommender systems, and knowledge graphs. Traditional sampling-based methods accelerate GNN by dropping edges and nodes, which impairs the graph integrity and model performance. This paper proposes DIstributed Graph Embedding SynchronizaTion (DIGEST), a novel distributed GNN training framework.
• Score: 9.503080586294406
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the recent success of Graph Neural Networks (GNNs), it remains challenging to train a GNN on large graphs, which are prevalent in various applications such as social network, recommender systems, and knowledge graphs. Traditional sampling-based methods accelerate GNN by dropping edges and nodes, which impairs the graph integrity and model performance. Differently, distributed GNN algorithms, which accelerate GNN training by utilizing multiple computing devices, can be classified into two types: "partition-based" methods enjoy low communication costs but suffer from information loss due to dropped edges, while "propagation-based" methods avoid information loss but suffer prohibitive communication overhead. To jointly address these problems, this paper proposes DIstributed Graph Embedding SynchronizaTion (DIGEST), a novel distributed GNN training framework that synergizes the complementary strength of both categories of existing methods. During subgraph parallel training, we propose to let each device store the historical embedding of its neighbors in other subgraphs. Therefore, our method does not discard any neighbors in other subgraphs, nor does it updates them intensively. This effectively avoids (1) the intensive computation on explosively-increasing neighbors and (2) excessive communications across different devices. We proved that the approximation error induced by the staleness of historical embedding can be upper bounded and it does NOT affect the GNN model's expressiveness. More importantly, our convergence analysis demonstrates that DIGEST enjoys a state-of-the-art convergence rate. Extensive experimental evaluation on large, real-world graph datasets shows that DIGEST achieves up to $21.82\times$ speedup without compromising the performance compared to state-of-the-art distributed GNN training frameworks.

Related papers

• DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment [57.62885438406724]
  Graph neural networks are recognized for their strong performance across various applications. BP has limitations that challenge its biological plausibility and affect the efficiency, scalability and parallelism of training neural networks for graph-based tasks. We propose DFA-GNN, a novel forward learning framework tailored for GNNs with a case study of semi-supervised learning.
  arXiv  Detail & Related papers  (2024-06-04T07:24:51Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  Graph Neural Networks (GNNs) show promising results for graph tasks. Existing GNNs' generalization ability will degrade when there exist distribution shifts between testing and training graph data. We propose a novel nonlinear graph decorrelation method, which can substantially improve the out-of-distribution generalization ability.
  arXiv  Detail & Related papers  (2023-12-19T12:25:10Z)
• 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)
• Staleness-Alleviated Distributed GNN Training via Online Dynamic-Embedding Prediction [13.575053193557697]
  This paper proposes SAT (Staleness-Alleviated Training), a novel and scalable distributed GNN training framework. The key idea of SAT is to model the GNN's embedding evolution as a temporal graph and build a model upon it to predict future embedding. Empirically, we demonstrate that SAT can effectively reduce embedding staleness and thus achieve better performance and convergence speed.
  arXiv  Detail & Related papers  (2023-08-25T16:10:44Z)
• Expediting Distributed DNN Training with Device Topology-Aware Graph Deployment [18.021259939659874]
  TAG is an automatic system to derive optimized DNN training graph and its deployment onto any device topology. We show that it can achieve up to 4.56x training speed-up as compared to existing schemes.
  arXiv  Detail & Related papers  (2023-02-13T06:30:24Z)
• 2-hop Neighbor Class Similarity (2NCS): A graph structural metric indicative of graph neural network performance [4.051099980410583]
  Graph Neural Networks (GNNs) achieve state-of-the-art performance on graph-structured data across numerous domains. On heterophilous graphs, in which different-type nodes are likely connected, GNNs perform less consistently. We introduce 2-hop Neighbor Class Similarity (2NCS), a new quantitative graph structural property that correlates with GNN performance more strongly and consistently than alternative metrics.
  arXiv  Detail & Related papers  (2022-12-26T16:16:51Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• AEGNN: Asynchronous Event-based Graph Neural Networks [54.528926463775946]
  Event-based Graph Neural Networks generalize standard GNNs to process events as "evolving"-temporal graphs. AEGNNs are easily trained on synchronous inputs and can be converted to efficient, "asynchronous" networks at test time.
  arXiv  Detail & Related papers  (2022-03-31T16:21:12Z)
• Training Free Graph Neural Networks for Graph Matching [103.45755859119035]
  TFGM is a framework to boost the performance of Graph Neural Networks (GNNs) based graph matching without training. Applying TFGM on various GNNs shows promising improvements over baselines.
  arXiv  Detail & Related papers  (2022-01-14T09:04:46Z)

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.