Graph-based semi-supervised learning by mixed label propagation with a soft constraint

Abstract In recent years, various graph-based algorithms have been proposed for semi-supervised learning, where labeled and unlabeled examples are regarded as vertices in a weighted graph, and similarity between examples is encoded by the weight of edges. However, most of these methods cannot be used to deal with dissimilarity or negative similarity. In this paper we propose a mixed label propagation model with a single soft constraint which can effectively handle positive similarity and negative similarity simultaneously, as well as allow the labeled data to be relabeled. Specifically, the soft mixed label propagation model is a fractional quadratic programming problem with a single quadratic constraint, and we apply the global optimal algorithm [1] for solving it, yielding an ∊ -global optimal solution in a computational effort of O ( n 3 log ∊ - 1 ) . Numerical comparisons with several existing methods for common test datasets and a class of collaborative filtering problems verify the effectiveness of the method.