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 various heuristics, e.g., pruning and ranking strategies.

The Web Conference is announcing latest news and developments biweekly or on a monthly basis. We respect The General Data Protection Regulation 2016/679.