Title: Efficient Graph Edit Distance Computation and Verification via Anchor-aware Lower Bound Estimation,
Abstract: Graph edit distance (GED) is an important similarity measure adopted in a
similarity-based analysis between two graphs, and computing GED is a primitive
operator in graph database analysis. Partially due to the NP-hardness, the
existing techniques for computing GED are only able to process very small
graphs with less than 30 vertices. Motivated by this, in this paper we
systematically study the problems of both GED computation, and GED verification
(i.e., verify whether the GED between two graphs is no larger than a user-given
threshold). Firstly, we develop a unified framework that can be instantiated
into either a best-first search approach AStar+ or a depth-first search
approach DFS+. Secondly, we design anchor-aware lower bound estimation
techniques to compute tighter lower bounds for intermediate search states,
which significantly reduce the search spaces of both AStar+ and DFS+. We also
propose efficient techniques to compute the lower bounds. Thirdly, based on our
unified framework, we contrast AStar+ with DFS+ regarding their time and space
complexities, and recommend that AStar+ is better than DFS+ by having a much
smaller search space. Extensive empirical studies validate that AStar+ performs
better than DFS+, and show that our AStar+-BMa approach outperforms the
state-of-the-art technique by more than four orders of magnitude.