Adaptive power iteration clustering

Abstract

Power iteration has been applied to compute the eigenvectors of the similarity matrix in spectral clustering tasks. However, these power iteration based clustering methods usually suffer from the following two problems: (1) the power iteration usually converges very slowly; (2) the singular value decomposition method adopted to obtain the eigenvectors of the similarity matrix is time-consuming. To solve these problems, we propose a novel clustering method named Adaptive Power Iteration Clustering (AdaPIC). Specifically, AdaPIC employs a sequence of rank-one matrices to approximate the normalized similarity matrix. Then, the first K+1 eigenvectors can be computed in parallel, and the stopping condition of power iteration can be automatically yielded based on the target clustering error. We performed extensive experiments on public datasets to demonstrate the effectiveness of the proposed AdaPIC method, comparing with leading baseline methods. The experimental results indicate that the proposed AdaPIC algorithm has a competitive advantage in running time. The running time taken by spectral clustering baseline methods is usually more than 2.52 times of that taken by AdaPIC. For clustering accuracy, AdaPIC outperforms classic PIC by 97% on average, over all experimental datasets. Moreover, AdaPIC achieves comparable clustering accuracy with other 3 baseline methods, and achieves 6%–15% better clustering accuracy than the remaining 6 state-of-the-art baseline methods.