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

• URL: http://arxiv.org/abs/2603.09257v1
• Date: Tue, 10 Mar 2026 06:43:18 GMT
• Title: Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification
• Abstract summary: We establish representation-based generalization bounds in a distribution-free transductive setting.<n>Our bounds are efficiently computable and strongly correlate with empirical generalization in graph node classification.<n>This yields depth-dependent characterizations that capture the non-monotonic relationship between depth and generalization error.
• Score: 17.399427621622703
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Beyond the Training Distribution: Mapping Generalization Boundaries in Neural Program Synthesis [13.460704771478866]
  Large-scale transformers achieve impressive results on program synthesis benchmarks.<n>But their true generalization capabilities remain obscured by data contamination and opaque training corpora.<n>We introduce a strictly controlled program synthesis environment based on a domain-specific arithmetic grammar.
  arXiv  Detail & Related papers  (2026-04-30T07:58:39Z)
• Understanding Generalization from Embedding Dimension and Distributional Convergence [13.491874401333021]
  We study generalization from a representation-centric perspective and analyze how the geometry of learned embeddings controls predictive performance for a fixed trained model.<n>We show that population risk can be bounded by two factors: (i) the intrinsic dimension of the embedding distribution, which determines the convergence rate of empirical embedding distribution to the population distribution in Wasserstein distance, and (ii) the sensitivity of the downstream mapping from embeddings to predictions, characterized by Lipschitz constants.
  arXiv  Detail & Related papers  (2026-01-30T09:32:04Z)
• Topology Identification and Inference over Graphs [61.06365536861156]
  Topology identification and inference of processes evolving over graphs arise in timely applications involving brain, transportation, financial, power, as well as social and information networks.<n>This chapter provides an overview of graph topology identification and statistical inference methods for multidimensional data.
  arXiv  Detail & Related papers  (2025-12-11T00:47:09Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Measuring Generalization with Optimal Transport [111.29415509046886]
  We develop margin-based generalization bounds, where the margins are normalized with optimal transport costs. Our bounds robustly predict the generalization error, given training data and network parameters, on large scale datasets.
  arXiv  Detail & Related papers  (2021-06-07T03:04:59Z)
• The Role of Mutual Information in Variational Classifiers [47.10478919049443]
  We study the generalization error of classifiers relying on encodings trained on the cross-entropy loss. We derive bounds to the generalization error showing that there exists a regime where the generalization error is bounded by the mutual information.
  arXiv  Detail & Related papers  (2020-10-22T12:27:57Z)
• Attentive Normalization for Conditional Image Generation [126.08247355367043]
  We characterize long-range dependence with attentive normalization (AN), which is an extension to traditional instance normalization. Compared with self-attention GAN, our attentive normalization does not need to measure the correlation of all locations. Experiments on class-conditional image generation and semantic inpainting verify the efficacy of our proposed module.
  arXiv  Detail & Related papers  (2020-04-08T06:12:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.