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

Basic Information

• Paper ID: 2510.10101
• Title: Rademacher Meets Colors: More Expressivity, but at What Cost?
• Authors: Martin Carrasco, Caio Deberaldini Netto, Vahan A. Martirosyan, Aneeqa Mehrab, Ehimare Okoyomon, Caterina Graziani
• Classification: cs.LG (Machine Learning)
• Publication Date: October 11, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.10101

Abstract

The expressive power of Graph Neural Networks (GNNs) is typically understood through its correspondence with graph isomorphism tests, such as the Weisfeiler-Leman hierarchy. While more expressive GNNs can distinguish richer sets of graphs, they also exhibit higher generalization error. This work connects expressivity with generalization capability through the lens of coloring algorithms, providing a theoretical explanation for this trade-off. Specifically, the authors prove that the number of equivalence classes induced by WL coloring directly bounds the Rademacher complexity of GNNs—a key data-dependent generalization measure. The analysis reveals that stronger expressivity leads to higher complexity, resulting in weaker generalization guarantees. Furthermore, the authors establish the stability of Rademacher complexity under color count perturbations across different samples. Importantly, the framework extends beyond message-passing GNNs or 1-WL to arbitrary GNN architectures and expressivity measures that partition graphs into equivalence classes.

Research Background and Motivation

Core Problem

This research addresses a fundamental theoretical question in the GNN field: the trade-off between expressive power and generalization capability. While empirical observations suggest that more expressive GNNs often exhibit worse generalization performance, rigorous theoretical explanations are lacking.

Problem Significance

1. Missing Theoretical Foundation: Existing research primarily focuses on analyzing GNN expressivity, but lacks sufficient theoretical understanding of its relationship with generalization capability
2. Practical Guidance Value: Understanding this trade-off is crucial for designing GNN architectures that possess sufficient expressivity while maintaining good generalization
3. Need for Unified Framework: A unified theoretical framework is needed to explain the generalization behavior of different GNN architectures

Limitations of Existing Approaches

1. Morris et al.'s VC Dimension Analysis: Applicable only to specific activation functions and bounded graphs, depending on parameter count rather than structural properties
2. Garg et al.'s Rademacher Complexity: While providing tighter bounds, it does not explore connections with WL coloring distributions
3. Lack of Generality: Existing analyses are mostly limited to specific GNN architectures or 1-WL tests

Core Contributions

1. Establishing Expressivity-Generalization Theoretical Connection: First direct linkage between GNN expressivity and Rademacher complexity through coloring algorithms
2. Providing Precise Complexity Bounds: Proves that the Rademacher complexity upper bound is $\sqrt{p/m}$, where $p$ is the number of equivalence classes
3. Establishing Stability Guarantees: Establishes Lipschitz continuity of Rademacher complexity under color count perturbations
4. Designing Universal Framework: Extends to arbitrary GNN architectures and corresponding coloring algorithms, not limited to message-passing GNNs or 1-WL
5. Improving Dudley Integral Bounds: Provides tighter covering number bounds utilizing $p$-dimensional structure

Methodology Details

Task Definition

The research studies graph-level binary classification tasks, where:

• Input: Graph dataset $S = \{(G_i, y_i)\}_{i=1}^m$, $G_i \in \mathcal{G}$, $y_i \in \{-1, +1\}$
• Output: Rademacher complexity bounds for function class $\mathcal{F} = \{f: \mathcal{G} \to [-1,1]\}$
• Objective: Establish quantitative relationship between expressivity measures and generalization capability

Theoretical Framework

Core Idea

Coloring algorithms partition sample $S$ into $p$ disjoint sets $I_1, \ldots, I_p$, where each $I_j$ contains all graphs with the same color $c_j$. This partition imposes structural constraints on the function class: any function implementable by the architecture must remain constant on equivalence classes.

Main Theoretical Results

Proposition 3.1 (Core Bound): For function class $\mathcal{F}$, if for each $f \in \mathcal{F}$, graphs with identical 1-WL colors have identical outputs, then the empirical Rademacher complexity bound is:

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

where $L(\Theta) = \sqrt{\sum_{i=1}^m f(G_i;\Theta)^2}$ is the $\ell_2$ norm of function outputs.

Corollary 3.2 (Bounded Output Case): When $f: \mathcal{G} \to [-1,1]$:

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

Proof Core Strategy

1. Summation Reorganization: Reorganize summations in the Rademacher complexity definition by graph colors
2. Cauchy-Schwarz Inequality: Separate function-related norms from Rademacher variables
3. Jensen's Inequality: Exploit concavity of the square root function
4. Expectation Calculation: Utilize independence and zero-mean properties of Rademacher variables

Stability Analysis

Proposition 3.4 (Stability Guarantee): For two samples $S$ and $S'$ of size $m$, if the count difference for each color $c_j$ across the two samples is at most $\epsilon_j$:

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

This ensures robustness of the bound under sampling variability.

Universal Extension

