{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T06:59:48Z","timestamp":1760597988486,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T00:00:00Z","timestamp":1597881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JST, PRESTO","award":["JPMJPR192B"],"award-info":[{"award-number":["JPMJPR192B"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,8,23]]},"DOI":"10.1145\/3394486.3403166","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T23:15:22Z","timestamp":1597965322000},"page":"1132-1140","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Average Sensitivity of Spectral Clustering"],"prefix":"10.1145","author":[{"given":"Pan","family":"Peng","sequence":"first","affiliation":[{"name":"University of Sheffield, Sheffield, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[{"name":"National Institute of Informatics & PRESTO, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,8,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Mikhail Belkin and Partha Niyogi. 2001. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. In NIPS . 585--591. Mikhail Belkin and Partha Niyogi. 2001. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. In NIPS . 585--591.","DOI":"10.7551\/mitpress\/1120.003.0080"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000193"},{"volume-title":"The combinatorics of network reliability","author":"Colbourn Charles J","key":"e_1_3_2_2_5_1","unstructured":"Charles J Colbourn . 1987. The combinatorics of network reliability . Oxford University Press, Inc. Charles J Colbourn. 1987. The combinatorics of network reliability .Oxford University Press, Inc."},{"key":"e_1_3_2_2_6_1","unstructured":"Justin Eldridge Mikhail Belkin and Yusu Wang. 2018. Unperturbed: spectral analysis beyond Davis-Kahan. In Algorithmic Learning Theory . 321--358. Justin Eldridge Mikhail Belkin and Yusu Wang. 2018. Unperturbed: spectral analysis beyond Davis-Kahan. In Algorithmic Learning Theory . 321--358."},{"key":"e_1_3_2_2_7_1","volume-title":"Algebraic connectivity of graphs. Czechoslovak mathematical journal","author":"Fiedler Miroslav","year":"1973","unstructured":"Miroslav Fiedler . 1973. Algebraic connectivity of graphs. Czechoslovak mathematical journal , Vol. 23 , 2 ( 1973 ), 298--305. Miroslav Fiedler. 1973. Algebraic connectivity of graphs. Czechoslovak mathematical journal , Vol. 23, 2 (1973), 298--305."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.056135"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1201846"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_2_12_1","unstructured":"Ling Huang Donghui Yan Michael I. Jordan and Nina Taft. 2008. Spectral Clustering with Perturbed Data. In NIPS. 705--712. Ling Huang Donghui Yan Michael I. Jordan and Nina Taft. 2008. Spectral Clustering with Perturbed Data. In NIPS. 705--712."},{"key":"e_1_3_2_2_13_1","volume-title":"Robustness of community structure in networks. Physical review E","author":"Karrer Brian","year":"2008","unstructured":"Brian Karrer , Elizaveta Levina , and Mark EJ Newman . 2008. Robustness of community structure in networks. Physical review E , Vol. 77 , 4 ( 2008 ), 046119. Brian Karrer, Elizaveta Levina, and Mark EJ Newman. 2008. Robustness of community structure in networks. Physical review E , Vol. 77, 4 (2008), 046119."},{"volume-title":"Perturbation theory for linear operators","author":"Kato Tosio","key":"e_1_3_2_2_14_1","unstructured":"Tosio Kato . 2013. Perturbation theory for linear operators . Vol. 132 . Springer Science & Business Media . Tosio Kato. 2013. Perturbation theory for linear operators . Vol. 132. Springer Science & Business Media."},{"key":"e_1_3_2_2_15_1","volume-title":"Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan.","author":"Kwok Tsz Chiu","year":"2013","unstructured":"Tsz Chiu Kwok , Lap Chi Lau , Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. 2013 a. Improved Cheeger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In STOC. 11--20. Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. 2013a. Improved Cheeger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In STOC. 11--20."},{"key":"e_1_3_2_2_16_1","volume-title":"Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan.","author":"Kwok Tsz Chiu","year":"2013","unstructured":"Tsz Chiu Kwok , Lap Chi Lau , Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. 2013 b. Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap . arXiv preprint arXiv:1301.5584 (2013). Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan. 2013b. Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap. arXiv preprint arXiv:1301.5584 (2013)."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2665063"},{"key":"e_1_3_2_2_19_1","volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability .","volume":"297","author":"MacQueen J.","year":"1967","unstructured":"J. MacQueen . 1967 . Some methods for classification and analysis of multivariate observations . In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability . Vol. I: Statistics, pp. 281-- 297 . J. MacQueen. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability . Vol. I: Statistics, pp. 281--297."},{"key":"e_1_3_2_2_20_1","volume-title":"Average Sensitivity of Spectral Clustering. CoRR","author":"Peng Pan","year":"2020","unstructured":"Pan Peng and Yuichi Yoshida . 2020. Average Sensitivity of Spectral Clustering. CoRR , Vol. abs\/ 2006 .04094 ( 2020 ). arxiv: 2006.04094 Pan Peng and Yuichi Yoshida. 2020. Average Sensitivity of Spectral Clustering. CoRR , Vol. abs\/2006.04094 (2020). arxiv: 2006.04094"},{"key":"e_1_3_2_2_21_1","first-page":"710","article-title":"Partitioning Well-Clustered Graphs: Spectral Clustering Works! SIAM J","volume":"46","author":"Peng Richard","year":"2017","unstructured":"Richard Peng , He Sun , and Luca Zanetti . 2017 . Partitioning Well-Clustered Graphs: Spectral Clustering Works! SIAM J . Comput. , Vol. 46 , 2 (2017), 710 -- 743 . Richard Peng, He Sun, and Luca Zanetti. 2017. Partitioning Well-Clustered Graphs: Spectral Clustering Works! SIAM J. Comput. , Vol. 46, 2 (2017), 710--743.","journal-title":"Comput."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_3_2_2_23_1","unstructured":"G.W. Stewart and J.G. Sun. 1990. Matrix Perturbation Theory .ACADEMIC PRESS INC. G.W. Stewart and J.G. Sun. 1990. Matrix Perturbation Theory .ACADEMIC PRESS INC."},{"key":"e_1_3_2_2_24_1","volume-title":"mbox","author":"Tropp Joel A","year":"2015","unstructured":"Joel A Tropp mbox . 2015 . An introduction to matrix concentration inequalities. Foundations and Trends\u00ae in Machine Learning , Vol. 8 , 1--2 (2015), 1--230. Joel A Tropp et almbox. 2015. An introduction to matrix concentration inequalities. Foundations and Trends\u00ae in Machine Learning , Vol. 8, 1--2 (2015), 1--230."},{"key":"e_1_3_2_2_25_1","volume-title":"Average Sensitivity of Graph Algorithms. CoRR","author":"Varma Nithin","year":"2019","unstructured":"Nithin Varma and Yuichi Yoshida . 2019. Average Sensitivity of Graph Algorithms. CoRR , Vol. abs\/ 1904 .03248 ( 2019 ). arxiv: 1904.03248 Nithin Varma and Yuichi Yoshida. 2019. Average Sensitivity of Graph Algorithms. CoRR , Vol. abs\/1904.03248 (2019). arxiv: 1904.03248"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_3_2_2_27_1","unstructured":"Yilin Zhang and Karl Rohe. 2018. Understanding regularized spectral clustering via graph conductance. In NeurIPS . 10631--10640. Yilin Zhang and Karl Rohe. 2018. Understanding regularized spectral clustering via graph conductance. In NeurIPS . 10631--10640."}],"event":{"name":"KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"],"location":"Virtual Event CA USA","acronym":"KDD '20"},"container-title":["Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394486.3403166","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3394486.3403166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:34Z","timestamp":1750195894000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394486.3403166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,20]]},"references-count":27,"alternative-id":["10.1145\/3394486.3403166","10.1145\/3394486"],"URL":"https:\/\/doi.org\/10.1145\/3394486.3403166","relation":{},"subject":[],"published":{"date-parts":[[2020,8,20]]},"assertion":[{"value":"2020-08-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}