Tight Continuous Relaxation of the Balanced $k$-Cut Problem

Syama Sundar Rangapuram, Pramod Kaushik Mudrakarta, Matthias Hein

Spectral Clustering as a relaxation of the normalized/ratio cut has become one of the standard graph-based clustering methods. Existing methods for the computation of multiple clus…