Submodular Optimization Approach for Entity Summarization in Knowledge Graph Driven by Large Language Models

doi:10.3778/j.issn.1673-9418.2305086

Abstract

Abstract: The continuous expansion of the knowledge graph has made entity summarization a research hotspot. The goal of entity summarization is to obtain a brief description of an entity from large-scale triple-structured facts that describe it. The research aims to propose a submodular optimization method for entity summarization based on a large language model. Firstly, based on the descriptive information of entities, relationships, and properties in the triples, a large language model is used to embed them to vectors, effectively capturing the semantic information of the triples and generating embedding vectors containing rich semantic information. Secondly, based on the embedding vectors generated by the large language model, a method is defined to characterize the relevance between any two triples that describe the same entity. The higher the relevance between any two triples, the more similar the information contained in these two triples. Finally, based on the defined method for characterizing triple relevance, a normalized and monotonically non-decreasing submodular function is defined, modeling entity summarization as a submodular function maximization problem. Therefore, greedy algorithms with performance guarantees can be directly applied to extracting entity summaries. Testing is conducted on three public benchmark datasets, and the quality of the extracted entity summaries is evaluated using two metrics, F1 score and NDCG (normalized discounted cumulative gain). Experimental results show that the proposed approach significantly outperforms the state-of-the-art method.

Key words: entity summarization, large language model, submodular function, greedy algorithm

摘要： 知识图谱的规模不断增加，使得实体摘要成为了研究的热点问题。实体摘要的目标是从描述实体的大规模三元结构事实中得到实体的简洁描述。研究的目的是基于大语言模型提出一种次模优化方法用于实体摘要的提取。首先，基于三元组中实体、关系和属性的描述信息，采用大语言模型对它们进行嵌入，能够有效地捕捉三元组的语义信息，生成包含丰富语义信息的嵌入向量。其次，基于大语言模型生成的嵌入向量，定义任意两个描述同一实体的三元组事实之间关联度的刻画方法，任意两个三元组之间的关联度越高，表示这两个三元组之间包含的信息越相似。最后，基于上述定义的三元组关联度的刻画方法，定义正规化且单调非减的次模函数，将实体摘要建模为次模函数最大化问题，那么具有性能保证的贪心算法可以直接用于提取实体的摘要。在三个公共基准数据集上进行测试，采用[F1]值和归一化折损累计增益（NDCG）两个指标对提取的实体摘要的质量进行评估，实验结果表明该方法显著优于当前最先进的方法。

关键词: 实体摘要, 大语言模型, 次模函数, 贪心算法

