{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T23:44:09Z","timestamp":1790034249604,"version":"4.0.1"},"reference-count":53,"publisher":"Public Library of Science (PLoS)","issue":"2","license":[{"start":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T00:00:00Z","timestamp":1738627200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["www.plosone.org"],"crossmark-restriction":false},"short-container-title":["PLoS ONE"],"abstract":"<jats:p>\n                    Spectral clustering methods are known for their ability to represent clusters of diverse shapes, densities etc. However, the results of such algorithms, when applied e.g. to text documents, are hard to explain to the user, especially due to embedding in the spectral space which has no obvious relation to document contents. Therefore, there is an urgent need to elaborate methods for explaining the outcome of the clustering. We have constructed in this paper a theoretical bridge linking the clusters resulting from Graph Spectral Clustering and the actual document content, given that similarities between documents are computed as cosine measures in tf or tfidf representation. This link enables to provide with explanation of cluster membership in clusters produced by GSA. We present a proposal of explanation of the results of combinatorial and normalized Laplacian based graph spectral clustering. For this purpose, we show (approximate) equivalence of combinatorial Laplacian embedding and of\n                    <jats:italic>K<\/jats:italic>\n                    -embedding (proposed in this paper) and term vector space embedding. We performed an experimental study showing that\n                    <jats:italic>K<\/jats:italic>\n                    -embedding approximates well Laplacian embedding under favourable block matrix conditions and show that approximation is good enough under other conditions. We show also perfect equivalence of normalized Laplacian embedding and the\n                    <jats:inline-formula id=\"pone.0313238.e001\">\n                      <jats:alternatives>\n                        <jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" id=\"pone.0313238.e001g\" mimetype=\"image\" position=\"anchor\" xlink:href=\"info:doi\/10.1371\/journal.pone.0313238.e001\" xlink:type=\"simple\"\/>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" id=\"M1\">\n                          <mml:mi mathvariant=\"script\">M<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -embedding (proposed in this paper) and (weighted) term vector space embedding. Hence a bridge is constructed between the textual contents and the clustering results using both combinatorial and normalized Laplacian based Graph Spectral Clustering methods. We provide a theoretical background for our approach. An initial version of this paper is available at arXiv, (Starosta B 2023). The Reader may refer to that text to get acquainted with formal aspects of our method and find a detailed overview of motivation.\n                  <\/jats:p>","DOI":"10.1371\/journal.pone.0313238","type":"journal-article","created":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T13:24:42Z","timestamp":1738675482000},"page":"e0313238","update-policy":"https:\/\/doi.org\/10.1371\/journal.pone.corrections_policy","source":"Crossref","is-referenced-by-count":3,"title":["Explainable Graph Spectral Clustering of text documents"],"prefix":"10.1371","volume":"20","author":[{"given":"Bart\u0142omiej","family":"Starosta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4685-7045","authenticated-orcid":true,"given":"Mieczys\u0142aw A.","family":"K\u0142opotek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u0142awomir T.","family":"Wierzcho\u0144","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dariusz","family":"Czerski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Sydow","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Borkowski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"340","published-online":{"date-parts":[[2025,2,4]]},"reference":[{"key":"pone.0313238.ref001","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1007\/s10115-022-01658-9","article-title":"Postimpact similarity: a similarity measure for effective grouping of unlabelled text using spectral clustering","volume":"64","author":"AK Roy","year":"2022","journal-title":"Knowl Inf Syst"},{"key":"pone.0313238.ref002","doi-asserted-by":"crossref","first-page":"107342","DOI":"10.1016\/j.knosys.2021.107342","article-title":"What is this cluster about? explaining textual clusters by extracting relevant keywords","volume":"229","author":"A Penta","year":"2021","journal-title":"Knowledge-Based Systems"},{"key":"pone.0313238.ref003","doi-asserted-by":"crossref","unstructured":"Makarychev K, Shan L. Explainable k-means. Don\u2019t be greedy, plant bigger trees! In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, June 2022; 2022. p. 1629\u20131642. Available from: https:\/\/arxiv.org\/abs\/2111.03193.","DOI":"10.1145\/3519935.3520056"},{"key":"pone.0313238.ref004","unstructured":"Dasgupta S, Frost N, Moshkovitz M, Rashtchian C. Explainable K-Means and k-Medians Clustering. In: Proceedings of the 37th International Conference on Machine Learning. ICML\u201920. JMLR.org; 2020. p. 7055\u20137065."},{"key":"pone.0313238.ref005","article-title":"ExKMC: Expanding Explainable k-Means Clustering","author":"N Frost","year":"2020","journal-title":"CoRR"},{"issue":"C","key":"pone.0313238.ref006","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/j.procs.2022.07.041","article-title":"Explainable K-Means Clustering for Occupancy Estimation","volume":"203","author":"K Prabhakaran","year":"2022","journal-title":"Procedia Comput Sci"},{"key":"pone.0313238.ref007","first-page":"0639","article-title":"Explainable Customer Segmentation Using K-means Clustering","author":"R Khan","year":"2021","journal-title":"IEEE Explore"},{"key":"pone.0313238.ref008","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.eswa.2019.05.030","article-title":"Text document clustering using Spectral Clustering algorithm with Particle Swarm Optimization","volume":"134","author":"R Janani","year":"2019","journal-title":"Expert Systems with Applications"},{"key":"pone.0313238.ref009","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/978-3-642-28601-8_15","volume-title":"Computational Linguistics and Intelligent Text Processing","author":"P Shrestha","year":"2012"},{"key":"pone.0313238.ref010","article-title":"Semantic Word Clusters Using Signed Normalized Graph Cuts","author":"J Sedoc","year":"2016","journal-title":"CoRR"},{"key":"pone.0313238.ref011","article-title":"Free Lunch for Efficient Textual Commonsense Integration in Language Models","author":"W Cui","year":"2023","journal-title":"CoRR"},{"issue":"4","key":"pone.0313238.ref012","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A Tutorial on Spectral Clustering","volume":"17","author":"U von Luxburg","year":"2007","journal-title":"Statistics and Computing"},{"key":"pone.0313238.ref013","first-page":"223","volume-title":"SAS Global Forum Proceedings 2011","author":"M Nareddy","year":"2011"},{"key":"pone.0313238.ref014","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.knosys.2013.11.005","article-title":"Beyond cluster labeling: Semantic interpretation of clusters\u2019 contents using a graph representation","volume":"56","author":"F Role","year":"2014","journal-title":"Knowledge-Based Systems"},{"key":"pone.0313238.ref015","first-page":"66","volume-title":"Proc. of the Australasian Language Technology Association Workshop","author":"H Poostchi","year":"2018"},{"key":"pone.0313238.ref016","author":"L Merrick","year":"2020","journal-title":"The Explanation Game: Explaining Machine Learning Models Using Shapley Values"},{"issue":"8","key":"pone.0313238.ref017","doi-asserted-by":"crossref","first-page":"3669","DOI":"10.1109\/TKDE.2020.3028943","article-title":"Deep Feature-Based Text Clustering and its Explanation","volume":"34","author":"R Guan","year":"2022","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"pone.0313238.ref018","doi-asserted-by":"crossref","unstructured":"Zhao Y, Liang S, Ren Z, Ma J, Yilmaz E, de Rijke M. Explainable User Clustering in Short Text Streams. In: Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval. SIGIR\u201916. New York, NY, USA: Association for Computing Machinery; 2016. p. 155\u2013164. Available from: https:\/\/doi.org\/10.1145\/2911451.2911522.","DOI":"10.1145\/2911451.2911522"},{"key":"pone.0313238.ref019","article-title":"Explainable Graph Spectral Clustering of Text Documents","author":"B Starosta","year":"2023","journal-title":"CoRR"},{"key":"pone.0313238.ref020","doi-asserted-by":"crossref","first-page":"104743","DOI":"10.1016\/j.engappai.2022.104743","article-title":"A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, taxonomy, challenges, and future research prospects","volume":"110","author":"AE Ezugwu","year":"2022","journal-title":"Engineering Applications of Artificial Intelligence"},{"key":"pone.0313238.ref021","volume-title":"vol. 34 of Studies in Big Data","author":"ST Wierzcho\u0144","year":"2018"},{"key":"pone.0313238.ref022","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/978-1-4614-3223-4_4","volume-title":"Mining Text Data","author":"CC Aggarwal","year":"2012"},{"key":"pone.0313238.ref023","unstructured":"Weiss D. Introduction to search results clustering. In: Suraj Z, editor. Proceedings of the 6th International Conference on Soft Computing and Distributed Processing. Uniwersytet Rzeszowski; 2002. p. 82\u201384."},{"key":"pone.0313238.ref024","unstructured":"Macgregor P, Sun H. A Tighter Analysis of Spectral Clustering, and Beyond. In: Chaudhuri K, Jegelka S, Song L, Szepesvari C, Niu G, Sabato S, editors. Proceedings of the 39th International Conference on Machine Learning. vol. 162 of Proceedings of Machine Learning Research. PMLR; 2022. p. 14717\u201314742. Available from: https:\/\/proceedings.mlr.press\/v162\/macgregor22a.html."},{"key":"pone.0313238.ref025","first-page":"247","volume-title":"A Selective Overview of Recent Advances in Spectral Clustering and Their Applications","author":"Y Xu","year":"2021"},{"key":"pone.0313238.ref026","first-page":"849","volume-title":"Advances in Neural Information Processing Systems","author":"AY Ng","year":"2002"},{"key":"pone.0313238.ref027","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.inffus.2019.12.012","article-title":"Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI","volume":"58","author":"AB Arrieta","year":"2020","journal-title":"Information Fusion"},{"key":"pone.0313238.ref028","first-page":"13","volume-title":"Explainable AI Methods\u2014A Brief Overview","author":"A Holzinger","year":"2022"},{"key":"pone.0313238.ref029","author":"S Bandyapadhyay","year":"2021","journal-title":"How to Find a Good Explanation for Clustering?"},{"issue":"1","key":"pone.0313238.ref030","doi-asserted-by":"crossref","first-page":"18","DOI":"10.3390\/e23010018","article-title":"Explainable AI: A review of machine learning interpretability methods","volume":"23","author":"P Linardatos","year":"2021","journal-title":"Entropy"},{"issue":"2","key":"pone.0313238.ref031","first-page":"277","article-title":"Combining distributed word representation and document distance for short text document clustering","volume":"16","author":"S Kongwudhikunakorn","year":"2020","journal-title":"J Inf Process Syst"},{"key":"pone.0313238.ref032","article-title":"How to Find a Good Explanation for Clustering?","author":"S Bandyapadhyay","year":"2021","journal-title":"CoRR"},{"key":"pone.0313238.ref033","article-title":"Nearly-Tight and Oblivious Algorithms for Explainable Clustering","author":"B Gamlath","year":"2021","journal-title":"CoRR"},{"key":"pone.0313238.ref034","article-title":"Explainable Clustering via Exemplars: Complexity and Efficient Approximation Algorithms","author":"I Davidson","year":"2022","journal-title":"CoRR"},{"key":"pone.0313238.ref035","doi-asserted-by":"crossref","first-page":"101556","DOI":"10.1109\/ACCESS.2022.3208957","article-title":"Enhancing cluster analysis with explainable AI and multidimensional cluster prototypes","volume":"10","author":"S Bobek","year":"2022","journal-title":"IEEE Access"},{"key":"pone.0313238.ref036","article-title":"From Clustering to Cluster Explanations via Neural Networks","author":"JR Kauffmann","year":"2019","journal-title":"CoRR"},{"key":"pone.0313238.ref037","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.ins.2021.02.027","article-title":"Deep multi-view document clustering with enhanced semantic embedding","volume":"564","author":"R Bai","year":"2021","journal-title":"Information Sciences"},{"key":"pone.0313238.ref038","doi-asserted-by":"crossref","first-page":"101250","DOI":"10.1016\/j.elerap.2023.101250","article-title":"Categorizing affective response of customer with novel explainable clustering algorithm: The case study of Amazon reviews","volume":"58","author":"W Kim","year":"2023","journal-title":"Electronic Commerce Research and Applications"},{"key":"pone.0313238.ref039","doi-asserted-by":"crossref","unstructured":"Xu Z, Ke Y. Effective and Efficient Spectral Clustering on Text and Link Data. In: CIKM\u201916: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management; 2016. p. 357\u2013366.","DOI":"10.1145\/2983323.2983708"},{"key":"pone.0313238.ref040","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to Information Retrieval","author":"CD Manning","year":"2008"},{"issue":"3","key":"pone.0313238.ref041","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1287\/mnsc.17.3.219","article-title":"An r-dimensional quadratic placement problem","volume":"17","author":"KM Hall","year":"1970","journal-title":"Management Science"},{"issue":"6","key":"pone.0313238.ref042","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1162\/089976603321780317","article-title":"Laplacian Eigenmaps for Dimensionality Reduction and Data Representation","volume":"15","author":"M Belkin","year":"2003","journal-title":"Neural Computation"},{"issue":"4","key":"pone.0313238.ref043","doi-asserted-by":"crossref","first-page":"703","DOI":"10.34768\/amcs-2020-0052","article-title":"A feasible k-means kernel trick under non-Euclidean feature space","volume":"30","author":"R K\u0142opotek","year":"2020","journal-title":"International Journal of Applied Mathematics and Computer Science"},{"issue":"3-4","key":"pone.0313238.ref044","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1093\/biomet\/53.3-4.325","article-title":"Some distance properties of latent root and vector methods used in multivariate analysis","volume":"53","author":"JC Gower","year":"1966","journal-title":"Biometrika"},{"key":"pone.0313238.ref045","doi-asserted-by":"crossref","unstructured":"Dhillon IS, Guan Y, Kulis B. Kernel K-means: Spectral Clustering and Normalized Cuts. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD\u201904. New York, NY, USA: ACM; 2004. p. 551\u2013556.","DOI":"10.1145\/1014052.1014118"},{"key":"pone.0313238.ref046","doi-asserted-by":"crossref","unstructured":"Whang J, Dhillon IS, Gleich D. Non-exhaustive, Overlapping k-means. In: SIAM International Conference on Data Mining (SDM); 2015. p. 936\u2013944.","DOI":"10.1137\/1.9781611974010.105"},{"key":"pone.0313238.ref047","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/s41586-020-2649-2","article-title":"Array programming with NumPy","volume":"585","author":"CR Harris","year":"2020","journal-title":"Nature"},{"key":"pone.0313238.ref048","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","article-title":"SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python","volume":"17","author":"P Virtanen","year":"2020","journal-title":"Nature Methods"},{"key":"pone.0313238.ref049","first-page":"108","volume-title":"ECML PKDD Workshop: Languages for Data Mining and Machine Learning","author":"L Buitinck","year":"2013"},{"key":"pone.0313238.ref050","author":"H Kim","year":"2020","journal-title":"clustering4docs GitHub repository"},{"key":"pone.0313238.ref051","doi-asserted-by":"crossref","first-page":"113288","DOI":"10.1016\/j.eswa.2020.113288","article-title":"Improving spherical k-means for document clustering: Fast initialization, sparse centroid projection, and efficient cluster labeling","volume":"150","author":"H Kim","year":"2020","journal-title":"Expert Systems with Applications"},{"issue":"3","key":"pone.0313238.ref052","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1016\/j.csda.2011.09.003","article-title":"Selection of the Number of Clusters via the Bootstrap Method","volume":"56","author":"Y Fang","year":"2012","journal-title":"Comput Stat Data Anal"},{"key":"pone.0313238.ref053","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.patrec.2019.02.006","article-title":"Approximate spectral clustering with eigenvector selection and self-tuned k","volume":"122","author":"M Alshammari","year":"2019","journal-title":"Pattern Recognition Letters"}],"container-title":["PLOS ONE"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pone.0313238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T13:25:05Z","timestamp":1738675505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pone.0313238"}},"subtitle":[],"editor":[{"given":"Tiago","family":"Pereira","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2025,2,4]]},"references-count":53,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2,4]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pone.0313238","relation":{},"ISSN":["1932-6203"],"issn-type":[{"value":"1932-6203","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,4]]}}}