論文の概要: On the Importance of Sampling in Learning Graph Convolutional Networks
- arxiv url: http://arxiv.org/abs/2103.02696v1
- Date: Wed, 3 Mar 2021 21:31:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-05 15:12:40.678926
- Title: On the Importance of Sampling in Learning Graph Convolutional Networks
- Title（参考訳）: グラフ畳み込みネットワーク学習におけるサンプリングの重要性について
- Authors: Weilin Cong, Morteza Ramezani, Mehrdad Mahdavi
- Abstract要約: Graph Convolutional Networks (GCNs) は、様々なグラフ関連アプリケーションにおいて、目覚ましい進歩を遂げている。
その成功にもかかわらず、大きなグラフ上でのgcnのトレーニングは計算とメモリの問題に苦しむ。
メモリ予算下で任意のサンプリングメソッドを高速化できる一般的なtextbftextitdoubly variance reductionスキーマを記述・解析する。
- 参考スコア（独自算出の注目度）: 13.713485304798368
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph Convolutional Networks (GCNs) have achieved impressive empirical
advancement across a wide variety of graph-related applications. Despite their
great success, training GCNs on large graphs suffers from computational and
memory issues. A potential path to circumvent these obstacles is sampling-based
methods, where at each layer a subset of nodes is sampled. Although recent
studies have empirically demonstrated the effectiveness of sampling-based
methods, these works lack theoretical convergence guarantees under realistic
settings and cannot fully leverage the information of evolving parameters
during optimization. In this paper, we describe and analyze a general
\textbf{\textit{doubly variance reduction}} schema that can accelerate any
sampling method under the memory budget. The motivating impetus for the
proposed schema is a careful analysis for the variance of sampling methods
where it is shown that the induced variance can be decomposed into node
embedding approximation variance (\emph{zeroth-order variance}) during forward
propagation and layerwise-gradient variance (\emph{first-order variance})
during backward propagation. We theoretically analyze the convergence of the
proposed schema and show that it enjoys an $\mathcal{O}(1/T)$ convergence rate.
We complement our theoretical results by integrating the proposed schema in
different sampling methods and applying them to different large real-world
graphs. Code is public available
at~\url{https://github.com/CongWeilin/SGCN.git}.
- Abstract（参考訳）: Graph Convolutional Networks (GCNs) は、様々なグラフ関連アプリケーションにおいて、目覚ましい進歩を遂げている。
大きなグラフでのGCNのトレーニングは、大きな成功にもかかわらず、計算とメモリの問題に悩まされている。
これらの障害を回避する潜在的パスはサンプリングベースのメソッドで、各レイヤにノードのサブセットがサンプリングされる。
近年の研究ではサンプリングベース手法の有効性が実証されているが、現実的な設定下では理論的収束保証がなく、最適化中に進化するパラメータの情報を完全に活用できない。
本稿では、メモリ予算の下で任意のサンプリングメソッドを加速できる一般の \textbf{\textit{二重分散還元}} スキーマを記述および分析する。
提案手法は, 前方伝搬時のノード埋め込み近似分散(\emph{zeroth-order variance})と後方伝搬時の層方向勾配分散(\emph{first-order variance})に, 誘導分散が分解可能であることを示すサンプリング手法の分散に対する注意深い解析である。
提案したスキーマの収束を理論的に解析し,$\mathcal{O}(1/T)$収束率を満足することを示す。
我々は,提案するスキーマを異なるサンプリング法に統合し,異なる実世界グラフに適用することにより,理論結果を補完する。
コードは~\url{https://github.com/CongWeilin/SGCN.git}で公開されている。
関連論文リスト
- Topology-Aware Dynamic Reweighting for Distribution Shifts on Graph [24.44321658238713]
グラフニューラルネットワーク(GNN)は、ノード分類タスクに広く使用されているが、トレーニングやテストノードが異なるディストリビューションから来ると、一般化に失敗することが多い。
トレーニング中にWasserstein空間の勾配流を通じて標本重量を動的に調整するTopology-Aware Dynamic Reweighting (TAR) フレームワークを導入する。
フレームワークの優位性は、4つのグラフOODデータセットと3つのクラス不均衡ノード分類データセットの標準テストによって実証される。
論文 参考訳（メタデータ） (2024-06-03T07:32:05Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - Graph Out-of-Distribution Generalization with Controllable Data
Augmentation [51.17476258673232]
グラフニューラルネットワーク(GNN)は,グラフ特性の分類において異常な性能を示した。
トレーニングとテストデータの選択バイアスが原因で、分散偏差が広まっています。
仮想サンプルの分布偏差を測定するためのOODキャリブレーションを提案する。
論文 参考訳（メタデータ） (2023-08-16T13:10:27Z) - MixupExplainer: Generalizing Explanations for Graph Neural Networks with
Data Augmentation [6.307753856507624]
グラフニューラルネットワーク(GNN)は、グラフ構造化データから学習する能力によって、注目を集めている。
GNN予測を理解するために、ポストホックなインスタンスレベルの説明法が提案されている。
我々は,既存手法における分布シフト問題の存在に光を当て,説明の質に影響を及ぼす。
論文 参考訳（メタデータ） (2023-07-15T15:46:38Z) - From Spectral Graph Convolutions to Large Scale Graph Convolutional
Networks [0.0]
グラフ畳み込みネットワーク(GCN)は、様々なタスクにうまく適用された強力な概念であることが示されている。
古典グラフ理論の関連部分を含むGCNの定義への道を開いた理論を考察する。
論文 参考訳（メタデータ） (2022-07-12T16:57:08Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。
提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。
いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
論文 参考訳（メタデータ） (2021-12-15T01:45:32Z) - Scaling Up Graph Neural Networks Via Graph Coarsening [18.176326897605225]
グラフニューラルネットワーク(GNN)のスケーラビリティは、マシンラーニングにおける大きな課題のひとつだ。
本稿では,GNNのスケーラブルなトレーニングにグラフ粗大化を用いることを提案する。
既成の粗大化法を単純に適用すれば,分類精度を著しく低下させることなく,ノード数を最大10倍に削減できることを示す。
論文 参考訳（メタデータ） (2021-06-09T15:46:17Z) - Minimal Variance Sampling with Provable Guarantees for Fast Training of
Graph Neural Networks [22.618779809748435]
既存のサンプリング手法は主にグラフ構造情報に基づいており、最適化の動的性を無視する。
最小分散のノードを適応的にサンプリングする(近似)勾配情報を利用する分離分散低減戦略を提案する。
提案手法は,小バッチサイズが小さい場合でも,より高速な収束率とより優れた一般化を必要とすることを理論的,実証的に示す。
論文 参考訳（メタデータ） (2020-06-24T16:49:29Z) - Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
グラフ畳み込みネットワーク(GCN)の訓練を高速化するために, ばらつきを低減したサンプリングアルゴリズムが提案されている。
これらのサンプリングアルゴリズムは、グラフ注意ネットワーク(GAT)のような固定重みよりも学習重量を含む、より一般的なグラフニューラルネットワーク(GNN)には適用できない。
論文 参考訳（メタデータ） (2020-06-10T12:48:37Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。