Semi-supervised Classification via Low Rank Graph

Graph plays a very important role in graph based semi-supervised learning (SSL) methods. However, most current graph construction methods emphasize on local properties of the graph. In this paper, inspired by the advances of compressive sensing, we present a novel method to construct a so-called low-rank graph (LR-graph) for graph based SSL methods. Assuming that the graph is sparse and low rank, our proposed method uses both the local property and the global property of the graph, and thus is better at capturing the global structure of all data. Compared with current graphs, LR-graph is more informative and discriminative, and robust to outliers. Experiments on generic object recognition show that LR-graph achieves state-of-the-art performance for graph based SSL methods.