Keyword-Based Knowledge Graph Exploration Based on Quadratic Group Steiner Trees
Keyword-Based Knowledge Graph Exploration Based on Quadratic Group Steiner Trees
Yuxuan Shi, Gong Cheng, Trung-Kien Tran, Jie Tang, Evgeny Kharlamov
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 1555-1562.
https://doi.org/10.24963/ijcai.2021/215
Exploring complex structured knowledge graphs (KGs) is challenging for non-experts as it requires knowledge of query languages and the underlying structure of the KGs. Keyword-based exploration is a convenient paradigm, and computing a group Steiner tree (GST) as an answer is a popular implementation. Recent studies suggested improving the cohesiveness of an answer where entities have small semantic distances from each other. However, how to efficiently compute such an answer is open. In this paper, to model cohesiveness in a generalized way, the quadratic group Steiner tree problem (QGSTP) is formulated where the cost function extends GST with quadratic terms representing semantic distances. For QGSTP we design a branch-and-bound best-first (B3F) algorithm where we exploit combinatorial methods to estimate lower bounds for costs. This exact algorithm shows practical performance on medium-sized KGs.
Keywords:
Data Mining: Mining Graphs, Semi Structured Data, Complex Data
Data Mining: Information Retrieval
Knowledge Representation and Reasoning: Semantic Web