A Caltech Library Service

Posterior consistency of semi-supervised regression on graphs

Bertozzi, Andrea L. and Hosseini, Bamdad and Li, Hao and Miller, Kevin and Stuart, Andrew M. (2021) Posterior consistency of semi-supervised regression on graphs. Inverse Problems, 37 (10). Art. No. 105011. ISSN 0266-5611. doi:10.1088/1361-6420/ac1e80.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Graph-based semi-supervised regression (SSR) involves estimating the value of a function on a weighted graph from its values (labels) on a small subset of the vertices; it can be formulated as a Bayesian inverse problem. This paper is concerned with the consistency of SSR in the context of classification, in the setting where the labels have small noise and the underlying graph weighting is consistent with well-clustered vertices. We present a Bayesian formulation of SSR in which the weighted graph defines a Gaussian prior, using a graph Laplacian, and the labeled data defines a likelihood. We analyze the rate of contraction of the posterior measure around the ground truth in terms of parameters that quantify the small label error and inherent clustering in the graph. We obtain bounds on the rates of contraction and illustrate their sharpness through numerical experiments. The analysis also gives insight into the choice of hyperparameters that enter the definition of the prior.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Bertozzi, Andrea L.0000-0003-0396-7391
Miller, Kevin0000-0003-4050-1849
Additional Information:© 2021 IOP Publishing Ltd. Received 24 March 2021; Revised 6 July 2021; Accepted 17 August 2021; Published 30 September 2021. This work is supported by NSF grant DMS 1818977, AFOSR grant FA9550-17-1-0185, NSERC PDF fellowship, a Caltech Von Kármán instructorship, DOD NDSEG Fellowship, and DARPA grant FA8750-18-2-0066.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-17-1-0185
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Caltech Von Kármán instructorshipUNSPECIFIED
National Defense Science and Engineering Graduate (NDSEG) FellowshipUNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)FA8750-18-2-0066
Subject Keywords:Semi-supervised learning, classification, consistency, graph Laplacian, Bayesian inference
Issue or Number:10
Classification Code:AMS subject classifications. 62H30, 62F15, 68R10, 68T10, 68Q87
Record Number:CaltechAUTHORS:20201109-141014452
Persistent URL:
Official Citation:Andrea L Bertozzi et al 2021 Inverse Problems 37 105011
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106563
Deposited By: George Porter
Deposited On:09 Nov 2020 22:35
Last Modified:02 Nov 2021 21:27

Repository Staff Only: item control page