Spectral Clustering via Orthogonalization-Free Methods
This work addresses the problem of inefficient parallel scaling in spectral clustering for large streaming graphs, offering incremental improvements over existing dimensionality reduction methods.
The authors tackled the scalability issue of orthogonalization in spectral clustering for large streaming graphs by proposing four orthogonalization-free methods, which converge to features isomorphic to eigenvectors and show competitive performance in streaming scenarios with fast convergence and improved scalability in parallel computing environments.
While orthogonalization exists in current dimensionality reduction methods in spectral clustering on undirected graphs, it does not scale in parallel computing environments. We propose four orthogonalization-free methods for spectral clustering. Our methods optimize one of two objective functions with no spurious local minima. In theory, two methods converge to features isomorphic to the eigenvectors corresponding to the smallest eigenvalues of the symmetric normalized Laplacian. The other two converge to features isomorphic to weighted eigenvectors weighting by the square roots of eigenvalues. We provide numerical evidence on the synthetic graphs from the IEEE HPEC Graph Challenge to demonstrate the effectiveness of the orthogonalization-free methods. Numerical results on the streaming graphs show that the orthogonalization-free methods are competitive in the streaming graph scenario since they can take full advantage of the computed features of previous graphs and converge fast. Our methods are also more scalable in parallel computing environments because orthogonalization is unnecessary. Numerical results are provided to demonstrate the scalability of our methods. Consequently, our methods have advantages over other dimensionality reduction methods when handling spectral clustering for large streaming graphs.