Label Propagation Based on Bipartite Graph

Label propagation (LP) is a popular graph-based semi-supervised learning framework. Its effectiveness is limited by the distribution of prior labels. If there are no objects with prior labels in parts of classes, label propagation has very poor performance. To address this issue, we propose a label propagation based on bipartite graph (LPBBG) algorithm. This approach try to learn a bipartite graph as exemplar constraints that reflect the relations between objects and exemplars to guide the learning process instead of label constraints in the traditional label propagation. In this paper, we provide a method for producing high-quality exemplars from two channels to represent the known classes (where some objects have prior labels) and the missing classes (where all the objects have no prior labels). Given generated exemplars, exemplar constraints can be learned using relationships in the known classes to evaluate that in the missing classes. Our experimental results show that the LPBBG algorithm outperforms existing LP methods in overcoming the label missing problem in some classes.