When Labelled Data Hurts: Deep Semi-Supervised Classification with the Graph 1-Laplacian.

We consider the task of classifying when a significantly reduced amount of labelled data is available. This problem is of a great interest, in several real-world problems, as obtaining large amounts of labelled data is expensive and time consuming. We present a novel semi-supervised framework for multi-class classification that is based on the non-smooth $\ell_1$ norm of the normalised graph 1-Laplacian. Our transductive framework is framed under a novel functional with carefully selected class priors - that enforces a sufficiently smooth solution and strengthens the intrinsic relation between the labelled and unlabelled data. We provide theoretical results of our new optimisation model and show its connections with deep learning for handling large-scale datasets. We demonstrate through extensive experimental results on large datasets - CIFAR-10, CIFAR-100 and ChestX-Ray14 - that our method outperforms classic methods and readily competes with recent deep-learning approaches.