Positive and Negative Label Propagations
This paper extends the state-of-the-art label propagation (LP) framework in the propagation of negative labels. More specifically, the state-of-the-art LP methods propagate information of the form “the sample <inline-formula> <tex-math notation="LaTeX">$i$ </tex-math></inline-formula> should be assigned the label <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>.” The proposed method extends the state-of-the-art framework by considering additional information of the form “the sample <inline-formula> <tex-math notation="LaTeX">$i$ </tex-math></inline-formula> should not be assigned the label <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>.” A theoretical analysis is presented in order to include negative LP in the problem formulation. Moreover, a method for selecting the negative labels in cases when they are not inherent from the data structure is presented. Furthermore, the incorporation of negative label information in two multigraph LP methods is presented. Finally, a discussion on the proposed algorithm extension to out of sample data, as well as scalability issues, is presented. Experimental results in various scenarios showed that the incorporation of negative label information increases, in all cases, the classification accuracy of the state of the art.