論文の概要: Generalization Guarantee of Training Graph Convolutional Networks with
Graph Topology Sampling
- arxiv url: http://arxiv.org/abs/2207.03584v1
- Date: Thu, 7 Jul 2022 21:25:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-11 14:02:40.363320
- 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のトレーニング(最大)におけるグラフトポロジサンプリングの最初の理論的正当性について述べる。
- 参考スコア(独自算出の注目度): 89.83096926339458
- 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の理論的解析において未探索の層間重みの非凸相互作用に対処する。
本稿では,グラフ構造とトポロジサンプリングが一般化性能および試料の複雑さに与える影響を明示し,数値実験により理論的知見を正当化する。
関連論文リスト
- Tensor-view Topological Graph Neural Network [16.433092191206534]
グラフニューラルネットワーク(GNN)は最近、グラフ学習において注目を集めている。
既存のGNNは、各ノード周辺の非常に限られた地区からのローカル情報のみを使用する。
本稿では,単純かつ効果的な深層学習のクラスであるTopological Graph Neural Network (TTG-NN)を提案する。
実データ実験により,提案したTTG-NNは,グラフベンチマークにおいて20の最先端手法より優れていた。
論文 参考訳(メタデータ) (2024-01-22T14:55:01Z) - Weisfeiler and Lehman Go Paths: Learning Topological Features via Path
Complexes [5.002862787862848]
グラフニューラルネットワーク(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) - Uncovering the Structural Fairness in Graph Contrastive Learning [87.65091052291544]
グラフコントラスト学習(GCL)は、ノード表現を学習するための有望な自己教師型アプローチとして登場した。
GCL法で得られた表現は,GCN法で学習した表現よりも既に公平であることを示す。
我々は、低次ノードと高次ノードに異なる戦略を適用し、GRAph contrastive learning for Degree bias (GRADE)と呼ばれるグラフ拡張手法を考案した。
論文 参考訳(メタデータ) (2022-10-06T15:58:25Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。