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.
Document type :
Conference papers
Liste complète des métadonnées

Contributor : Paulo Gonçalves <>
Submitted on : Wednesday, September 13, 2017 - 11:27:14 AM
Last modification on : Wednesday, April 3, 2019 - 1:10:08 AM


  • HAL Id : hal-01586760, version 1


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. ⟨hal-01586760⟩



Record views