Skip to Main content Skip to Navigation
Journal articles

Graph Edit Distance: Accuracy of Local Branching from an application point of view

Abstract : In the context of graph-based representations, comparing and measuring the dissimilarities between graphs can be done by solving the Graph Edit Distance (GED) problem. It is well known and embedded in many application fields such as Computer Vision and Cheminformat-ics. GED is a NP-hard minimization problem, therefore the optimal solution cannot be found in reasonable time. The GED problem has been addressed by exact approaches like Mixed Integer Linear Programs (MILP) formulations and heuristic approaches like beam-search, bi-partite graph matching among others. Recently, a novel heuristic, called local branching (LocBra) for the GED problem, has been proposed and shown to be efficient. In this work, the focus is on evaluating LocBra with other competitive heuristics available in the literature from an application point of view. Moreover, it tries to answer the following question: is it important to compute an accurate GED regarding the final applications? Similarity search and graph matching are considered as final applications. Three experiments are conducted to evaluate the accuracy and efficiency of the heuristics. The quality of the obtained solutions and matching w.r.t. optimal solutions and ground-truth matching is studied. The results of those experiments show that LocBra has a high correlation with the optimal solutions and the ground-truth matching.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Romain Raveaux Connect in order to contact the contributor
Submitted on : Wednesday, April 18, 2018 - 4:33:07 PM
Last modification on : Tuesday, January 11, 2022 - 5:56:22 PM


Files produced by the author(s)



Mostafa Darwiche, Donatello Conte, Romain Raveaux, Vincent t'Kindt. Graph Edit Distance: Accuracy of Local Branching from an application point of view. Pattern Recognition Letters, Elsevier, 2020, 134, pp.20 - 28. ⟨10.1016/j.patrec.2018.03.033⟩. ⟨hal-01761595⟩



Record views


Files downloads