Graph Edit Distance Testing through Synthetic Graphs Generation
Pep Santacruz, Francesc Serratosa · 2018
Error-tolerant graph matching has been demonstrated to be an NP-problem, for this reason, several suboptimal algorithms have been presented with the aim of making the runtime acceptable in some applications. These algorithms have been tested with relative small graphs due to the computation of the true distance for comparison purposes is too costly. We present a method to generate graphs together with an upper and lower bound distance with linear computational cost. Through this method, we can test the behaviour of the known or new sub-optimal error-tolerant graph matching algorithms against a lower and an upper bound graph edit distance on large graphs, even though we do not have the true distance. The computational cost to generate a pair of graphs together with their upper and lower bounds is linear with regard to the number of nodes. The practical experimentation shows that the runtime to generate a pair of graphs is negligible with regard to the runtime to match them.