Positive and negative label propagation

Olga Zoidi, Anastasios Tefas, Nikos Nikolaidis, Ioannis Pitas

Research output: Contribution to journalArticle (Academic Journal)peer-review

10 Citations (Scopus)
307 Downloads (Pure)


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 i should be assigned the label k.' The proposed method extends the state-of-the-art framework by considering additional information of the form 'the sample i should not be assigned the label k.' 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.

Original languageEnglish
Article number7539355
Pages (from-to)342-355
Number of pages14
JournalIEEE Transactions on Circuits and Systems for Video Technology
Issue number2
Early online date10 Aug 2016
Publication statusPublished - 1 Feb 2018


  • Action recognition
  • face recognition
  • graph-based semisupervised learning (GSSL)
  • label propagation (LP)


Dive into the research topics of 'Positive and negative label propagation'. Together they form a unique fingerprint.

Cite this