Label propagation turns a few labels into labels for every point by spreading them over a similarity graph. Implement four functions. Labels are integers 0..C-1; labeled_idx lists the labeled nodes and y_labeled their classes.
knn_graph(X, k, sigma): symmetric weight matrix W of shape (N, N). Node j is a neighbour of i if it is among the k nearest points to i by Euclidean distance (excluding i; break distance ties by the smaller index). Connect i and j if either is a neighbour of the other, with weight . All other entries, including the diagonal, are 0.
propagate(W, labeled_idx, y_labeled, C, n_iter): the iteration of [ZG02]. Build . Start from Y with one-hot rows for labeled nodes and uniform rows for the rest. Repeat n_iter times: , divide each row by its sum, then reset the labeled rows to their one-hot labels. Return Y.
harmonic(W, labeled_idx, y_labeled, C): the minimiser of with labeled rows clamped to their one-hot labels. Return the full (N, C) matrix.
spread(W, labeled_idx, y_labeled, C, alpha): label spreading [Zho+04], the fixed point of with , , and one-hot on labeled rows and zero elsewhere. Return the closed-form F (unnormalised).
Every node has at least one edge in the tests.