# Transductive Rademacher Complexity and its Applications

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2014.

## Built on by (most cited first, 25 of 25)

- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Generative Social Choice](https://mlsanity.com/paper/2309.01291/) (2023)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Rethinking Neural vs. Matrix-Factorization Collaborative Filtering: the Theoretical Perspectives](https://mlsanity.com/paper/2110.12141/) (2021)
- [Multi-class Probabilistic Bounds for Self-learning](https://mlsanity.com/paper/2109.14422/) (2021)
- [TransBoost: Improving the Best ImageNet Performance using Deep Transduction](https://mlsanity.com/paper/2205.13331/) (2022)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guarantees](https://mlsanity.com/paper/2508.09427/) (2025)
- [Learning from one graph: transductive learning guarantees via the geometry of small random worlds](https://mlsanity.com/paper/2509.06894/) (2025)
- [Layer-wise Adaptive Graph Convolution Networks Using Generalized Pagerank](https://mlsanity.com/paper/2108.10636/) (2021)
- [Robust Graph Structure Learning with the Alignment of Features and Adjacency Matrix](https://mlsanity.com/paper/2307.02126/) (2023)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Understanding Generalization in Node and Link Prediction](https://mlsanity.com/paper/2507.00927/) (2025)
- [Minimax-Optimal Two-Sample Test with Sliced Wasserstein](https://mlsanity.com/paper/2510.27498/) (2025)
- [Multi-fidelity Stability for Graph Representation Learning](https://mlsanity.com/paper/2111.12865/) (2021)
- [Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs](https://mlsanity.com/paper/2209.05020/) (2022)
- [Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection](https://mlsanity.com/paper/2405.11349/) (2024)
- [UPL: Uncertainty-aware Pseudo-labeling for Imbalance Transductive Node Classification](https://mlsanity.com/paper/2502.00716/) (2025)
- [Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification](https://mlsanity.com/paper/2603.09257/) (2026)
- [Generalization Bounds for Spectral GNNs via Fourier Domain Analysis](https://mlsanity.com/paper/2604.00918/) (2026)
- [Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2605.25452/) (2026)
- [Bounded Difference Concentration for Infinitely Exchangeable Sequences with Applications to AI Benchmark Uncertainty](https://mlsanity.com/paper/2606.17426/) (2026)
- [Even Sharper Bounds for Transductive Learning and Its Applications](https://mlsanity.com/paper/2609.28459/) (2026)

## Abstract (arXiv)

We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher averages for particular algorithms, in terms of their "unlabeled-labeled" representation. This technique is relevant to many advanced graph-based transductive algorithms and we demonstrate its effectiveness by deriving error bounds to three well known algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds.