Improving bipartite graph edit distance approximation using various search strategies

• We show how the well-known bipartite graph edit distance approximation can substantially be improved with respect to distance accuracy.
• To this end, we introduce and compare six different methodologies for extending the graph matching framework.
• We empirically verify a substantial gain of distance accuracy by means of all methods while run time remains remarkably low.
• The benefit of improved distance quality is also verified in a clustering application.

Recently the authors of the present paper introduced an approximation framework for the graph edit distance problem. The basic idea of this approximation is to first build a square cost matrix C=(cij)C=(cij), where each entry cij reflects the cost of a node substitution, deletion or insertion plus the matching cost arising from the local edge structure. Based on C an optimal assignment of the nodes and their local structure can be established in polynomial time. Since this approach considers local – rather than the global – structural properties of the graphs only, the graph edit distance derived from the optimal node assignment generally overestimates the true edit distance. The present paper pursues the idea of applying additional search strategies that build upon the initial assignment in order to reduce this overestimation. To this end, six different search strategies are investigated in this paper. In an exhaustive experimental evaluation on five real world graph data sets we empirically verify a substantial gain of distance accuracy by means of all search methods while run time remains remarkably low.