Research map / Graph learning / GNN architectures
Transductive Generalization for GNNs via Optimal Transport
MoonJeong Park, Seungbeom Lee, Kyungmin Kim, Jaeseung Heo, Seunghyuk Cho, Shouheng Li, Sangdon Park, Dongwoo Kim
Read the paperCheck your idea against 137,217 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 tractable transductive generalization bound for GNN node classification using optimal transport, which correlates better with empirical generalization than classical transductive bounds.
Problem
Generalization analysis of GNNs for node classification is hard because message passing creates dependencies that violate the i.i.d. assumption; existing distribution-free transductive bounds are intractable or correlate poorly with empirical generalization.
Approach
Uses optimal transport to derive a transductive generalization bound for GNNs that is tractable and tracks empirical generalization better than classical transductive bounds (abstract is truncated, so details beyond this are unknown).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add OT bound regularizer (ablation) | GCN · Roman-empire | accuracy (%): 56.06 -> 64.68 | Improved |
| add OT bound regularizer (ablation) | GCNII, GAT, SAGE · heterophilic graphs | accuracy (%): +5.42 (GCNII Roman-empire), +4.26 (GAT), +1.41 (SAGE) | Improved |
| add OT bound regularizer (ablation) | GCN, GCNII, GAT, SAGE · homophilic graphs (Cora, PubMed, Photo) | accuracy (%): +0.85 (GCN Cora), +0.12 (GCN PubMed) | Improved |
| add OT bound regularizer (ablation) | GCN, GCNII, GAT · Amazon-ratings | accuracy (%): 49.38 -> 49.02 (GCN) | Hurt |
| add OT bound regularizer (ablation) | all GNNs · nine datasets, four GNNs | accuracy (%): 32 of 36 setups improve | Improved |
| add OT bound regularizer (ablation) | SimMatch · CIFAR-10 (2% labels) | accuracy (%): 90.58 -> 92.41 | Improved |
| add OT bound regularizer (ablation) | FixMatch · CIFAR-10 and SVHN | accuracy (%): +0.06 CIFAR-10, +0.05 SVHN | No clear effect |
| add OT bound regularizer (ablation) | supervised CNN · SVHN (30% labels) | accuracy (%): 88.15 -> 91.00 | Improved |
| use OT bound instead of RC bound as predictor of generalization gap | OT bound vs RC · SGC, Cora | rank correlation: -0.92 -> 0.79 | Improved |
| use OT bound instead of PAC-Bayes bound as predictor | OT bound vs PAC · GCN, Cora | rank correlation: -0.78 -> 0.55 | Improved |
| estimate OT bound from training labels only instead of all labels (ablation) | OT bound · SGC and GCN node classification | rank correlation: 0.80 vs 0.79 (SGC Cora) | No clear effect |
| increase GNN depth (ablation) | SGC, GCN · Cora, CiteSeer | generalization error | Mixed |
Experimental setup
Metrics: generalization bound tightness correlation with empirical generalization
Builds on: transductive generalization theory
Closest papers by meaning
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.92)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.91)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.90)
- Generalization of Graph Neural Networks Is Robust to Model Mismatch (AAAI 2025 · similarity 0.90)
- Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.90)
- Towards Pre-trained Graph Condensation via Optimal Transport (NeurIPS 2025 · similarity 0.89)
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.
