Sparse graphs using global and local smoothness constraints

Graph-based learning methods are very useful for many machine learning approaches and classification tasks. Constructing an informative graph is one of the most important steps since a graph can significantly affect the final performance of the learning algorithms. Sparse representation is a useful tool in machine learning and pattern recognition area. Recently, it was shown that sparse graphs (sparse representation based graphs) provide a powerful approach to graph-based semi-supervised classification. In this paper, we introduce a new graph construction method that simultaneously provides a sparse graph and integrates manifold constraints on the sparse coefficients without any prior knowledge on the graph or on its similarity matrix. Furthermore, we propose an efficient solution to the optimization problem. The proposed method imposes that the sparse coding vectors of similar samples should be also similar. Different from existing graph construction methods that are based on the use of explicit constraints or a predefined graph matrix, the proposed smoothness constraints on the graph weights implicitly adapt data to the global structure of the estimated graph. A series of experiments conducted on several public image databases shows that the proposed method can outperform many state-of-the-art methods when applied to the problem of graph-based label propagation.