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

• arxiv url: http://arxiv.org/abs/2510.10101v3
• Date: Tue, 28 Oct 2025 07:57:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-29 15:35:36.196343
• 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)
• 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 Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56:38Z)
• On the Expressiveness and Generalization of Hypergraph Neural Networks [77.65788763444877]
  この拡張抽象化はハイパーグラフニューラルネットワーク(HyperGNN)の表現性、学習、および(構造的)一般化を分析するためのフレームワークを記述する。 具体的には、HyperGNNが有限データセットからどのように学習し、任意の入力サイズのグラフ推論問題に構造的に一般化するかに焦点を当てる。
  論文  参考訳（メタデータ） (2023-03-09T18:42:18Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  トレーニンググラフとテストグラフの分散シフトを考慮せずにグラフニューラルネットワーク(GNN)を提案する。 このような環境では、GNNは、たとえ素早い相関であるとしても、予測のためのトレーニングセットに存在する微妙な統計的相関を利用する傾向がある。 本稿では,スプリアス相関の影響を排除するため,StableGNNと呼ばれる一般的な因果表現フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-11-20T18:57:18Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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