Fast Semisupervised Learning with Bipartite Graph for Large-Scale Data

As the captured information in our real word is very scare and labeling sample is time cost and expensive, semisupervised learning (SSL) has an important application in computer vision and machine learning. Among SSL approaches, a graph-based SSL (GSSL) model has recently attracted much attention for high accuracy. However, for most traditional GSSL methods, the large-scale data bring higher computational complexity, which acquires a better computing platform. In order to dispose of these issues, we propose a novel approach, bipartite GSSL normalized (BGSSL-normalized) method, in this paper. This method consists of three parts. First, the bipartite graph between the original data and the anchor points is constructed, which is parameter-insensitive, scale-invariant, naturally sparse, and simple operation. Then, the label of the original data and anchors can be inferred through the graph. Besides, we extend our algorithm to handle out-of-sample for large-scale data by the inferred label of anchors, which not only retains good classification result but also saves a large amount of time. The computational complexity of BGSSL-normalized can be reduced to O(ndm+nm{2}) , which is a significant improvement compared with traditional GSSL methods that need O(n{2}d+n{3}) , where n , d, and m are the number of samples, features, and anchors, respectively. The experimental results on several publicly available data sets demonstrate that our approaches can achieve better classification accuracy with less time costs.