Graph-based Semi-Supervised Learning in the Extreme Low-Label Regime

Graph-based semi-supervised learning spreads a small set of labels across a graph whose edges encode similarity between data points, and it is the natural tool wherever annotation is costly but relations between samples are known. The underlying task is combinatorial, since each vertex must receive exactly one label and each class must retain its share of the vertices. Established methods relax those requirements, in the sense of losing tightness, solving a continuous surrogate and reading a labeling off it afterwards; we keep the problem discrete throughout. An auxiliary variable linearizes the quadratic objective, so that every iteration becomes a transportation problem with a totally unimodular constraint matrix, whose solution is integral without any rounding and meets the prescribed class sizes exactly. We prove that the iteration ascends monotonically, that the objective sequence converges, and that its limit points are stationary. Because the problem is non-convex, the initialization also matters, and we therefore unroll the iteration into a network whose ingredients are learned and which keeps the prescribed class sizes exact at inference. Our study is directed at the extreme low-label regime, where only a few labels per class are observed and where graph-based methods are most needed. On citation benchmarks in that regime the proposed method outperforms the state of the art in accuracy and labels each graph in a fraction of a second.