Abstract: A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral
clustering and kernel k-means are two of the main methods. In this paper, we discuss an equivalence between the objective functions
used in these seemingly different methods—in particular, a general weighted kernel k-means objective is mathematically equivalent to a
weighted graph clustering objective.We exploit this equivalence to develop a fast high-quality multilevel algorithm that directly optimizes
various weighted graph clustering objectives, such as the popular ratio cut, normalized cut, and ratio association criteria. This eliminates
the need for any eigenvector computation for graph clustering problems, which can be prohibitive for very large graphs. Previous
multilevel graph partitioning methods such as Metis have suffered from the restriction of equal-sized clusters; our multilevel algorithm
removes this restriction by using kernel k-means to optimize weighted graph cuts. Experimental results show that our multilevel algorithm
outperforms a state-of-the-art spectral clustering algorithm in terms of speed, memory usage, and quality. We demonstrate that our
algorithm is applicable to large-scale clustering tasks such as image segmentation, social network analysis, and gene network analysis.
- Topics:
- Graph Clustering
Download: pdf, software
Citation
- Weighted Graph Cuts without Eigenvectors: A Multilevel Approach (pdf, software)
I. Dhillon, Y. Guan, B. Kulis.
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 29(11), pp. 1944-1957, November 2007.
Bibtex: