Graph Edit Distance: Accuracy of Local Branching from an application point of view - Archive ouverte HAL Access content directly
Journal Articles Pattern Recognition Letters Year : 2020

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

(1) , (1) , (1) , (1)
1

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.
Fichier principal
Vignette du fichier
templateLIFAT.pdf (999.49 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01761595 , version 1 (18-04-2018)

Identifiers

Cite

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, 2020, 134, pp.20 - 28. ⟨10.1016/j.patrec.2018.03.033⟩. ⟨hal-01761595⟩
164 View
181 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More