Label Propagation Based on Bipartite Graph

Label propagation is a popular graph-based semi-supervised learning framework. Its effectiveness depends on the distribution of prior labels. If there are no objects with prior labels in parts of classes, the label propagation has a very bad performance. To get rid of this deficiency, we propose a label propagation based on bipartite graph algorithm. In this algorithm, we try to learn a bipartite graph as exemplar constraints that reflect the relations between objects and exemplars representing all the classes to guide the learning process, instead of label constraints in original label propagation. We provide a method to produce high-quality exemplars from two channels representing the known classes (where some objects have prior labels) and the missing classes (where all the objects have no prior labels), respectively. Based on the generated exemplars, the exemplar constraints can be learned by using relations in the known classes to evaluate that in the missing classes. Compared to other existing versions of the LP algorithms , we use different experiments to prove that the proposed algorithm can effectively overcome the label missing problem in some classes.