Abstract
Graph based semi-supervised learning (GSSL) plays an important role in machine learning systems. The most crucial step in GSSL is graph construction. Although several interesting graph construction methods have been proposed in recent years, how to construct an effective graph is still an open problem. In this paper, we develop a novel approach to constructing graph, which is based on low-rank coding and b-matching constraint. By virtue of recent advances in low-rank subspace recovery theory, compact encoding using low-rank representation coefficients allows us to obtain a robust similarity metric between all pairs of samples. Meanwhile, the b-matching constraint helps in obtaining a sparse and balanced graph, which benefits label propagation in GSSL. We build a joint optimization model to learn lowrank codes and balanced graph simultaneously. After using a graph re-weighting strategy, we present a semi-supervised learning algorithm by incorporating our sparse and balanced graph with Gaussian harmonic function (GHF). Experimental results on the Extended YaleB, PIE, ORL and USPS databases demonstrate that our graph outperforms several state-of-the-art graphs, especially when the labeled samples are very scarce.