用最优传输理论构建可计算的图节点分类泛化界。
Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification
- 基于最优传输构建依赖表示的泛化边界，使用编码特征分布的Wasserstein距离。
- 边界计算高效且与实际泛化误差高度相关，优于传统复杂度度量。
- 揭示了深度对类内凝聚与类间分离的权衡，解释深度非单调现象。
现有许多归纳式泛化界依赖于计算不可行且与实证行为不一致的经典复杂度度量。本文在无分布假设的归纳设置下，建立了基于表示的新泛化界，其中学习到的表示是相关的，且测试特征在训练时可用。我们通过最优传输推导出全局和类别级的泛化界，以编码特征分布间的Wasserstein距离表示。实验表明，这些边界可高效计算，并与图节点分类中的实际泛化表现强相关，优于传统复杂度度量。此外，分析揭示了GNN聚合过程如何改变表示分布，引致类内凝聚与类间分离之间的权衡，从而获得随深度变化的表征特性，捕捉实践中观察到的深度与泛化误差间的非单调关系。代码已公开于https://github.com/ml-postech/Transductive-OT-Gen-Bound。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。