Lévy Flights for Graph Based Semi-Supervised Classification. - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (1) , (2) , (3) , (1)


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.
Not file

Dates and versions

hal-01586760 , version 1 (13-09-2017)


  • 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⟩
274 View
0 Download


Gmail Facebook Twitter LinkedIn More