Graph similarity search is to retrieve data graphs that are similar to a given query graph. It has become an essential operation in many application areas. In this paper, we investigate the problem of graph similarity search with edit distance constraints. Existing solutions adopt the filter-and-verify strategy to speed up the search, where lower and upper bounds of graph edit distance are employed as pruning and validation rules in this process. The main problem with existing lower bounds is that they show different performance on different data graphs. An interesting group of lower bounds is the global counting ones. These bounds come almost for free and can be injected with any filtering methodology to work as preliminary filters. In this paper, we present an improvement upon these bounds without adding any computation overhead. We show that the new bound is tighter than the previous global ones except for few cases where they identically evaluate. Via experiments, we show how the new bound, when incorporated into previous lower bounding methods, increases the performance significantly. |
