Multilevel Diffusion Based Spectral Graph Clustering
Additional information
Authors
Editors
Type
Conference proceedings
Year
forthcoming
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.
Month
September
Publisher
IEEE
Start page number
1
End page number
6
Meeting name
28th Annual IEEE High Performance Extreme Computing Virtual Conference
Keywords
Graph clustering, kernel k-means, spectral clustering, multilevel framework
