Interactive demo · Probabilistic Machine Learning · Chapter 23

Label propagation on a nearest-neighbour graph

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.

Method

Labelled points per moon m

Neighbours in the graph k

Sweeps shown t (iteration)

Spreading α

Try these

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.

In the lecture notes