{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T13:57:12Z","timestamp":1772114232315,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>\n            Spectral clustering is one of the most advantageous clustering approaches. However, standard Spectral Clustering is sensitive to noisy input data and has a high runtime complexity. Tackling one of these problems often exacerbates the other. As real-world datasets are often large\n            <jats:italic>and<\/jats:italic>\n            compromised by noise, we need to improve both robustness and runtime at once. Thus, we propose Spectral Clustering - Accelerated and Robust (SCAR), an accelerated, robustified spectral clustering method. In an iterative approach, we achieve robustness by separating the data into two latent components: cleansed and noisy data. We accelerate the eigendecomposition - the most time-consuming step - based on the Nystr\u00f6m method. We compare SCAR to related recent state-of-the-art algorithms in extensive experiments. SCAR surpasses its competitors in terms of speed and clustering quality on highly noisy data.\n          <\/jats:p>","DOI":"10.14778\/3551793.3551850","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"3031-3044","source":"Crossref","is-referenced-by-count":9,"title":["SCAR"],"prefix":"10.14778","volume":"15","author":[{"given":"Ellen","family":"Hohma","sequence":"first","affiliation":[{"name":"Technical University of Munich, Munich, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian M. M.","family":"Frey","sequence":"additional","affiliation":[{"name":"Christian-Albrecht University of Kiel, Kiel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Beer","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Seidl","sequence":"additional","affiliation":[{"name":"LMU Munich, Munich, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of applied mathematics 9, 1","author":"Arnoldi Walter Edwin","year":"1951","unstructured":"Walter Edwin Arnoldi . 1951. The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of applied mathematics 9, 1 ( 1951 ), 17--29. Walter Edwin Arnoldi. 1951. The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of applied mathematics 9, 1 (1951), 17--29."},{"key":"e_1_2_1_3_1","volume-title":"Learning spectral clustering. Advances in neural information processing systems 16, 2","author":"Bach Francis","year":"2004","unstructured":"Francis Bach and Michael Jordan . 2004. Learning spectral clustering. Advances in neural information processing systems 16, 2 ( 2004 ), 305--312. Francis Bach and Michael Jordan. 2004. Learning spectral clustering. Advances in neural information processing systems 16, 2 (2004), 305--312."},{"key":"e_1_2_1_4_1","volume-title":"Noise thresholds for spectral clustering. Advances in Neural Information Processing Systems 24","author":"Balakrishnan Sivaraman","year":"2011","unstructured":"Sivaraman Balakrishnan , Min Xu , Akshay Krishnamurthy , and Aarti Singh . 2011. Noise thresholds for spectral clustering. Advances in Neural Information Processing Systems 24 ( 2011 ). Sivaraman Balakrishnan, Min Xu, Akshay Krishnamurthy, and Aarti Singh. 2011. Noise thresholds for spectral clustering. Advances in Neural Information Processing Systems 24 (2011)."},{"key":"e_1_2_1_5_1","unstructured":"Anna Beer Ekaterina Allerborn Valentin Hartmann and Thomas Seidl. 2021. KISS-A fast kNN-based Importance Score for Subspaces. In EDBT. 391--396.  Anna Beer Ekaterina Allerborn Valentin Hartmann and Thomas Seidl. 2021. KISS-A fast kNN-based Importance Score for Subspaces. In EDBT. 391--396."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47977-5_35"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098156"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1004191"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0920-5632(00)00436-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220039"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40935-6_26"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014118"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_22"},{"key":"e_1_2_1_14_1","volume-title":"Stork","author":"Duda Richard O.","year":"2001","unstructured":"Richard O. Duda , Peter E. Hart , and David G . Stork . 2001 . Pattern Classification (2 ed.). Wiley , New York. Richard O. Duda, Peter E. Hart, and David G. Stork. 2001. Pattern Classification (2 ed.). Wiley, New York."},{"key":"e_1_2_1_15_1","first-page":"1251","article-title":"The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems","volume":"35","author":"Ericsson Thomas","year":"1980","unstructured":"Thomas Ericsson and Axel Ruhe . 1980 . The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems . Math. Comp. 35 , 152 (1980), 1251 -- 1268 . Thomas Ericsson and Axel Ruhe. 1980. The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems. Math. Comp. 35, 152 (1980), 1251--1268.","journal-title":"Math. Comp."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262185"},{"key":"e_1_2_1_17_1","volume-title":"International Conference on Machine Learning. PMLR, 567--575","author":"Gittens Alex","year":"2013","unstructured":"Alex Gittens and Michael Mahoney . 2013 . Revisiting the nystrom method for improved large-scale machine learning . In International Conference on Machine Learning. PMLR, 567--575 . Alex Gittens and Michael Mahoney. 2013. Revisiting the nystrom method for improved large-scale machine learning. In International Conference on Machine Learning. PMLR, 567--575."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.110"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2004.1334558"},{"key":"e_1_2_1_20_1","volume-title":"Supercomputing '95: Proceedings of the 1995 ACM\/IEEE Conference on Supercomputing (CDROM)","author":"Hendrickson Bruce","year":"1995","unstructured":"Bruce Hendrickson and Robert W. Leland . 1995. A Multi-Level Algorithm For Partitioning Graphs . Supercomputing '95: Proceedings of the 1995 ACM\/IEEE Conference on Supercomputing (CDROM) ( 1995 ), 1--14. Bruce Hendrickson and Robert W. Leland. 1995. A Multi-Level Algorithm For Partitioning Graphs. Supercomputing '95: Proceedings of the 1995 ACM\/IEEE Conference on Supercomputing (CDROM) (1995), 1--14."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33013788"},{"key":"e_1_2_1_22_1","unstructured":"Desmond J Higham and Milla Kibble. 2004. A unified view of spectral clustering. University of Strathclyde mathematics research report 2 (2004).  Desmond J Higham and Milla Kibble. 2004. A unified view of spectral clustering. University of Strathclyde mathematics research report 2 (2004)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.15"},{"key":"e_1_2_1_24_1","volume-title":"Spectral clustering with perturbed data. Advances in Neural Information Processing Systems 21","author":"Huang Ling","year":"2008","unstructured":"Ling Huang , Donghui Yan , Nina Taft , and Michael Jordan . 2008. Spectral clustering with perturbed data. Advances in Neural Information Processing Systems 21 ( 2008 ). Ling Huang, Donghui Yan, Nina Taft, and Michael Jordan. 2008. Spectral clustering with perturbed data. Advances in Neural Information Processing Systems 21 (2008)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2015.07.074"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4304\/jsw.8.5.1101-1108"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/305219.305248"},{"key":"e_1_2_1_28_1","unstructured":"Sanjiv Kumar Mehryar Mohri and Ameet Talwalkar. 2009. Sampling techniques for the nystrom method. In Artificial Intelligence and Statistics. 304--311.  Sanjiv Kumar Mehryar Mohri and Ameet Talwalkar. 2009. Sampling techniques for the nystrom method. In Artificial Intelligence and Statistics. 304--311."},{"key":"e_1_2_1_29_1","volume-title":"An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. United States Governm","author":"Lanczos Cornelius","unstructured":"Cornelius Lanczos . 1950. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. United States Governm . Press Office Los Angeles , CA. Cornelius Lanczos. 1950. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. United States Governm. Press Office Los Angeles, CA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Richard B Lehoucq Danny C Sorensen and Chao Yang. 1998. ARPACK users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM.  Richard B Lehoucq Danny C Sorensen and Chao Yang. 1998. ARPACK users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM.","DOI":"10.1137\/1.9780898719628"},{"key":"e_1_2_1_32_1","volume-title":"ICML 2010-Proceedings, 27th International Conference on Machine Learning. 631","author":"Li Mu","year":"2010","unstructured":"Mu Li , James Tin-Yau Kwok , and Baoliang Lu . 2010 . Making large-scale Nystr\u00f6m approximation possible . In ICML 2010-Proceedings, 27th International Conference on Machine Learning. 631 . Mu Li, James Tin-Yau Kwok, and Baoliang Lu. 2010. Making large-scale Nystr\u00f6m approximation possible. In ICML 2010-Proceedings, 27th International Conference on Machine Learning. 631."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995425"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.126"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2007.4409061"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_37_1","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. 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_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/IJCNN.2017.7965829"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-803130-8.00010-5"},{"key":"e_1_2_1_40_1","volume-title":"On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems 14","author":"Ng Andrew","year":"2001","unstructured":"Andrew Ng , Michael Jordan , and Yair Weiss . 2001. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems 14 ( 2001 ), 849--856. Andrew Ng, Michael Jordan, and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems 14 (2001), 849--856."},{"key":"e_1_2_1_41_1","volume-title":"The Symmetric Eigenvalue Problem","author":"Parlett Beresford N.","unstructured":"Beresford N. Parlett . 1998. The Symmetric Eigenvalue Problem . Society for Industrial and Applied Mathematics , Philadelphia . Beresford N. Parlett. 1998. The Symmetric Eigenvalue Problem. Society for Industrial and Applied Mathematics, Philadelphia."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276958.1277258"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/OJSP.2020.3039330"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.3007087"},{"key":"e_1_2_1_45_1","volume-title":"Fast Spectral Clustering with Random Projection and Sampling. In International Workshop on Machine Learning and Data Mining in Pattern Recognition. Springer, 372--384","author":"Sakai Tomoya","year":"2009","unstructured":"Tomoya Sakai and Atsushi Imiya . 2009 . Fast Spectral Clustering with Random Projection and Sampling. In International Workshop on Machine Learning and Data Mining in Pattern Recognition. Springer, 372--384 . Tomoya Sakai and Atsushi Imiya. 2009. Fast Spectral Clustering with Random Projection and Sampling. In International Workshop on Machine Learning and Data Mining in Pattern Recognition. Springer, 372--384."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479800371529"},{"key":"e_1_2_1_48_1","article-title":"Cluster Ensembles - A Knowledge Reuse Framework for Combining Multiple Partitions","author":"Strehl Alexander","year":"2002","unstructured":"Alexander Strehl and Joydeep Ghosh . 2002 . Cluster Ensembles - A Knowledge Reuse Framework for Combining Multiple Partitions . Journal on Machine Learning Research (JMLR) 3 ( December 2002), 583--617. Alexander Strehl and Joydeep Ghosh. 2002. Cluster Ensembles - A Knowledge Reuse Framework for Combining Multiple Partitions. Journal on Machine Learning Research (JMLR) 3 (December 2002), 583--617.","journal-title":"Journal on Machine Learning Research (JMLR) 3"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983745"},{"key":"e_1_2_1_50_1","volume-title":"DCF: An Efficient and Robust Density-Based Clustering Method. In 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 629--638","author":"Tobin Joshua","year":"2021","unstructured":"Joshua Tobin and Mimi Zhang . 2021 . DCF: An Efficient and Robust Density-Based Clustering Method. In 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 629--638 . Joshua Tobin and Mimi Zhang. 2021. DCF: An Efficient and Robust Density-Based Clustering Method. In 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 629--638."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29349-9_5"},{"key":"e_1_2_1_52_1","volume-title":"A tutorial on spectral clustering. Statistics and computing 17, 4","author":"Luxburg Ulrike Von","year":"2007","unstructured":"Ulrike Von Luxburg . 2007. A tutorial on spectral clustering. Statistics and computing 17, 4 ( 2007 ), 395--416. Ulrike Von Luxburg. 2007. A tutorial on spectral clustering. Statistics and computing 17, 4 (2007), 395--416."},{"key":"e_1_2_1_53_1","volume-title":"Approximate Spectral Clustering. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (Advances in Knowledge Discovery and Data Mining). Springer Berlin Heidelberg, 134--146","author":"Wang Liang","year":"2009","unstructured":"Liang Wang , Christopher Leckie , Kotagiri Ramamohanarao , and James Bezdek . 2009 . Approximate Spectral Clustering. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (Advances in Knowledge Discovery and Data Mining). Springer Berlin Heidelberg, 134--146 . Liang Wang, Christopher Leckie, Kotagiri Ramamohanarao, and James Bezdek. 2009. Approximate Spectral Clustering. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (Advances in Knowledge Discovery and Data Mining). Springer Berlin Heidelberg, 134--146."},{"key":"e_1_2_1_54_1","unstructured":"Christopher Williams and Matthias Seeger. 2001. Using the Nystr\u00f6m method to speed up kernel machines. In Advances in neural information processing systems. 682--688.  Christopher Williams and Matthias Seeger. 2001. Using the Nystr\u00f6m method to speed up kernel machines. In Advances in neural information processing systems. 682--688."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1177\/17483026221078111"},{"key":"e_1_2_1_56_1","volume-title":"Inductive kernel low-rank decomposition with priors: A generalized nystrom method. arXiv preprint arXiv:1206.4619","author":"Zhang Kai","year":"2012","unstructured":"Kai Zhang , Liang Lan , Jun Liu , Andreas Rauber , and Fabian Moerchen . 2012. Inductive kernel low-rank decomposition with priors: A generalized nystrom method. arXiv preprint arXiv:1206.4619 ( 2012 ). Kai Zhang, Liang Lan, Jun Liu, Andreas Rauber, and Fabian Moerchen. 2012. Inductive kernel low-rank decomposition with priors: A generalized nystrom method. arXiv preprint arXiv:1206.4619 (2012)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.188"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551850","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:49:37Z","timestamp":1672224577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551850"}},"subtitle":["spectral clustering accelerated and robustified"],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":56,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551850"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551850","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}