Semi-supervised classification and projection with adaptive flexible structure optimal graph.

Abstract

Graph-based semi-supervised learning (GSSL) has received more attention in recent years. Many existing methods obtain a fixed similarity graph based on the original data. Affected by the redundant information and noise of the original data, the obtained similarity graph is not optimal, which greatly affects the subsequent work. And the similarity graphs obtained by these methods are fully connected, so the local structure information of the data cannot be preserved. Moreover, many GSSL methods project the original data into a low-dimensional space through a linear mapping function. However, linear functions may not be appropriate for data embedded in a nonlinear manifold. In order to overcome these shortcomings mentioned above, we relax the linear mapping function and impose a ℓ₀-norm constraint on the similarity graph to gain an adaptive flexible structure optimal graph. Furthermore, incorporating the principle of maximum separability, an efficient GSSL method is proposed, named semi-supervised classification and projection with adaptive flexible structure optimal graph (SAFSG). Combining the construction of similarity graphs and label propagation, SAFSG can simultaneously get an adaptive flexible structure optimal graph, a label prediction matrix and a projection matrix. In addition, an efficient iterative algorithm for optimizing SAFSG is proposed. Finally, we conduct experiments on more than ten benchmark datasets, and the experimental results show that SAFSG performs satisfactorily in both classification and projection.