Estimating Graph Edit Distance Using Lower and Upper Bounds of Bipartite Approximations

Abstract

The concept of graph edit distance (GED) is still one of the most flexible and powerful graph matching approaches available. Yet, exact computation of GED can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, this approach considers local — rather than the global — structural properties of the graphs only, and thus GED derived from the optimal node assignment generally overestimates the true edit distance. Recently, it has been shown how the existing approximation framework can be exploited to additionally derive a lower bound of the exact edit distance without any additional computations. In this paper we make use of regression analysis in order to predict the exact GED using these two bounds. In an experimental evaluation on diverse graph data sets we empirically verify the gain of distance accuracy of the estimated GEDs compared to both bounds.