Robust and sparse label propagation for graph-based semi-supervised classification

Traditional graph-based semi-supervised classification algorithms are usually composed of two independent parts: graph construction and label propagation. However, the predefined graph may not be optimal for label propagation, and these methods usually use the raw data containing noise directly, which may reduce the accuracy of the algorithm. In this paper, we propose a robust label prediction model called the robust and sparse label propagation (RSLP) algorithm. First, our RSLP algorithm decomposes the raw data into a low-rank clean part and a sparse noise part, and performs graph construction and label propagation in the clean data space. Second, RSLP seamlessly combines the processes of graph construction and label propagation. By jointly minimizing the sample reconstruction error and the label reconstruction error, the resulting graph structure is globally optimal. Third, the proposed RSLP performs l(2,1)-norm regularization on the predicted label matrix, thereby enhancing the sparsity and discrimination of soft labels. We also analyze the connection between RSLP and other related algorithms, including label propagation algorithms, the robust graph construction method, and principal component analysis. A series of experiments on several benchmark datasets show that our RSLP algorithm achieves comparable and even higher accuracy than other state-of-the-art algorithms.