Research map / Graph learning / GNN architectures

Towards Bridging Generalization and Expressivity of Graph Neural Networks

ICLR 2025 · 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.

Proposes a k-variance/Wasserstein margin-based generalization bound for graph encoders, bounding any encoder's generalization by a more expressive bounding encoder, and validates it on TU and molecular graph classification with MPNNs and homomorphism-augmented F-MPNNs.

Problem

Understanding how GNN expressivity affects generalization, given theory predicting an expressivity-generalization trade-off while empirics show expressive GNNs often generalize well.

Approach

Bound the generalization gap of any graph encoder via the Wasserstein-1 variance of embeddings under a more expressive bounding encoder (distinguishing-power ordering plus Lipschitz factorization), yielding a margin bound that trades off intra-class concentration against inter-class separation.

Key results

• The proposed sample-based bound tracks empirical generalization gaps across 1-6 MPNN layers on five datasets, while the VC bound plateaus after about three layers and is looser.
• On PROTEINS, adding C4 homomorphism counts reduces intra-class W1 distance (4.123 vs 4.796 for 1-WL) and lowers Lip(f), improving generalization; on ENZYMES, K4 counts increase W1 (5.000 vs 4.796), worsening it.
• l1 normalization of the last MPNN layer reduces the generalization gap on all five datasets, with the smallest gain on SIDER.

Measured effects reported in the paper

Surprising findings

• Greater expressivity from homomorphism counts can worsen generalization on ENZYMES, despite better graph separation, because intra-class concentration degrades.

Limitations

• Validation limited to six graph classification datasets; broader large-scale studies needed.
• Expectation term in the main bound is intractable, so experiments use a sample-based variant with additional approximation terms.

Experimental setup

Datasets: ENZYMES PROTEINS MUTAG SIDER BACE

Benchmarks: ENZYMES PROTEINS MUTAG SIDER BACE

Metrics: generalization gap (accuracy and loss) generalization bound value 1-Wasserstein distance Lipschitz constant of f

Baselines: VC bound (1-WL color histograms) MPNN with varying layers F-MPNN with C3-C6 homomorphism patterns

Builds on: margin-based generalization bounds for multiclass classification (Lei et al.) F-MPNN homomorphism-enhanced GNNs 1-WL expressivity of MPNNs sample-based Wasserstein generalization bound (Cao et al.)

Closest papers by meaning

• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.94)
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.94)
• Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.92)
• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs (ICLR 2025 · similarity 0.91)
• Weisfeiler-Leman at the margin: When more expressivity matters (ICML 2024 · similarity 0.91)
• An Empirical Study of Realized GNN Expressiveness (ICML 2024 · similarity 0.91)