Greedy multi-class label propagation

In many real-world applications such as image classification, labeled training examples are difficult to obtain while unlabeled examples are readily available. In this context, semi-supervised learning methods take advantage of both labeled and unlabeled examples. In this paper, a greedy graph-based semi-supervised learning (GGSL) approach is proposed for multi-class classification problems. The labels are propagated through different graphs, which are obtained with neighborhoods of different sizes. The method assumes that nearby points share the same label, by starting with a small neighborhood where a reliable decision can be obtained, and iterates with larger neighborhoods where more examples are needed to determine the label of an example. The experimental results on toy data-sets and real data-sets, such as handwritten digit recognition, demonstrate the effectiveness of the proposed approach if a well chosen distance is used. Finally, the method does not require the tuning of hyper-parameters. We show that it is possible to achieve a recognition rate of 97.16% on handwritten digits (MNIST) while considering only one labeled example per class in the training data-set.