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 metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-espci.archives-ouvertes.fr/hal-01761595
Contributor : Romain Raveaux <>
Submitted on : Wednesday, April 18, 2018 - 4:33:07 PM
Last modification on : Tuesday, November 19, 2019 - 4:46:13 PM

File

templateLIFAT.pdf
Files produced by the author(s)

Identifiers

Citation

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, inPress, ⟨10.1016/j.patrec.2018.03.033⟩. ⟨hal-01761595⟩

Share

Metrics

Record views

219

Files downloads

229