TR-2003-11
Regression and Regularization on Large Graphs
Mikhail Belkin; Irina Matveeva; Partha Niyogi. 4 November, 2003.
Communicated by Partha Niyogi.
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 application when the data is abundant but labeling is expensive or requires human assistance.Our approach develops a framework for regularization on such graphs. Within this framework, two algorithms are developed. 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 the structural invariants of the graph. Some experimental comparisons to existing algorithms suggest that this approach is competitive.
Original Document
The original document is available in Postscript (uploaded 4 November, 2003 by Partha Niyogi).