論文の概要: Provably Convergent Subgraph-wise Sampling for Fast GNN Training
- arxiv url: http://arxiv.org/abs/2303.11081v1
- Date: Fri, 17 Mar 2023 05:16:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-21 15:37:37.128688
- Title: Provably Convergent Subgraph-wise Sampling for Fast GNN Training
- Title（参考訳）: 高速gnn訓練のための有理収束サブグラフサンプリング
- Authors: Jie Wang, Zhihao Shi, Xize Liang, Shuiwang Ji, Bin Li, and Feng Wu
- Abstract要約: 収束保証,すなわちローカルメッセージ補償(LMC)を用いた新しいサブグラフワイズサンプリング手法を提案する。
LMCは、後方パスのメッセージパスの定式化に基づいて、後方パスで破棄されたメッセージを検索する。
大規模ベンチマーク実験により、LCCは最先端のサブグラフワイドサンプリング法よりもはるかに高速であることが示された。
- 参考スコア（独自算出の注目度）: 63.530816506578674
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Subgraph-wise sampling -- a promising class of mini-batch training techniques
for graph neural networks (GNNs -- is critical for real-world applications.
During the message passing (MP) in GNNs, subgraph-wise sampling methods discard
messages outside the mini-batches in backward passes to avoid the well-known
neighbor explosion problem, i.e., the exponentially increasing dependencies of
nodes with the number of MP iterations. However, discarding messages may
sacrifice the gradient estimation accuracy, posing significant challenges to
their convergence analysis and convergence speeds. 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 first subgraph-wise sampling method with provable convergence. The key idea
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.
Moreover, LMC is applicable to various MP-based GNN architectures, including
convolutional GNNs (finite message passing iterations with different layers)
and recurrent GNNs (infinite message passing iterations with a shared layer).
Experiments on large-scale benchmarks demonstrate that LMC is significantly
faster than state-of-the-art subgraph-wise sampling methods.
- Abstract（参考訳）: グラフニューラルネットワーク(GNN)のための、有望なミニバッチトレーニングテクニックである、サブグラフワイズサンプリングは、現実世界のアプリケーションには不可欠である。
gnnのメッセージパッシング(mp)の間、サブグラフでサンプリングするメソッドは、よく知られた隣の爆発問題、つまりmpイテレーション数でノードの指数関数的に増加する依存性を避けるために、ミニバッチの外側のメッセージを後方に破棄する。
しかし、メッセージの破棄は勾配推定の精度を犠牲にし、収束解析と収束速度に大きな課題をもたらす可能性がある。
この課題に対処するために,収束保証,すなわちローカルメッセージ補償(LMC)を備えた新しいサブグラフワイズサンプリング手法を提案する。
我々の知る限り、LCCは証明可能な収束性を持つ最初のサブグラフワイドサンプリング法である。
鍵となるアイデアは、後方パスのメッセージパッシング定式化に基づいて、後方パスで破棄されたメッセージを取得することである。
前と後の両方で破棄されたメッセージの効率よく効果的な補償によって、LCCは正確なミニバッチ勾配を計算し、収束を加速する。
さらに、LCCは、畳み込みGNN(異なる層を持つ有限メッセージパッシングイテレーション)や繰り返しGNN(共有層を持つ無限メッセージパッシングイテレーション)など、様々なMPベースのGNNアーキテクチャに適用できる。
大規模ベンチマーク実験により、LCCは最先端のサブグラフワイドサンプリング法よりもはるかに高速であることが示された。
関連論文リスト
- Faster Convergence with Less Communication: Broadcast-Based Subgraph
Sampling for Decentralized Learning over Wireless Networks [32.914407967052114]
$texttBASS$はD-SGDの収束を加速するために設計された放送ベースのサブグラフサンプリング手法である。
既存のリンクベースのスケジューリング手法と比較して,送信スロットが少ないため,$texttBASS$はより高速な収束を可能にする。
論文 参考訳（メタデータ） (2024-01-24T20:00:23Z) - Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo [30.4930148381328]
拡散に基づくモンテカルロ (DMC) は、等尺条件を超えた一般目標分布から試料を採取する手法である。
DMCは、高い勾配の複雑さに遭遇し、その結果、得られたサンプルのエラー耐性$epsilon$に指数関数的に依存する。
本稿では,新しい再帰に基づくスコア推定法に基づくRS-DMCを提案する。
私たちのアルゴリズムは、人気のあるLangevinベースのアルゴリズムよりもはるかに高速です。
論文 参考訳（メタデータ） (2024-01-12T02:33:57Z) - AdjointDPM: Adjoint Sensitivity Method for Gradient Backpropagation of
Diffusion Probabilistic Models [136.58244210412352]
既存のカスタマイズ方法は、事前訓練された拡散確率モデルをユーザが提供する概念に合わせるために、複数の参照例にアクセスする必要がある。
本論文は、DPMカスタマイズの課題として、生成コンテンツ上で定義された差別化可能な指標が唯一利用可能な監督基準である場合に解決することを目的とする。
本稿では,拡散モデルから新しいサンプルを初めて生成するAdjointDPMを提案する。
次に、随伴感度法を用いて、損失の勾配をモデルのパラメータにバックプロパゲートする。
論文 参考訳（メタデータ） (2023-07-20T09:06:21Z) - LMC: Fast Training of GNNs via Subgraph Sampling with Provable
Convergence [7.135975474441761]
収束保証,すなわちローカルメッセージ補償(LMC)を用いた新しいサブグラフワイズサンプリング手法を提案する。
LMCは、後方パスのメッセージパスの定式化に基づいて、後方パスで破棄されたメッセージを検索する。
LMCは、効率の点で最先端のサブグラフワイドサンプリング法を著しく上回っている。
論文 参考訳（メタデータ） (2023-02-02T07:52:34Z) - Calibrate and Debias Layer-wise Sampling for Graph Convolutional
Networks [39.56471534442315]
本稿では,行列近似の観点からアプローチを再考する。
本稿では,サンプリング確率と効率的なデバイアスアルゴリズムを構築するための新しい原理を提案する。
改良は、推定分散の広範囲な解析と、一般的なベンチマークの実験によって実証される。
論文 参考訳（メタデータ） (2022-06-01T15:52:06Z) - VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using
Vector Quantization [70.8567058758375]
VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。
我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
論文 参考訳（メタデータ） (2021-10-27T11:48:50Z) - Autoregressive Belief Propagation for Decoding Block Codes [113.38181979662288]
誤り訂正符号の復号化にグラフニューラルネットワークを用いた最近の手法を再検討する。
本手法は,他手法がゼロワードでのみ学習できる対称性条件に反する。
1つの単語でトレーニングする余地がなく、関連するサンプル空間のごく一部でトレーニングできないにもかかわらず、効果的なトレーニングを実演する。
論文 参考訳（メタデータ） (2021-01-23T17:14:55Z) - MG-GCN: Fast and Effective Learning with Mix-grained Aggregators for
Training Large Graph Convolutional Networks [20.07942308916373]
グラフ畳み込みネットワーク(GCN)は、隣人層の情報を層ごとに集約することでノードの埋め込みを生成する。
GCNの高計算とメモリコストにより、大きなグラフのトレーニングが不可能になる。
MG-GCNと呼ばれる新しいモデルでは、精度、トレーニング速度、収束速度、メモリコストの点で最先端のパフォーマンスを実現している。
論文 参考訳（メタデータ） (2020-11-17T14:51:57Z) - Solving Sparse Linear Inverse Problems in Communication Systems: A Deep
Learning Approach With Adaptive Depth [51.40441097625201]
疎信号回復問題に対するエンドツーエンドの訓練可能なディープラーニングアーキテクチャを提案する。
提案手法は,出力するレイヤ数を学習し,各タスクのネットワーク深さを推論フェーズで動的に調整する。
論文 参考訳（メタデータ） (2020-10-29T06:32:53Z) - MLE-guided parameter search for task loss minimization in neural
sequence modeling [83.83249536279239]
ニューラル自己回帰シーケンスモデルは、さまざまな自然言語処理(NLP)タスクのシーケンスを生成するために使用される。
本稿では,現在のパラメータとその周辺における乱探索の混合である更新方向の分布から,最大至適勾配の分布をサンプリングする,最大至適誘導パラメータ探索(MGS)を提案する。
以上の結果から,MGS は,機械翻訳における最小リスクトレーニングに比べて,繰り返しや非終端の大幅な削減を図り,シーケンスレベルの損失を最適化できることが示唆された。
論文 参考訳（メタデータ） (2020-06-04T22:21:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。