A Fast Hop-Biased Approximation Algorithm for the Quadratic Group Steiner Tree Problem

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.