Published on Fri Mar 17 2017

On Consistency of Graph-based Semi-supervised Learning

Chengan Du, Yunpeng Zhao, Feng Wang

Graph-based semi-supervised learning is one of the most popular methods in machine learning. We prove the consistency of graph-based learning in the case that the estimated scores are enforced to be equal to the observed responses.

0
0
0
Abstract

Graph-based semi-supervised learning is one of the most popular methods in machine learning. Some of its theoretical properties such as bounds for the generalization error and the convergence of the graph Laplacian regularizer have been studied in computer science and statistics literatures. However, a fundamental statistical property, the consistency of the estimator from this method has not been proved. In this article, we study the consistency problem under a non-parametric framework. We prove the consistency of graph-based learning in the case that the estimated scores are enforced to be equal to the observed responses for the labeled data. The sample sizes of both labeled and unlabeled data are allowed to grow in this result. When the estimated scores are not required to be equal to the observed responses, a tuning parameter is used to balance the loss function and the graph Laplacian regularizer. We give a counterexample demonstrating that the estimator for this case can be inconsistent. The theoretical findings are supported by numerical studies.

Sat Jul 25 2020
Machine Learning
Posterior Consistency of Semi-Supervised Regression on Graphs
Graph-based semi-supervised regression (SSR) is the problem of estimating the value of a function on a weighted graph. We present a Bayesian formulation of SSR in which the weighted graph defines aGaussian prior, using a graph Laplacian.
0
0
0
Sat Feb 14 2015
Machine Learning
Asymptotic Justification of Bandlimited Interpolation of Graph signals for Semi-Supervised Learning
Graph-based methods play an important role in unsupervised and semi-supervised learning tasks by taking into account the underlying geometry of the data set. We demonstrate the practical utility of our results through simple experiments.
0
0
0
Wed Oct 10 2018
Machine Learning
Properly-weighted graph Laplacian for semi-supervised learning
The performance of traditional graph Laplacian methods for semi-supervised learning degrades substantially as the ratio of labeled to unlabeled data decreases. Several approaches have been proposed recently to address this, but some of them remain ill-posed in the large-data limit.
0
0
0
Mon Oct 19 2015
Machine Learning
Robust Semi-Supervised Classification for Multi-Relational Graphs
Graph-regularized semi-supervised learning has been used effectively for classification when (i) instances are connected through a graph, and (ii)labeled data is scarce. If available, using multiple relations (or graphs) between the instances can improve the prediction performance.
0
0
0
Tue Jun 18 2019
Machine Learning
Consistency of semi-supervised learning algorithms on graphs: Probit and one-hot methods
Graph-based semi-supervised learning is the problem of propagating labels from a small number of labelled data points to a larger set of unlabelled data. We study graph-based probit for binary classification, and a natural generalization of this method to multi-class classification.
0
0
0
Fri Oct 20 2017
Machine Learning
On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms
When consistency holds, carefully designed graph-based Markov chain Monte Carlo algorithms are proved to have a uniform spectral gap. Several numerical experiments corroborate both the statistical consistency and the algorithmic scalability established by the theory.
0
0
0