Towards explainability of hashtags in the light of Graph Spectral Clustering methods

• Autorzy: Starosta Bartłomiej , Kłopotek Mieczysław A. , Wierzchoń Sławomir T.

Identyfikatory

DOI

10.34739/si.2023.29.04

• Języki publikacji: EN

Abstrakty

EN

Hashtags constitute an indispensable part of modern social media world. As more and more hashtags are invented, it becomes a necessity to create clusters of these hashtags. Nowadays, however, the clustering alone does not help the users. They are asking for justification or expressed in the modern AI language, the clustering has to be explainable. We discuss a novel approach to hashtag explanation via a measure of similarity between hashtags based on the Graph Spectral Analysis. The application of this similarity measure may go far beyond the classical clustering task. It can be used to provide with explanations for the hashtags. In this paper we propose such a novel view of the proposed hashtag similarity measure.

Słowa kluczowe

EN

graph spectral analysis; hashtag similarity; eigenvalue spectrograms; explainable artificial intelligence

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2023
• Tom: Vol. 2(29)
• Strony: 57--68
• Opis fizyczny: Bibliogr. 67 poz., tab., wykr.

Twórcy

autor

Starosta Bartłomiej

• Institute of Computer Science of Polish Academy of Sciencesul. Jana Kazimierza 5, 01-248 Warszawa, Poland

• https://orcid.org/0000-0002-5554-4596

autor

Kłopotek Mieczysław A.

• Institute of Computer Science of Polish Academy of Sciencesul. Jana Kazimierza 5, 01-248 Warszawa, Poland

• https://orcid.org/0000-0003-4685-7045

autor

Wierzchoń Sławomir T.

• Institute of Computer Science of Polish Academy of Sciencesul. Jana Kazimierza 5, 01-248 Warszawa, Poland

• https://orcid.org/0000-0001-8860-392X

Bibliografia

