Analysis of Graph-Based Semi-supervised Regression

Semi-supervised learning has been of growing interest over the past few years. Although there are various algorithms to implement semi-supervised learning task, the crucial issue of dependence of generalization error on the number of labeled and unlabeled examples is still very poorly understood. In this paper, we consider a regularization graph-based semi-supervised learning algorithm and give some error analysis for it. The convergence rates of the regularization algorithm, related to structural invariants of the graph, are established.