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

arXiv: https://arxiv.org/abs/2603.09257 · HTML: https://mlsanity.com/paper/2603.09257/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 38 references that are in the map.
- First posted on arXiv 10 Mar 2026.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Understanding plasticity in neural networks](https://mlsanity.com/paper/2303.01486/) (2023)
- [Predicting the Generalization Gap in Deep Networks with Margin Distributions](https://mlsanity.com/paper/1810.00113/) (2018)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [NeurIPS 2020 Competition: Predicting Generalization in Deep Learning](https://mlsanity.com/paper/2012.07976/) (2020)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Representation Based Complexity Measures for Predicting Generalization in Deep Learning](https://mlsanity.com/paper/2012.02775/) (2020)
- [Transductive Rademacher Complexity and its Applications](https://mlsanity.com/paper/1401.3441/) (2014)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [k-Variance: A Clustered Notion of Variance](https://mlsanity.com/paper/2012.06958/) (2020)
- [Localized Complexities for Transductive Learning](https://mlsanity.com/paper/1411.7200/) (2014)
- [Influence Functions for Edge Edits in Non-Convex Graph Neural Networks](https://mlsanity.com/paper/2506.04694/) (2025)

## Abstract (arXiv)

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.