論文の概要: Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsification

• arxiv url: http://arxiv.org/abs/2507.05533v1
• Date: Mon, 07 Jul 2025 23:10:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-09 16:34:37.444945
• Title: Theoretical Learning Performance of Graph Neural Networks: The Impact of Jumping Connections and Layer-wise Sparsification
• Title（参考訳）: グラフニューラルネットワークの理論的学習性能:跳躍接続と層分割の影響
• Authors: Jiawei Sun, Hongkang Li, Meng Wang,
• Abstract要約: ジャンプ接続により、Graph Convolutional Networks (GCN) はオーバースムーシングを克服できる。 グラフスペーシフィケーションは、近傍の集約中にグラフ隣接行列のサブ行列を選択することで、計算要求を減らす。 本稿では,グラフスペーシフィケーションを用いた跳躍接続を用いたGCNの学習力学と一般化解析について述べる。
• 参考スコア（独自算出の注目度）: 13.18876315910168
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Jumping connections enable Graph Convolutional Networks (GCNs) to overcome over-smoothing, while graph sparsification reduces computational demands by selecting a sub-matrix of the graph adjacency matrix during neighborhood aggregation. Learning GCNs with graph sparsification has shown empirical success across various applications, but a theoretical understanding of the generalization guarantees remains limited, with existing analyses ignoring either graph sparsification or jumping connections. This paper presents the first learning dynamics and generalization analysis of GCNs with jumping connections using graph sparsification. Our analysis demonstrates that the generalization accuracy of the learned model closely approximates the highest achievable accuracy within a broad class of target functions dependent on the proposed sparse effective adjacency matrix $A^*$. Thus, graph sparsification maintains generalization performance when $A^*$ preserves the essential edges that support meaningful message propagation. We reveal that jumping connections lead to different sparsification requirements across layers. In a two-hidden-layer GCN, the generalization is more affected by the sparsified matrix deviations from $A^*$ of the first layer than the second layer. To the best of our knowledge, this marks the first theoretical characterization of jumping connections' role in sparsification requirements. We validate our theoretical results on benchmark datasets in deep GCNs.
• Abstract（参考訳）: 跳躍接続により、グラフ畳み込みネットワーク(GCN)はオーバースムースを克服し、グラフスカラー化はグラフ隣接行列のサブ行列を近傍集約中に選択することで計算要求を減少させる。 グラフスペーシフィケーションを用いたGCNの学習は、様々なアプリケーションで経験的な成功を示しているが、一般化の保証に関する理論的理解は、グラフスペーシフィケーションや跳躍接続を無視した既存の分析によって制限されている。 本稿では,グラフスペーシフィケーションを用いた跳躍接続を用いたGCNの学習力学と一般化解析について述べる。 解析の結果、学習モデルの一般化精度は、提案したスパース有効隣接行列である$A^*$に依存する対象関数の幅広いクラスにおいて、最も高い達成可能な精度を近似していることが示されている。 このように、グラフスペーシフィケーションは、意味のあるメッセージの伝搬をサポートする必要不可欠なエッジを$A^*$で保持する場合、一般化性能を維持する。 ジャンプ接続がレイヤ間で異なるスパーシフィケーション要件につながることが明らかになった。 2層GCNでは、一般化は第2層よりも第1層の$A^*$からの偏差によって影響を受ける。 我々の知る限りでは、これはスパーシフィケーション要求における跳躍接続の役割に関する最初の理論的特徴である。 深部GCNのベンチマークデータセットの理論的結果を検証する。

関連論文リスト

• Why Does Dropping Edges Usually Outperform Adding Edges in Graph Contrastive Learning? [54.44813218411879]
  グラフがネットワークにどのように適合するかを定量化するために、新しいメトリック、すなわちエラー通過率(EPR)を導入する。 理論的な結論とポジティブ・インセンティブ雑音のアイデアに触発されて、我々は新しいGCLアルゴリズム、エラー・パッシングに基づくグラフコントラスト学習(EPAGCL)を提案する。 EPRから得られる重みに基づいてエッジの追加とドロップによりビューを生成する。
  論文  参考訳（メタデータ） (2024-12-11T06:31:06Z)
• Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness [80.87683145376305]
  グラフニューラルネットワーク(GNN)は、様々なグラフ学習タスクに優れるが、大規模グラフに適用した場合、計算上の課題に直面している。 データレベルで空間を動的に操作するグラフスパーストレーニング(GST)を提案する。 GSTは、最大位相整合性と性能劣化のないスパースグラフを生成する。
  論文  参考訳（メタデータ） (2024-02-02T09:10:35Z)
• Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons [50.33260238739837]
  グラフネットワーク(GNN)は、グラフ構造化データから学習する際、顕著な能力を示した。 最適化と一般化の観点から、GNNと一般化を比較した分析の欠如がまだ残っている。
  論文  参考訳（メタデータ） (2023-06-24T10:21:11Z)
• A Graph is Worth 1-bit Spikes: When Graph Contrastive Learning Meets Spiking Neural Networks [35.35462459134551]
  SpikeGCLは、グラフのバイナライズされた1ビット表現を学ぶための新しいフレームワークである。 SpikeGCLが完全精度に匹敵するものであることを示すための理論的保証を提供する。
  論文  参考訳（メタデータ） (2023-05-30T16:03:11Z)
• Rethinking Graph Lottery Tickets: Graph Sparsity Matters [22.494153884469288]
  Lottery Ticket hypothesis (LTH) は、オリジナルの高密度ネットワークに対する競争性能を達成できる勝利チケットの存在を主張している。 本稿では,グラフ間隔が高い場合のGNN性能を改善するための2つの手法を提案する。
  論文  参考訳（メタデータ） (2023-05-03T15:35:15Z)
• Triple Sparsification of Graph Convolutional Networks without Sacrificing the Accuracy [4.023062108297454]
  我々は、GNNにおける全てのスペーサー化を研究するために、SparseGCNパイプラインを開発した。 一般的に使用されているベンチマークグラフデータセットの精度を犠牲にすることなく、埋め込み行列に最大11.6%の間隔を追加できることを実証的に示す。
  論文  参考訳（メタデータ） (2022-08-06T18:26:30Z)
• Principle of Relevant Information for Graph Sparsification [27.54740921723433]
  グラフスペーシフィケーションは、グラフの構造的特性を維持しながら、グラフのエッジ数を減らすことを目的としている。 我々は、関係情報原理(PRI)から着想を得て、グラフスカラー化の汎用的で効果的な情報理論の定式化を提案する。 本稿では,グラフスペーシフィケーション,グラフ正規化マルチタスク学習,医用画像由来の脳ネットワーク分類の3つの応用例を示す。
  論文  参考訳（メタデータ） (2022-05-31T21:00:42Z)

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

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