While graph-based semi-supervised learning is easy to implement, it is computationally intractable for large scale problems. In this paper, we address the scalability issue via a small number of anchor points which adequately cover the entire data set and, critically, support label regression that predicts the label for each data point as a linear function of the labels on anchor points. Because conventional graph construction is computationally inefficient in large scale, we propose to construct a tractable large graph by coupling anchor-based label regression and adjacency matrix design. Contrary to previous low-rank approximation of adjacency matrices which results in indefinite graph Laplacians and in turn leads to potential non-convex optimization on graphs, the proposed graph construction approach provides nonnegative adjacency matrices to guarantee positive semidefinite graph Laplacians. Our approach usually obtains a large sparse graph and scales linearly with the data size. Experiments on synthetic and real-world data sets exhibit superior performance and scalable properties of the proposed approach.
Download PDF