Spectral clustering is one of the most popular graph clustering algorithms,
which achieves the best performance for many scientific and engineering
applications. However, existing implementations in commonly used software
platforms such as Matlab and Python do not scale well for many of the emerging
Big Data applications. In this paper, we present a fast implementation of the
spectral clustering algorithm on a CPU-GPU heterogeneous platform. Our
implementation takes advantage of the computational power of the multi-core CPU
and the massive multithreading and SIMD capabilities of GPUs. Given the input
as data points in high dimensional space, we propose a parallel scheme to build
a sparse similarity graph represented in a standard sparse representation
format. Then we compute the smallest $k$ eigenvectors of the Laplacian matrix
by utilizing the reverse communication interfaces of ARPACK software and
cuSPARSE library, where $k$ is typically very large. Moreover, we implement a
very fast parallelized $k$-means algorithm on GPUs. Our implementation is shown
to be significantly faster compared to the best known Matlab and Python
implementations for each step. In addition, our algorithm scales to problems
with a very large number of clusters.

本文研究了基于 CPU-GPU 异构平台实现的高效谱聚类算法。通过对高维空间中的数据点进行并行处理，建立标准的稀疏相似性图并计算拉普拉斯矩阵的最小 $k$ 个特征向量，同时在 GPU 上实现了快速的 $k$ 均值聚类算法。实验结果表明，该算法比 Matlab 和 Python 的最佳实现方法快得多，并且可以扩展到具有大量聚类的问题。