論文の概要: Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspective
- arxiv url: http://arxiv.org/abs/2605.13597v1
- Date: Wed, 13 May 2026 14:32:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-14 23:30:28.108112
- Title: Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspective
- Title（参考訳）: グラフニューラルネットワークにおける一般化の再考:構造的複雑性の観点から
- Authors: Peiyao Wang, Liang Bai, Xian Yang, Richard Yi Da Xu, Jiye Liang,
- Abstract要約: グラフニューラルネットワーク(GNN)は、グラフ構造化データから学習するための基本的なツールとして登場した。
グラフ構造は実際に一般化に影響を与えますか?
最初の質問に答え、直観を検証するために、予測プロセスにより多くのエッジを組み込むことで、入力表現が出力モデルに過度に同調するように変換され、過度な適合が生じることを理論的に証明する。
2つ目の問題に対処するために、有効エッジの数に基づいて構造的複雑性尺度を定式化し、Radecher複雑性に基づく一般化境界を導出する。
- 参考スコア（独自算出の注目度）: 41.727617218821386
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph neural networks (GNNs) have emerged as a fundamental tool for learning from graph-structured data, achieving strong performance across a wide range of applications. However, understanding their generalization capabilities remains challenging due to the complex structural dependencies inherent in such data. Existing generalization analyses largely follow the classical machine learning paradigm, focusing primarily on model complexity while overlooking the fundamental role of graph structure. Therefore, in this work, we systematically investigate this role by asking: does the graph structure actually influence generalization, and if so, by how much? To answer the first question and validate our intuition, we theoretically prove that incorporating more edges into the prediction process transforms the input representations to be overly accommodating to the output model, thereby inducing overfitting. To address the second question, we formulate a structural complexity measure based on the number of effective edges and derive a Rademacher complexity-based generalization bound. In doing so, we demonstrate that GNN generalization depends explicitly on structural complexity, alongside traditional parameter-dependent factors. Motivated by these theoretical findings, we propose a structural entropy regularization method. This approach controls structural complexity by regulating effective edges to balance underfitting and overfitting, ultimately improving the generalization performance of GNNs.
- Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフ構造化データから学習するための基本的なツールとして登場し、幅広いアプリケーションで強力なパフォーマンスを実現している。
しかし、そのようなデータに固有の複雑な構造的依存関係のため、それらの一般化能力を理解することは依然として困難である。
既存の一般化分析は、グラフ構造の基本的役割を見越しながら、主にモデルの複雑さに焦点を当てた古典的な機械学習パラダイムに大きく従っている。
したがって、本研究では、グラフ構造が実際に一般化に影響を及ぼすか、もしそうであれば、どの程度の量で、この役割を体系的に研究する。
最初の質問に答え、直観を検証するために、予測プロセスにより多くのエッジを組み込むことで、入力表現が出力モデルに過度に同調するように変換され、過度な適合が生じることを理論的に証明する。
2つ目の問題に対処するために、有効エッジの数に基づいて構造的複雑性尺度を定式化し、Radecher複雑性に基づく一般化境界を導出する。
このようにして、GNNの一般化は、従来のパラメータ依存因子とともに、構造的複雑性に明示的に依存することを示した。
これらの理論的な知見により,構造エントロピー正則化法を提案する。
このアプローチは、効率の良いエッジを規制して過度な適合と過度な適合のバランスを保ち、最終的にGNNの一般化性能を改善することによって構造的複雑性を制御する。
関連論文リスト
- Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks [21.139538521229273]
グラフ畳み込みネットワーク(GCN)のための位相対応PAC-Bayesianノルムに基づく一般化フレームワークを提案する。
空間的およびスペクトル的な視点から、感度行列の異なる構造を付与することにより、グラフ構造が埋め込まれた一般化誤差の族を導出する。
特に,提案フレームワークはグラフ構造特性を一般化解析に明示的に統合し,GNN一般化挙動の統一検査を可能にする。
論文 参考訳（メタデータ） (2026-04-12T09:52:27Z) - GADPN: Graph Adaptive Denoising and Perturbation Networks via Singular Value Decomposition [6.24191713518868]
GADPNはグラフ構造学習フレームワークであり、低ランクな denoising と一般化された構造摂動によってグラフトポロジーを適応的に洗練する。
最先端のパフォーマンスを実現し、効率を大幅に向上させる。
グラフ構造を強固に学習する能力を検証することで、不合理なグラフに挑戦する上で特に大きな利益をもたらす。
論文 参考訳（メタデータ） (2026-01-13T05:25:32Z) - Towards Bridging Generalization and Expressivity of Graph Neural Networks [11.560730203511111]
グラフニューラルネットワーク(GNN)における表現性と一般化の関係について検討する。
本稿では,GNNの一般化と,それらが捉えることのできるグラフ構造の分散を結合する新しいフレームワークを提案する。
我々は,クラス内濃度とクラス間分離のトレードオフを明らかにする。
論文 参考訳（メタデータ） (2024-10-14T00:31:16Z) - Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
本稿では,グラフ構造情報をメッセージパッシングなしで学習するグラフ構造自己コントラスト(GSSC)フレームワークを提案する。
提案するフレームワークは,構造情報を事前知識として暗黙的にのみ組み込む,MLP(Multi-Layer Perceptrons)に基づいている。
これはまず、近傍の潜在的非形式的あるいはノイズの多いエッジを取り除くために構造的スペーシングを適用し、その後、スペーシングされた近傍で構造的自己コントラストを行い、ロバストなノード表現を学ぶ。
論文 参考訳（メタデータ） (2024-09-09T12:56:02Z) - Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms [15.473123662393169]
ディープニューラルネットワーク(DNN)は、顕著な一般化特性を示す。
これらの能力の源泉は依然として解明され、確立された統計的学習理論を否定している。
近年の研究では、訓練軌跡の性質が一般化の指標であることが示されている。
論文 参考訳（メタデータ） (2024-07-11T17:56:03Z) - On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games [55.2480439325792]
逐次的意思決定問題において、情報構造とは、異なる時点に発生するシステム内の事象が相互にどのように影響するかを記述するものである。
対照的に、現実のシーケンシャルな意思決定問題は通常、システム変数の複雑で時間的な相互依存を伴う。
情報構造を明示する新しい強化学習モデルを定式化する。
論文 参考訳（メタデータ） (2024-03-01T21:28:19Z) - On the Expressiveness and Generalization of Hypergraph Neural Networks [77.65788763444877]
この拡張抽象化はハイパーグラフニューラルネットワーク(HyperGNN)の表現性、学習、および(構造的)一般化を分析するためのフレームワークを記述する。
具体的には、HyperGNNが有限データセットからどのように学習し、任意の入力サイズのグラフ推論問題に構造的に一般化するかに焦点を当てる。
論文 参考訳（メタデータ） (2023-03-09T18:42:18Z) - Out-of-distributional risk bounds for neural operators with applications
to the Helmholtz equation [6.296104145657063]
既存のニューラル演算子(NO)は、全ての物理問題に対して必ずしもうまく機能しない。
非線形作用素の波動速度を解にマッピングする実験的な近似を可能にするNOのサブファミリーを提案する。
本実験は, 深度導入の一般化と関連性において, ある種のサプライズを明らかにするものである。
我々は、NOsのサブファミリーのハイパーネットワークバージョンを、前述のフォワード演算子のサロゲートモデルとして提案することで結論付ける。
論文 参考訳（メタデータ） (2023-01-27T03:02:12Z) - Amortized Inference for Causal Structure Learning [72.84105256353801]
因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。
本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。
我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
論文 参考訳（メタデータ） (2022-05-25T17:37:08Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳（メタデータ） (2021-06-09T08:05:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。