Sparse graphs with smoothness constraints: Application to dimensionality reduction and semi-supervised classification. (November 2019)

• Record Type: Journal Article
• Authors: Dornaika, F.; Weng, L.
• Is Part Of: Pattern recognition. Volume 95(2019:Nov.)
• Page Start: 285
• Page End: 295
• Publication Date: 2019-11
• Subjects: Graph construction -- Sparse representation -- Manifold constraints -- Laplacian smoothness -- Graph-based semi-supervised learning -- Label propagation -- Graph-based embedding -- Classification,; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2019.06.015
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: A constrained sparse graph construction method is proposed. The method does not require a predefined affinity matrix. The proposed constraints impose edge weights smoothness. The proposed constraints lead to a structured sparse graph. Performance is assessed on graph-based label propagation and embedding. Abstract: Sparse representation is a useful tool in machine learning and pattern recognition area. Sparse graphs (graphs constructed using sparse representation of data) proved to be very informative graphs for many learning tasks such as label propagation, embedding, and clustering. It has been shown that constructing an informative graph is one of the most important steps since it significantly affects the final performance of the post graph-based learning algorithm. In this paper, we introduce a new sparse graph construction method that integrates manifold constraints on the unknown sparse codes as a graph regularizer. These constraints seem to be a natural regularizer that was discarded in existing state-of-the art graph construction methods. This regularizer imposes constraints on the graph coefficients in the same way a locality preserving constraint imposes on data projection in non-linear manifold learning. The proposed method is termed Sparse Graph with Laplacian Smoothness (SGLS). We also propose a kernelized version of the SGLS method. A series of experimental results on several public image datasets show that the proposed methods can out-perform many state-of-the-art methods for the tasks of label propagation, nonlinear and linear embedding.