Lévy Flights for Graph Based Semi-Supervised Classification.

Esteban Bautista 1 Sarah De Nigris 1 Patrice Abry 2 Konstantin Avrachenkov 3 Paulo Gonçalves 1
1 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
3 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Classification through Graph-based semi-supervised learning algorithms can be viewed as a diffusion process with restart on the labels. In this work, we exploit this equivalence to introduce a novel algorithm which relies on the formulation of a non-local diffusion process, fueled by the γ-th power of the standard Laplacian matrix Lγ, with 0 < γ < 1. This approach allows to jump in one step between far apart nodes and such long-range transitions, called Lévy Flights, entail a wider exploration of the graph. In the present contribution, we embed such mechanism in graph based semi-supervised algorithms to improve the classification outcome, even in settings traditionally poorly performing such as unbalanced classes, and we derive a theoretical rule for classification decision.
Type de document :
Communication dans un congrès
26th colloquium GRETSI, Sep 2017, Juan-Les-Pins, France. GRETSI, 2017 - Proceeding of the 26th colloquium
Liste complète des métadonnées

https://hal.inria.fr/hal-01586760
Contributeur : Paulo Gonçalves <>
Soumis le : mercredi 13 septembre 2017 - 11:27:14
Dernière modification le : vendredi 20 avril 2018 - 15:44:27

Identifiants

  • HAL Id : hal-01586760, version 1

Citation

Esteban Bautista, Sarah De Nigris, Patrice Abry, Konstantin Avrachenkov, Paulo Gonçalves. Lévy Flights for Graph Based Semi-Supervised Classification. . 26th colloquium GRETSI, Sep 2017, Juan-Les-Pins, France. GRETSI, 2017 - Proceeding of the 26th colloquium. 〈hal-01586760〉

Partager

Métriques

Consultations de la notice

167