Efficient Label Propagation

Abstract

Label propagation is a popular graph-based semi-supervised learning framework. So as to obtain the optimal labeling scores, the label propagation algorithm requires an inverse matrix which in-curs the high computational cost ofO(n3+cn2), where n and c are the numbers of data points and labels, respectively. This paper proposes an effi-cient label propagation algorithm that guarantees exactly the same labeling results as those yielded by optimal labeling scores. The key to our ap-proach is to iteratively compute lower and upper bounds of labeling scores to prune unnecessary score computations. This idea significantly re-duces the computational cost to O(cnt) where t is the average number of iterations for each label and t ≪ n in practice. Experiments demonstrate the significant superiority of our algorithm over existing label propagation methods. 1.