2011/10/01 by Konstantin Avrachenkov, Paulo Gonçalvés, Avrachenkov, Konstantin +6 · 1 citation
Computer Science · #Advanced Graph Neural Networks #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning and Data Classification #Networking and Internet Architecture (cs.NI) #Text and Document Classification Technologies
paper · pdf · doi:10.48550/arxiv.1110.4278
openalex publication_date 2011/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop a generalized optimization framework for graph-based\nsemi-supervised learning. The framework gives as particular cases the Standard\nLaplacian, Normalized Laplacian and PageRank based methods. We have also\nprovided new probabilistic interpretation based on random walks and\ncharacterized the limiting behaviour of the methods. The random walk based\ninterpretation allows us to explain di erences between the performances of\nmethods with di erent smoothing kernels. It appears that the PageRank based\nmethod is robust with respect to the choice of the regularization parameter and\nthe labelled data. We illustrate our theoretical results with two realistic\ndatasets, characterizing di erent challenges: Les Miserables characters social\nnetwork and Wikipedia hyper-link graph. The graph-based semi-supervised\nlearning classi- es the Wikipedia articles with very good precision and perfect\nrecall employing only the information about the hyper-text links.\n