• 1. Schmidt, A. & Others Using Spectral Clustering of Hashtag Adoptions to Find Interest-Based Communities. 2018 IEEE International Conference On Communications (ICC). pp. 1-7 (2018).
• 2. Jeon, M., Jun, S. & Hwang, E. Hashtag Recommendation Based on User Tweet and Hashtag Classification on Twitter. Web-Age Information Management. pp. 325-336 (2014).
• 3. Gupta, V. & Hewett, R. Unleashing the Power of Hashtags in Tweet Analytics with Distributed Framework on Apache Storm. (arXiv,2018).
• 4. Golub, G. & Loan, C. Matrix computation. A comprehensive treatment of numerical linear algebra from the standpoint of both theory and practice.. (JHU Press,2013).
• 5. Chaudhuri, K., Chung, F. & Tsiatas, A. Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model. Proceedings Of The 25th Annual Conference On Learning Theory. 23 pp. 35.1- 35.23 (2012), https://proceedings.mlr.press/v23/chaudhuri12.html
• 6. Kumar, N. & Schneider, J. Literature survey on low rank approximation of matrices. Linear And Multilinear Algebra. 65, 2212-2244 (2017), https://doi.org/10.1080/03081087.2016.1267104
• 7. Luxburg, U. A Tutorial on Spectral Clustering. Statistics And Computing. 17, 395-416 (2007), http://dx.doi.org/10.1007/s11222-007-9033-z
• 8. Dudek, A. Classification via spectral clustering. Acta Universitas Lodziensis. 135 pp. 121-130 (2021), https://dspace.uni.lodz.pl/xmlui/bitstream/handle/11089/344/121-130.pdf?sequence=1
• 9. Suganthi, R. & S. Manimekalai Spectral Clustering Based Classification Algorithm for Text Classification . International Journal Of Engineering Science Invention (IJESI). pp. 36-41 (2018),ℎ𝑡𝑡𝑝𝑠 : //𝑐𝑠.𝑏𝑟𝑜𝑤𝑛.𝑒𝑑𝑢/𝑐𝑜𝑢𝑟𝑠𝑒𝑠/𝑐𝑠𝑐𝑖1820/𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠/𝑆𝑢𝑔𝑎𝑛𝑡ℎ𝑖𝑀𝑎𝑛𝑖𝑚𝑒𝑘𝑎𝑙𝑎𝑖2018.𝑝𝑑𝑓, One Day National Conference On “Internet Of Things– The Current Trend In Connected World” 36 Page NCIOT-2018.
• 10. Suganthi, R. & S. Manimekalai Spectral Clustering Based Classification Algorithm for Text Classification . International Journal Of Engineering Science Invention (IJESI). pp. 36-41 (2018), urlhttp://www.ijesi.org/papers/NCIOT-2018/Volume-3/7.
• 11. Owhadi-Kareshk, M. & Akbarzadeh-T., M. Spectral Clustering-based Classification. 2015 5th International Conference On Computer And Knowledge Engineering (ICCKE). pp. 222-227 (2015).
• 12. Karami, H. &Taheri, M. Anovel framework to generate clustering algorithms based on a particular classification structure. 2017 Artificial Intelligence And Signal Processing Conference (AISP). pp. 201-204 (2017).
• 13. Mahmood, A. & Mian, A. Semi-supervised Spectral Clustering for Classification. (arXiv,2014).
• 14. Fowlkes, C., Belongie, S., Chung, F. & Malik, J. Spectral grouping using the Nyström method. IEEE Transactions On Pattern Analysis And Machine Intelligence. 26 (2004).
• 15. Li, S. & Hao, J. Spectral Clustering-Based Semi-supervised Sentiment Classification. Ad vanced Data Mining And Applications. ADMA 2012. LNAI 7713 pp. 271-283 (2012), ℎ𝑡𝑡𝑝𝑠 : //𝑑𝑜𝑖.𝑜𝑟𝑔/10.1007/978−3−642−35527−123
• 16. Pourkamali-Anaraki, F. Scalable Spectral Clustering With Nyström Approximation: Practical and Theoretical Aspects. IEEE Open Journal Of Signal Processing. 1 pp. 242-256 (2020), ℎ𝑡𝑡𝑝𝑠 : //𝑑𝑜𝑖.𝑜𝑟𝑔/10.1109/𝑂𝐽𝑆𝑃.2020.3039330
• 17. Kamvar, S., Klein, D. & Manning, C. Spectral Learning. Proceedings Of The 18th International Joint Conf. On Artificial Intelligence. IJCAI’03. pp. 561-566 (2003).
• 18. Baraniak, K. & Sydow, M. A dataset for Sentiment analysis of Entities in News headlines (SEN). Procedia Computer Science. 192 (2021).
• 19. Gasparetto, A., Marcuzzo, M., Zangari, A. & Albarelli, A. A Survey on Text Classification Algorithms: From Text to Predictions. Information. 13 (2022).
• 20. Kowsari, K., Jafari Meimandi, K., Heidarysafa, M., Mendu, S., Barnes, L. & Brown, D. Text Classification Algorithms: A Survey. Information. 10 (2019)
• 21. Sevi, H., Jonckheere, M. & Kalogeratos, A. Generalized Spectral Clustering for Directed and Undirected Graphs. (arXiv,2022).
• 22. Tu, J., Mei, G. & Picciallib, F. An improved Nyström spectral graph clustering using k-core decomposition as a sampling strategy for large networks. Journal Of King Saud University Computer And Information Sciences. (2022).
• 23. Janani, R. & Vijayarani, S. Text document clustering using Spectral Clustering algorithm with Particle Swarm Optimization. Expert Systems With Applications. 134 pp. 192-200 (2019).
• 24. Nie, F., Zeng, Z., Tsang, I., Xu, D. & Changshui, C. Spectral Embedded Clustering: A Framework for In-Sample and Out-of-Sample Spectral Clustering. IEEE Trans. Neur. Netw.. (2011).
• 25. Bengio, Y., Paiement, J., Vincent, P., Delalleau, O., Roux, N. & Ouimet, M. Out-of-sample extensions for LLE, ISOMAP, MDS, eigenmaps, and spectral clustering. NIPS 16. pp. 177-184 (2003).
• 26. Alzate, C. & Suykens, J. Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA. IEEE Transactions On Pattern Analysis And Machine Intelligence. 32, 335- 347 (2010,2).
• 27. Shen,D.,Li,X.&Yan,G.Improve the spectral clustering by integrating a new modularity similarity index and out-of-sample extension. Modern Physics Letters B. 34, 2050105 (2020).
• 28. Xanthopoulos, P., Guarracino, M. & Pardalos, P. Robust generalized eigenvalue classifier with ellipsoidal uncertainty. Ann. Oper. Res.. 216, 327-342 (2014), https://doi.org/10.1007/s10479-012-1303-2
• 29. Guarracino, M., Cifarelli, C., Seref, O. & Pardalos, P. A classification method based on generalized eigenvalue problems. Optim. Methods Softw.. 22, 73-81 (2007), https://doi.org/10.1080/10556780600883874
• 30. Zeng, Y. & Liang, Y. Eigenvalue-based spectrum sensing algorithms for cognitive radio. IEEE Transactions On Communications. 57, 1784-1793 (2009).
• 31. Rebagliati, N. & Verri, A. Spectral clustering with more than K eigenvectors. Neurocomputing. 74, 1391-1401 (2011,4), DOI: 10.1016/j.neurocom.2010.12.08
• 32. Liu, B., Shen, X. & Pan, W. Semi-supervised spectral clustering with application to detect population stratification. Frontiers In Genetics. pp. Article 215 (2013,10), https://doi.org/10.3389/fgene.2013.00215
• 33. Floridi,L.&Chiriatti,M.GPT-3:ItsNature,Scope,Limits,andConsequences..Minds&Machines. 30 pp. 681-694 (2020).
• 34. Mikolov, T., Chen, K., Corrado, G. & Dean, J. Efficient Estimation of Word Representations in Vector Space. (arXiv,2013).
• 35. Jeffrey Pennington, C. GloVe: Global Vectors for Word Representation. Proceedings Of The 2014 Conference On Empirical Methods In Natural Language Processing (EMNLP). pp. 1532-1543 (2014).
• 36. De Boom, C., Van Canneyt, S., Demeester, T. & Dhoedt, B. Representation learning for very short texts using weighted word embedding aggregation. Pattern Recognition Letters. 80 pp. 150-156 (2016), https://www.sciencedirect.com/science/article/pii/S0167865516301362
• 37. Kiros, R., Zhu, Y., Salakhutdinov, R., Zemel, R., Urtasun, R., Torralba, A. & Fidler, S. Skip-Thought Vectors. Advances In Neural Information Processing Systems. 28 pp. 3294-3302 (2015), https://proceedings.neurips.cc/paper/2015/file/f442d33fa06832082290ad8544a8da27-Paper.pdf
• 38. Xie, J., Girshick, R. & Farhadi, A. Unsupervised Deep Embedding for Clustering Analysis. Proceedings Of The 33rd International Conference On Machine Learning. 48 pp. 478-487 (2016,6,20), https://proceedings.mlr.press/v48/xieb16.html
• 39. Hadifar, A., Sterckx, L., Demeester, T. & Develder, C. A Self-Training Approach for Short Text Clustering. Proceedings Of The 4th Workshop On Representation Learning For NLP (RepL4NLP2019). pp. 194-199 (2019,8), https://aclanthology.org/W19-4322
• 40. Zhang, D., Nan, F., Wei, X., Li, S., Zhu, H., McKeown, K., Nallapati, R., Arnold, A. & Xiang, B. Supporting Clustering with Contrastive Learning. (arXiv,2021).
• 41. Xu, J., Xu, B., Wang, P., Zheng, S., Tian, G., Zhao, J. & Xu, B. Self-Taught convolutional neural networks for short text clustering. Neural Networks. 88 pp. 22-31 (2017), https://www.sciencedirect.com/science/article/pii/S0893608016301976
• 42. Zhang, D., Nan, F., Wei, X., Li, S., Zhu, H., McKeown, K., Nallapati, R., Arnold, A. & Xiang, B. Supporting Clustering with Contrastive Learning. (arXiv,2021).
• 43. Devlin, J., Chang, M., Lee, K. & Toutanova, K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. (arXiv,2018).
• 44. Rakib, M., Zeh, N., Jankowska, M. & Milios, E. Enhancement of Short Text Clustering by Iterative Classification. Natural Language Processing And Information Systems. pp. 105-117 (2020).
• 45. Li, C., Chen, S. & Qi, Y. Filtering and Classifying Relevant Short Text with a Few Seed Words. Data And Information Management. 3, 165-186 (2019), https://doi.org/10.2478/dim-2019-0011
• 46. Kowsari,K.,Meimandi,K.,Heidarysafa,M.,Mendu,S.,Barnes,L.&Brown,D.TextClassification Algorithms: A Survey. Information. 10, 150 (2019), https://doi.org/10.3390/info10040150
• 47. Xiang, T. & Gong, S. Spectral clustering with eigenvector selection. Pattern Recognition. 41, 1012-1029 (2008).
• 48. Avrachenkov, K., Chebotarev, P. & Rubanov, D. Kernels on Graphs as Proximity Measures. Proc. WAW2017, Toronto, Canada. pp. 27-41 (2017).
• 49. Dhillon, I., Guan, Y. & Kulis, B. Kernel k-means: spectral clustering and normalized cuts. Proc. KDD’04, ACM. pp. 551-556 (2004).
• 50. Filippone, M., Camastra, F., Masulli, F. & Rovetta, S. A survey of kernel and spectral methods for clustering. Pattern Recognition. 41, 176-190 (2008).
• 51. Wierzchon, S. & Klopotek, M. Spectral Cluster Maps Versus Spectral Clustering. Computer Information Systems And Industrial Management. 12133 pp. 472-484 (2020), https://doi.org/10.1007/978-3-030-47679-3
• 52. Dhillon, I., Guan, Y. & Kulis, B. A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts. (UTCS Tech. Rep. TR-04-25,2005,2), http://www.cs.utexas.edu/ftp/techreports/tr04-25.pdf
• 53. Hofmann,T.Probabilistic Latent Semantic Indexing. Proceedings Of The 22nd Annual International ACMSIGIR Conference On Research And Development In Information Retrieval.pp.50-57(1999), https://doi.org/10.1145/312624.312649
• 54. Blei, D., Ng, A. & Jordan, M. Latent dirichlet allocation. J. Mach. Learn. Res.. 3 pp. 993-1022 (2003).
• 55. Luxburg, U. A Tutorial on Spectral Clustering. Statistics And Computing. 17, 395-416 (2007).
• 56. Tu, J., Mei, G. & Piccialli, F. An improved Nyström spectral graph clustering using k-core decomposition as a sampling strategy for large networks. Journal Of King Saud University- Computer And Information Sciences. 34, 3673-3684 (2022).
• 57. Kauffmann, J., Esders, M., Ruff, L., Montavon, G., Samek, W. & Muller, K. From Clustering to Cluster Explanations via Neural Networks. IEEE Transactions On Neural Networks And Learning Systems. pp. 1-15 (2022), https://doi.org/10.1109.
• 58. Makarychev, K. & Shan, L. Explainable k-means. Don’t be greedy, plant bigger trees!. Proceedings Of The 54th Annual ACM SIGACT Symposium On Theory Of Computing, June 2022. pp. 1629-1642 (2022).
• 59. Arrieta, A., Díaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S., Barbado, A., Garcia, S., Gil-Lopez, S., Molina, D., Benjamins, R., Chatila, R. & Herrera, F. Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI. Information Fusion. 58 pp. 82- 115 (2020).
• 60. Bandyapadhyay, S., Fomin, F., Golovach, P., Lochet, W., Purohit, N. & Simonov, K. How to Find a Good Explanation for Clustering?. (arXiv,2021).
• 61. Devlin, J., Chang, M., Lee, K. & Toutanova, K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. (arXiv,2019).
• 62. Lau, J. & Baldwin, T. An Empirical Evaluation of doc2vec with Practical Insights into Document Embedding Generation. (arXiv,2016).
• 63. Wierzchoń, S. & Kłopotek, M. Modern Clustering Algorithms. (Springer Verlag,2018).
• 64. Starosta, B., Kłopotek, M., Wierzchoń, S. & Czerski, D. Hashtag Discernability– Competitiveness Study of Graph Spectral and Other Clustering Methods. Accepted For The 18th Conference On ComputerScience AndIntelligence Systems FedCSIS 2023 (IEEE #57573) Warsaw, Poland, 17–20 September, 2023 . (2023).
• 65. Wierzchon, S. & Klopotek, M. Spectral Cluster Maps Versus Spectral Clustering. Computer Information Systems And Industrial Management. 12133 pp. 472-484 (2020), https://doi.org/10.1007/978-3-030-47679-3
• 66. Borkowski, P., Kłopotek, M., Starosta, B., Wierzchoń, S. & Sydow, M. Eigenvalue based spectral classification. PLoS ONE. 18, e0283413 (2023).
• 67. B. Starosta, S. Hashtag Similarity Based on Laplacian Eigenvalue Spectrum. to appear in Proc. PP-RAI’2023- 4th Polish Conference on Artificial Intelligence , Łódź, Poland 2023.