Weighted Graph Cuts without Eigenvectors A Multilevel Approach

TLDR

Recent clustering methods, such as spectral clustering and kernel k‑means, address non‑linearly separable data. The paper shows that weighted kernel k‑means and weighted graph clustering objectives are equivalent and uses this equivalence to design a fast multilevel algorithm that directly optimizes objectives like ratio cut, normalized cut, and ratio association. The multilevel algorithm removes equal‑size cluster restrictions by applying kernel k‑means to optimize weighted graph cuts, directly targeting objectives such as ratio cut, normalized cut, and ratio association. The algorithm eliminates eigenvector computation, runs faster, uses less memory, and achieves higher quality than state‑of‑the‑art spectral clustering, and it scales to large‑scale tasks such as image segmentation, social network analysis, and gene network analysis.

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.