Graph based semi-supervised learning via label fitting

The global smoothness and the local label fitting are two key issues for estimating the function on the graph in graph based semi-supervised learning (GSSL). The unsupervised normalized cut method can provide a more reasonable criterion for learning the global smoothness of the data than classic GSSL methods. However, the semi-supervised norm of the normalized cut, which is a NP-hard problem, has not been studied well. In this paper, a new GSSL framework is proposed by extending normalized cut to its semi-supervised norm. The NP-hard semi-supervised normalized cut problem is innovatively solved by effective algorithms. In addition, we can design more reasonable local label fitting terms than conventional GSSL methods. Other graph cut methods are also investigated to extend the proposed semi-supervised learning algorithms. Furthermore, we incorporate the nonnegative matrix factorization with the proposed learning algorithms to solve the out-of-sample problem in semi-supervised learning. Solutions obtained by the proposed algorithms are sparse, nonnegative and congruent with unit matrix. Experiment results on several real benchmark datasets indicate that the proposed algorithms achieve good results compared with state-of-art methods.