Experimental Comparison of Graph Edit Distance Computation Methods
Gaoming Zhang, Sen Lin, Xianmin Wang, Teng Hsing Huang, Xuan Hu, Lingyun Zou · 2023
Graph edit distance (GED) is a fundamental graph similarity metric. GED computation is NP-hard [10], and exact GED computation is only feasible for small graphs. Therefore, many methods of approximate GED computation have been proposed in the literature. In this paper, we select the five representative GED approximation methods and compare their performance on two real-world datasets. We observe that non-heuristic algorithms such as LSa [1] are fast and accurate in computing true GED for small graphs, and heuristic algorithms such as GENN [4] are very effective in computing the estimated path cost. This effort helps us pinpoint suitable algorithms for different applications.