One hundred and twenty points on two noisy half-moons are joined to their \(k\) nearest neighbours; only a few points per moon carry a label (circled). Label propagation repeatedly replaces the value at every unlabelled node by the weighted average of its neighbours, with the labelled values clamped; its limit is the harmonic solution \(\mathbf f_U=(\mathbf D_{UU}-\mathbf W_{UU})^{-1}\mathbf W_{UL}\mathbf f_L\), the minimiser of the Dirichlet energy \(\tfrac12\sum_{ij}W_{ij}(f_i-f_j)^2\). Label spreading instead solves \(\mathbf F=(1-\alpha)(\mathbf I-\alpha\mathbf S)^{-1}\mathbf Y\) with \(\mathbf S=\mathbf D^{-1/2}\mathbf W\mathbf D^{-1/2}\). Colour is the predicted probability of the red moon; a cross marks a wrongly classified point.
The labelled points are the first \(m\) of each moon in the order of the data file. The accuracy counts all 120 points. The middle panel shows the accuracy of the iteration after \(t\) sweeps (gold marker) against the accuracy of the harmonic solution (dashed); the lower panel shows how fast the iterates approach the harmonic solution.
code/ch23_graph_embeddings.py (knn_graph, label_propagation, harmonic_solution, label_spreading).