Is one label enough?

Labels are expensive, unlabelled data is plentiful. The intuition behind semi-supervised learning is simple: data points do not scatter randomly through space, they live on a low-dimensional manifold. Points close together on the same surface probably share a class. So spreading a few labels along that surface may be enough to classify the unlabelled points too.

We do not know the surface but we can approximate it: build a graph linking each point to its k nearest neighbours. Then diffuse the labels over that graph like heat; every point takes its neighbours’ average while the labelled points hold their values. That is label propagation.

On the two moons a single label per class is often enough. Raise the noise or grow k: red edges appear that bridge the two moons, and the label leaks across the bridge. The honesty of the graph matters more than the number of labels.

With k too small the graph falls apart into islands: no information reaches an island without a label. With k too large every point also links to distant points of the wrong class and purity drops. In a narrow band between, the graph is both connected and honest. That is atlas’s central finding: one label per class recovers about 95 percent of MNIST when the metric is good enough; when the metric is poor, the same method hurts.

You will see two edges in the curves: the cliff on the left comes from the graph breaking apart, the slow decline on the right from purity decaying. Adding labels closes the left cliff but cannot fully rescue a dirty graph. atlas measures this balance on MNIST, reproducibly, across metrics and label budgets.