ZHANG Qi, ZHONG Hao. Submodular Optimization Approach for Entity Summarization in Knowledge Graph Driven by Large Language Models[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(7): 1806-1813.

张琪, 钟昊. 大语言模型驱动的知识图谱实体摘要的次模优化方法[J]. 计算机科学与探索, 2024, 18(7): 1806-1813.

References

[1] LIU Q, CHENG G, GUNARATNA K, et al. Entity summarization: state of the art and future challenges[J]. Journal of Web Semantics, 2021, 69: 100647.
[2] DEVLIN J, CHANG M W, LEE K, et al. BERT: pre-training of deep bidirectional transformers for language understanding[C]//Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Minneapolis, Jun 2-7, 2019. Stroudsburg: ACL, 2009: 4171-4186.
[3] EKGREN A, GYLLENSTEN A C, GOGOULOU E, et al. Lessons learned from GPT-SW3: building the first large-scale generative language model for Swedish[C]//Proceedings of the 13th Language Resources and Evaluation Conference, Marseille, Jun 20-25, 2022: 3509-3518.
[4] NONG Q, SUN T, GONG S, et al. Maximize a monotone function with a generic submodularity ratio[C]//Proceedings of the 13th Algorithmic Aspects in Information and Management, Beijing, Aug 6-8, 2019. Cham: Springer, 2019: 249-260.
[5] MIRZASOLEIMAN B, BADANIDIYURU A, KARBASI A, et al. Lazier than lazy greedy[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, Jan 25-30, 2015. Menlo Park: AAAI, 2015: 1812-1818.
[6] CHEBOLU P, MELSTED P. PageRank and the random surfer model[C]//Proceedings of the 19th Annual Symposium on Discrete Algorithms, San Francisco, Jan 20-22, 2008: 1010-1018.
[7] CHENG G, TRAN T, QU Y. RELIN: relatedness and informativeness-based centrality for entity summarization[C]//Proceedings of the 10th International Semantic Web Conference, Bonn, Oct 23-27, 2011. Berlin, Heidelberg: Springer, 2011: 114-129.
[8] GUNARATNA K, THIRUNARAYAN K, SHETH A. FACES: diversity-aware entity summarization using incremental hierarchical conceptual clustering[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, Jan 25-30, 2015. Menlo Park: AAAI, 2015: 116-122.
[9] BECK H W, ANWAR T, NAVATHE S B. A conceptual clustering algorithm for database schema design[J]. IEEE Transactions on Knowledge and Data Engineering, 1994, 6(3): 396-411.
[10] THALHAMMER A, LASIERRA N, RETTINGER A. LinkSUM: using link analysis to summarize entity data[C]//Proceedings?of?the?16th?International?Conference?on?Web?Engineering, Lugano, Jun 6-9, 2016. Cham: Springer, 2016: 244-261.
[11] LIU Q, CHENG G, GUNARATNA K, et al. ESBM: an entity summarization benchmark[C]//Proceedings of the 17th International Conference on Extended Semantic Web Conference, Heraklion, May 31-Jun 4, 2020. Cham: Springer, 2020: 548-564.
[12] WEI D, LIU Y, ZHU F, et al. ESA: entity summarization with attention[EB/OL]. [2023-03-05]. https://arxiv.org/abs/1905.10625.
[13] LIU Q, CHENG G, QU Y. DeepLens: deep learning for entity summarization[C]//Proceedings of the 2020 Workshop on Deep Learning for Knowledge Graphs Co-located with the 17th Extended Semantic Web Conference, Heraklion, Jun 2, 2020: 2635.
[14] WEI D, LIU Y, ZHU F, et al. AutoSUM: automating feature extraction and multi-user preference simulation for entity summarization[C]//Proceedings of the 24th Pacific-Asia Conf-erence on Knowledge Discovery and Data Mining, May 11-14, 2020. Cham: Springer, 2020: 580-592.
[15] LIU Q, CHEN Y, CHENG G, et al. Entity summarization with user feedback[C]//Proceedings of the 17th International Conference on Extended Semantic Web Conference, Heraklion, May 31-Jun 4, 2020. Cham: Springer, 2020: 376-392.
[16] FIRMANSYAH A F, MOUSSALLEM D, NGOMO A C N. GATES: using graph attention networks for entity summarization[C]//Proceedings of the 11th Knowledge Capture Conference, Dec 2-3, 2021. New York: ACM, 2021: 73-80.
[17] LIN H, BILMES J. Multi-document summarization via budgeted maximization of submodular functions[C]//Proceedings of the 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Los Angeles, Jun 2-4, 2010. Stroudsburg: ACL, 2010: 912-920.
[18] LIN H, BILMES J. A class of submodular functions for document summarization[C]//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Portland, Jun 19-24, 2011.Stroudsburg: ACL, 2011: 510-520.
[19] JAYANTH J, SUNDARARAJ J, BHATTACHARYYA P. Monotone submodularity in opinion summaries[C]//Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, Lisbon, Sep 17-21, 2015. Str-oudsburg: ACL, 2015: 169-178.
[20] WANG Y, WANG L, LI Y, et al. A theoretical analysis of NDCG type ranking measures[C]//Proceedings of the 26th Annual Conference on Learning Theory, Princeton, Jun 12-14, 2013: 25-54.
[21] RIVES A, MEIER J, SERCU T, et al. Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences[J]. Proceedings of the National Academy of Sciences of the United States of America, 2021, 118(15): e2016239118.
[22] LIU Y, OTT M, GOYAL N, et al. RoBERTa: a robustly optimized BERT pretraining approach[EB/OL]. [2023-03-05].https://arxiv.org/abs/1907.11692.
[23] YANG Z, DAI Z, YANG Y, et al. XLNet: generalized auto-regressive pretraining for language understanding[C]//Proceedings of the 33rd International Conference on Neural Information Processing Systems, Vancouver, Dec 8-14, 2019. New York: ACM, 2019: 5753-5763.