論文の概要: Towards Bridging Generalization and Expressivity of Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2410.10051v1
• Date: Mon, 14 Oct 2024 00:31:16 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 03:23:50.249780
• Title: Towards Bridging Generalization and Expressivity of Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークのブリッジ一般化と表現性に向けて
• Authors: Shouheng Li, Floris Geerts, Dongwoo Kim, Qing Wang,
• Abstract要約: グラフニューラルネットワーク(GNN)における表現性と一般化の関係について検討する。 本稿では,GNNの一般化と,それらが捉えることのできるグラフ構造の分散を結合する新しいフレームワークを提案する。 我々は,クラス内濃度とクラス間分離のトレードオフを明らかにする。
• 参考スコア（独自算出の注目度）: 11.560730203511111
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Expressivity and generalization are two critical aspects of graph neural networks (GNNs). While significant progress has been made in studying the expressivity of GNNs, much less is known about their generalization capabilities, particularly when dealing with the inherent complexity of graph-structured data. In this work, we address the intricate relationship between expressivity and generalization in GNNs. Theoretical studies conjecture a trade-off between the two: highly expressive models risk overfitting, while those focused on generalization may sacrifice expressivity. However, empirical evidence often contradicts this assumption, with expressive GNNs frequently demonstrating strong generalization. We explore this contradiction by introducing a novel framework that connects GNN generalization to the variance in graph structures they can capture. This leads us to propose a $k$-variance margin-based generalization bound that characterizes the structural properties of graph embeddings in terms of their upper-bounded expressive power. Our analysis does not rely on specific GNN architectures, making it broadly applicable across GNN models. We further uncover a trade-off between intra-class concentration and inter-class separation, both of which are crucial for effective generalization. Through case studies and experiments on real-world datasets, we demonstrate that our theoretical findings align with empirical results, offering a deeper understanding of how expressivity can enhance GNN generalization.
• Abstract（参考訳）: 表現性と一般化はグラフニューラルネットワーク(GNN)の2つの重要な側面である。 GNNの表現性の研究において大きな進歩があったが、特にグラフ構造化データの本質的な複雑さを扱う場合、その一般化能力についてはあまり知られていない。 本稿では,GNNにおける表現性と一般化の複雑な関係について述べる。 理論的な研究は2つの間のトレードオフを予想している:高度に表現力のあるモデルが過度に適合するリスク、一般化に焦点を当てたモデルが表現性を犠牲にする可能性がある。 しかしながら、実証的な証拠はしばしばこの仮定に矛盾し、表現的なGNNはしばしば強い一般化を示す。 我々は、GNN一般化と、それらが捉えることができるグラフ構造の分散を結びつける新しいフレームワークを導入することで、この矛盾を探求する。 これにより、グラフ埋め込みの構造的性質を上界表現力の観点から特徴づける、$k$分散マージンに基づく一般化が提案される。 我々の分析は特定のGNNアーキテクチャに依存しないので、GNNモデルに広く適用できます。 さらに,クラス内濃度とクラス間分離のトレードオフを明らかにする。 実世界のデータセットに関するケーススタディと実験を通じて、我々の理論的結果は経験的な結果と一致し、表現性がGNNの一般化をいかに促進できるかをより深く理解することを示した。

関連論文リスト

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。 我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。 最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
  論文  参考訳（メタデータ） (2024-09-08T18:55:57Z)
• Generalization of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  グラフニューラルネットワーク(GNN)は、その一般化能力によってサポートされている様々なタスクにおいて、その効果を実証している。 本稿では,多様体モデルから生成される幾何グラフで動作するGNNについて検討する。 本稿では,そのようなモデルミスマッチの存在下でのGNN一般化の堅牢性を明らかにする。
  論文  参考訳（メタデータ） (2024-08-25T16:00:44Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Generalization of Graph Neural Networks through the Lens of Homomorphism [7.223313563198697]
  本稿では,グラフ・ニューラル・ネットワーク(GNN)の一般化を,グラフ準同型のエントロピー解析という新たな視点で研究することを提案する。 グラフ準同型と情報理論測度を結びつけることにより、グラフ分類とノード分類の両方の一般化境界を導出する。 これらの境界は、パス、サイクル、傾きなど、様々なグラフ構造に固有の微妙さを捉えることができる。
  論文  参考訳（メタデータ） (2024-03-10T03:51:59Z)
• Graph Out-of-Distribution Generalization via Causal Intervention [69.70137479660113]
  本稿では,ノードレベルの分散シフトの下で頑健なグラフニューラルネットワーク(GNN)をトレーニングするための,概念的に単純だが原則化されたアプローチを提案する。 本手法は,環境推定器と熟練GNN予測器を協調する因果推論に基づく新たな学習目標を提案する。 本モデルでは,様々な分散シフトによる一般化を効果的に向上し,グラフOOD一般化ベンチマーク上での最先端の精度を最大27.4%向上させることができる。
  論文  参考訳（メタデータ） (2024-02-18T07:49:22Z)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness [35.409017863665575]
  準同型表現性は、GNNモデルが準同型の下でグラフを数える能力を測定する。 ケーススタディとして著名なGNNの4つのクラスを調べることで、それらの同型表現の単純で統一的でエレガントな記述を導き出す。 本研究の結果は, 過去の一連の研究に対する新たな洞察を与え, 地域社会における様々なサブアレスの景観を統一し, いくつかのオープンな疑問を解決した。
  論文  参考訳（メタデータ） (2024-01-16T17:23:23Z)
• Towards Understanding the Generalization of Graph Neural Networks [9.217947432437546]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データ指向学習と表現において最も広く採用されているモデルである。 まず,帰納学習における一般化ギャップと勾配の確率境界を確立する。 理論的な結果は、一般化ギャップに影響を与えるアーキテクチャ固有の要因を明らかにする。
  論文  参考訳（メタデータ） (2023-05-14T03:05:14Z)
• On the Expressiveness and Generalization of Hypergraph Neural Networks [77.65788763444877]
  この拡張抽象化はハイパーグラフニューラルネットワーク(HyperGNN)の表現性、学習、および(構造的)一般化を分析するためのフレームワークを記述する。 具体的には、HyperGNNが有限データセットからどのように学習し、任意の入力サイズのグラフ推論問題に構造的に一般化するかに焦点を当てる。
  論文  参考訳（メタデータ） (2023-03-09T18:42:18Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  トレーニンググラフとテストグラフの分散シフトを考慮せずにグラフニューラルネットワーク(GNN)を提案する。 このような環境では、GNNは、たとえ素早い相関であるとしても、予測のためのトレーニングセットに存在する微妙な統計的相関を利用する傾向がある。 本稿では,スプリアス相関の影響を排除するため,StableGNNと呼ばれる一般的な因果表現フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-11-20T18:57:18Z)

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

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