Label propagation on a similarity graph

Spread known labels along a similarity graph

Label propagation (Zhou et al., 2004) treats semi-supervised learning as smoothing over a graph. Each point has a seed label row Y0 (one-hot for labeled points, zero for unlabeled ones). Labels spread along weighted edges until neighbours agree.

With S = D^(-1/2) W D^(-1/2), the iteration is F <- alpha * S F + (1 - alpha) * Y0. Its fixed point is F* = (1 - alpha) (I - alpha S)^(-1) Y0.

Implement propagate(W, Y0, alpha, iters). It runs iters iterations starting from F = Y0 and returns F.

Constraints

• W is a square, symmetric, nonnegative matrix with no node of zero degree. Otherwise raise ValueError.
• Y0 has one row per node. Its row count must match W.
• alpha must be in the open interval (0, 1). Otherwise raise ValueError.
• iters must be a nonnegative integer. Otherwise raise ValueError.
• Do not modify the inputs.

Hints