Robust and efficient multi-way spectral clustering

Abstract

We present a new algorithm for spectral clustering based on a column-pivoted QR factorization that may be directly used for cluster assignment or to provide an initial guess for k-means. Our algorithm is simple to implement, direct, and requires no initial guess. Furthermore, it scales linearly in the number of nodes of the graph and a randomized variant provides significant computational gains. Provided the subspace spanned by the eigenvectors used for clustering contains a basis that resembles the set of indicator vectors on the clusters, we prove that both our deterministic and randomized algorithms recover a basis close to the indicators in Frobenius norm. We also experimentally demonstrate that the performance of our algorithm tracks recent information theoretic bounds for exact recovery in the stochastic block model. Finally, we explore the performance of our algorithm when applied to a real world graph.

23 pages, 4 figures; slight algorithm update, does not change existing results; new real data example; expanded theory section with connections to relevant models

References in corpus (4)

• A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm
• The geometry of kernelized spectral clustering
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

Cited by in corpus (6)

• On the Random Batch Method for second order interacting particle systems
• Spectral Clustering with Graph Neural Networks for Graph Pooling
• An Automated Spectral Clustering for Multi-scale Data
• Random batch methods (RBM) for interacting particle systems
• Spectral Embedding Norm: Looking Deep into the Spectrum of the Graph Laplacian
• Fast algorithm for quantum polar decomposition, pretty-good measurements, and the Procrustes problem