論文の概要: LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence

• arxiv url: http://arxiv.org/abs/2302.00924v3
• Date: Sat, 23 Mar 2024 15:40:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-27 04:08:18.528699
• Title: LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence
• Title（参考訳）: LMC: 予測収束を用いたサブグラフサンプリングによるGNNの高速トレーニング
• Authors: Zhihao Shi, Xize Liang, Jie Wang,
• Abstract要約: 収束保証,すなわちローカルメッセージ補償(LMC)を用いた新しいサブグラフワイズサンプリング手法を提案する。 LMCは、後方パスのメッセージパスの定式化に基づいて、後方パスで破棄されたメッセージを検索する。 LMCは、効率の点で最先端のサブグラフワイドサンプリング法を著しく上回っている。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: メッセージパッシングベースのグラフニューラルネットワーク(GNN)は多くの現実世界のアプリケーションで大きな成功を収めている。 しかし、大規模グラフ上でのGNNのトレーニングは、よく知られた隣り合う爆発的問題、すなわち、メッセージパッシング層の数が指数関数的に増加するノードの依存関係に悩まされる。 サブグラフワイズサンプリング手法(ミニバッチトレーニング技術の有望なクラス)は、勾配推定精度を犠牲にして隣の爆発問題を避けるために、後方のミニバッチの外でメッセージを破棄する。 これは収束解析と収束速度に大きな課題をもたらし、現実の信頼性を著しく制限する。 この課題に対処するために,収束保証,すなわちローカルメッセージ補償(LMC)を備えた新しいサブグラフワイズサンプリング手法を提案する。 我々の知る限りでは、LCCは証明可能な収束性を持つ部分グラフワイドサンプリング法である。 LMCの鍵となる考え方は、後方パスのメッセージパスの定式化に基づいて、破棄されたメッセージを後方パスで取り出すことである。 前と後の両方で破棄されたメッセージの効率よく効果的な補償によって、LCCは正確なミニバッチ勾配を計算し、収束を加速する。 さらに,LCCはGNNの1次定常点に収束することを示す。 大規模ベンチマークタスクの実験では、LCCは効率の点で最先端のサブグラフワイドサンプリング手法よりも大幅に優れていた。

関連論文リスト

• Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlo [55.452453947359736]
  Twisted Sequential Monte Carlo(TSMC)に基づく新しい検証手法を提案する。 TSMCを大規模言語モデルに適用し、部分解に対する将来的な報酬を推定する。 このアプローチは、ステップワイドなヒューマンアノテーションを必要としない、より直接的なトレーニングターゲットをもたらす。
  論文  参考訳（メタデータ） (2024-10-02T18:17:54Z)
• Learning to Explore for Stochastic Gradient MCMC [15.286308920219446]
  マルチモーダルなターゲット分布を効率的に探索できるglssgmcmcを構築するメタラーニング戦略を提案する。 我々のアルゴリズムは、学習したSGMCMCが後部景観の高密度領域を迅速に探索することを可能にする。
  論文  参考訳（メタデータ） (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]
  本稿では,既存のMTL手法の効率性に焦点をあてる。 バックボーンを小さくしたメソッドの大規模な実験と,MetaGraspNetデータセットを新しいテストグラウンドとして実施する。 また,MTLにおける課題の新規かつ効率的な識別子として,特徴分散尺度を提案する。
  論文  参考訳（メタデータ） (2024-02-05T22:15:55Z)
• Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo [30.4930148381328]
  拡散に基づくモンテカルロ (DMC) は、等尺条件を超えた一般目標分布から試料を採取する手法である。 DMCは、高い勾配の複雑さに遭遇し、その結果、得られたサンプルのエラー耐性$epsilon$に指数関数的に依存する。 本稿では,新しい再帰に基づくスコア推定法に基づくRS-DMCを提案する。 私たちのアルゴリズムは、人気のあるLangevinベースのアルゴリズムよりもはるかに高速です。
  論文  参考訳（メタデータ） (2024-01-12T02:33:57Z)
• Diffusion Generative Flow Samplers: Improving learning signals through partial trajectory optimization [87.21285093582446]
  Diffusion Generative Flow Samplers (DGFS) はサンプルベースのフレームワークであり、学習プロセスを短い部分的軌道セグメントに分解することができる。 生成フローネットワーク(GFlowNets)のための理論から着想を得た。
  論文  参考訳（メタデータ） (2023-10-04T09:39:05Z)
• Small Object Detection via Coarse-to-fine Proposal Generation and Imitation Learning [52.06176253457522]
  本稿では,粗粒度パイプラインと特徴模倣学習に基づく小型物体検出に適した2段階フレームワークを提案する。 CFINetは、大規模な小さなオブジェクト検出ベンチマークであるSODA-DとSODA-Aで最先端の性能を達成する。
  論文  参考訳（メタデータ） (2023-08-18T13:13:09Z)
• Provably Convergent Subgraph-wise Sampling for Fast GNN Training [122.68566970275683]
  収束保証,すなわちローカルメッセージ補償(LMC)を用いた新しいサブグラフワイズサンプリング手法を提案する。 LMCは、後方パスのメッセージパスの定式化に基づいて、後方パスで破棄されたメッセージを検索する。 大規模ベンチマーク実験により、LCCは最先端のサブグラフワイドサンプリング法よりもはるかに高速であることが示された。
  論文  参考訳（メタデータ） (2023-03-17T05:16:49Z)
• Solving Sparse Linear Inverse Problems in Communication Systems: A Deep Learning Approach With Adaptive Depth [51.40441097625201]
  疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。 提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
  論文  参考訳（メタデータ） (2020-10-29T06:32:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。