論文の概要: Rademacher Meets Colors: More Expressivity, but at What Cost ?

• arxiv url: http://arxiv.org/abs/2510.10101v2
• Date: Tue, 14 Oct 2025 19:21:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-16 13:11:49.460554
• Title: Rademacher Meets Colors: More Expressivity, but at What Cost ?
• Title（参考訳）: Rademacher氏が色を語る: 表現力は向上するが、コストは?
• Authors: Martin Carrasco, Caio F. Deberaldini Netto, Vahan A. Martirosyan, Aneeqa Mehrab, Ehimare Okoyomon, Caterina Graziani,
• Abstract要約: グラフニューラルネットワーク(GNN)の表現力は、グラフ同型テストとの対応によって一般的に理解される。 この研究は、色付けアルゴリズムのレンズを通して表現性と一般化をリンクすることで、このトレードオフの理論的な説明を提供する。
• 参考スコア（独自算出の注目度）: 1.3420962121821391
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The expressive power of graph neural networks (GNNs) is typically understood through their correspondence with graph isomorphism tests such as the Weisfeiler-Leman (WL) hierarchy. While more expressive GNNs can distinguish a richer set of graphs, they are also observed to suffer from higher generalization error. This work provides a theoretical explanation for this trade-off by linking expressivity and generalization through the lens of coloring algorithms. Specifically, we show that the number of equivalence classes induced by WL colorings directly bounds the GNNs Rademacher complexity -- a key data-dependent measure of generalization. Our analysis reveals that greater expressivity leads to higher complexity and thus weaker generalization guarantees. Furthermore, we prove that the Rademacher complexity is stable under perturbations in the color counts across different samples, ensuring robustness to sampling variability across datasets. Importantly, our framework is not restricted to message-passing GNNs or 1-WL, but extends to arbitrary GNN architectures and expressivity measures that partition graphs into equivalence classes. These results unify the study of expressivity and generalization in GNNs, providing a principled understanding of why increasing expressive power often comes at the cost of generalization.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)の表現力は、一般にWeisfeiler-Leman(WL)階層のようなグラフ同型テストと対応して理解される。 より表現力のあるGNNはよりリッチなグラフの集合を区別することができるが、より一般化誤差に悩まされていることも観察されている。 この研究は、色付けアルゴリズムのレンズを通して表現性と一般化をリンクすることで、このトレードオフの理論的な説明を提供する。 具体的には、WL着色によって誘導される同値類の数は、一般化の鍵となるデータ依存測度であるGNNs Rademacher複雑性に直接有界であることを示す。 解析の結果, 表現性が向上すると複雑性が増し, 一般化保証が弱くなることがわかった。 さらに、Radecherの複雑さは、異なるサンプルにまたがる色数の摂動の下で安定であり、データセット間でのばらつきをサンプリングする堅牢性を保証する。 重要なことは、我々のフレームワークはメッセージパッシングGNNや1-WLに限らず、グラフを等価クラスに分割する任意のGNNアーキテクチャや表現度尺度にまで拡張されている。 これらの結果は、GNNにおける表現力と一般化の研究を統一し、なぜ表現力の増加が一般化のコストを伴うのかを原則的に理解する。

関連論文リスト

• Graph Representational Learning: When Does More Expressivity Hurt Generalization? [15.458310474570299]
  グラフニューラルネットワーク(GNN)は、構造化データを学ぶための強力なツールである。 グラフ間の構造的類似性の異なる度合いをキャプチャするプレメトリックの族を導入する。 私たちは、トレーニングとテストグラフ、モデルの複雑さ、トレーニングセットサイズの間の距離に依存する一般化境界を導出します。
  論文  参考訳（メタデータ） (2025-05-16T14:28:34Z)
• Towards Bridging Generalization and Expressivity of Graph Neural Networks [11.560730203511111]
  グラフニューラルネットワーク(GNN)における表現性と一般化の関係について検討する。 本稿では,GNNの一般化と,それらが捉えることのできるグラフ構造の分散を結合する新しいフレームワークを提案する。 我々は,クラス内濃度とクラス間分離のトレードオフを明らかにする。
  論文  参考訳（メタデータ） (2024-10-14T00:31:16Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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