Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2015 | OriginalPaper | Buchkapitel

Greedy Graph Edit Distance

verfasst von : Kaspar Riesen, Miquel Ferrer, Rolf Dornberger, Horst Bunke

Erschienen in: Machine Learning and Data Mining in Pattern Recognition

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In pattern recognition and data mining applications, where the underlying data is characterized by complex structural relationships, graphs are often used as a formalism for object representation. Yet, the high representational power and flexibility of graphs is accompanied by a significant increase of the complexity of many algorithms. For instance, exact computation of pairwise graph dissimilarity, i.e. distance, can be accomplished in exponential time complexity only. A previously introduced approximation framework reduces the problem of graph comparison to an instance of a linear sum assignment problem which allows graph dissimilarity computation in cubic time. The present paper introduces an extension of this approximation framework that runs in quadratic time. We empirically confirm the scalability of our extension with respect to the run time, and moreover show that the quadratic approximation leads to graph dissimilarities which are sufficiently accurate for graph based pattern classification.

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
Nächstes Kapitel Learning Heuristics to Reduce the Overestimation of Bipartite Graph Edit Distance Approximation
Fußnoten
1
Note that QAPs are known to be \(\mathcal {NP}\) -complete, and therefore, an exact and efficient algorithm for the graph edit distance problem can not be developed unless \(\mathcal {P} = \mathcal {NP}\).
 
2
In [24] it is formally proven that this approximation scheme builds an upper bound of the exact graph edit distance.
 
3
The assignment problem can also be formulated as finding a matching in a complete bipartite graph and is therefore also referred to as bipartite graph matching problem.
 
Literatur
1.
Perner, P. (ed.): MLDM 2012. LNCS, vol. 7376. Springer, Heidelberg (2012) MATH
2.
Perner, P. (ed.): MLDM 2013. LNCS, vol. 7988. Springer, Heidelberg (2013) MATH
3.
Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification, 2nd edn. Wiley-Interscience, New York (2000)
4.
Bishop, C.: Pattern Recognition and Machine Learning. Springer, New York (2008)
5.
Shawe-Taylor, J., Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge (2004)CrossRef
6.
Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recogn. Artif. Intell. 18(3), 265–298 (2004)CrossRef
7.
8.
Cook, D., Holder, L. (eds.): Mining Graph Data. Wiley-Interscience, New York (2007)MATH
9.
Schenker, A., Bunke, H., Last, M., Kandel, A.: Graph-Theoretic Techniques for Web Content Mining. World Scientific Publishing, Singapore (2005)MATH
10.
Gärtner, T.: Kernels for Structured Data. World Scientific Publishng, Singapore (2008)MATH
11.
Gärtner, T., Horvath, T., Wrobel, S.: Graph kernels. In: Smmut, C., Webb, G.I. (eds.) Encyclopedia of Machine Learning, pp. 467–469. Springer US, London (2010)
12.
Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern Recogn. Lett. 1, 245–253 (1983)MATHCrossRef
13.
Sanfeliu, A., Fu, K.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. (Part B) 13(3), 353–363 (1983)MATHCrossRef
14.
Cortés, X., Serratosa, F., Solé, A.: Active graph matching based on pairwise probabilities between nodes. In: Gimelfarb, G., Hancock, E., Imiya, A., Kuijper, A., Kudo, M. (eds.) SSPR 2012. LNCS, vol. 7626, pp. 98–106. Springer, Heidelberg (2012)CrossRef
15.
Boeres, M., Ribeiro, C., Bloch, I.: A randomized heuristic for scene recognition by graph matching. In: Ribeiro, C., Martins, S. (eds.) WEA 2004. LNCS, vol. 3059, pp. 100–113. Springer, Heidelberg (2004)CrossRef
16.
Sorlin, S., Solnon, C.: Reactive tabu search for measuring graph similarity. In: Brun, L., Vento, M. (eds.) GbRPR 2005. LNCS, vol. 3434, pp. 172–182. Springer, Heidelberg (2005)CrossRef
17.
Neuhaus, M., Bunke, H.: An error-tolerant approximate matching algorithm for attributed planar graphs and its application to fingerprint classification. In: Fred, A., Caelli, T.M., Duin, R.P.W., Campilho, A.C. (eds.) SSPR 2004. LNCS, vol. 3138, pp. 180–189. Springer, Heidelberg (2004)CrossRef
18.
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
19.
Dickinson, P., Bunke, H., Dadej, A., Kraetzl, M.: On graphs with unique node labels. In: Hancock, E., Vento, M. (eds.) GbRPR 2003. LNCS, vol. 2726, pp. 13–23. Springer, Heidelberg (2003)CrossRef
20.
Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput. 27(4), 950–959 (2009)CrossRef
21.
Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Society for Industrial and Applied Mathematics, Philadelphia (2009)MATHCrossRef
22.
Caetano, T.S., McAuley, J.J., Cheng, L., Le, Q.V., Smola, A.J.: Learning graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 31(6), 1048–1058 (2009)CrossRef
23.
Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef
24.
Riesen, K., Fischer, A., Bunke, H.: Computing upper and lower bounds of graph edit distance in cubic time. Accepted for publication in Proceedings of the IAPR TC3 International Workshop on Artificial Neural Networks in Pattern Recognition
25.
26.
Kuhn, H.: The hungarian method for the assignment problem. Naval Res. Logistic Q. 2, 83–97 (1955)CrossRef
27.
Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325–340 (1987)MATHMathSciNetCrossRef
28.
29.
Bertsekas, D.: The auction algorithm: a distributed relaxation method for the assignment problem. Ann. Oper. Res. 14, 105–123 (1988)MATHMathSciNetCrossRef
30.
Hung, M.: A polynomial simplex method for the assignment problem. Oper. Res. 28, 969–982 (1983)CrossRef
31.
32.
33.
34.
35.
Achatz, H., Kleinschmidt, P., Paparrizos, K.: A dual forest algorithm for the assignment problem. Appl. Geom. Discret. Math. AMS 4, 1–11 (1991)MathSciNet
36.
Burkard, R., Ceia, E.: Linear assignment problems and extensions. Technical report 127, Karl-Franzens-Universität Graz und Technische Universität Graz (1998)
37.
38.
39.
Riesen, K., Bunke, H.: Graph classification based on vector space embedding. Int. J. Pattern Recogn. Artif. Intell. 23(6), 1053–1081 (2008)MathSciNetCrossRef
40.
Neuhaus, M., Bunke, H.: Bridging the Gap Between Graph Edit Distance and Kernel Machines. World Scientific Publishing, Singapore (2007)MATH
41.
Riesen, K., Bunke, H.: IAM graph database repository for graph based pattern recognition and machine learning. In: da Vitoria Lobo, N., et al. (eds.) Structural, Syntactic, and Statistical Pattern Recognition. LNCS, vol. 5342, pp. 287–297. Springer, Heidelberg (2008)CrossRef
42.
Dosch, P., Valveny, E.: Report on the second symbol recognition contest. In: Wenyin, L., Lladós, J. (eds.) GREC 2005. LNCS, vol. 3926, pp. 381–397. Springer, Heidelberg (2005)CrossRef
Metadaten
Titel
Greedy Graph Edit Distance
verfasst von
Kaspar Riesen
Miquel Ferrer
Rolf Dornberger
Horst Bunke
Copyright-Jahr
2015
Buch
Machine Learning and Data Mining in Pattern Recognition

Print ISBN: 978-3-319-21023-0

Electronic ISBN: 978-3-319-21024-7

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-21024-7_1