Distributional Equivalence of Kernel $k$-means and Spectral Clustering

The relationship between spectral clustering and kernel $k$-means has long been a subject of interest, but existing work primarily focuses on methodological connections, i.e., how to achieve the objectives of spectral clustering through kernel $k$-means or vice versa. This work, however, overlooks the fundamental connection between their objectives. This paper explores the relationship between their optimization objectives from a distributional perspective and provides a unified framework encompassing both. From a distributional perspective, kernel $k$-means aims to maximize the similarity of the distribution of each cluster, while spectral clustering also minimizes the similarity between the distribution of each cluster and the overall data distribution. Ncut combines these two through division, while Rcut uses subtraction. Based on this connection, a unified framework is proposed that simultaneously overcomes the shortcomings of both NCut and kernel $k$-means.