Generalized Optimization Framework for Graph-based Semi-supervised Learning

Konstantin Avrachenkov; Paulo Gonçalves; Alexey Mishenin; Marina Sokol

inria-00633818, version 1

Generalized Optimization Framework for Graph-based Semi-supervised Learning

Konstantin Avrachenkov () ¹, Paulo Gonçalves ()^a^, 2, Alexey Mishenin ()^b^, 3, Marina Sokol () ¹

N° RR-7774 (2011)

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.

a – INRIA
b – St. Petersburg State University
1: MAESTRO (INRIA Sophia Antipolis)
INRIA – Université Montpellier II - Sciences et techniques
2: Laboratoire de l'Informatique du Parallélisme (LIP)
Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I
3: Mathematics and Mechanics Faculty [St Petersbourg]
St. Petersburg State University

inria-00633818, version 1
http://hal.inria.fr/inria-00633818
oai:hal.inria.fr:inria-00633818
From: Marina Sokol <>
Submitted on: Wednesday, 19 October 2011 14:56:52
Updated on: Friday, 6 January 2012 14:01:39

See detailed view

Associated documents

PDF :

arXiv: 1110.4278

Export

Bibtex EndNote TEI RefWorks

%F inria-00633818, version 1
%0 Report
%U http://hal.inria.fr/inria-00633818
%2 INFO:INFO_NI
%T Generalized Optimization Framework for Graph-based Semi-supervised Learning
%A Avrachenkov, Konstantin
%A Gonçalves, Paulo
%A Mishenin, Alexey
%A Sokol, Marina
%+ MAESTRO - INRIA Sophia Antipolis , Laboratoire de l'Informatique du Parallélisme - LIP , Mathematics and Mechanics Faculty [St Petersbourg]
%X 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.
%2 Dans ce rapport nous proposons un schéma d'optimisation générique pour l'apprentissage semi-supervisé sur des graphes. Ce cadre intègre comme cas particuliers les approches dites du Laplacien standard et du Laplacien normalis é ainsi qu'une méthode basée sur PageRank. Nous proposons également une interprétation probabiliste originale qui s'appuie sur la notion de marche aléatoire, puis nous étudions les comportements limites de ces méthodes. Le recours aux marches aléatoires nous permet d'expliquer les di érences de performances existant entre ces trois noyaux de lissage. Une des conclusions principales de ce travail est que les méthodes construites sur PageRank sont plus robustes face au choix du paramètre de régularisation et des points marqués. Nous illustrons nos résultats théoriques avec deux jeux de données réelles représentatives de deux dé s distincts: celui des réseaux sociaux avec le cas des personnages du roman "Les Misérables" et celui des graphes d'hyper-liens à travers l'application Wikipedia. En particulier, nous démontrons qu'il est possible de classi er les articles de Wikipedia avec une très bonne précision et un très bon rappel, à partir de la seule information fournie par les liens hyper-texte.
%G English
%2 Research Report
%8 2011-10-19
%K Semi-supervised Learning; PageRank; Random Walk on Graphs; Wikipedia Automatic Article Classi cation
%Z RR-7774
%Z The work has been supported by the joint INRIA Alcatel-Lucent Laboratory.

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00633818"><monogr>
<author><persName><forename>Konstantin</forename><surname>Avrachenkov</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">MAESTRO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<author><persName><forename>Paulo</forename><surname>Gonçalves</surname></persName>
<affiliation>
<orgName type="laboratory">LIP</orgName>
<orgName type="team">Laboratoire de l'Informatique du Parallélisme</orgName>
<country>FR</country>
<orgName type="institution">Université de Lyon</orgName>
<orgName type="institution">CNRS : UMR5668</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">École Normale Supérieure - Lyon</orgName>
<orgName type="institution">Université Claude Bernard - Lyon I</orgName>
</affiliation>
</author>
<author><persName><forename>Alexey</forename><surname>Mishenin</surname></persName>
<affiliation>
<orgName type="team">Mathematics and Mechanics Faculty [St Petersbourg]</orgName>
<country>RU</country>
<orgName type="institution">St. Petersburg State University</orgName>
</affiliation>
</author>
<author><persName><forename>Marina</forename><surname>Sokol</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">MAESTRO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<title type="main" level="m">Generalized Optimization Framework for Graph-based Semi-supervised Learning</title><title type="main" level="m">Generalized Optimization Framework for Graph-based Semi-supervised Learning</title><imprint><biblScope type="publicationDate">2011-10-19</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00633818</idno><idno type="HALFile">http://hal.inria.fr/inria-00633818/PDF/RR-7774.pdf</idno></biblStruct>
</listBibl>
</listBibl>