Graph construction based on data self-representativeness and Laplacian smoothness

Recently, graph-based semi-supervised learning (SSL) becomes a hot topic in machine learning and pattern recognition. It has been shown that constructing an informative graph is one of the most important steps in SSL since a good graph can significantly affect the final performance of learning algorithms. This paper has the following main contributions. First, we introduce a new graph construction method based on data self-representativeness and Laplacian smoothness (SRLS). Second, this method is refined by incorporating an adaptive coding scheme aiming at getting a sparse graph. Third, we propose two kernelized versions of the SRLS method. A series of experiments on several public image data sets show that the proposed methods can out-perform many state-of-the-art methods. It is shown that Laplacian smoothness criterion is indeed a powerful tool to get informative graphs.