Structured sparse graphs using manifold constraints for visual data analysis

Data-driven graphs constitute the cornerstone of many machine learning approaches. 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 structured sparse graph that is derived by integrating manifold-type constraints on the sparse coefficients without any a priori graph or similarity matrix. Furthermore, we introduce a direct and efficient solution to the proposed optimization problem. Unlike recent sparse graph construction methods that are based on the use of hand-crafted constraints or a predefined reference similarity matrix, our constraints are directly defined on the graph weights themselves, and can provide additional information to both local and global structures of the sparse graph. Experiments conducted on several image databases show that the proposed graph can give better results than many state-of-the-art sparse graphs when applied to the problem of graph-based label propagation.