Mastering Machine Learning Algorithms

Label propagation in Scikit-Learn

Scikit-Learn implements a slightly different algorithm proposed by Zhu and Ghahramani (in the aforementioned paper) where the affinity matrix W can be computed using both methods (KNN and RBF), but it is normalized to become a probability transition matrix:

The algorithm operates like a Markov random walk, with the following sequence (assuming that there are Q different labels):

1. Define a matrix Y^M_i = [P(label=y₀), P(label=y₁), ..., and P(label=y_Q)], where P(label=yi) is the probability of the label yi, and each row is normalized so that all the elements sum up to 1
2. Define Y⁽⁰⁾ = Y^M

3. Iterate until convergence ...