Lévy Flights for Graph Based Semi-Supervised Classification

National audience; 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.