Department of Mathematical Sciences
Financial Math Seminar
Monday, October 6th, 2025
10:00AM-11:00AM
Salisbury Labs 104
Speaker: Nils Detering, Heinrich-Heine-Universität Düsseldorf
Title: Learning from one graph: transductive learning guarantees viageometry of random small worlds
Abstract: One of the primary use-cases of graph convolution neural networks (GCNs) is for transductive learning (TL), such as node-label prediction where missing node labels are inferred using only one realization of a (random) graph and one realization of a (random) node features matrix. However, TL for GCNs remains poorly understood since it lies outside of the standard statistical toolbox which requires multiple samples to perform inference. This paper fills these gaps in TL with new concentration of measure-based tools that exploit the emergent geometry of large dense random graphs using new, low-dimensional, metric embedding arguments.
Our TL guarantees remain meaningful with few labelled nodes N and attain the optimal
non-parametric rate O(N-1/2 ) when N is large. We present two results: one for arbitrary
deterministic k-vertex graphs, and another for random graphs sharing key geometric traits with an Erdős-Rényi graph G=G(k, p) in the regime P € (log(k)1/2 /k1/2. We apply our results to the convolutional neural network (GCN) setting where additional challenges materialize.