| Abstract [eng] |
This paper present an experimental study of graph edit distance (GED) heuristic algorithms with the goal of improving the performance and accuracy of state of the art heuristics. First half of this paper defines GED and provides detailed explanation of three heuristic algorithm classes for computing GED. In the second half, experimental study and analysis of its results is given. The main focus of this paper is the algorithm IPFP [BDB+18] which is based on local search and produces tightest upper bounds for GED to this date [BBG+20]. In order to improve performance of IPFP as well as improve tightness of produced upper bounds, a good initial solution for the local search must be used. Initial GED solution can be relatively quickly computed using heuristic algorithms based on linear sum assignment problem with error correction (LSAPE‑GED). This paper shows that the task of choosing an algorithm for finding the initial GED solution isn’t trivial. Graph vertex and edge count are not the only factors influencing GED algorithms, graph structure has an effect as well. This paper provides three modified LSAPE‑GED algorithms that showed good results in GED computation: Star‑5, Branch‑Const‑2 and Branch‑Const‑4. Experimental study showed, that in case where a fast GED algorithm is needed one should consider Branch‑ Const‑4. If tighter upper bounds of GED are needed, local search algorithm IPFP should be used for which initial GED solution should be computed using one of LSAPE‑GED heuristics. For small and sparse graphs, algorithms Refine(BP) or Refine(Branch‑Fast) should be used, for medium sized graphs algorithm Star‑5 should be used, for large or very dense graphs, algorithms BP, Branch‑Fast and Branch‑Const‑2 work the best. |
