LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence

• URL: http://arxiv.org/abs/2302.00924v3
• Date: Sat, 23 Mar 2024 15:40:58 GMT
• Title: LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence
• Authors: Zhihao Shi, Xize Liang, Jie Wang,
• Abstract summary: We propose a novel subgraph-wise sampling method with a convergence guarantee, namely Local Message Compensation (LMC) LMC retrieves the discarded messages in backward passes based on a message passing formulation of backward passes. LMC significantly outperforms state-of-the-art subgraph-wise sampling methods in terms of efficiency.
• Score: 8.630426703200541
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The message passing-based graph neural networks (GNNs) have achieved great success in many real-world applications. However, training GNNs on large-scale graphs suffers from the well-known neighbor explosion problem, i.e., the exponentially increasing dependencies of nodes with the number of message passing layers. Subgraph-wise sampling methods -- a promising class of mini-batch training techniques -- discard messages outside the mini-batches in backward passes to avoid the neighbor explosion problem at the expense of gradient estimation accuracy. This poses significant challenges to their convergence analysis and convergence speeds, which seriously limits their reliable real-world applications. To address this challenge, we propose a novel subgraph-wise sampling method with a convergence guarantee, namely Local Message Compensation (LMC). To the best of our knowledge, LMC is the {\it first} subgraph-wise sampling method with provable convergence. The key idea of LMC is to retrieve the discarded messages in backward passes based on a message passing formulation of backward passes. By efficient and effective compensations for the discarded messages in both forward and backward passes, LMC computes accurate mini-batch gradients and thus accelerates convergence. We further show that LMC converges to first-order stationary points of GNNs. Experiments on large-scale benchmark tasks demonstrate that LMC significantly outperforms state-of-the-art subgraph-wise sampling methods in terms of efficiency.

Related papers

• Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlo [55.452453947359736]
  We introduce a novel verification method based on Twisted Sequential Monte Carlo (TSMC) We apply TSMC to Large Language Models by estimating the expected future rewards at partial solutions. This approach results in a more straightforward training target that eliminates the need for step-wise human annotations.
  arXiv  Detail & Related papers  (2024-10-02T18:17:54Z)
• Learning to Explore for Stochastic Gradient MCMC [15.286308920219446]
  We propose a meta-learning strategy to build glssgmcmc which can efficiently explore the multi-modal target distributions. Our algorithm allows the learned SGMCMC to quickly explore the high-density region of the posterior landscape.
  arXiv  Detail & Related papers  (2024-08-17T08:36:42Z)
• Robust Analysis of Multi-Task Learning Efficiency: New Benchmarks on Light-Weighed Backbones and Effective Measurement of Multi-Task Learning Challenges by Feature Disentanglement [69.51496713076253]
  In this paper, we focus on the aforementioned efficiency aspects of existing MTL methods. We first carry out large-scale experiments of the methods with smaller backbones and on a the MetaGraspNet dataset as a new test ground. We also propose Feature Disentanglement measure as a novel and efficient identifier of the challenges in MTL.
  arXiv  Detail & Related papers  (2024-02-05T22:15:55Z)
• Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo [30.4930148381328]
  Diffusion-based Monte Carlo (DMC) is a method to sample from a general target distribution beyond the isoperimetric condition. DMC encountered high gradient complexity, resulting in an exponential dependency on the error tolerance $epsilon$ of the obtained samples. We propose RS-DMC, based on a novel recursion-based score estimation method. Our algorithm is provably much faster than the popular Langevin-based algorithms.
  arXiv  Detail & Related papers  (2024-01-12T02:33:57Z)
• Diffusion Generative Flow Samplers: Improving learning signals through partial trajectory optimization [87.21285093582446]
  Diffusion Generative Flow Samplers (DGFS) is a sampling-based framework where the learning process can be tractably broken down into short partial trajectory segments. Our method takes inspiration from the theory developed for generative flow networks (GFlowNets)
  arXiv  Detail & Related papers  (2023-10-04T09:39:05Z)
• Small Object Detection via Coarse-to-fine Proposal Generation and Imitation Learning [52.06176253457522]
  We propose a two-stage framework tailored for small object detection based on the Coarse-to-fine pipeline and Feature Imitation learning. CFINet achieves state-of-the-art performance on the large-scale small object detection benchmarks, SODA-D and SODA-A.
  arXiv  Detail & Related papers  (2023-08-18T13:13:09Z)
• Provably Convergent Subgraph-wise Sampling for Fast GNN Training [122.68566970275683]
  We propose a novel subgraph-wise sampling method with a convergence guarantee, namely Local Message Compensation (LMC) LMC retrieves the discarded messages in backward passes based on a message passing formulation of backward passes. Experiments on large-scale benchmarks demonstrate that LMC is significantly faster than state-of-the-art subgraph-wise sampling methods.
  arXiv  Detail & Related papers  (2023-03-17T05:16:49Z)
• Solving Sparse Linear Inverse Problems in Communication Systems: A Deep Learning Approach With Adaptive Depth [51.40441097625201]
  We propose an end-to-end trainable deep learning architecture for sparse signal recovery problems. The proposed method learns how many layers to execute to emit an output, and the network depth is dynamically adjusted for each task in the inference phase.
  arXiv  Detail & Related papers  (2020-10-29T06:32:53Z)

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.