Multilevel Diffusion Based Spectral Graph Clustering
Additional information
Authors
Lechekhab M.,
Pasadakis D.,
Schenk O.
Type
Article in conference proceedings
Year
2025
Language
English
Abstract
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-qualitypartitions 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.
Keywords
Graph clustering, kernel k-means, spectral clustering, multilevel framework
Conference proceedings
28th Annual IEEE High Performance Extreme Computing Virtual Conference
Numero ( Mese )
September
Publisher
IEEE
Meeting name
28th Annual IEEE High Performance Extreme Computing Virtual Conference
Meeting place
Wakefield, MA, USA
Meeting date
September 23-27, 2024
Pages (or article number)
1-6
ISSN
2643-1971
Diffusion
Visibility
Public
