Generalized optimization framework for graph-based semi-supervised learning. Submitted for publication, available upon request

We develop a generalized optimization framework for graph-based semi-supervised learning. The framework gives as particular cases the Standard Laplacian, Normalized Lapla-cian and PageRank based methods. We have also provided new probabilistic interpretation based on random walks and characterized the limiting behaviour of the methods. The random walk based interpretation allows us to explain dif-ferences between the performances of methods with differ-ent smoothing kernels. It appears that the PageRank based method is robust with respect to the choice of the regu-larization parameter and the labelled data. We illustrate our theoretical results with two realistic datasets, charac-terizing different challenges: Les Miserables characters so-cial network and Wikipedia hyper-link graph. The graph-based semi-supervised learning classifies the Wikipedia ar-ticles with very good precision and perfect recall employing only the information about the hyper-text links