論文の概要: Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling

• arxiv url: http://arxiv.org/abs/2207.03584v2
• Date: Sun, 10 Dec 2023 16:50:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-13 03:31:09.733163
• Title: Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling
• Title（参考訳）: グラフトポロジサンプリングを用いたトレーニンググラフ畳み込みネットワークの一般化保証
• Authors: Hongkang Li, Meng Wang, Sijia Liu, Pin-Yu Chen, Jinjun Xiong
• Abstract要約: グラフ畳み込みネットワーク(GCN)は近年,グラフ構造化データの学習において大きな成功を収めている。 スケーラビリティ問題に対処するため、Gsの学習におけるメモリと計算コストを削減するため、グラフトポロジサンプリングが提案されている。 本稿では,3層GCNのトレーニング(最大)におけるグラフトポロジサンプリングの最初の理論的正当性について述べる。
• 参考スコア（独自算出の注目度）: 83.77955213766896
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graph-structured data. To address its scalability issue due to the recursive embedding of neighboring features, graph topology sampling has been proposed to reduce the memory and computational cost of training GCNs, and it has achieved comparable test performance to those without topology sampling in many empirical studies. To the best of our knowledge, this paper provides the first theoretical justification of graph topology sampling in training (up to) three-layer GCNs for semi-supervised node classification. We formally characterize some sufficient conditions on graph topology sampling such that GCN training leads to a diminishing generalization error. Moreover, our method tackles the nonconvex interaction of weights across layers, which is under-explored in the existing theoretical analyses of GCNs. This paper characterizes the impact of graph structures and topology sampling on the generalization performance and sample complexity explicitly, and the theoretical findings are also justified through numerical experiments.
• Abstract（参考訳）: グラフ畳み込みネットワーク(GCN)は近年,グラフ構造化データの学習において大きな成功を収めている。 隣り合う機能の再帰的埋め込みによるスケーラビリティの問題に対処するために、gcnのトレーニングのメモリと計算コストを削減するためにグラフトポロジサンプリングが提案されており、多くの実証研究でトポロジーサンプリングのないものと同等のテスト性能を達成している。 本稿では,半教師付きノード分類のための(最大)3層gcnの学習におけるグラフトポロジーサンプリングの理論的正当化について述べる。 グラフトポロジサンプリングにおいて,GCNトレーニングが一般化誤差を減少させるような条件を公式に特徴付ける。 さらに,本手法は,既存のGCNの理論的解析において未探索の層間重みの非凸相互作用に対処する。 本稿では,グラフ構造とトポロジサンプリングが一般化性能および試料の複雑さに与える影響を明示し,数値実験により理論的知見を正当化する。

関連論文リスト

• Understanding the Effect of GCN Convolutions in Regression Tasks [8.299692647308323]
  グラフ畳み込みネットワーク(GCN)は、グラフ上の関数をモデル化する機械学習において重要な手法となっている。 本稿では、同好ネットワーク上の回帰タスクにおける畳み込み演算子の影響を公式解析する。
  論文  参考訳（メタデータ） (2024-10-26T04:19:52Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。 本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
  論文  参考訳（メタデータ） (2024-06-04T05:30:16Z)
• On the Topology Awareness and Generalization Performance of Graph Neural Networks [6.598758004828656]
  我々は,GNNのトポロジ的認識をいかなるトポロジ的特徴においても特徴付けるための包括的枠組みを導入する。 本研究は,各ベンチマークデータセットの経路距離を最短とする内在グラフを用いたケーススタディである。
  論文  参考訳（メタデータ） (2024-03-07T13:33:30Z)
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes [4.23480641508611]
  グラフニューラルネットワーク(GNN)は理論上、1-Weisfeiler-Lehmanテストによって拘束される。 本研究では, トポロジ的メッセージパッシング過程において, グラフ内の単純な経路に着目し, 新たな視点を示す。
  論文  参考訳（メタデータ） (2023-08-13T19:45:20Z)
• Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks [89.28881869440433]
  本稿では,グラフニューラルネットワーク(GNN)における結合エッジモデルスパース学習の理論的特徴について述べる。 解析学的には、重要なノードをサンプリングし、最小のマグニチュードでプルーニングニューロンをサンプリングすることで、サンプルの複雑さを減らし、テスト精度を損なうことなく収束を改善することができる。
  論文  参考訳（メタデータ） (2023-02-06T16:54:20Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• SStaGCN: Simplified stacking based graph convolutional networks [2.556756699768804]
  グラフ畳み込みネットワーク(GCN)は、様々なグラフ構造データ学習タスクにおいて広く研究されている強力なモデルである。 本稿では, SStaGCN (Simplified stacking based GCN) と呼ばれる新しいGCNを提案する。 SStaGCNはGCNの過密問題を効果的に軽減できることを示す。
  論文  参考訳（メタデータ） (2021-11-16T05:00:08Z)
• Wide Graph Neural Networks: Aggregation Provably Leads to Exponentially Trainability Loss [17.39060566854841]
  グラフ畳み込みネットワーク(GCN)とその変種は、グラフ構造化データを扱う上で大きな成功を収めた。 深いGCNが過スムージング問題に苦しむことはよく知られています。 深部GCNの表現性と訓練性を研究するための理論的分析はほとんど行われていない。
  論文  参考訳（メタデータ） (2021-03-03T11:06:12Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  グラフ畳み込みは近傍の集約を行い、最も重要なグラフ操作の1つである。 いくつかの最近の研究で、この性能劣化は過度に滑らかな問題に起因している。 本研究では,大きな受容領域からの情報を適応的に組み込むディープ適応グラフニューラルネットワーク(DAGNN)を提案する。
  論文  参考訳（メタデータ） (2020-07-18T01:11:14Z)
• Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning via Gaussian Processes [144.6048446370369]
  グラフ畳み込みニューラルネットワーク(GCN)は近年,グラフに基づく半教師付き半教師付き分類において有望な結果を示した。 グラフに基づく半教師付き学習のためのGCN(GPGC)を用いたGP回帰モデルを提案する。 GPGCを評価するための広範囲な実験を行い、他の最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-02-26T10:02:32Z)

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

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