Fast Iterative Normalized Cut

EasyChair Preprint 1550

Abstract

Normalized cut is a popular spectral clustering method and has been widely used in many applications. In this paper, we
propose a novel Fast Iterative Normalized Cut (FINC) algorithm to solve the classic normalized cut problem in a fast way. In the new method, we rewrite the classical normalized cut problem as a new problem and propose an iterative method with proved convergency to effectively solve the new model without eigendecomposition. Theoretical analysis reveals that solving the new method is equivalent to solving the classic normalized cut. Extensive experimental results show the superior performance of the new method.

Keyphrases: Clustering, Data Mining, Normalized cut, spectral clustering

@booklet{EasyChair:1550,
  author    = {Zhicong Xiao and Xiaojun Chen and Zitong Zhang and Feiping Nie},
  title     = {Fast Iterative Normalized Cut},
  howpublished = {EasyChair Preprint 1550},
  year      = {EasyChair, 2019}}