Scalable Spectral Clustering Using Random Binning Features
  Spectral clustering is one of the most effective clustering approaches that
capture hidden cluster structures in the data. However, it does not scale well
to large-scale problems due to its quadratic complexity in constructing
similarity graphs and computing subsequent eigendecomposition. Although a
number of methods have been proposed to accelerate spectral clustering, most of
them compromise considerable information loss in the original data for reducing
computational bottlenecks. In this paper, we present a novel scalable spectral
clustering method using Random Binning features (RB) to simultaneously
accelerate both similarity graph construction and the eigendecomposition.
Specifically, we implicitly approximate the graph similarity (kernel) matrix by
the inner product of a large sparse feature matrix generated by RB. Then we
introduce a state-of-the-art SVD solver to effectively compute eigenvectors of
this large matrix for spectral clustering. Using these two building blocks, we
reduce the computational cost from quadratic to linear in the number of data
points while achieving similar accuracy. Our theoretical analysis shows that
spectral clustering via RB converges faster to the exact spectral clustering
than the standard Random Feature approximation. Extensive experiments on 8
benchmarks show that the proposed method either outperforms or matches the
state-of-the-art methods in both accuracy and runtime. Moreover, our method
exhibits linear scalability in both the number of data samples and the number
of RB features.
