Regularization and Semi-Supervised Learning on Large Graphs
Abstract
We consider the problem of labeling a partially labeled graph. This setting may arise in a number of situations from survey sampling to information retrieval to pattern recognition in manifold settings. It is also of potential practical importance, when the data is abundant, but labeling is expensive or requires human assistance. Our approach develops a framework for regularization on such graphs. The algorithms are very simple and involve solving a single, usually sparse, system of linear equations. Using the notion of algorithmic stability, we derive bounds on the generalization error and relate it to structural invariants of the graph. Some experimental results testing the performance of the regularization algorithm and the usefulness of the generalization bound are presented.
Cite
Text
Belkin et al. "Regularization and Semi-Supervised Learning on Large Graphs." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_43Markdown
[Belkin et al. "Regularization and Semi-Supervised Learning on Large Graphs." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/belkin2004colt-regularization/) doi:10.1007/978-3-540-27819-1_43BibTeX
@inproceedings{belkin2004colt-regularization,
title = {{Regularization and Semi-Supervised Learning on Large Graphs}},
author = {Belkin, Mikhail and Matveeva, Irina and Niyogi, Partha},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {624-638},
doi = {10.1007/978-3-540-27819-1_43},
url = {https://mlanthology.org/colt/2004/belkin2004colt-regularization/}
}