nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Graph Edit Distance in the Exact Context

verfasst von : Mostafa Darwiche, Romain Raveaux, Donatello Conte, Vincent T’Kindt

Erschienen in: Structural, Syntactic, and Statistical Pattern Recognition

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents a new Mixed Integer Linear Program (MILP) formulation for the Graph Edit Distance (GED) problem. The contribution is an exact method that solves the GED problem for attributed graphs. It has an advantage over the best existing one when dealing with the case of dense of graphs, because all its constraints are independent from the number of edges in the graphs. The experiments have shown the efficiency of the new formulation in the exact context.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Ring Based Approximation of Graph Edit Distance

Nächstes Kapitel The VF3-Light Subgraph Isomorphism Algorithm: When Doing Less Is More Effective

Abu-Aisheh, Z., Raveaux, R., Ramel, J.: A graph database repository and performance evaluation metrics for graph edit distance. In: Proceedings of Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15, pp. 138–147 (2015)

Abu-Aisheh, Z., Raveaux, R., Ramel, J.Y., Martineau, P.: An exact graph edit distance algorithm for solving pattern recognition problems. In: 4th International Conference on Pattern Recognition Applications and Methods 2015 (2015)

Bougleux, S., Brun, L., Carletti, V., Foggia, P., Gaüzère, B., Vento, M.: Graph edit distance as a quadratic assignment problem. Pattern Recogn. Lett. 87, 38–46 (2017)CrossRef

Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern Recogn. Lett. 18(8), 689–694 (1997)CrossRef

Darwiche, M., Conte, D., Raveaux, R., T’Kindt, V.: A local branching heuristic for solving a graph edit distance problem. Comput. Oper. Res. (2018). https://doi.org/10.1016/j.cor.2018.02.002. ISSN 0305-0548

Ferrer, M., Serratosa, F., Riesen, K.: Improving bipartite graph matching by assessing the assignment confidence. Pattern Recogn. Lett. 65, 29–36 (2015)CrossRef

Justice, D., Hero, A.: A binary linear programming formulation of the graph edit distance. IEEE Trans. Pattern Anal. Mach. Intell. 28(8), 1200–1214 (2006)CrossRef

Lerouge, J., Abu-Aisheh, Z., Raveaux, R., Héroux, P., Adam, S.: New binary linear programming formulation to compute the graph edit distance. Pattern Recogn. 72, 254–265 (2017). https://doi.org/10.1016/j.patcog.2017.07.029CrossRef

Moreno-García, C.F., Cortés, X., Serratosa, F.: A graph repository for learning error-tolerant graph matching. In: Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F., Wilson, R. (eds.) S+SSPR 2016. LNCS, vol. 10029, pp. 519–529. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49055-7_46CrossRef

10.

Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)MathSciNetCrossRef

11.

Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput.-Aided Mol. Des. 16(7), 521–533 (2002)CrossRef

12.

Riesen, K., Neuhaus, M., Bunke, H.: Bipartite graph matching for computing the edit distance of graphs. In: Escolano, F., Vento, M. (eds.) GbRPR 2007. LNCS, vol. 4538, pp. 1–12. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72903-7_1CrossRefMATH

13.

Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. SMC 13(3), 353–362 (1983). https://doi.org/10.1109/TSMC.1983.6313167CrossRefMATH

14.

Serratosa, F.: Computation of graph edit distance: reasoning about optimality and speed-up. Image Vis. Comput. 40, 38–48 (2015)CrossRef

15.

Zhang, Z., Shi, Q., McAuley, J.J., Wei, W., Zhang, Y., Van Den Hengel, A.: Pairwise matching through max-weight bipartite belief propagation. In: CVPR, vol. 5, p. 7 (2016)

Titel: Graph Edit Distance in the Exact Context
verfasst von: Mostafa Darwiche
Romain Raveaux
Donatello Conte
Vincent T’Kindt
Verlag: Springer International Publishing
Buch: Structural, Syntactic, and Statistical Pattern Recognition
Print ISBN: 978-3-319-97784-3

Electronic ISBN: 978-3-319-97785-0

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-97785-0_29

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"