Research map / Graph learning / GNN architectures

On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry

NeurIPS 2026 · Graph learning › GNN architectures · approach: Weisfeiler-Leman expressivity hierarchies · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives data-dependent empirical Rademacher complexity bounds for GNNs governed by the equivalence-class distribution induced by an expressivity-bounding graph invariant (e.g., 1-WL), extended to Lipschitz pseudo-metric geometry and Wasserstein stability; purely theoretical, with no experiments.

Problem

Generalization of GNNs is typically analyzed with VC dimension, which ignores training data and does not reflect how expressivity (WL-style colorings) and input geometry jointly affect generalization.

Approach

Bound empirical Rademacher complexity of GNN classes that are upper-bounded in expressivity by a graph invariant T by sums over the sqrt of class proportions, refine via covering numbers under Lipschitz pseudo-metrics, and show Lipschitz dependence of Rademacher complexity on Wasserstein distance between samples.

Key results

• Partition-based bound R_S(F) <= sum_j sqrt(mu_j/m), tight up to factor 2 for maximally expressive classes.
• Dudley-type bound improves the first term from 1/sqrt(m) to sqrt(p)/m, where p is the number of invariant classes.
• Rademacher complexity is alpha-Lipschitz in W1 between samples, with alpha=2 for discrete partitions and alpha=lambda for continuous pseudo-metrics.

Surprising findings

• Generalization bound term decreases when training data is concentrated in few dense equivalence classes, so heterogeneity can reduce complexity.

Limitations

• No empirical verification of the derived bounds.
• Restricted to binary classification; multi-class and regression not covered.
• Bounds do not assume a graph distribution; true Rademacher complexity under random graph models left open.

Experimental setup

Metrics: empirical Rademacher complexity generalization gap bound

Baselines: VC-dimension bounds for GNNs Rademacher bounds for MPGNNs

Builds on: Rademacher complexity bounds for MPGNNs 1-WL expressivity correspondence Tree Mover's Distance Dudley entropy integral

Closest papers by meaning

• Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.94)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.92)
• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs (ICLR 2025 · similarity 0.91)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.90)
• Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.90)
• What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.90)