Research map / Graph learning / GNN architectures

A Manifold Perspective on the Statistical Generalization of Graph Neural Networks

ICML 2025 · Graph learning › GNN architectures · approach: GNN generalization theory · 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.

Proves that GNNs on graphs sampled from a manifold have generalization gaps that shrink with the number of nodes and grow with the spectral continuity constant of their filters, validated on a chair manifold and eight real-world node-classification datasets.

Problem

Existing GNN generalization bounds ignore graph structure and often grow with the number of nodes, contrary to practice. The paper asks how GNN generalization behaves for graphs sampled from an underlying manifold.

Approach

Relate GNNs on sampled graphs to manifold neural networks in the spectral domain via eigenvector/eigenvalue convergence of graph Laplacians, then bound the empirical-vs-statistical risk gap in terms of sample size N and the spectral continuity constant C_L of filter frequency responses.

Key results

• Generalization gap in accuracy decreases roughly linearly with the number of nodes on a log scale in the non-overfitting regime (training accuracy below 95%), for 2- and 3-layer GNNs on ArXiv and other datasets.
• A larger regularizer (smaller spectral continuity constant C_L) yields a smaller generalization gap, while overly strong regularization reduces test accuracy due to lower discriminability.
• The bound grows with the number of features and number of layers, consistent with the theory.

Measured effects reported in the paper

Surprising findings

• Overly smooth filters (very small C_L) hurt test accuracy because of reduced discriminability, so the best generalization is not simply the smoothest filter.

Limitations

• Analysis restricted to bandlimited manifold signals and assumes points sampled i.i.d. from a smooth compact manifold.
• Bounds contain constants depending on manifold geometry that are not made explicit, and the empirical rate is only observed outside the overfitting regime.

Experimental setup

Datasets: Chair manifold (synthetic) ArXiv Cora CiteSeer PubMed Amazon-Ratings Roman-Empire CoAuthors CS CoAuthors Physics

Benchmarks: Chair manifold (synthetic) ArXiv Cora CiteSeer PubMed Amazon-Ratings Roman-Empire CoAuthors CS CoAuthors Physics

Metrics: generalization gap (accuracy) generalization gap (cross-entropy loss) test accuracy

Builds on: graph convolutional networks manifold neural networks graph Laplacian convergence to manifold Laplace operator

Closest papers by meaning

• Generalization of Graph Neural Networks Is Robust to Model Mismatch (AAAI 2025 · similarity 0.93)
• Generalization Error of Graph Neural Networks in the Mean-field Regime (ICML 2024 · similarity 0.92)
• Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.91)
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.90)
• Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.90)
• On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective (NeurIPS 2025 · similarity 0.90)