An efficient algorithm for graph edit distance computation

摘要

The graph edit distance (GED) is a well-established distance measure widely used in many applications, such as bioinformatics, data mining, pattern recognition, and graph classification. However, existing solutions for computing the GED suffer from several drawbacks: large search spaces, excessive memory requirements, and many expensive backtracking calls. In this paper, we presentBSS_GED, a novel vertex-based mapping method that calculates the GED in a reduced search space created by identifying invalid and redundant mappings.BSS_GEDemploys the beam-stack search paradigm, a widely utilized search algorithm in AI, combined with two specially designed heuristics to improve the GED computation, achieving a trade-off between memory utilization and expensive backtracking calls. Through extensive experiments, we demonstrate thatBSS_GEDis highly efficient on both sparse and dense graphs and outperforms the state-of-the-art methods. Furthermore, we applyBSS_GEDto solve the well-investigated graph similarity search problem. The experimental results show that this method is dozens of times faster than state-of-the-art graph similarity search methods.