論文の概要: A Local Graph Limits Perspective on Sampling-Based GNNs
- arxiv url: http://arxiv.org/abs/2310.10953v1
- Date: Tue, 17 Oct 2023 02:58:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 17:54:20.875132
- Title: A Local Graph Limits Perspective on Sampling-Based GNNs
- Title（参考訳）: サンプリングベースGNNにおける局所グラフの視点
- Authors: Yeganeh Alimohammadi, Luana Ruiz, Amin Saberi
- Abstract要約: 本稿では,グラフニューラルネットワーク(GNN)を大規模入力グラフ上で学習するための理論的枠組みを提案する。
大規模な入力グラフの小さなサンプルを用いてサンプリングベースGNNのトレーニングから得られたパラメータが、グラフ全体において同じアーキテクチャをトレーニングした結果の$epsilon$近傍にあることを証明した。
- 参考スコア（独自算出の注目度）: 7.601210044390688
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a theoretical framework for training Graph Neural Networks (GNNs)
on large input graphs via training on small, fixed-size sampled subgraphs. This
framework is applicable to a wide range of models, including popular
sampling-based GNNs, such as GraphSAGE and FastGCN. Leveraging the theory of
graph local limits, we prove that, under mild assumptions, parameters learned
from training sampling-based GNNs on small samples of a large input graph are
within an $\epsilon$-neighborhood of the outcome of training the same
architecture on the whole graph. We derive bounds on the number of samples, the
size of the graph, and the training steps required as a function of $\epsilon$.
Our results give a novel theoretical understanding for using sampling in
training GNNs. They also suggest that by training GNNs on small samples of the
input graph, practitioners can identify and select the best models,
hyperparameters, and sampling algorithms more efficiently. We empirically
illustrate our results on a node classification task on large citation graphs,
observing that sampling-based GNNs trained on local subgraphs 12$\times$
smaller than the original graph achieve comparable performance to those trained
on the input graph.
- Abstract（参考訳）: 本稿では,大規模入力グラフ上でグラフニューラルネットワーク(gnns)を訓練するための理論的枠組みを提案する。
このフレームワークは、GraphSAGEやFastGCNといった一般的なサンプリングベースのGNNなど、幅広いモデルに適用できる。
グラフ局所限界の理論を活用し、穏やかな仮定の下で、大きな入力グラフの小さなサンプルでサンプリングベースのgnnのトレーニングから得られたパラメータが、グラフ全体の同じアーキテクチャをトレーニングした結果の$\epsilon$-neighborhood内にあることを証明する。
我々は、サンプルの数、グラフのサイズ、および$\epsilon$の関数として必要とされるトレーニングステップに基づいて、境界を導出する。
本研究は,GNNの学習におけるサンプリングに関する理論的考察である。
彼らはまた、入力グラフの小さなサンプルでgnnをトレーニングすることで、最適なモデル、ハイパーパラメータ、サンプリングアルゴリズムをより効率的に識別し、選択することができることを示唆している。
我々は,局所サブグラフで学習したサンプリングベースのgnnが,元のグラフよりも12$\times$小さく,入力グラフでトレーニングされたものと同等の性能が得られることを観察し,ノード分類タスクにおける結果について実証的に示す。
関連論文リスト
- Graph Structure Prompt Learning: A Novel Methodology to Improve Performance of Graph Neural Networks [13.655670509818144]
グラフネットワーク(GNN)のトレーニングを強化するための新しいグラフ構造Prompt Learning法(GPL)を提案する。
GPLはタスク非依存のグラフ構造損失を利用して、GNNが下流タスクを同時に解決しながら固有のグラフ特性を学習することを奨励している。
11の実世界のデータセットの実験では、ニューラルネットワークによってトレーニングされた後、GNNはノード分類、グラフ分類、エッジタスクにおいて、元のパフォーマンスを大幅に上回った。
論文 参考訳（メタデータ） (2024-07-16T03:59:18Z) - Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity [30.2972965458946]
グラフネットワーク(GNN)はノード分類などのグラフ学習問題に広く適用されている。
GNNの基盤となるグラフをより大きなサイズにスケールアップする場合、完全なグラフをトレーニングするか、あるいは完全なグラフの隣接とノードのメモリへの埋め込みを維持せざるを得ません。
本稿では,学習時間と記憶量がグラフサイズに比例して増加するスケッチベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-21T18:22:11Z) - GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels [81.93520935479984]
本稿では,ラベル付きおよび観測されたグラフに基づいて学習した特定のGNNモデルの性能を評価することを目的とした,新しい問題であるGNNモデル評価について検討する。
本稿では,(1) DiscGraph セット構築と(2) GNNEvaluator トレーニングと推論を含む2段階の GNN モデル評価フレームワークを提案する。
DiscGraphセットからの効果的なトレーニング監督の下で、GNNEvaluatorは、評価対象であるGNNモデルのノード分類精度を正確に推定することを学ぶ。
論文 参考訳（メタデータ） (2023-10-23T05:51:59Z) - GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks [2.4175455407547015]
グラフニューラルネットワークは、隣人からの情報を集約することでノードを表現することを学ぶ。
いくつかの既存手法では、ノードの小さなサブセットをサンプリングし、GNNをもっと大きなグラフにスケールすることで、この問題に対処している。
本稿では,GNNのトレーニングに不可欠なノードの集合を識別する適応サンプリング手法であるGRAPESを紹介する。
論文 参考訳（メタデータ） (2023-10-05T09:08:47Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳（メタデータ） (2022-10-27T16:00:45Z) - Similarity-aware Positive Instance Sampling for Graph Contrastive
Pre-training [82.68805025636165]
トレーニングセット内の既存グラフから直接正のグラフインスタンスを選択することを提案する。
私たちの選択は、特定のドメイン固有のペアワイズ類似度測定に基づいています。
さらに,ノードを動的にマスキングしてグラフ上に均等に分配する適応ノードレベルの事前学習手法を開発した。
論文 参考訳（メタデータ） (2022-06-23T20:12:51Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。
GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。
提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
論文 参考訳（メタデータ） (2022-03-03T09:53:53Z) - Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。
これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-07T15:05:59Z) - XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。
GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。
我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
論文 参考訳（メタデータ） (2020-06-03T23:52:43Z) - Ripple Walk Training: A Subgraph-based training framework for Large and
Deep Graph Neural Network [10.36962234388739]
本稿では,深部および大規模グラフニューラルネットワークのための一般的なサブグラフベーストレーニングフレームワークであるRipple Walk Training(RWT)を提案する。
RWTは、全グラフからサブグラフをサンプリングしてミニバッチを構成し、全GNNはミニバッチ勾配に基づいて更新される。
グラフの異なるサイズに関する大規模な実験は、様々なGNNを訓練する際のRWTの有効性と効率を実証している。
論文 参考訳（メタデータ） (2020-02-17T19:07:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。