Directory Intranet
Chargement
DALL''AMICO Lorenzo

Méthodes spectrales pour la classification sur les graphes // Spectral methods for graph clustering

 

Directeur de thèse :     Romain COUILLET

Co-encadrant :     Nicolas TREMBLAY

École doctorale : Electronique, electrotechnique, automatique, traitement du signal (EEATS)

Spécialité : Signal, image, parole, télécoms

Structure de rattachement : Grenoble-INP

Établissement d'origine : École Polytechnique Palaiseau - Paris

Financement(s) : Contrat doctoral ; Sans financement

 

Date d'entrée en thèse : 01/10/2018

Date de soutenance : 12/10/2021

 

Composition du jury :

Monsieur Romain COUILLET: PROFESSEUR DES UNIVERSITES, Université Paris-Saclay, Directeur de thèse
Madame Lenka ZDEBOROVA: PROFESSEUR ASSOCIE, EPFL, Rapporteure
Monsieur Tiago DE PAULA PEIXOTO: PROFESSEUR ASSOCIE, Central European University, Rapporteur
Monsieur Alain BARRAT: DIRECTEUR DE RECHERCHE, CNRS, Examinateur
Monsieur Francesco BONCHI: DOCTEUR EN SCIENCES, ISI foundation, Examinateur
Monsieur Jean-Philippe BOUCHAUD: PROFESSEUR DES UNIVERSITES, CFM, Examinateur
Monsieur Laurent MASSOULIE: DIRECTEUR DE RECHERCHE, INRIA, Examinateur

 

Résumé :
La catégorisation, c'est-à-dire la capacité à attribuer les mêmes étiquettes à des objets partageant des propriétés similaires, est l'une des principales tâches de l'apprentissage automatique. Ces dernières années, la quantité toujours croissante de données à notre disposition nous offre la possibilité sans précédent de concevoir des méthodes de catégorisation sophistiquées et statistiquement significatives, mais elle exige également un effort con- sidérable pour concevoir des algorithmes évolutifs et efficaces, capables de traiter correctement ces ensembles de données. Le clustering spectral (SC) est l'une des techniques les plus populaires pour catégoriser les éléments d'un ensemble de données qui peut être représenté sous la forme d'un graphe. Il s'agit d'une classe d'algorithmes non supervisés pour lesquels la “meilleure partition ne nécessite pas l'aide d'informations supplémentaires et est plutôt obtenue en exploitant les dépendances entre les éléments du jeu de données. Dans les algorithmes SC, l'information concernant la structure des données d'entrée est obtenue grâce aux vecteurs propres d'une matrice appropriée. Les intuitions et les résultats justifiant le SC sont à la croisée des chemins de plusieurs domaines tels que les statistiques, la théorie des matrices aléatoires, l'informatique, la science des réseaux, le traitement du signal, la physique statistique et ont jusqu'à présent été traités de manière indépendante. Nous étudions le cadre difficile (mais pertinent) des ma- trices parcimonieuses, dans lesquelles seules quelques entrées de la représentation matricielle sont différentes de zéro. Nous nous concentrons en parti- culier sur les applications du SC pour la détection de communautés (à la fois statiques et dynamiques) et pour la sparsification des matrices à noyau pour le clustering de vecteurs en grande dimension. Nous nous appuyons pour cela sur les avancées récentes de la physique statistique pour le SC afin de proposer des algorithmes améliorés qui surpassent, preuve à l'appui, les méthodes existantes pour les tâches de classification autant sur des don- nées synthétiques que sur des données réelles. De plus, nous proposons un cadre simple qui donne une vue unifiée de certaines des méthodes les plus influentes qui forment l'état de l'art pour le SC. Les algorithmes existants de la littérature peuvent souvent être considérés comme des cas extrêmes des méthodes que nous proposons qui constituent plutôt un “optimum capable de s'adapter à la difficulté du problème de classification. Nous détaillons également une implémentation efficace des algorithmes que nous proposons pour les tâches pratiques de SC.
ABSTRACT:
Categorization, i.e. the ability to assign the same labels to objects sharing similar properties, is one of the main task in machine learning. In recent times, the ever increasing amount of data at our disposal gives us unprece dented possibilities to devise sophisticated and statistically significant cate- gorization methods but it also requires a considerable effort in designing scalable and efficient algorithms, capable to properly deal with these datasets. Spectral clustering (SC) is one of the most popular techniques to categorize the items of a dataset that can be represented as a graph. This is a class of unsupervised algorithms in which the “best partition does not require the help of additional information to be determined and is instead obtained by exploiting the dependencies between the dataset's items. In SC algorithms, the information concerning the class structure of the input dataset is de- termined by the eigenvectors of a suited matrix. The intuitions and results justifying SC are at the crossroads between several fields such as statistics, random matrix theory, computer science, network science, signal processing, statistical physics and have so far mostly been treated independently. We study the challenging (but relevant) sparse setting, in which only few entries of the matrix representation of the input dataset are non-zero. We focus in particular on the applications of SC for community detection (in both static and dynamical graphs) and for the sparsification of kernel matrices for time-efficient clustering of high dimensional vectors. We build on the recent advances in statistical physics for SC to propose improved algorithms that provably outperform the existing methods for both synthetic as well as real clustering tasks. Moreover, we propose a simple framework that gives a unified view of some of the most influential state-of-the-art methods for SC. The existing algorithms from the literature can often be considered as corner cases of our proposed methods that constitute instead an “optimum capable of self-adapting to the hardness of the clustering problem. We further detail extensively how to efficiently implement our proposed algorithms for practical SC tasks.


GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 SAINT MARTIN D'HERES CEDEX - 33 (0)4 76 82 71 31