A Caltech Library Service

Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithms

Dunlop, Matthew M. and Slepčev, Dejan and Stuart, Andrew M. and Thorpe, Matthew (2020) Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithms. Applied and Computational Harmonic Analysis, 49 (2). pp. 655-697. ISSN 1063-5203.

[img] PDF - Accepted Version
See Usage Policy.

[img] PDF (arXiv) - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Scalings in which the graph Laplacian approaches a differential operator in the large graph limit are used to develop understanding of a number of algorithms for semi-supervised learning; in particular the extension, to this graph setting, of the probit algorithm, level set and kriging methods, are studied. Both optimization and Bayesian approaches are considered, based around a regularizing quadratic form found from an affine transformation of the Laplacian, raised to a, possibly fractional, exponent. Conditions on the parameters defining this quadratic form are identified under which well-defined limiting continuum analogues of the optimization and Bayesian semi-supervised learning problems may be found, thereby shedding light on the design of algorithms in the large graph setting. The large graph limits of the optimization formulations are tackled through Γ−convergence, using the recently introduced TL^p metric. The small labelling noise limits of the Bayesian formulations are also identified, and contrasted with pre-existing harmonic function approaches to the problem.

Item Type:Article
Related URLs:
URLURL TypeDescription
Dunlop, Matthew M.0000-0001-7718-3755
Slepčev, Dejan0000-0002-7600-1144
Thorpe, Matthew0000-0003-2480-5404
Additional Information:© 2019 Elsevier Inc. Received 25 May 2018, Revised 28 December 2018, Accepted 8 March 2019, Available online 4 April 2019. The authors are grateful to Ian Tice and Giovanni Leoni for valuable insights and references. The authors are thankful to Christopher Sogge and Steve Zelditch for useful background informtion. The authors are also grateful to the Center for Nonlinear Analysis (CNA) and Ki-Net (NSF Grant RNMS11-07444). MT is grateful to the Cantab Capital Institute for the Mathematics of Information (CCIMI) and the Cambridge Image Analysis (CIA) group. DS acknowledges the support of the National Science Foundation under the grant DMS 1516677 and DMS 1814991. MMD and AMS are supported by AFOSR Grant FA9550-17-1-0185 and the National Science Foundation grant DMS 1818977. DS and MT acknowledge funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie grant agreement No 777826.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-17-1-0185
Marie Curie Fellowship777826
Issue or Number:2
Classification Code:MSC: 62G20; 62C10; 62F15; 49J55
Record Number:CaltechAUTHORS:20190404-103712251
Persistent URL:
Official Citation:Matthew M. Dunlop, Dejan Slepčev, Andrew M. Stuart, Matthew Thorpe, Large data and zero noise limits of graph-based semi-supervised learning algorithms, Applied and Computational Harmonic Analysis, Volume 49, Issue 2, 2020, Pages 655-697, ISSN 1063-5203, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94453
Deposited By: Tony Diaz
Deposited On:04 Apr 2019 17:54
Last Modified:01 Jul 2020 22:12

Repository Staff Only: item control page