Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification

MoonJeong Park; Seungbeom Lee; Kyungmin Kim; Jaeseung Heo; Seunghyuk Cho; Shouheng Li; Sangdon Park; Dongwoo Kim

cs.LGMar 10, 2026

Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification

Authors: MoonJeong Park, Seungbeom Lee, Kyungmin Kim, Jaeseung Heo, Seunghyuk Cho, Shouheng Li, Sangdon Park, Dongwoo Kim

Organizations: Graduate School of Artificial Intelligence, POSTECH, South Korea · CSIRO’s Data61, Canberra, Australia · Department of Computer Science & Engineering, POSTECH, South Korea

Abstract

Many existing transductive bounds rely on classical complexity measures that are computationally intractable and often misaligned with empirical behavior. In this work, we establish new representation-based generalization bounds in a distribution-free transductive setting, where learned representations are dependent, and test features are accessible during training. We derive global and class-wise bounds via optimal transport, expressed in terms of Wasserstein distances between encoded feature distributions. We demonstrate that our bounds are efficiently computable and strongly correlate with empirical generalization in graph node classification, improving upon classical complexity measures. Additionally, our analysis reveals how the GNN aggregation process transforms the representation distributions, inducing a trade-off between intra-class concentration and inter-class separation. This yields depth-dependent characterizations that capture the non-monotonic relationship between depth and generalization error observed in practice. The code is available at https://github.com/ml-postech/Transductive-OT-Gen-Bound.

Figures & tables

Panel of Figure 1 — Figure 1: Rank scatter plots of the empirical generalization error against (a) the PAC bound and (b) our proposed bound for SGC on the Squirrel dataset. The PAC bound shows weak rank correlation with the empirical generalization error, whereas our bound exhibits a stronger positive rank correlation.

Figure 2: Rank correlation between generalization bounds and empirical error gap across nine datasets and four GNN architectures. Global reports our bound from Section 4.2 . Class-wise and Class-wise approx correspond to Section 4.2 with and without test labels, respectively. Darker blue indicates a stronger positive correlation. Our bounds consistently achieve high correlations, while PAC and RC bounds show weak or negative correlations in most cases. N/A indicates the bound cannot be computed.

Panel of Figure 3 — Figure 3: Depth analysis on SGC (top) and GCN (bottom) with Cora dataset.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Rank correlation between generalization bounds and empirical error gap across nine datasets and GraphSAGE. Darker blue indicates stronger positive correlation. N/A indicates the bound cannot be computed.

Dataset	# nodes	# edges	# features	# classes
Cora	2,708	5,278	1,433	7
CiteSeer	3,327	4,552	3,703	6
PubMed	19,717	44,324	500	3
Computers	13,752	245,861	767	10
Photo	7,650	119,081	745	8
Squirrel	2,223	46,998	2,089	5

Appendix

Table 1: Statistics of the datasets utilized in the experiments.

			# sampled permutations
			1	4	16	64
SGC	Cora	Class-wise	0.84 (0.50s)	0.89 (1.99s)	0.9 (8.22s)	0.88 (23.7s)
	Cora	Class-wise approx	0.84 (0.36s)	0.87 (1.67s)	0.87 (6.21s)	0.86 (20.1s)
	Amazon-	Class-wise	0.76 (9.69s)	0.93 (39.8s)	0.89 (147s)	0.91 (611s)
	ratings	Class-wise approx	0.76 (0.83s)	0.91 (3.31s)	0.87 (13.2s)	0.92 (49.2s)
GCN	Cora	Class-wise	0.7 (0.69s)	0.81 (2.58s)	0.75 (10.5s)	0.78 (43.9s)

Appendix

Table 2: Correlation values (with computation time in seconds) for estimating the expectation in Theorem 4.2 using different numbers of sampled permutations (1, 4, 16, 64). Results are reported for SGC and GCN on the Cora and Amazon-Ratings datasets under both the Class-wise and Class-wise approx settings.

	$p$ -percentile	Cora	CiteSeer	PubMed	Computers	Photo	Squirrel	Chameleon	Roman-empire	Amazon-ratings
SGC	1.0	-0.03	0.19	0.12	-0.51	0.06	0.01	-0.37	0.67	-0.12
	0.9	0.82	0.92	0.97	0.13	0.85	0.97	0.82	0.85	0.99
	0.5	0.92	0.94	0.96	0.18	0.87	0.98	0.90	0.85	0.98
GCN	1.0	0.07	0.21	0.08	-0.63	-0.62	0.08	0.14	-0.44	-0.42
	0.9	0.88	0.95	0.96	0.89	0.76	0.88	0.59	0.92	0.83
	0.5	0.92	0.93	0.96	0.82	0.76	0.91	0.81	0.91	0.94

Appendix

Table 3: Correlation between empirical error gap and generalization bounds across datasets and GNNs.

1.0

0.9

and

0.5

correspond to

1.0

0.9

, and

0.5

percentile of the change rate among all combination sets of

(i,j,y)

for

M(f,\phi)

from Section 4.2 .

Explore similar work

Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification
May 18, 2026Brown Zaz, Mar Gonzàlez I Català, Ferran Hernandez Caralt +2Graph Neural Networks Graph-Based Semi-Supervised Learning
University of Cambridge
CGRL: Causal-Guided Representation Learning for Node-Level Out-of-Distribution Generalization
Mar 25, 2026Bowen Lu, Lianqiang Yang, Teng Li +1OOD Generalization Graph Neural Networks
Anhui University, Hefei, China · Carnegie Mellon University, Pittsburgh, Commonwealth of Pennsylvania, USA
Node4All: Learning Node Representation Beyond Datasets
Jul 19, 2026Dooho Lee, Jaemin YooGraph Representation Learning Graph SSL
KAIST · Daejeon, Republic of Korea · Seoul National University +1

May 18, 2026J/K move · Enter open · S save

Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification

Brown Zaz, Mar Gonzàlez I Català, Ferran Hernandez Caralt, Moshe Eliasof+1

University of Cambridge

Graph Neural Networks Graph-Based Semi-Supervised Learning Transductive Learning Classification Semi-Supervised Learning Node Classification+1

Open paper AskPDF arXiv

In the transductive setting, where the full graph is observed but node labels are only partially available, progress in semi-supervised node classification has largely focused on architectural innovation. In this paper, we revisit an orthogonal axis: the training objective. We start from a simple observation: transductive models produce predictions for every node during training, including nodes without labels. These unlabeled-node predictions may contain useful training signal, but standard supervised objectives discard them because no ground-truth labels are available. Inspired by the decomposition of cross-entropy into a label-dependent alignment term and a label-independent entropy term, we propose prediction confidence as a natural way to extract this signal in the absence of labels. This motivates Transductive Sharpening (TS): a loss-level modification that minimizes prediction entropy on unlabeled nodes while counterbalancing this effect on labeled nodes. We evaluate Transductive Sharpening across a wide range of node-classification benchmarks and observe consistent performance improvements without requiring any changes to the backbone architecture. Code is available at https://github.com/transductive-sharpening/tunedGNN.

Abstract

Explore similar work

Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification

CGRL: Causal-Guided Representation Learning for Node-Level Out-of-Distribution Generalization

Node4All: Learning Node Representation Beyond Datasets