論文の概要: LMC: Fast Training of GNNs via Subgraph Sampling with Provable
Convergence
- arxiv url: http://arxiv.org/abs/2302.00924v1
- Date: Thu, 2 Feb 2023 07:52:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-03 14:56:37.666385
- 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は、効率の点で最先端のサブグラフワイドサンプリング法を著しく上回っている。
- 参考スコア(独自算出の注目度): 7.135975474441761
- 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のトレーニングは、よく知られた隣り合う爆発問題、すなわちメッセージパッシング層の数でノードの指数関数的に増加する依存性に苦しむ。
subgraph-wise sampling method -- 有望なミニバッチトレーニングテクニックのクラス -- は、勾配推定精度を犠牲にして隣の爆発問題を避けるために、ミニバッチの外側のメッセージを後方に破棄する。
これは収束解析と収束速度に大きな課題をもたらし、現実の信頼性を著しく制限する。
この課題に対処するために,収束保証,すなわちローカルメッセージ補償(LMC)を備えた新しいサブグラフワイズサンプリング手法を提案する。
我々の知る限りでは、LCCは証明可能な収束性を持つ部分グラフワイドサンプリング法である。
LMCの鍵となる考え方は、後方パスのメッセージパスの定式化に基づいて、破棄されたメッセージを後方パスで取り出すことである。
前と後の両方で破棄されたメッセージの効率よく効果的な補償によって、LCCは正確なミニバッチ勾配を計算し、収束を加速する。
さらに、LCCはGNNの1次定常点に収束することを示す。
大規模ベンチマークタスクの実験では、LCCは効率の点で最先端のサブグラフワイドサンプリング手法よりも大幅に優れていた。
関連論文リスト
- Convergence Acceleration of Markov Chain Monte Carlo-based Gradient
Descent by Deep Unfolding [5.584060970507506]
本研究では,深部展開法(deep unfolding)と呼ばれる深部学習手法を用いて,最適化問題(COP)のトレーニング可能なサンプリングベース解法を提案する。
提案手法は,マルコフ鎖モンテカルロ(MCMC)と勾配勾配を結合したオオゼキ法に基づいている。
数個のCOPの数値計算結果から,提案した解法はオリジナルの大関法と比較して収束速度を著しく向上させた。
論文 参考訳(メタデータ) (2024-02-21T08:21:48Z) - 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 [63.530816506578674]
収束保証,すなわちローカルメッセージ補償(LMC)を用いた新しいサブグラフワイズサンプリング手法を提案する。
LMCは、後方パスのメッセージパスの定式化に基づいて、後方パスで破棄されたメッセージを検索する。
大規模ベンチマーク実験により、LCCは最先端のサブグラフワイドサンプリング法よりもはるかに高速であることが示された。
論文 参考訳(メタデータ) (2023-03-17T05:16:49Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Parallel MCMC Without Embarrassing Failures [19.429985676081618]
MCMCはデータパーティションで定義された(サブ)後続体上で並列に実行される。
効率的ではあるが、このフレームワークは後部サンプリングの品質に非常に敏感である。
我々はこの問題を緩和するための新しい組み合わせ戦略を提案する。
論文 参考訳(メタデータ) (2022-02-22T20:17:46Z) - Crossover-SGD: A gossip-based communication in distributed deep learning
for alleviating large mini-batch problem and enhancing scalability [0.5249805590164902]
大規模ミニバッチ問題におけるゴシップ法の特徴について検討する。
セグメントワイズ通信による重量パラメータの遅延伝播を緩和するクロスオーバーSGDを提案する。
また,ゴシップに基づくコミュニケーション手法における労働者数を制限するため,階層的なコミュニケーションも行う。
論文 参考訳(メタデータ) (2020-12-30T15:39:13Z) - Solving Sparse Linear Inverse Problems in Communication Systems: A Deep
Learning Approach With Adaptive Depth [51.40441097625201]
疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。
提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
論文 参考訳(メタデータ) (2020-10-29T06:32:53Z) - Multi-Scale Positive Sample Refinement for Few-Shot Object Detection [61.60255654558682]
Few-shot Object Detection (FSOD) は、ディテクターがトレーニングインスタンスをほとんど持たない未確認のクラスに適応するのに役立つ。
FSODにおけるオブジェクトスケールを拡張化するためのMPSR(Multi-scale Positive Sample Refinement)アプローチを提案する。
MPSRは、オブジェクトピラミッドとして多スケールの正のサンプルを生成し、様々なスケールで予測を洗練させる。
論文 参考訳(メタデータ) (2020-07-18T09:48:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。