Spectral sparsification in spectral clustering

Abstract

Graph spectral clustering algorithms have been shown to be effective in finding clusters and generally outperform traditional clustering algorithms, such as k-means. However, they have scalibility issues in both memory usage and computational time. To overcome these limitations, the common approaches sparsify the similarity matrix by zeroing out some of its elements. They generally consider local neighborhood relationships between the data instances such as the k-nearest neighbor method. Although, they eventually work with the Laplacian matrix, there is no evidence about preservation of its spectral properties with approximation guarantees. As a result, in this paper, we adopt the idea of spectral sparsification to sparsify the Laplacian matrix. A spectral sparsification algorithm takes a dense graph G with n vertices and m edges (that is usually O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> )), and returns a new graph H with the same set of vertices and many fewer edges, on the order of O(n log n), that approximately preserves the spectral properties of the input graph. We study the effect of the spectral sparsification method based on sampling by effective resistance on the spectral clustering outputs. Through experiments, we show that the clustering results obtained from sparsified graphs are very similar to the results of the original non-sparsified graphs.