New binary linear programming formulation to compute the graph edit distance

PATTERN RECOGNITION

卷:72

Article

Lerouge, Julien¹  Abu-Aisheh, Zeina²  Raveaux, Romain²  Heroux, Pierre¹  Adam, Sebastien¹ 

[1] Normandie Univ, UNIROUEN, UNIHAVRE, INSA Rouen,LITIS, F-76000 Rouen, France

[2] Univ Francois Rabelais Tours, LI, F-37200 Tours, France

关键词: Graph edit distance;    Integer linear programming;    Graph matching;    Pattern matching;   

DOI  :  10.1016/j.patcog.2017.07.029

来源: Elsevier

【 摘 要 】

In this paper, a new binary linear programming formulation for computing the exact Graph Edit Distance (GED) between two graphs is proposed. A fundamental strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs. Moreover, a continuous relaxation of the domain constraints in the formulation provides an efficient lower bound approximation of the GED. A complete experimental study that compares the proposed formulations with six state-of-the-art algorithms is provided. By considering both the accuracy of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominate the others in the Pareto sense. In general, our formulation converges faster to optimality while being able to scale up to match the largest graphs in our experiments. The relaxed formulation leads to an accurate approach that is 12% more accurate than the best approximate method of our benchmark. (C) 2017 Elsevier Ltd. All rights reserved.

【 授权许可】

Free