GSCAN : Clusterisation par Stabilité Graphique pour des Applications Bruitées en Utilisant l'Excès de Masse Axé sur les Arêtes

Le regroupement de graphes est essentiel à l’identification des communautés et des groupes au sein d’un réseau donné. Ces dernières années, de nombreuses tentatives ont été entreprises pour développer des outils adaptés à cette fin. Plus récemment, ces approches s’appuient sur les avancées les plus récentes en apprentissage profond, en particulier les réseaux de neurones sur graphes (Graph Neural Networks, GNN). Bien que certaines méthodes tiennent compte de la structure topologique intrinsèque du graphe tout au long du processus, les méthodes de regroupement les plus performantes ignorent cette structure lors de la phase finale d’affectation des clusters, ce qui conduit à des résultats sous-optimaux. Dans cet article, nous proposons GSCAN : un algorithme de regroupement basé sur la stabilité des graphes, conçu pour des applications sujettes au bruit, et fondé à la fois sur les caractéristiques des nœuds et sur la structure du graphe. Notre approche s’inspire de la méthode célèbre de l’Excès de Masse (Excess-of-Mass, EoM), fondée sur le principe de maximisation de la stabilité des clusters. Cette méthode présente des propriétés supplémentaires souhaitables, telles qu’une résilience aux valeurs aberrantes et le fait qu’elle ne nécessite pas de fixer a priori le nombre de clusters. Nous étendons la méthode EoM afin qu’elle s’adapte à la structure intrinsèque du graphe, et proposons deux post-traitements pour corriger l’un de ses défauts : sa tendance à sur-identifier les points de données comme étant des outliers. Ces post-traitements exploitent la topologie du graphe et permettent d’obtenir des performances supérieures, même par rapport aux méthodes de regroupement les plus avancées entraînées de bout en bout. Nous démontrons que l’approche proposée peut être mise en œuvre de manière rapide et évolutif. Nos conclusions sont validées sur trois jeux de données standards largement utilisés. Le code source est disponible à l’adresse suivante : https://github.com/GraphEoM/GSCAN