New binary linear programming formulation to compute the graph edit distance
| Autor: | Julien Lerouge, Romain Raveaux, Sébastien Adam, Zeina Abu-Aisheh, Pierre Héroux |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), Equipe Apprentissage (DocApp - LITIS), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Informatique, Image et Interaction - EA 2118 (L3I), Université de La Rochelle (ULR), Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA) |
| Rok vydání: | 2017 |
| Předmět: |
Comparability graph
02 engineering and technology 01 natural sciences Upper and lower bounds law.invention Pattern Matching Pathwidth Artificial Intelligence law 0103 physical sciences Line graph 0202 electrical engineering electronic engineering information engineering Pattern matching 010306 general physics Integer programming Mathematics Integer Linear Programming Graph Matching [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV] 1-planar graph Graph Edit Distance [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV] Signal Processing 020201 artificial intelligence & image processing Computer Vision and Pattern Recognition Algorithm Software Graph product |
| Zdroj: | Pattern Recognition Pattern Recognition, Elsevier, 2017, 72, pp.254-265. ⟨10.1016/j.patcog.2017.07.029⟩ |
| ISSN: | 0031-3203 |
| DOI: | 10.1016/j.patcog.2017.07.029 |
| Popis: | International audience; Graph edit distance (GED) is a powerful and flexible graph matching paradigm that can be used to address different tasks in structural pattern recognition, machine learning, and data mining. In this paper, some new binary linear programming formulations for computing the exact GED between two graphs are proposed. A major strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs (i.e. with attributes on both vertices and edges). Moreover, a relaxation of the domain constraints in the formulations provides efficient lower bound approximations of the GED. A complete experimental study comparing the proposed formulations with 4 state-of-the-art algorithms for exact and approximate graph edit distances is provided. By considering both the quality of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominates the others in the Pareto sense. As a consequence, faced to a given real-world problem, a trade-off between quality and efficiency has to be chosen w.r.t. the application constraints. In this context, this paper provides a guide that can be used to choose the appropriate method. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect