Research map / Graph learning / GNN architectures
Generalization Error of Graph Neural Networks in the Mean-field Regime
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 O(1/n) expected generalization error bounds (via functional derivatives and symmetrized KL) and a high-probability Rademacher bound for one-hidden-layer GCNs and MPGNNs in the mean-field regime, with a small synthetic/PROTEINS empirical check.
Problem
Generalization error of over-parameterized graph neural networks (GCNs and MPGNNs) for graph classification, where existing bounds become vacuous as hidden width grows.
Approach
Model one-hidden-layer GNNs in the mean-field regime as measures over neuron parameters and bound generalization of the KL-regularized (Gibbs) solution via symmetrized KL divergence and functional derivatives, giving a width-independent O(1/n) bound; a Rademacher-complexity analysis gives a high-probability O(1/sqrt(n)) bound.
Key results
- Functional-derivative bound gives generalization error at most alpha*C/n with C=(M_l' M_phi L_psi N_max)^2, the first O(1/n) rate reported for GNN generalization bounds, versus O(1/sqrt(n)) in prior work.
- Empirically, absolute generalization error of GCN and MPGNN decreases as hidden width h increases (averaged over ten runs), consistent with the width-independent bound and contrary to width-dependent prior bounds.
- Rademacher-based high-probability bound holds with probability 1-delta and scales as O(1/sqrt(n)), with a graph-degree dependence of (d_max+1)/(d_min+1) raised to 3/4 for GCNs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the functional-derivative bound instead of the Rademacher-complexity bound | Over-parameterized one-hidden-layer GCN · Graph classification | generalization error upper-bound convergence rate: O(1/√n) -> O(1/n) | Helped |
| Use mean-readout instead of sum-readout | Generic GNN · Graph classification | generalization error upper bound | Helped |
| Increase the number of hidden neurons | One-hidden-layer GCN and MPGNN · Synthetic and PROTEINS graph classification datasets | absolute generalization error | Helped |
| Choose a graph filter with smaller norm | Over-parameterized one-hidden-layer GCN · Graph classification | generalization error upper bound | Helped |
Surprising findings
- Empirical generalization error decreases as the hidden width grows, contrary to width-dependent bounds that increase with h.
Limitations
- Analysis restricted to one hidden layer for GCNs and MPGNNs.
- Relies on assumptions such as bounded loss, bounded features, bounded unit functions, and Lipschitz nonlinearities that the authors note could be relaxed.
- Bounds are for the Gibbs measure under KL-regularized ERM rather than standard SGD-trained networks.
Experimental setup
Datasets: PROTEINS synthetic stochastic block model graphs synthetic Erdos-Renyi graphs
Benchmarks: PROTEINS
Metrics: absolute empirical generalization error
Baselines: VC-dimension GNN bound Rademacher complexity GNN bound PAC-Bayesian GNN bounds continuous MPGNN bound
Builds on: mean-field neural network analysis Rademacher complexity bounds for GNNs PAC-Bayesian bounds for GNNs graph convolutional networks message passing neural networks
Closest papers by meaning
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.92)
- Generalization Error Bounds of Gradient Descent for Learning Over-Parameterized Deep ReLU Networks (AAAI 2020 · similarity 0.91)
- Generalization of Graph Neural Networks Is Robust to Model Mismatch (AAAI 2025 · similarity 0.88)
- Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.88)
- Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.88)
- Adversarial Robust Generalization of Graph Neural Networks (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.