Computation of graph edit distance: Reasoning about optimality and speed-up

• Graph Edit Distance (GED) is the most used error-tolerant graph matching method.
• Bipartite graph matching algorithm (BP) is the most used algorithm to solve GED.
• 2 new versions of BP published that reduce the runtime but restrictions are imposed.
• We study how much extend these restrictions limits their applicability.
• Empirical validation shows new versions reduce runtime but keep recognition ratio.

Bipartite graph matching has been demonstrated to be one of the most efficient algorithms to solve error-tolerant graph matching. This algorithm is based on defining a cost matrix between the whole nodes of both graphs and solving the nodes' correspondence through a linear assignment method (for instance, Hungarian or Jonker–Volgenant methods). Recently, two versions of this algorithm have been published called Fast Bipartite and Square Fast Bipartite. They compute the same distance value than Bipartite but with a reduced runtime if some restrictions on the edit costs are considered. In this paper, we do not present a new algorithm but we compare the three versions of Bipartite algorithm and show how the violation of the theoretically imposed restrictions in Fast Bipartite and Square Fast Bipartite do not affect the algorithm's performance. That is, in practice, we show that these restrictions do not affect the optimality of the algorithm and so, the three algorithms obtain similar distances and recognition ratios in classification applications although the restrictions do not hold. Moreover, we conclude that the Square Fast Bipartite with the Jonker–Volgenant solver is the fastest algorithm.