Generalized Optimization Framework for Graph-based Semi-supervised Learning

Abstract : We develop a generalized optimization framework for graph-based semi-supervised learning. The framework gives as particular cases the Standard Laplacian, Normalized Laplacian 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 di erences between the performances of methods with di erent smoothing kernels. It appears that the PageRank based method is robust with respect to the choice of the regularization parameter and the labelled data. We illustrate our theoretical results with two realistic datasets, characterizing di erent challenges: Les Miserables characters social network and Wikipedia hyper-link graph. The graph-based semi-supervised learning classi- es the Wikipedia articles with very good precision and perfect recall employing only the information about the hyper-text links.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00633818
Contributor : Marina Sokol <>
Submitted on : Wednesday, October 19, 2011 - 2:56:52 PM
Last modification on : Wednesday, November 20, 2019 - 2:48:32 AM
Long-term archiving on: Thursday, November 15, 2012 - 10:01:55 AM

Files

RR-7774.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00633818, version 1
  • ARXIV : 1110.4278

Collections

Citation

Konstantin Avrachenkov, Paulo Gonçalves, Alexey Mishenin, Marina Sokol. Generalized Optimization Framework for Graph-based Semi-supervised Learning. [Research Report] RR-7774, INRIA. 2011. ⟨inria-00633818⟩

Share

Metrics

Record views

520

Files downloads

399