Improving bipartite graph edit distance approximation using various search strategies

作者：

Highlights：

• 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.

摘要

Highlights•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.

论文关键词：Bipartite graph matching,Approximate graph edit distance

论文评审过程：Received 22 July 2014, Revised 20 October 2014, Accepted 1 November 2014, Available online 10 November 2014.

论文官网地址：https://doi.org/10.1016/j.patcog.2014.11.002