Generating Compact and Relaxable Answers to Keyword Queries over Knowledge Graphs
Lists
Only you see this
Abstract
Keyword search has been a prominent approach to querying knowledge graphs. For exploratory search tasks, existing methods commonly extract subgraphs that are group Steiner trees (GSTs) as answers. However, a GST that connects all the query keywords may not exist, or may inevitably have a large and unfocused graph structure in contrast to users’ favor to a compact answer. Therefore, in this paper, we aim at generating compact but relaxable subgraphs as answers, i.e., we require a computed subgraph to have a bounded diameter but allow it to only connect an incomplete subset of query keywords. We formulate it as a new combinatorial optimization problem of computing a minimally relaxed answer with a compactness guarantee, and we present a novel best-first search algorithm. Extensive experiments showed that our approach efficiently computed compact answers of high completeness.
BibTeX
@inproceedings{cheng2020generating,
author = {Gong Cheng and Shuxin Li and Ke Zhang and Chengkai Li},
title = {{Generating Compact and Relaxable Answers to Keyword Queries over Knowledge Graphs}},
booktitle = {ISWC},
year = {2020},
doi = {10.1007/978-3-030-62419-4\_7},
}Loading related content...