2025-11-11T11:58:09.609989

Rademacher Meets Colors: More Expressivity, but at What Cost ?

Carrasco, Netto, Martirosyan et al.

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.

academic

ラーデマッハー複雑度とグラフ彩色：より高い表現力、しかし代償は？

基本情報

論文ID: 2510.10101
タイトル: Rademacher Meets Colors: More Expressivity, but at What Cost?
著者: Martin Carrasco, Caio Deberaldini Netto, Vahan A. Martirosyan, Aneeqa Mehrab, Ehimare Okoyomon, Caterina Graziani
分類: cs.LG（機械学習）
発表日: 2025年10月11日（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2510.10101

要約

グラフニューラルネットワーク（GNN）の表現力は、通常、グラフ同型判定テスト（Weisfeiler-Leman階層など）との対応関係を通じて理解されます。より表現力の高いGNNはより豊かなグラフ集合を区別できますが、より高い汎化誤差も示します。本研究は、彩色アルゴリズムの観点から表現力と汎化能力を結びつけることで、このトレードオフに対する理論的説明を提供します。具体的には、著者らはWL彩色によって誘導される等価類の数がGNNのラーデマッハ複雑度（重要なデータ依存汎化尺度）を直接制限することを証明しています。分析により、より強い表現力がより高い複雑度をもたらし、より弱い汎化保証につながることが明らかになります。さらに、著者らはラーデマッハ複雑度が異なるサンプル間の彩色計数摂動に対して安定であることを証明しています。重要なことに、このフレームワークはメッセージパッシングGNNまたは1-WLに限定されず、任意のGNNアーキテクチャと等価類にグラフを分割する表現力尺度に拡張されます。

研究背景と動機

核心問題

本研究は、GNN分野における基本的な理論問題に対処することを目指しています：表現力と汎化能力のトレードオフ。経験的観察により、より表現力の高いGNNはしばしばより悪い汎化性能を示すことが示唆されていますが、厳密な理論的説明が欠けています。

問題の重要性

理論的基礎の欠落：既存研究は主にGNNの表現力分析に焦点を当てていますが、その汎化能力との関係に対する理論的理解が不足しています
実践的指導価値：このトレードオフを理解することは、十分な表現力を持ちながら良好に汎化するGNNアーキテクチャを設計するために重要です
統一フレームワークの必要性：異なるGNNアーキテクチャの汎化動作を説明する統一的な理論フレームワークが必要です

既存手法の限界

Morris等によるVC次元分析：特定の活性化関数と有界グラフにのみ適用可能であり、構造特性ではなくパラメータ数に依存しています
Garg等によるラーデマッハ複雑度：より厳密な界を提供していますが、WL彩色分布との関連性を探索していません
汎用性の欠落：既存分析は多くの場合、特定のGNNアーキテクチャまたは1-WLテストに限定されています

核心的貢献

表現力-汎化理論の接続確立：彩色アルゴリズムを通じてGNNの表現力とラーデマッハ複雑度を初めて直接結びつけます
正確な複雑度界の提供：ラーデマッハ複雑度の上界が $\sqrt{p/m}$ であることを証明します。ここで $p$ は等価類の数です
安定性保証の証明：ラーデマッハ複雑度が彩色計数摂動に対してリプシッツ連続であることを確立します
汎用フレームワークの設計：任意のGNNアーキテクチャと対応する彩色アルゴリズムに拡張され、メッセージパッシングGNNまたは1-WLに限定されません
改善されたDudley積分界： $p$ 次元構造を利用してより厳密なカバリング数界を提供します

方法論の詳細

タスク定義

グラフレベルの二値分類タスクを研究します。ここで：

入力：グラフデータセット $S = \{(G_i, y_i)\}_{i=1}^m$ 、 $G_i \in \mathcal{G}$ 、 $y_i \in \{-1, +1\}$
出力：関数クラス $\mathcal{F} = \{f: \mathcal{G} \to [-1,1]\}$ のラーデマッハ複雑度界
目標：表現力尺度と汎化能力の定量的関係を確立します

理論フレームワーク

核心的考え方

彩色アルゴリズムはサンプル $S$ を $p$ 個の互いに素な集合 $I_1, \ldots, I_p$ に分割し、各 $I_j$ は同じ彩色 $c_j$ を持つすべてのグラフを含みます。この分割は関数クラスに構造的制約を課します：アーキテクチャで実装可能な任意の関数は等価類上で定数である必要があります。

主要な理論的結果

命題3.1（核心界）：関数クラス $\mathcal{F}$ に対して、各 $f \in \mathcal{F}$ について同じ1-WL彩色を持つグラフが同じ出力を持つ場合、経験的ラーデマッハ複雑度界は：

$R_S(\mathcal{F}) \leq \frac{\sup_\Theta L(\Theta)\sqrt{p}}{\sqrt{m}}$

ここで $L(\Theta) = \sqrt{\sum_{i=1}^m f(G_i;\Theta)^2}$ は関数出力の $\ell_2$ ノルムです。

系3.2（有界出力の場合）： $f: \mathcal{G} \to [-1,1]$ のとき：

$R_S(\mathcal{F}) \leq \sqrt{\frac{p}{m}}$

証明の核心的思考

合計の再構成：ラーデマッハ複雑度定義における合計をグラフ彩色によって再構成します
コーシー・シュワルツ不等式：関数関連ノルムとラーデマッハ変数を分離します
ジェンセン不等式：平方根関数の凹性を利用します
期待値計算：ラーデマッハ変数の独立性とゼロ平均特性を利用します

安定性分析

命題3.4（安定性保証）：サイズ $m$ の2つのサンプル $S$ と $S'$ に対して、各彩色 $c_j$ の計数差が両サンプルで最大 $\epsilon_j$ である場合：

$|R_S(\mathcal{F}) - R_{S'}(\mathcal{F})| \leq \frac{\sum_{c_j \in GC} \epsilon_j}{m}$

これにより、サンプリング変動性下での界の堅牢性が保証されます。

汎用拡張

フレームワークは任意の $(A, T)$ ペアに拡張されます。ここで $A$ はGNNアーキテクチャ、 $T$ はその表現力を制限する彩色アルゴリズムです。 $T \sqsubseteq S$ （ $T$ の表現力が $S$ を超えない）の場合、 $p_T \leq p_S$ であり、より表現力の高いアーキテクチャはより大きなラーデマッハ複雑度界を持つことを意味します。