Title:
Label propagation is an approach to iteratively spread the prior state of label confidence associated with each of samples to its neighbors until achieving a global convergence state. Such process has been shown to hold close connection with a general graph-based regularization framework. Within this framework, a closed- form linear system can be built to carry out label propagation. In this paper, to address several issues inherent with previous graph-based label propagation framework, we propose a reformulated one, i.e., local structure sensitive label propagation (LSSLP). By associating each graph vertex with a local structure sensitive tuning factor, the empirical loss error on each vertex can be controlled preferably to keep consistent with the commonly preconditioned 'cluster assumption' of data structure. Out of consideration for information conservation, we relax the state conservation constraint of label confidence from labeled samples proposed by Belkin etal. (2004) to a more general form. Meanwhile, an inverse-warping procedure is incorporated into the proposed local structure sensitive label propagation framework to maintain large and stable enough classification margin. Based on the felicitous inversion technique for blocked matrix, we extend LSSLP to its incremental and inductive versions and also present computationally efficient implementation of it. Experimental results demonstrate the performance of the reformulated regularization framework for label propagation is much competitive. (C) 2015 Elsevier Inc. All rights reserved.