Generalized Optimization Framework for Graph-based Semi-supervised Learning

Konstantin Avrachenkov 1 Paulo Gonçalves 2 Alexey Mishenin Marina Sokol 1
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
2 RESO - Protocols and softwares for very high-performance network
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We develop a generalized optimization framework for graphbased 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 differences 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 graphbased semi-supervised learning classi es the Wikipedia articles with very good precision and perfect recall employing only the information about the hyper-text links.
Type de document :
Communication dans un congrès
SIAM Data Mining, Date-Added = 2012-01-05 12:17:13 +0100, Date-Modified = 2012-04-16 17:23:09 +0200, Apr 2012, Anaheim (CA), United States. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00747649
Contributeur : Paulo Gonçalves <>
Soumis le : mercredi 31 octobre 2012 - 18:24:00
Dernière modification le : mardi 16 janvier 2018 - 15:33:49

Identifiants

  • HAL Id : hal-00747649, version 1

Collections

Citation

Konstantin Avrachenkov, Paulo Gonçalves, Alexey Mishenin, Marina Sokol. Generalized Optimization Framework for Graph-based Semi-supervised Learning. SIAM Data Mining, Date-Added = 2012-01-05 12:17:13 +0100, Date-Modified = 2012-04-16 17:23:09 +0200, Apr 2012, Anaheim (CA), United States. 2012. 〈hal-00747649〉

Partager

Métriques

Consultations de la notice

129