Large Graph Clustering with Simultaneous Spectral Embedding and Discretization

Spectral clustering methods are gaining more and more interests and successfully applied in many fields because of their superior performance. However, there still exist two main problems to be solved: 1) spectral clustering methods consist of two successive optimization stages - spectral embedding and spectral rotation, which may not lead to globally optimal solutions, 2) and it is known that spectral methods are time-consuming with very high computational complexity. There are methods proposed to reduce the complexity for data vectors but not for graphs that only have information about similarity matrices. In this paper, we propose a new method to solve these two challenging problems for graph clustering. In the new method, a new framework is established to perform spectral embedding and spectral rotation simultaneously. The newly designed objective function consists of both terms of embedding and rotation, and we use an improved spectral rotation method to make it mathematically rigorous for the optimization. To further accelerate the algorithm, we derive a low-dimensional representation matrix from a graph by using label propagation, with which, in return, we can reconstruct a double-stochastic and positive semidefinite similarity matrix. Experimental results demonstrate that our method has excellent performance in time cost and accuracy.