New binary linear programming formulation to compute the graph edit distance
作者：
Highlights：
• A binary linear programming formulation for computing the exact graph edit distance is proposed.
• A lower bound is derived from the formulation through a continuous relaxation.
• Comparison with 6 exact and approximate state-of-the-art algorithms is achieved.
• Generally speaking, our formulations were the most precise ones.
• Our formulation converged faster to optimality under a time constraint.
摘要
•A binary linear programming formulation for computing the exact graph edit distance is proposed.•A lower bound is derived from the formulation through a continuous relaxation.•Comparison with 6 exact and approximate state-of-the-art algorithms is achieved.•Generally speaking, our formulations were the most precise ones.•Our formulation converged faster to optimality under a time constraint.
论文关键词：Graph edit distance,Integer linear programming,Graph matching,Pattern matching
论文评审过程：Received 25 September 2016, Revised 29 May 2017, Accepted 27 July 2017, Available online 1 August 2017, Version of Record 2 August 2017.
论文官网地址：https://doi.org/10.1016/j.patcog.2017.07.029
