An Optimization Solver of Min-Max Cut for Spectral Clustering

Spectral clustering has received widespread attention for its effectiveness in handling nonconvex geometries. The classic methods of spectral clustering include Ratio Cut (Rcut), Normalized Cut (Ncut), and Min-Max Cut (MMcut). Among them, the objective function of MMcut is more reasonable. Unfortunately, existing methods cannot solve MMcut problem without relaxing the discrete or nonnegative constraints. To this end, based on coordinate descent, we propose a basic optimization algorithm to solve MMcut problem without relaxing any constraint. And then, a fast version of the solver is proposed to improve the computational efficiency. Besides, we prove the convergence of the proposed solver, evaluate its computational complexity, and discuss the connection between MMcut and NCut. Finally, extensive experiments are performed to evaluate the effectiveness of our proposed method.