Abstract
As a typical means for semi-supervised learning, label propagation (LP) generally aims at predicting unlabeled samples by a tiny percentage of labeled samples. After briefly reviewing the existing LP methods based on the manifold assumption, this study summarizes three phenomenal-level issues in all these methods, including an explicit or implicit calculation of matrix inversion, strong dependency on K-nearest neighbor graph, and insufficient affinity learning. To address these issues, a novel LP method called Fast Doubly Reconstructed Affinity Propagation (FDRAP) for semi-supervised data classification is accordingly proposed by resorting to fast doubly reconstruction of the affinity graph. FDRAP starts with two unique ideas: (1) By characterizing the pairwise typicality of each nodal pair through the strength of each node therein, the given affinity graph is reconstructed to reflect the tendency of each nodal pair in representing two respective clusters. (2) By estimating the label propagation probability of each nodal pair through the difference from its disaffinity to the own disaffinity of each sample therein, each disaffinity originating from the reconstructed affinity graph is again reconstructed with such probability for much stronger separability of the final propagation matrix. And accordingly, its simple label propagation for each unlabeled sample is accomplished only through the summation of the reconstructed disaffinity multiplied by the label vector. The striking results on several test cases indicate that FDRAP has competitive classification accuracy and outlier detection, fast running speed and strong scalability.