Multilevel Diffusion Based Spectral Graph Clustering
Informazioni aggiuntive
Autori
Lechekhab M.,
Pasadakis D.,
Schenk O.
Tipo
Contributo in atti di convegno
Anno
2025
Lingua
Inglese
Sommario
Spectral clustering and kernel k-means are ubiquitous methods for dividing non-linearly separable data into distinct groups. Spectral methods, while effective in partitioning non-convex spaces, are computationally intensive as they involve eigenvector computations. Conversely, kernel k-means maps data to higher dimensions and circumvents the need for this costly computation, with a weighted variant of it being mathematically equivalent to spectral clustering. This work extends this equivalence to diffusion based spectral methods and introduces the Multilevel Diffusion Clustering (MDC) algorithm. MDC leverages diffusion principles to minimize the normalized cut, adds flexibility through a diffusion parameter, and retrieves high-quality partitions in a multilevel fashion without computing eigenpairs. Our numerical examples and comparative results with modern multilevel graph clustering packages reveal that the proposed method can improve the clustering of graphs both in terms of balanced cut criteria and classification accuracy.
Parole chiave
Graph clustering, kernel k-means, spectral clustering, multilevel framework
Titolo atti di convegno
28th Annual IEEE High Performance Extreme Computing Virtual Conference
Number ( Month )
September
Editore
IEEE
Nome convegno
28th Annual IEEE High Performance Extreme Computing Virtual Conference
Luogo convegno
Wakefield, MA, USA
Data convegno
September 23-27, 2024
Pagine (o numero dell’articolo)
1-6
Luogo di pubblicazione
Wakefield, MA, USA
ISSN
2643-1971
Diffusione
Licenza
Licenza non definita
Visibilità
Pubblico
