paper-with-me

홈 › Papers

Learning from one graph: transductive learning guarantees via the geometry of small random worlds

2025-09-08 · Nils Detering, Luca Galimberti, Anastasis Kratsios, Giulia Livieri, A. Martina Neuman arxiv

Since their introduction by Kipf and Welling in $2017$, a primary use of graph convolutional networks is transductive node classification, where missing labels are inferred within a single observed graph and its feature matrix. Despite the widespread use of the network model, the statistical foundations of transductive learning remain limited, as standard inference frameworks typically rely on multiple independent samples rather than a single graph. In this work, we address these gaps by developing new concentration-of-measure tools that leverage the geometric regularities of large graphs via low-dimensional metric embeddings. The emergent regularities are captured using a random graph model; however, the methods remain applicable to deterministic graphs once observed. We establish two principal learning results. The first concerns arbitrary deterministic $k$-vertex graphs, and the second addresses random graphs that share key geometric properties with an Erdős-Rényi graph $\mathbf{G}=\mathbf{G}(k,p)$ in the regime $p \in \mathcal{O}((\log (k)/k)^{1/2})$. The first result serves as the basis for and illuminates the second. We then extend these results to the graph convolutional network setting, where additional challenges arise. Lastly, our learning guarantees remain informative even with a few labelled nodes $N$ and achieve the optimal nonparametric rate $\mathcal{O}(N^{-1/2})$ as $N$ grows.

📄 PDF Abstract BibTeX arXiv:2509.06894

Code (0)

등록된 구현이 없습니다.

Tasks

Node Classification

Similar Papers 제목 키워드 기반

Revisiting Random Walks for Learning on Graphs

2024-07-01 · Jinwoo Kim, Olga Zaghen, Ayhan Suleymanzade, Youngmin Ryou 외

We revisit a simple idea for machine learning on graphs, where a random walk on a graph produces a machine-readable record, and this record is processed by a deep neural network to directly make vertex-level or graph-lev…

Language Modelling

Information-Theoretic Generalization Bounds for Transductive Learning and its Applications

2023-11-08 · Huayi Tang, Yong liu

In this paper, we establish generalization bounds for transductive learning algorithms in the context of information theory and PAC-Bayes, covering both the random sampling and the random splitting setting. First, we sho…

Generalization BoundsGraph LearningInductive LearningTransductive Learning

Small Transformers Compute Universal Metric Embeddings

2022-09-14 · NeurIPS 2023 11 · Anastasis Kratsios, Valentin Debarnot, Ivan Dokmanić

We study representations of data from an arbitrary metric space $\mathcal{X}$ in the space of univariate Gaussian mixtures with a transport metric (Delon and Desolneux 2020). We derive embedding guarantees for feature ma…

Memorization

Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples

2020-07-10 · NeurIPS 2020 12 · Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, Omar Montasser

We present a transductive learning algorithm that takes as input training examples from a distribution $P$ and arbitrary (unlabeled) test examples, possibly chosen by an adversary. This is unlike prior work that assumes …

Transductive Learning

LATA: Laplacian-Assisted Transductive Adaptation for Conformal Uncertainty in Medical VLMs

2026-02-19 · Behzad Bozorgtabar, Dwarikanath Mahapatra, Sudipta Roy, Muzammal Naseer 외 arxiv

Medical vision-language models (VLMs) are strong zero-shot recognizers for medical imaging, but their reliability under domain shift hinges on calibrated uncertainty with guarantees. Split conformal prediction (SCP) offe…