Fast Semi-Supervised Learning with Optimal Bipartite Graph

Recently, with the explosive increase in Internet data, the traditional Graph-based Semi-Supervised Learning (GSSL) model is not suitable to deal with large scale data as the high computation complexity. Besides, GSSL models perform classification on a fixed input data graph. The quality of initialized graph has a great effect on the classification result. To solve this problem, in this paper, we propose a novel approach, named optimal bipartite graph-based SSL (OBGSSL). Instead of fixing the input data graph, we learn a new bipartite graph to make the result more robust. Based on the learned bipartite graph, the labels of the original data and anchors can be calculated simultaneously, which solves co-classification problem in SSL. Then, we use the label of anchor to handle out-of-sample problem, which preserves well classification performance and saves much time. The computational complexity of OBGSSL is O(ndmt+nm^2)O(ndmt+nm2), which is a significant improvement compared with traditional GSSL methods that need O(n^2d+n^3)O(n2d+n3), where nn, dd, mm and tt are the number of samples, features anchors and iterations, respectively. Experimental results demonstrate the effectiveness and efficiency of our OBGSSL model.