Label Propagation through Linear Neighborhoods.

In many practical data mining applications such as text classification, unlabeled training examples are readily available, but labeled ones are fairly expensive to obtain. Therefore, semisupervised learning algorithms have aroused considerable interests from the data mining and machine learning fields. In recent years, graph-based semisupervised learning has been becoming one of the most active research areas in the semisupervised learning community. In this paper, a novel graph-based semisupervised learning approach is proposed based on a linear neighborhood model, which assumes that each data point can be linearly reconstructed from its neighborhood. Our algorithm, named Linear Neighborhood Propagation (LNP), can propagate the labels from the labeled points to the whole data set using these linear neighborhoods with sufficient smoothness. A theoretical analysis of the properties of LNP is presented in this paper. Furthermore, we also derive an easy way to extend LNP to out-of-sample data. Promising experimental results are presented for synthetic data, digit, and text classification tasks. [ABSTRACT FROM AUTHOR]