AI Paper Atlas

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

NeurIPS 2026 · Graph learning › GNN architectures · approach: GNN generalization theory · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
add OT bound regularizer (ablation)GCN · Roman-empireaccuracy (%): 56.06 -> 64.68Improved
add OT bound regularizer (ablation)GCNII, GAT, SAGE · heterophilic graphsaccuracy (%): +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-ratingsaccuracy (%): 49.38 -> 49.02 (GCN)Hurt
add OT bound regularizer (ablation)all GNNs · nine datasets, four GNNsaccuracy (%): 32 of 36 setups improveImproved
add OT bound regularizer (ablation)SimMatch · CIFAR-10 (2% labels)accuracy (%): 90.58 -> 92.41Improved
add OT bound regularizer (ablation)FixMatch · CIFAR-10 and SVHNaccuracy (%): +0.06 CIFAR-10, +0.05 SVHNNo clear effect
add OT bound regularizer (ablation)supervised CNN · SVHN (30% labels)accuracy (%): 88.15 -> 91.00Improved
use OT bound instead of RC bound as predictor of generalization gapOT bound vs RC · SGC, Corarank correlation: -0.92 -> 0.79Improved
use OT bound instead of PAC-Bayes bound as predictorOT bound vs PAC · GCN, Corarank correlation: -0.78 -> 0.55Improved
estimate OT bound from training labels only instead of all labels (ablation)OT bound · SGC and GCN node classificationrank correlation: 0.80 vs 0.79 (SGC Cora)No clear effect
increase GNN depth (ablation)SGC, GCN · Cora, CiteSeergeneralization errorMixed

Experimental setup

Metrics: generalization bound tightness correlation with empirical generalization

Builds on: transductive generalization theory

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy