Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification
Yongyu Wang (Michigan Technological University),* Zhuo Feng (Stevens Institute of Technology)
The 33rd British Machine Vision Conference
Abstract
Eigenvalue decomposition of Laplacian matrices for large nearest-neighbor (NN) graphs is the major computational bottleneck in spectral clustering (SC). To fundamentally address this computational challenge in SC, we propose a scalable spectral sparsification framework that enables to construct nearly-linear-sized ultra-sparse NN graphs with guaranteed preservation of key eigenvalues and eigenvectors of the original Laplacian. The proposed method is based on the latest theoretical results in spectral graph theory and thus can be applied to robustly handle general undirected graphs. By leveraging a nearly-linear time spectral graph topology sparsification phase and a subgraph scaling phase via stochastic gradient descent (SGD) iterations, our approach allows computing tree-like NN graphs that can serve as high-quality proxies of the original NN graphs, leading to highly-scalable and accurate SC of large data sets. Our extensive experimental results on a variety of public domain data sets show dramatically improved performance when compared with state-of-the-art SC methods.Video
Citation
@inproceedings{Wang_2022_BMVC,
author = {Yongyu Wang and Zhuo Feng},
title = {Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification},
booktitle = {33rd British Machine Vision Conference 2022, {BMVC} 2022, London, UK, November 21-24, 2022},
publisher = {{BMVA} Press},
year = {2022},
url = {https://bmvc2022.mpi-inf.mpg.de/0307.pdf}
}
Copyright © 2022
The British Machine Vision Conference is organised by