Accelerating Graph Similarity Search via Efficient GED Computation

Computing the graph edit distance (GED) between graphs is the core operation in graph similarity search. Recent studies suggest that the existing index structures are ineffective in reducing the overall processing time of graph similarity search, and that directly verifying the GED between the query graph and every data graph in the database is still the best option. The state-of-the-art algorithm for GED verification is the recently proposed AStar-LSa. However, AStar-LSa may consume an extremely large amount of main memory or even run out-of-memory, when the graphs become larger and/or the GED threshold becomes larger. In this paper, we aim to improve the efficiency of GED verification and simultaneously lower the main memory consumption. To achieve that, we propose a new estimation for the lower bounds of partial mappings between graphs. We formally prove that our new lower bound is tighter than the one used in AStar-LSa. Moreover, we also propose efficient algorithms to compute the lower bounds, as well as optimization techniques to improve the efficiency. Empirical studies on real datasets demonstrate that our newly proposed algorithm AStar-BMao runs faster, and at the same time consumes much less main memory, than AStar-LSa.

Automated summary

Computing the graph edit distance (GED) is important in graph similarity search. The existing index structures are ineffective in reducing processing time, so verifying GED directly is still the best option. However, the AStar-LSa algorithm may consume a lot of memory, but we propose a new estimation and efficient algorithms to improve efficiency.