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. (2020) Posterior Consistency of Semi-Supervised Regression on Graphs. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Graph-based semi-supervised regression (SSR) is the problem of estimating the value of a function on a weighted graph from its values (labels) on a small subset of the vertices. 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 nodes. 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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Bertozzi, Andrea L.0000-0003-0396-7391
Additional Information: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
Classification Code:AMS subject classifications. 62H30, 62F15, 68R10, 68T10, 68Q87
Record Number:CaltechAUTHORS:20201109-141014452
Persistent URL:
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:09 Nov 2020 22:35

Repository Staff Only: item control page