l1-spectral clustering algorithm: a spectral clustering method using l1-regularization

Camille Champion (1) , Magali Champion (2) , Mélanie Blazère (3) , Rémy Burcelin (4) , Jean-Michel Loubes (3)

1 MGP (US 1367) - MetaGenoPolis
2 MAP5 - UMR 8145 - Mathématiques Appliquées Paris 5
3 IMT - Institut de Mathématiques de Toulouse UMR5219
4 I2MC - Institut des Maladies Métaboliques et Cardiovasculaires

Detecting cluster structure is a fundamental task to understand and visualize functional characteristics of a graph. Among the different clustering methods available, spectral clustering is one of the most widely used due to its speed and simplicity, while still being sensitive to perturbations imposed on the graph. In this paper, we present a variant of the spectral clustering algorithm, called l1-spectral clustering, based on Lasso regularization and adapted to perturbed graph models. Contrary to the spectral clustering, this procedure does not require the use of the k-means: it detects the hidden natural cluster structure of the graph by promoting sparse eigenbases solutions of specific l1-minimization problems. The effectiveness and robustness to noise perturbations of the l1-spectral clustering algorithm is confirmed through a collection of simulated and real biological data.

Mots clés: Unsupervised learning; Spectral clustering; l1-penalty; Biological networks

Domaines: Statistiques [math.ST]

Camille Champion, Magali Champion, Mélanie Blazère, Rémy Burcelin, Jean-Michel Loubes. l1-spectral clustering algorithm: a spectral clustering method using l1-regularization. 2022. ⟨hal-03095805v3⟩