A Fast Spectral Clustering Algorithm Based on Granular-Ball and Similarity Graph Approximation

Spectral clustering is widely used due to its effectiveness in handling nonlinear data, but its performance is limited by high computational complexity when processing large-scale datasets. To address this issue, this paper proposes a fast spectral clustering algorithm based on granular-balls and similarity graph approximation (GBASC). Through granular-ball computation, fine-grained data is transformed into coarse-grained granular-balls, reducing the scale of the similarity graph. The paper proposes a fast approximation algorithm for granular-ball similarity graphs based on kernel density estimation, achieving a sparse approximation of the fully connected granular-ball similarity graph. This method significantly reduces the time and space complexity of constructing the granular-ball similarity graph, and by generating sparse matrices, it improves the efficiency of Laplacian matrix eigenvalue decomposition. Experimental results demonstrate that GBASC achieves high clustering performance and computational efficiency on large-scale datasets.