論文の概要: Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural
Networks
- arxiv url: http://arxiv.org/abs/2302.02922v1
- Date: Mon, 6 Feb 2023 16:54:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-07 16:03:33.612691
- Title: Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural
Networks
- Title（参考訳）: グラフニューラルネットワークにおけるエッジモデルスパース学習の有用性
- Authors: Shuai Zhang, Meng Wang, Pin-Yu Chen, Sijia Liu, Songtao Lu, Miao Liu
- Abstract要約: 本稿では,グラフニューラルネットワーク(GNN)における結合エッジモデルスパース学習の理論的特徴について述べる。
解析学的には、重要なノードをサンプリングし、最小のマグニチュードでプルーニングニューロンをサンプリングすることで、サンプルの複雑さを減らし、テスト精度を損なうことなく収束を改善することができる。
- 参考スコア（独自算出の注目度）: 89.28881869440433
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Due to the significant computational challenge of training large-scale graph
neural networks (GNNs), various sparse learning techniques have been exploited
to reduce memory and storage costs. Examples include \textit{graph
sparsification} that samples a subgraph to reduce the amount of data
aggregation and \textit{model sparsification} that prunes the neural network to
reduce the number of trainable weights. Despite the empirical successes in
reducing the training cost while maintaining the test accuracy, the theoretical
generalization analysis of sparse learning for GNNs remains elusive. To the
best of our knowledge, this paper provides the first theoretical
characterization of joint edge-model sparse learning from the perspective of
sample complexity and convergence rate in achieving zero generalization error.
It proves analytically that both sampling important nodes and pruning neurons
with the lowest-magnitude can reduce the sample complexity and improve
convergence without compromising the test accuracy. Although the analysis is
centered on two-layer GNNs with structural constraints on data, the insights
are applicable to more general setups and justified by both synthetic and
practical citation datasets.
- Abstract（参考訳）: 大規模グラフニューラルネットワーク(GNN)をトレーニングする際の大きな計算課題のため、メモリとストレージコストを削減するために、さまざまなスパース学習技術が活用されている。
例えば、データ集約量を減らすためにサブグラフをサンプリングする \textit{graph sparsification} や、トレーニング可能な重みを減らすためにニューラルネットワークを脅かす \textit{model sparsification} などがある。
テスト精度を維持しながらトレーニングコストを削減した経験的成功にもかかわらず、GNNのためのスパース学習の理論的一般化分析はいまだ解明されていない。
そこで本研究では, 一般化誤差をゼロにする際の, サンプルの複雑性と収束率の観点から, 結合エッジモデルスパース学習の理論的評価を行った。
解析学的には、重要なノードをサンプリングし、最小のマグニチュードでプルーニングニューロンをサンプリングすることで、サンプルの複雑さを減らし、テスト精度を損なうことなく収束を改善することができる。
この分析は、データに構造的制約を持つ2層GNNを中心にしているが、より一般的な設定に適用でき、合成および実用的な引用データセットの両方で正当化される。
関連論文リスト
- Learning and generalization of one-hidden-layer neural networks, going
beyond standard Gaussian data [14.379261299138147]
本稿では,入力特徴がガウス混合モデルに従えば,一層ニューラルネットワークの収束と反復を解析する。
本論文は,入力分布がサンプルに与える影響と学習率に与える影響を初めて特徴付ける。
論文 参考訳（メタデータ） (2022-07-07T23:27:44Z) - Generalization Guarantee of Training Graph Convolutional Networks with
Graph Topology Sampling [83.77955213766896]
グラフ畳み込みネットワーク(GCN)は近年,グラフ構造化データの学習において大きな成功を収めている。
スケーラビリティ問題に対処するため、Gsの学習におけるメモリと計算コストを削減するため、グラフトポロジサンプリングが提案されている。
本稿では,3層GCNのトレーニング(最大)におけるグラフトポロジサンプリングの最初の理論的正当性について述べる。
論文 参考訳（メタデータ） (2022-07-07T21:25:55Z) - How does unlabeled data improve generalization in self-training? A
one-hidden-layer theoretical analysis [93.37576644429578]
この研究は、既知の反復的自己学習パラダイムに関する最初の理論的分析を確立する。
トレーニング収束と一般化能力の両面で、ラベルなしデータの利点を実証する。
また、浅部ニューラルネットワークから深部ニューラルネットワークへの実験は、我々の確立した自己学習に関する理論的知見の正しさを正当化するものである。
論文 参考訳（メタデータ） (2022-01-21T02:16:52Z) - Tackling Oversmoothing of GNNs with Contrastive Learning [35.88575306925201]
グラフニューラルネットワーク(GNN)は、グラフデータと表現学習能力の包括的な関係を統合する。
オーバースムーシングはノードの最終的な表現を識別不能にし、ノード分類とリンク予測性能を劣化させる。
本稿では,TGCL(Topology-Guided Graph Contrastive Layer)を提案する。
論文 参考訳（メタデータ） (2021-10-26T15:56:16Z) - Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity
on Pruned Neural Networks [79.74580058178594]
目的関数の幾何学的構造を解析することにより、刈り取られたニューラルネットワークを訓練する性能を解析する。
本稿では,ニューラルネットワークモデルがプルーニングされるにつれて,一般化が保証された望ましいモデル近傍の凸領域が大きくなることを示す。
論文 参考訳（メタデータ） (2021-10-12T01:11:07Z) - Topological obstructions in neural networks learning [67.8848058842671]
損失勾配関数フローのグローバル特性について検討する。
損失関数とそのモースコンプレックスの位相データ解析を用いて,損失面の大域的特性と勾配軌道に沿った局所的挙動を関連付ける。
論文 参考訳（メタデータ） (2020-12-31T18:53:25Z) - A Revision of Neural Tangent Kernel-based Approaches for Neural Networks [34.75076385561115]
ニューラルネットワークカーネルを使用して、ネットワークが任意の有限トレーニングサンプルに完全に適合できることを示す。
単純で解析的なカーネル関数は、完全に訓練されたネットワークと同等のものとして導出された。
より厳密な分析により,スケーリングの問題が解決され,元のNTKに基づく結果の検証が可能となった。
論文 参考訳（メタデータ） (2020-07-02T05:07:55Z) - Fast Learning of Graph Neural Networks with Guaranteed Generalizability:
One-hidden-layer Case [93.37576644429578]
グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。
回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
論文 参考訳（メタデータ） (2020-06-25T00:45:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。