A Novel Normalized-Cut Solver With Nearest Neighbor Hierarchical Initialization
Feiping Nie, Jitao Lu, Danyang Wu, Rong Wang, Xuelong Li
Abstract
Normalized-Cut (N-Cut) is a famous model of spectral clustering. The traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via <inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula> -means or spectral rotation. However, this paradigm brings two vital problems: 1) two-stage methods solve a relaxed version of the original problem, so they cannot obtain good solutions for the original N-Cut problem; 2) solving the relaxed problem requires eigenvalue decomposition, which has <inline-formula><tex-math notation="LaTeX">${\mathcal {O}}(n^{3})$</tex-math></inline-formula> time complexity ( <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> is the number of nodes). To address the problems, we propose a novel N-Cut solver designed based on the famous coordinate descent method. Since the vanilla coordinate descent method also has <inline-formula><tex-math notation="LaTeX">${\mathcal {O}}(n^{3})$</tex-math></inline-formula> time complexity, we design various accelerating strategies to reduce the time complexity to <inline-formula><tex-math notation="LaTeX">${\mathcal {O}}(|E|)$</tex-math></inline-formula> ( <inline-formula><tex-math notation="LaTeX">$|E|$</tex-math></inline-formula> is the number of edges). To avoid reliance on random initialization which brings uncertainties to clustering, we propose an efficient initialization method that gives deterministic outputs. Extensive experiments on several benchmark datasets demonstrate that the proposed solver can obtain larger objective values of N-Cut, meanwhile achieving better clustering performance compared to traditional solvers.