Adjacency Matrix Construction Using Sparse Coding for Label Propagation

Abstract

Graph-based semi-supervised learning algorithms have attracted increasing attentions recently due to their superior performance in dealing with abundant unlabeled data and limited labeled data via the label propagation. The principle issue of constructing a graph is how to accurately measure the similarity between two data examples. In this paper, we propose a novel approach to measure the similarities among data points by means of the local linear reconstruction of their corresponding sparse codes. Clearly, the sparse codes of data examples not only preserve their local manifold semantics but can significantly boost the discriminative power among different classes. Moreover, the sparse property helps to dramatically reduce the intensive computation and storage requirements. The experimental results over the well-known dataset Caltech-101 demonstrate that our proposed similarity measurement method delivers better performance of the label propagation.