論文の概要: Provably Convergent Subgraph-wise Sampling for Fast GNN Training

• arxiv url: http://arxiv.org/abs/2303.11081v2
• Date: Wed, 21 Aug 2024 02:54:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-22 23:25:53.993922
• Title: Provably Convergent Subgraph-wise Sampling for Fast GNN Training
• Title（参考訳）: 高速GNNトレーニングのための確率収束サブグラフワイドサンプリング
• Authors: Jie Wang, Zhihao Shi, Xize Liang, Defu Lian, Shuiwang Ji, Bin Li, Enhong Chen, Feng Wu,
• Abstract要約: 収束保証,すなわちローカルメッセージ補償(LMC)を用いた新しいサブグラフワイズサンプリング手法を提案する。 LMCは、後方パスのメッセージパスの定式化に基づいて、後方パスで破棄されたメッセージを検索する。 大規模ベンチマーク実験により、LCCは最先端のサブグラフワイドサンプリング法よりもはるかに高速であることが示された。
• 参考スコア（独自算出の注目度）: 122.68566970275683
• 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)の間、サブグラフワイズサンプリングメソッドは、後方のミニバッチの外でメッセージを破棄し、よく知られた隣の爆発問題を避ける。 しかし、メッセージの破棄は勾配推定の精度を犠牲にし、収束解析と収束速度に大きな課題を生じさせる可能性がある。 この課題に対処するために,収束保証,すなわちローカルメッセージ補償(LMC)を備えた新しいサブグラフワイズサンプリング手法を提案する。 我々の知る限り、LCCは証明可能な収束性を持つ最初のサブグラフワイドサンプリング法である。 キーとなるアイデアは、後方パスのメッセージパスの定式化に基づいて、破棄されたメッセージを後方パスで検索することである。 前と後の両方で破棄されたメッセージの効率よく効果的な補償によって、LCCは正確なミニバッチ勾配を計算し、収束を加速する。 さらに、LCCは、畳み込みGNN(異なる層を持つ有限メッセージパッシングイテレーション)や繰り返しGNN(共有層を持つ無限メッセージパッシングイテレーション)など、様々なMPベースのGNNアーキテクチャに適用できる。 大規模ベンチマーク実験により、LCCは最先端のサブグラフワイドサンプリング法よりもはるかに高速であることが示された。

関連論文リスト

• Nearest Neighbor Speculative Decoding for LLM Generation and Attribution [87.3259169631789]
  Nearest Speculative Decoding (NEST)は、任意の長さの実世界のテキストスパンをLM世代に組み込むことができ、それらのソースへの属性を提供する。 NESTは、様々な知識集約タスクにおいて、基本LMの生成品質と帰属率を大幅に向上させる。 さらに、NESTは、Llama-2-Chat 70Bに適用した場合の推論時間において1.8倍のスピードアップを達成することにより、生成速度を大幅に改善する。
  論文  参考訳（メタデータ） (2024-05-29T17:55:03Z)
• 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 [103.41269503488546]
  既存のカスタマイズ方法は、事前訓練された拡散確率モデルをユーザが提供する概念に合わせるために、複数の参照例にアクセスする必要がある。 本論文は、DPMカスタマイズの課題として、生成コンテンツ上で定義された差別化可能な指標が唯一利用可能な監督基準である場合に解決することを目的とする。 本稿では,拡散モデルから新しいサンプルを初めて生成するAdjointDPMを提案する。 次に、随伴感度法を用いて、損失の勾配をモデルのパラメータにバックプロパゲートする。
  論文  参考訳（メタデータ） (2023-07-20T09:06:21Z)
• LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence [8.630426703200541]
  収束保証,すなわちローカルメッセージ補償(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)
• 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)

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

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