SBSC: A fast Self-tuned Bipartite proximity graph-based Spectral Clustering
Proceedings of the ACM on Management of Data · 17.06.2025 · 3 (3) · 1-22
DOI: 10.1145/3725418 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.06.2025. Verfasst von Abdul Atif Khan und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 47 Literaturangaben.
Abstract (Originalsprache)
Spectral clustering (SC) is well-known for discovering natural groups present in the data by projecting them into Eigen-space based on the proximity graph but incurs cubic time in terms of size (N) of the data as all pair proximity is used. To enhance the efficiency of the SC techniques, the proximity between the data instances and their representatives ( R ) is captured through a bipartite similarity graph. However, extrinsic parameters such as the number of representatives and nearby representatives of data instances, influence the clustering performance, time, and memory usage. Therefore, in this work, we construct a parameter-free bipartite graph to further improve the clustering quality and computational cost of SC by introducing a locality-based sparsification technique. First, the proposed method (SBSC) determines O(√N) numbers of well-distributed representatives in O(N lg N) time by applying Bi-means and K -means partitioning techniques. Next, SBSC utilizes the local neighbors of R to search the nearby representatives, which fastens the search time to O(N). To the best of our knowledge, the proposed bipartite graph is the least (O(N)) sized and therefore, by exploiting the high sparsity of the graph accelerates the Eigen-decomposition step of SBSC. The proposed algorithm takes overall O(N(K 2 +lg N)) time only to detect K clusters, and experimental results on eighteen large-sized diversified datasets suggest that SBSC discovers complex clusters much faster than the competing methods with enhanced clustering quality.
Zitieren
APA
Khan, A. A., Maheshwari, R., Akhter, M. M., & Mohanty, S. K. (2025). SBSC: A fast Self-tuned Bipartite proximity graph-based Spectral Clustering. Proceedings of the ACM on Management of Data, 3(3), 1-22. https://doi.org/10.1145/3725418
Vancouver
Khan AA, Maheshwari R, Akhter MM, Mohanty SK. SBSC: A fast Self-tuned Bipartite proximity graph-based Spectral Clustering. Proceedings of the ACM on Management of Data. 2025;3(3):1-22. doi:10.1145/3725418
BibTeX
@article{Khan2025,
author = {Khan, Abdul Atif and Maheshwari, Rashmi and Akhter, Mohammad Maksood and Mohanty, Sraban Kumar},
title = {SBSC: A fast Self-tuned Bipartite proximity graph-based Spectral Clustering},
journal = {Proceedings of the ACM on Management of Data},
year = {2025},
volume = {3},
number = {3},
pages = {1--22},
doi = {10.1145/3725418}
}
EUVIMED