Efficient Computation of Semantically Cohesive Subgraphs for Keyword-Based Knowledge Graph Exploration

Yuxuan Shi, Gong Cheng, Trung-Kien Tran, Evgeny Kharlamov, Yulin Shen

Abstract

A knowledge graph (KG) represents a set of entities and their relations. To explore the content of a large and complex KG, a convenient way is keyword-based querying. Traditional methods assign small weights to salient entities or relations, and answer an exploratory keyword query by computing a group Steiner tree (GST), which is a minimum-weight subgraph that connects all the keywords in the query. Recent studies have suggested improving the semantic cohesiveness of a query answer by minimizing the pairwise semantic distances between the entities in a subgraph, but it remains unclear how to efficiently compute such a semantically cohesive subgraph. In this paper, we formulate it as a quadratic group Steiner tree problem (QGSTP) by extending the classical minimum-weight GST problem which is NP-hard. We design two approximation algorithms for QGSTP and prove their approximation ratios. Furthermore, to improve their practical performance, we present heuristics including pruning and ranking strategies.
BibTeX
@inproceedings{shi2021efficient,
  author = {Yuxuan Shi and Gong Cheng and Trung-Kien Tran and Evgeny Kharlamov and Yulin Shen},
  title = {{Efficient Computation of Semantically Cohesive Subgraphs for Keyword-Based Knowledge Graph Exploration}},
  booktitle = {The Web Conference},
  year = {2021},
  doi = {10.1145/3442381.3449900},
}

Loading related content...

Figure