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):
- Define a matrix YMi = [P(label=y0), P(label=y1), ..., and P(label=yQ)], 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
- Define Y(0) = YM
- Iterate until convergence ...