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

Abstract

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. 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 as N grows. 

About the speaker

Dr Giulia Livieri is an Associate Professor at the London School of Economics and Political Science (LSE). She previously served as an Assistant Professor at LSE and held a fixed-term Assistant Professor position at Scuola Normale Superiore (SNS) until November 2022. 

Before that, she was a Postdoctoral Researcher at SNS, where she earned a PhD in Financial Mathematics in October 2017 with the highest distinction (70/70 cum laude). In 2013, she completed a postgraduate course in Mathematical Finance at the University of Bologna, achieving top marks (30/30 cum laude) and undertaking an internship at Mediobanca, a leading investment bank in Italy. She graduated in Mathematics from the University of Padova in 2012 with the highest score (110/110).

Dr Livieri’s research focuses on financial econometrics for modelling financial markets at both high and low frequencies, as well as on Mean-Field Game (MFG) theory. Her current work develops machine learning techniques to address memory, forecasting and filtering problems in parametric stochastic time series, and aims to build a mathematical foundation for machine learning.

This event is part of the Financial Computing and Analytics Research Group seminar series at UCL Computer Science.