A survey of graph edit distance

作者：Gao, Xinbo; Xiao, Bing; Tao, Dacheng; Li, Xuelong^*

来源：Pattern Analysis and Applications, 2010, 13(1): 113-129.

DOI：10.1007/s10044-008-0141-y

• Inexact graph matching
• Graph edit distance
• Attributed graph
• Non-attributed graph

Inexact graph matching has been one of the significant research foci in the area of pattern analysis. As an important way to measure the similarity between pairwise graphs error-tolerantly, graph edit distance (GED) is the base of inexact graph matching. The research advance of GED is surveyed in order to provide a review of the existing literatures and offer some insights into the studies of GED. Since graphs may be attributed or non-attributed and the definition of costs for edit operations is various, the existing GED algorithms are categorized according to these two factors and described in detail. After these algorithms are analyzed and their limitations are identified, several promising directions for further research are proposed.

• 出版日期2010-2
• 单位南阳理工学院; 西安电子科技大学