{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:45:09Z","timestamp":1787017509004,"version":"3.56.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    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 (\n                    <jats:italic toggle=\"yes\">R<\/jats:italic>\n                    ) 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(\u221aN) numbers of well-distributed representatives in O(N lg N) time by applying Bi-means and\n                    <jats:italic toggle=\"yes\">K<\/jats:italic>\n                    -means partitioning techniques. Next, SBSC utilizes the local neighbors of\n                    <jats:italic toggle=\"yes\">R<\/jats:italic>\n                    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\n                    <jats:sup>2<\/jats:sup>\n                    +lg N)) time only to detect\n                    <jats:italic toggle=\"yes\">K<\/jats:italic>\n                    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.\n                  <\/jats:p>","DOI":"10.1145\/3725418","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-22","source":"Crossref","is-referenced-by-count":3,"title":["SBSC: A fast Self-tuned Bipartite proximity graph-based Spectral Clustering"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-7943-6545","authenticated-orcid":false,"given":"Abdul Atif","family":"Khan","sequence":"first","affiliation":[{"name":"PDPM Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, Jabalpur, Madhya Pradesh, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9178-284X","authenticated-orcid":false,"given":"Rashmi","family":"Maheshwari","sequence":"additional","affiliation":[{"name":"PDPM Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, Jabalpur, Madhya Pradesh, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2539-1859","authenticated-orcid":false,"given":"Mohammad Maksood","family":"Akhter","sequence":"additional","affiliation":[{"name":"PDPM Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, Jabalpur, Madhya Pradesh, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9203-7174","authenticated-orcid":false,"given":"Sraban Kumar","family":"Mohanty","sequence":"additional","affiliation":[{"name":"PDPM Indian Institute of Information Technology, Design and Manufacturing, Jabalpur, Jabalpur, Madhya Pradesh, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCVW60793.2023.00010"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2358564"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.88"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2021.3049490"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40935-6_26"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2017.7966217"},{"key":"e_1_2_2_7_1","unstructured":"Dheeru Dua and Casey Graff. April 2024. UCI Machine Learning Repository. http:\/\/archive.ics.uci.edu\/ml"},{"key":"e_1_2_2_8_1","first-page":"226","article-title":"A density-based algorithm for discovering clusters in large spatial databases with noise","volume":"96","author":"Ester Martin","year":"1996","unstructured":"Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, Xiaowei Xu, et al., 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In KDD, Vol. 96. 226-231.","journal-title":"KDD"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262185"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551850"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2022.11.063"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2903410"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588685"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2020.01.003"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.09.011"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2019.05.030"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289588"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2017.07.038"},{"key":"e_1_2_2_20_1","unstructured":"Abdul Atif Khan. March 2025. SBSC Source Code. https:\/\/github.com\/k-atif\/SBSC"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3483572"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2022.07.101"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2022.06.006"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403086"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i10.17037"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2012.6247750"},{"key":"e_1_2_2_27_1","first-page":"281","volume-title":"Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability","volume":"1","author":"James","unstructured":"James MacQueen et al., 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1. Oakland, CA, USA, 281-297."},{"key":"e_1_2_2_28_1","first-page":"1472","article-title":"Fast Spectral Learning using Lanczos Eigenspace Projections","author":"Mahadevan Sridhar","year":"2008","unstructured":"Sridhar Mahadevan. 2008. Fast Spectral Learning using Lanczos Eigenspace Projections. In AAAI. 1472-1475.","journal-title":"AAAI."},{"key":"e_1_2_2_29_1","volume-title":"The Laplacian spectrum of graphs. Graph theory, Combinatorics, and Applications","author":"Mohar Bojan","year":"1991","unstructured":"Bojan Mohar, Y Alavi, G Chartrand, and OR Oellermann. 1991. The Laplacian spectrum of graphs. Graph theory, Combinatorics, and Applications, Vol. 2, 871--898 (1991), 12."},{"key":"e_1_2_2_30_1","volume-title":"Advances in Neural Information Processing Systems","author":"Ng Andrew","year":"2001","unstructured":"Andrew Ng, Michael Jordan, and Yair Weiss. 2001. On Spectral Clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems, Vol. 14. MIT Press. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2001\/file\/801272ee79cfde7fa5960571fee36b9b-Paper.pdf"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2014.08.001"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3150403"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1971.10482356"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM58522.2023.00062"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2020.105841"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1242072"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.114326"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2014.10.023"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220090"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3249475"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/860435.860485"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557118"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3267167"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2014.10.012"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:58:26Z","timestamp":1774983506000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725418"],"URL":"https:\/\/doi.org\/10.1145\/3725418","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}