This is the authors' abstract. We don't add key points for this paper.
Knowledge Graph (KG) exploration helps Web users understand the contents of a large and unfamiliar KG and extract relevant insights. The task has recently been formulated as a Quadratic Group Steiner Tree Problem (QGSTP) to search for a semantically cohesive subgraph connecting entities that match query keywords. However, on large graphs, existing algorithms for this NP-hard problem cannot meet the performance need. In this paper, we propose a novel approximation algorithm for QGSTP called HB. It finds and merges an optimal set of paths according to a Hop-Biased objective function, which not only leads to a guaranteed approximation ratio but is also decomposable by paths to enable efficient dynamic programming based search. Accompanied by a set of pruning heuristics, HB outperformed the state of the art by 1-2 orders of magnitude, empirically reducing the average time for answering a query on a million-scale graph from about one minute to one second.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Wang et al. (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: