Research map / Graph learning / GNN architectures

Generalization of Graph Neural Networks Is Robust to Model Mismatch

AAAI 2025 · Graph learning › GNN architectures · approach: GNN generalization theory · 2 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 with low-pass, integral-Lipschitz filters trained on manifold-generated geometric graphs generalize robustly when the testing data come from a mismatched manifold, with a bound that trades generalization against high-frequency discriminability.

Problem

Generalization analysis of GNNs typically assumes i.i.d. training and testing data from the same generative model; this paper asks whether GNN generalization holds when testing graphs are generated from a mismatched manifold model.

Approach

Models manifold mismatch as a diffeomorphic displacement that induces node feature perturbations and Laplacian (edge) perturbations, then combines the convergence of geometric GNNs to manifold neural networks with MNN stability under manifold deformation to bound the generalization gap under mismatch, for node and graph level tasks.

Key results

• Theoretical bound: generalization gap under manifold mismatch decreases with number of nodes N as (log N / N)^(1/d) plus epsilon terms, and grows linearly with mismatch gamma (C_4 gamma).
• On OGBN-Arxiv, the generalization gap of GCN-style GNNs grows approximately linearly with perturbation level and with log of the number of nodes, and deeper or wider GNNs show larger gaps.
• On ModelNet10 (N=40 points), gaps scale with mismatch size and decrease with number of nodes; Lipschitz-constrained filters improve generalization.

Measured effects reported in the paper

Limitations

• Analysis restricted to bandlimited input functions and low-pass, integral Lipschitz filters, a mild but restrictive assumption.
• Experiments use node/edge perturbations as proxies for manifold mismatch rather than true manifold models.
• Code promised only after acceptance; bound constants not tightly characterized.

Experimental setup

Datasets: OGBN-Arxiv ModelNet10

Benchmarks: OGBN-Arxiv ModelNet10

Metrics: generalization gap accuracy

Builds on: manifold neural networks graph convolutional networks

Closest papers by meaning

• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.93)
• Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.90)
• What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.89)
• Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.89)
• Adversarial Robust Generalization of Graph Neural Networks (ICML 2025 · similarity 0.89)
• Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness–Generalization Perspective (NeurIPS 2025 · similarity 0.89)