Using Graph-Based Maximum Independent Sets with Large Language Models for Extractive Text Summarization
Source abstract
Abstract
Large Language Models (LLMs) have shown a strong performance across various tasks but still face challenges in automatic text summarization. While they are effective in capturing semantic patterns from large corpora, they typically lack mechanisms for encoding structural relationships between sentences or paragraphs. Their high hardware requirements and limited analysis as to processing efficiency further constrain their applicability. This paper proposes a framework employing the Graph Independent Set approach to extract the essence of textual graphs and address the limitations of LLMs. The framework encapsulates nodes and relations into structural graphs generated through Natural Language Processing (NLP) techniques based on the Maximum Independent Set (MIS) theory. The incorporation of graph-derived structural features enables more semantically cohesive and accurate summarization outcomes. Experiments on the Document Understanding Conference (DUC) and Cable News Network (CNN)/DailyMail datasets are conducted with different summary lengths to evaluate the performance of the framework. The proposed method provides up to a 41.05% (Recall-Oriented Understudy for Gisting Evaluation, ROUGE-2 F1) increase in summary quality and a 60.71% improvement in response times on models such as XLNet, Pegasus, and DistilBERT. The proposed framework enables more informative and concise summaries by embedding structural relationships into LLM-driven semantic representations, while reducing computational costs. In this study, we explore whether integrating MIS-based graph filtering with LLMs significantly enhances both the accuracy and efficiency of extractive text summarization.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Topic Modeling · Advanced Text Analysis Techniques · Text and Document Classification Technologies
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Engineering, İnönü University, Malatya 44000, Turkey
References (61)
Show source-provided references
1. Language models are few-shot learners
2. GPT-3: Its Nature, Scope, Limits, and Consequences10.1007/s11023-020-09548-1 ↗
3. Shetty, A.M., DH., M., and Aljunid, M.F. (2025). Fine-tuning XLNet for Amazon review sentiment analysis: A comparative evaluation of transformer models. ETRI J., 1–18.10.4218/etrij.2024-0318 ↗
4. Zhang, J., Zhao, Y., Saleh, M., and Liu, P. (2020, January 13–18). Pegasus: Pre-training with extracted gap-sentences for abstractive summarization. Proceedings of the International Conference on Machine Learning, Vienna, Austria.
5. Harnessing the Power of Hugging Face Transformers for Predicting Mental Health Disorders in Social Networks10.1109/ACCESS.2024.3366653 ↗
6. Tsai, Y.-H., Chang, C.-M., Chen, K.-H., and Hwang, S.-Y. (2022). An Integration of TextGCN and Autoencoder into Aspect-Based Sentiment Analysis, Springer.10.1007/978-3-031-12670-3_1 ↗
7. Yang, S., Duan, X., Xiao, Z., Li, Z., Liu, Y., Jie, Z., Tang, D., and Du, H. (2022). Sentiment Classification of Chinese Tourism Reviews Based on ERNIE-Gram+GCN. Int. J. Environ. Res. Public Health, 19.10.3390/ijerph192013520 ↗
8. Zeng, D., Zha, E., Kuang, J., and Shen, Y. (2024). Multi-label text classification based on semantic-sensitive graph convolutional network. Knowl. -Based Syst., 284.10.1016/j.knosys.2023.111303 ↗
9. Zuo, Y., Wu, J., Zhang, H., Lin, H., Wang, F., Xu, K., and Xiong, H. (2016, January 13–17). Topic Modeling of Short Texts. Proceedings of the Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.10.1145/2939672.2939880 ↗
10. Zhao, K., Huang, L., Song, R., Shen, Q., and Xu, H. (2021). A Sequential Graph Neural Network for Short Text Classification. Algorithms, 14.10.3390/a14120352 ↗
11. Mouratidis, D., and Kermanidis, K.L. (2019). Ensemble and Deep Learning for Language-Independent Automatic Selection of Parallel Data. Algorithms, 12.10.3390/a12010026 ↗
12. Chai, Z., Zhang, T., Wu, L., Han, K., Hu, X., Huang, X., and Yang, Y. (2023). GraphLLM: Boosting Graph Reasoning Ability of Large Language Model. arXiv, Available online: https://arxiv.org/abs/2310.05845.
13. Chen, Z., Mao, H., Li, H., Jin, W., Wen, H., Wei, X., Wang, S., Yin, D., Fan, W., and Liu, H. (2024). Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs. arXiv, Available online: https://arxiv.org/abs/2307.03393.
14. Fatemi, B., Halcrow, J., and Perozzi, B. (2023). Talk like a Graph: Encoding Graphs for Large Language Models. arXiv, Available online: https://arxiv.org/abs/2310.04560.
15. Guo, J., Du, L., Liu, H., Zhou, M., He, X., and Han, S. (2023). GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking. arXiv, Available online: https://arxiv.org/abs/2305.15066.
16. GoSum: Extractive summarization of long documents by reinforcement learning and graph-organized discourse state10.1007/s10115-024-02195-3 ↗
17. Chen, T., Wang, X., Yue, T., Bai, X., Le, C.X., and Wang, W. (2023). Enhancing Abstractive Summarization with Extracted Knowledge Graphs and Multi-Source Transformers. Appl. Sci., 13.10.3390/app13137753 ↗
18. Zeng, G.-H., Liu, Y.-Q., Zhang, C.-Y., Cai, H.-C., and Chen, C.L.P. (2024). Adaptive Multi-Document Summarization Via Graph Representation Learning. IEEE Trans. Cogn. Dev. Syst., 1–12.10.1109/TCDS.2024.3519181 ↗
19. Ivanisenko, T.V., Demenkov, P.S., and Ivanisenko, V.A. (2024). An Accurate and Efficient Approach to Knowledge Extraction from Scientific Publications Using Structured Ontology Models, Graph Neural Networks, and Large Language Models. Int. J. Mol. Sci., 25.10.3390/ijms252111811 ↗
20. Chen, J., and Yang, D. (2021). Structure-Aware Abstractive Conversation Summarization via Discourse and Action Graphs. arXiv, Available online: https://arxiv.org/abs/2104.08400.10.18653/v1/2021.naacl-main.109 ↗
21. Cui, P., Hu, L., and Liu, Y. (2020). Enhancing Extractive Text Summarization with Topic-Aware Graph Neural Networks. arXiv, Available online: https://arxiv.org/abs/2010.06253.10.18653/v1/2020.coling-main.468 ↗
22. Yasunaga, M., Zhang, R., Meelu, K., Pareek, A., Srinivasan, K., and Radev, D. (2017). Graph-based Neural Multi-Document Summarization. arXiv, Available online: https://arxiv.org/abs/1706.06681.10.18653/v1/K17-1045 ↗
23. Sun, G., Wang, Y., Niyato, D., Wang, J., Wang, X., Poor, H.V., and Letaief, K.B. (2024). Large Language Model (LLM)-enabled Graphs in Dynamic Networking. IEEE Netw.10.1109/MNET.2024.3511662 ↗
24. A semantic graph-based approach to biomedical summarisation10.1016/j.artmed.2011.06.005 ↗
25. Givchi, A., Ramezani, R., and Baraani-Dastjerdi, A. (2022). Graph-based abstractive biomedical text summarization. J. Biomed. Inform., 132.10.1016/j.jbi.2022.104099 ↗
26. Zhu, X., Xue, H., Zhao, Z., Xu, W., Huang, J., Guo, M., Wang, Q., Zhou, K., and Zhang, Y. (2025). LLM as GNN: Graph Vocabulary Learning for Text-Attributed Graph Foundation Models. arXiv, Available online: https://arxiv.org/abs/2503.03313.10.2139/ssrn.5162133 ↗
27. (2021, July 14). Document Understanding Conferences, Available online: http://duc.nist.gov.
28. See, A., Liu Google Brain, P.J., and Manning, C.D. (2017). Get To The Point: Summarization with Pointer-Generator Networks. arXiv.10.18653/v1/P17-1099 ↗
29. Lin, C.Y. (2004). Rouge: A package for automatic evaluation of summaries. Text Summarization Branches Out (WAS 2004), Association for Computational Linguistics.
30. Hermann, K.M., Kocisky, T., Grefenstette, E., Espeholt, L., Kay, W., Suleyman, M., and Blunsom, P. (2015, January 7–12). Teaching machines to read and comprehend. Proceedings of the Advances in Neural Information Processing Systems, Montréal, QC, Canada.
31. Moscibroda, T., and Wattenhofer, R. (2005, January 17–20). Maximal independent sets in radio networks. Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, Las Vegas, NV, USA.10.1145/1073814.1073842 ↗
32. McIlroy, D. (1978, January 1–3). The UNIX Time-Sharing System: Foreword. Proceedings of the First ACM SIGPLAN Conference on History of Programming Languages (HOPL-I), Los Angeles, CA, USA.
33. Mrzic, A., Meysman, P., Bittremieux, W., Moris, P., Cule, B., Goethals, B., and Laukens, K. (2018). Grasping frequent subgraph mining for bioinformatics applications. BioData Min., 11.10.1186/s13040-018-0181-9 ↗
34. Extractive multi-document text summarization based on graph independent sets10.1016/j.eij.2019.12.002 ↗
35. Öztemiz, F. (2025). A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm. Eng. Sci. Technol. Int. J., 63.10.1016/j.jestch.2025.101995 ↗
36. A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm
37. The Number Of Maximum Independent Sets In Graphs
38. Zhao, W.X., Zhou, K., Li, J., Tang, T., Wang, X., Hou, Y., Min, Y., Zhang, B., Zhang, J., and Dong, Z. (2025). A Survey of Large Language Models. arXiv, Available online: https://arxiv.org/abs/2303.18223.
39. Feng, S.Y., Gangal, V., Wei, J., Chandar, S., Vosoughi, S., Mitamura, T., and Hovy, E. (2021). A Survey of Data Augmentation Approaches for NLP. arXiv, Available online: https://arxiv.org/abs/2105.03075.10.18653/v1/2021.findings-acl.84 ↗
40. Taking AI risks seriously: A new assessment model for the AI Act10.1007/s00146-023-01723-z ↗
41. Cai, Y., Mao, S., Wu, W., Wang, Z., Liang, Y., Ge, T., Wu, C., You, W., Song, T., and Xia, Y. (2024). Low-code LLM: Graphical User Interface over Large Language Models. arXiv, Available online: https://arxiv.org/abs/2304.08103.
42. Yao, Y., Duan, J., Xu, K., Cai, Y., Sun, Z., and Zhang, Y. (2024). A survey on large language model (LLM) security and privacy: The Good, The Bad, and The Ugly. High-Confid. Comput., 4.10.1016/j.hcc.2024.100211 ↗
43. Zhongyu, S., Zhou, W., Ding, C., and Xia, M. (2022). Multi-Resolution Transformer Network for Building and Road Segmentation of Remote Sensing Image. ISPRS Int. J. Geo-Inf., 11.10.3390/ijgi11030165 ↗
44. Kalyan, K.S. (2024). A survey of GPT-3 family large language models including ChatGPT and GPT-4. Nat. Lang. Process. J., 6.10.1016/j.nlp.2023.100048 ↗
45. AI-based language models powering drug discovery and development10.1016/j.drudis.2021.06.009 ↗
46. AI Assisted Attention Mechanism for Hybrid Neural Model to Assess Online Attitudes About COVID-1910.1007/s11063-022-11112-0 ↗
47. On the transferability of adversarial perturbation attacks against fingerprint based authentication systems10.1016/j.patrec.2021.10.015 ↗
48. A transformer-based approach to irony and sarcasm detection10.1007/s00521-020-05102-3 ↗
49. Yang, T., Li, F., Ji, D., Liang, X., Xie, T., Tian, S., Li, B., and Liang, P. (2021). Fine-grained depression analysis based on Chinese micro-blog reviews. Inf. Process. Manag., 58.10.1016/j.ipm.2021.102681 ↗
50. A Convolutional Neural Network-enabled IoT framework to verify COVID-19 hygiene conditions and authorize access to facilities10.1016/j.procs.2022.07.108 ↗
51. Towards smarter hiring: Resume parsing and ranking with YOLOv5 and DistilBERT10.1007/s11042-024-18778-9 ↗
52. Wang, H., Kang, X., and Ren, F. (2022). Emotion-Sentence-DistilBERT: A Sentence-BERT-Based Distillation Model for Text Emotion Classification, Springer.10.1007/978-981-19-7943-9_27 ↗
53. Leteno, T., Gourru, A., Laclau, C., and Gravier, C. (2023). An Investigation of Structures Responsible for Gender Bias in BERT and DistilBERT, Springer.10.1007/978-3-031-30047-9_20 ↗
54. Natural language processing analysis applied to COVID-19 open-text opinions using a distilBERT model for sentiment categorization10.1007/s00146-022-01594-w ↗
55. Qiu, K., Zhang, Y., Feng, Y., and Chen, F. (2025). LogAnomEX: An Unsupervised Log Anomaly Detection Method Based on Electra-DP and Gated Bilinear Neural Networks. J. Netw. Syst. Manag., 33.10.1007/s10922-025-09912-5 ↗
56. Deep learning in target prediction and drug repositioning: Recent advances and challenges10.1016/j.drudis.2021.10.010 ↗
57. The road from MLE to EM to VAE: A brief tutorial10.1016/j.aiopen.2021.10.001 ↗
58. Textual emotion recognition method based on ALBERT-BiLSTM model and SVM-NB classification10.1007/s00500-023-07924-4 ↗
59. Heim, E., Ramia, J.A., Hana, R.A., Burchert, S., Carswell, K., Cornelisz, I., Cuijpers, P., El Chammay, R., Noun, P., and van Klaveren, C. (2021). Step-by-step: Feasibility randomised controlled trial of a mobile-based intervention for depression among populations affected by adversity in Lebanon. Internet Interv., 24.10.1016/j.invent.2021.100380 ↗
60. Hunhevicz, J.J., and Hall, D.M. (2020). Do you need a blockchain in construction? Use case categories and decision framework for DLT design options. Adv. Eng. Inform., 45.10.1016/j.aei.2020.101094 ↗
61. An abstractive Arabic text summarizer with user controlled granularity10.1016/j.ipm.2018.06.002 ↗