The framework extends to arbitrary $(A, T)$ pairs, where $A$ is a GNN architecture and $T$ is a coloring algorithm bounding its expressivity. If $T \sqsubseteq S$ (expressivity of $T$ does not exceed $S$), then $p_T \leq p_S$, meaning more expressive architectures have larger Rademacher complexity bounds.

Experimental Setup

Theoretical Verification

This is primarily a theoretical work, with all proposed bounds verified through mathematical proofs. The authors provide visualization examples in Figure 1, demonstrating how function classes of different expressivity induce different sample partitions.

Applicable Scope

• GNN Architectures: Message-passing GNNs, k-GNNs, CW networks, subgraph GNNs, path GNNs, etc.
• Coloring Algorithms: 1-WL, k-WL, cellular WL, etc.
• Loss Functions: Logistic loss, cross-entropy loss, margin loss (must satisfy Lipschitz conditions)

Experimental Results

Theoretical Results Verification

All theoretical results are verified through rigorous mathematical proofs:

1. Main Bound: Proves that $R_S(\mathcal{F}) \leq \sqrt{p/m}$ holds for bounded output functions
2. Improved Dudley Bound: Improves the classical $4\alpha/\sqrt{m}$ term to $4\alpha\sqrt{p}/\sqrt{m}$
3. Stability: Establishes linear stability of Rademacher complexity

Key Insights

1. Cost of Expressivity: Stronger expressivity directly leads to larger $p$ values, increasing the generalization error upper bound
2. Structural Constraints: Equivalence classes induced by coloring limit the function's overfitting capacity
3. Architecture Comparison: Provides theoretical tools for comparing generalization capabilities of different GNN architectures

Related Work

Expressivity Research

• Xu et al. and Morris et al.: Established correspondence between MPGNN and 1-WL
• Subsequent Work: Extended to more expressive GNN variants (k-GNN, CW networks, etc.)

Generalization Theory

• Morris et al. (VC Dimension): First connected GNN expressivity with VC dimension, but limited to specific settings
• D'Inverno et al.: Extended VC dimension analysis to Pfaffian activation functions
• Garg et al.: Provided first Rademacher complexity bounds for MPGNN

Advantages of This Work

1. Direct Connection: First direct linkage between expressivity measures (color count) and generalization measures
2. Universality: Applicable to arbitrary GNN architectures and coloring algorithms
3. Data Dependence: Provides finer data-dependent bounds

Conclusions and Discussion

Main Conclusions

1. Quantifying Trade-offs: First quantification of the trade-off between GNN expressivity and generalization capability
2. Theoretical Unification: Unifies expressivity and generalization research through coloring algorithms
3. Practical Guidance: Provides theoretical principles for GNN architecture design

Limitations

1. Task Restrictions: Current analysis limited to graph-level binary classification
2. Discrete Partitioning: Uses discrete equivalence classes rather than continuous similarity measures
3. Distribution Assumptions: Does not consider behavior under specific graph distributions

Future Directions

1. Task Extension: Extend to multi-classification, regression, and node-level tasks
2. Pseudo-metric Methods: Replace discrete partitions with structure similarity based on pseudo-metrics
3. Probabilistic Models: Study asymptotic behavior under random graph models and graphons
4. Empirical Verification: Systematic empirical studies to verify practical tightness of theoretical bounds

In-Depth Evaluation

Strengths

1. Theoretical Innovation: First direct theoretical connection between expressivity and generalization, filling an important theoretical gap
2. Mathematical Rigor: Complete and rigorous proofs with general applicability
3. Practical Value: Provides quantitative guidance for GNN architecture selection
4. Framework Universality: Applicable to broad range of GNN architectures and expressivity measures
5. Stability Guarantees: Proves robustness of bounds

Weaknesses

1. Missing Empirical Verification: Lacks experimental validation of theoretical bound tightness
2. Task Limitations: Only considers binary classification, restricting applicability
3. Unknown Bound Tightness: Does not analyze tightness of provided bounds
4. Computational Complexity: Does not discuss complexity of color count computation

Impact

1. Theoretical Contribution: Provides important foundation for GNN theory, expected to inspire subsequent research
2. Architecture Design: Guides practical GNN architecture selection and design
3. Research Direction: Opens new research direction on expressivity-generalization trade-offs

Applicable Scenarios

1. Theoretical Research: GNN expressivity and generalization theory analysis
2. Architecture Design: Application scenarios requiring balance between expressivity and generalization
3. Model Selection: Selecting appropriate expressivity GNN architectures for specific tasks

References

This paper cites 28 relevant references, covering important works in core areas including GNN expressivity, generalization theory, and Rademacher complexity, providing solid foundation for theoretical analysis.

Summary: Through the lens of coloring algorithms, this paper establishes for the first time a quantitative theoretical connection between GNN expressivity and generalization capability, providing important theoretical tools for understanding and designing GNNs. Despite some limitations, its theoretical contributions hold significant value and are expected to advance GNN theory research.