Graph edit distance: Restrictions to be a metric

作者：

Highlights：

• Always considered graph edit distance (GED) is a metric if edit functions are a metric.

• We discern between GED computed through edit path and graph bijection.

• Triangle inequality of edit functions not necessary if GED defined by graph bijection.

• Important: usually recognition ratio is maximized in non-metric edit functions.

摘要

•Always considered graph edit distance (GED) is a metric if edit functions are a metric.•We discern between GED computed through edit path and graph bijection.•Triangle inequality of edit functions not necessary if GED defined by graph bijection.•Important: usually recognition ratio is maximized in non-metric edit functions.

论文关键词：Graph edit distance,Distance definition,Sub-optimality

论文评审过程：Received 17 September 2018, Revised 18 December 2018, Accepted 26 January 2019, Available online 30 January 2019, Version of Record 20 February 2019.

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