Revisiting Fast Spectral Clustering with Anchor Graph

Cheng Long Wang, Feiping Nie, Rong Wang, Xuelong Li

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

34 Scopus citations

Abstract

Many anchor-graph-based spectral clustering methods have been proposed to accelerate spectral clustering for large scale problems. In this paper, we revisit the popular large-scale spectral clustering method based on the anchor graph which is equivalent to the spectral decomposition on a similar matrix obtained using a second-order transition probability. However, due to the special structure of the bipartite graph, there is no stable distribution of the random walk process. The even-order transition probabilities may only a side view of the bipartite structure, resulting in breaking the independence of data points and leading to undesired artifacts for boundary samples. Therefore, we propose a Fast Spectral Clustering based on the Random Walk Laplacian (FRWL) method. The random walk Laplacian balances explicitly the popularity of anchors and the independence of data points, which keeps the structure of boundary samples. The experimental results demonstrate the efficiency and effectiveness of our method.

Original languageEnglish
Title of host publication2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3902-3906
Number of pages5
ISBN (Electronic)9781509066315
DOIs
StatePublished - May 2020
Event2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020 - Barcelona, Spain
Duration: 4 May 20208 May 2020

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2020-May
ISSN (Print)1520-6149

Conference

Conference2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020
Country/TerritorySpain
CityBarcelona
Period4/05/208/05/20

Keywords

  • Spectral Clustering
  • anchor-based graph
  • large scale clustering
  • random walk Laplacian

Fingerprint

Dive into the research topics of 'Revisiting Fast Spectral Clustering with Anchor Graph'. Together they form a unique fingerprint.

Cite this