Skip to main content
Erschienen in: Pattern Analysis and Applications 3/2013

01.08.2013 | Survey

The graph matching problem

verfasst von: Lorenzo Livi, Antonello Rizzi

Erschienen in: Pattern Analysis and Applications | Ausgabe 3/2013

Einloggen

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

search-config
loading …

Abstract

In this paper, we propose a survey concerning the state of the art of the graph matching problem, conceived as the most important element in the definition of inductive inference engines in graph-based pattern recognition applications. We review both methodological and algorithmic results, focusing on inexact graph matching procedures. We consider different classes of graphs that are roughly differentiated considering the complexity of the defined labels for both vertices and edges. Emphasis will be given to the understanding of the underlying methodological aspects of each identified research branch. A selection of inexact graph matching algorithms is proposed and synthetically described, aiming at explaining some significant instances of each graph matching methodology mainly considered in the technical literature.

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!

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!

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!

Literatur
2.
Zurück zum Zitat Aizerman A, Braverman EM, Rozoner LI (1964) Theoretical foundations of the potential function method in pattern recognition learning. Automat Remote Control 25:821–837 Aizerman A, Braverman EM, Rozoner LI (1964) Theoretical foundations of the potential function method in pattern recognition learning. Automat Remote Control 25:821–837
3.
Zurück zum Zitat Ambauen R, Fischer S, Bunke H (2003) Graph edit distance with node splitting and merging, and its application to diatom identification. In: Proceedings of the 4th IAPR international conference on Graph based representations in pattern recognition, GbRPR’03. Springer-Verlag, Berlin, Heidelberg, pp 95–106. http://portal.acm.org/citation.cfm?id=1757868.1757880 Ambauen R, Fischer S, Bunke H (2003) Graph edit distance with node splitting and merging, and its application to diatom identification. In: Proceedings of the 4th IAPR international conference on Graph based representations in pattern recognition, GbRPR’03. Springer-Verlag, Berlin, Heidelberg, pp 95–106. http://​portal.​acm.​org/​citation.​cfm?​id=​1757868.​1757880
4.
Zurück zum Zitat Bardaji I, Ferrer M, Sanfeliu A (2010) A comparison between two representatives of a set of graphs: median vs barycenter graph. In: Proceedings of the 2010 joint IAPR international conference on structural, syntactic, and statistical pattern recognition, SSPR& SPR’10. Springer-Verlag, Berlin, Heidelberg, pp 149–158. http://portal.acm.org/citation.cfm?id=1887003.1887022 Bardaji I, Ferrer M, Sanfeliu A (2010) A comparison between two representatives of a set of graphs: median vs barycenter graph. In: Proceedings of the 2010 joint IAPR international conference on structural, syntactic, and statistical pattern recognition, SSPR& SPR’10. Springer-Verlag, Berlin, Heidelberg, pp 149–158. http://​portal.​acm.​org/​citation.​cfm?​id=​1887003.​1887022
13.
Zurück zum Zitat Borgelt C (2002) Mining molecular fragments: finding relevant substructures of molecules. In: Proceedings of 2002 IEEE international conference on data mining (ICDM). IEEE Press, pp 51–58 Borgelt C (2002) Mining molecular fragments: finding relevant substructures of molecules. In: Proceedings of 2002 IEEE international conference on data mining (ICDM). IEEE Press, pp 51–58
20.
Zurück zum Zitat Burges CJC (1998) A tutorial on support vector machines for pattern recognition. Data Min Knowl Disc 2:121–167CrossRef Burges CJC (1998) A tutorial on support vector machines for pattern recognition. Data Min Knowl Disc 2:121–167CrossRef
21.
Zurück zum Zitat Buriol LS, Castillo C, Donato D, Leonardi S, Millozzi S (2006) Temporal analysis of the wikigraph. In: Web intelligence conference. IEEE CS Press, pp 45–51 Buriol LS, Castillo C, Donato D, Leonardi S, Millozzi S (2006) Temporal analysis of the wikigraph. In: Web intelligence conference. IEEE CS Press, pp 45–51
22.
Zurück zum Zitat Cinti A, Rizzi A (2011) Neurofuzzy min–max networks implementation on FPGA. In: International joint conference on computational intalligence (IJCCI), neural computation theories and analysis (NCTA) Cinti A, Rizzi A (2011) Neurofuzzy min–max networks implementation on FPGA. In: International joint conference on computational intalligence (IJCCI), neural computation theories and analysis (NCTA)
23.
27.
Zurück zum Zitat Del Vescovo G, Livi L, Rizzi A, Frattale Mascioli FM (2011) Clustering structured data with the SPARE library. In: Proceeding of 2011 4th IEEE international conference on computer science and information technology, vol 9, pp 413–417 Del Vescovo G, Livi L, Rizzi A, Frattale Mascioli FM (2011) Clustering structured data with the SPARE library. In: Proceeding of 2011 4th IEEE international conference on computer science and information technology, vol 9, pp 413–417
30.
Zurück zum Zitat Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J R Stat Soc Ser B 39(1):1–38MathSciNetMATH Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J R Stat Soc Ser B 39(1):1–38MathSciNetMATH
33.
Zurück zum Zitat Dorfler F, Bullo F (2011) Kron reduction of graphs with applications to electrical networks. ArXiv e-prints Dorfler F, Bullo F (2011) Kron reduction of graphs with applications to electrical networks. ArXiv e-prints
34.
Zurück zum Zitat ElGhawalby H, Hancock ER (2008) Graph characteristic from the Gauss–Bonnet Theorem. In: Lobo NdV, Kasparis T, Roli F, Kwok JTY, Georgiopoulos M, Anagnostopoulos GC, Loog M (eds) SSPR/SPR, lecture notes in computer science, vol 5342. Springer, pp 207–216 ElGhawalby H, Hancock ER (2008) Graph characteristic from the Gauss–Bonnet Theorem. In: Lobo NdV, Kasparis T, Roli F, Kwok JTY, Georgiopoulos M, Anagnostopoulos GC, Loog M (eds) SSPR/SPR, lecture notes in computer science, vol 5342. Springer, pp 207–216
36.
Zurück zum Zitat Eshera MA, Fu KS (1984) A graph distance measure for image analysis. IEEE Trans Syst Man Cybern 14(3):398–408MATHCrossRef Eshera MA, Fu KS (1984) A graph distance measure for image analysis. IEEE Trans Syst Man Cybern 14(3):398–408MATHCrossRef
41.
42.
Zurück zum Zitat Garey MR, Johnson DS (1990) Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USA Garey MR, Johnson DS (1990) Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USA
44.
Zurück zum Zitat Gartner T, Flach P, Wrobel S (2003) On graph kernels: hardness results and efficient alternatives. Lecture notes in computer science, pp 129–143 Gartner T, Flach P, Wrobel S (2003) On graph kernels: hardness results and efficient alternatives. Lecture notes in computer science, pp 129–143
45.
Zurück zum Zitat Ghias A, Logan J, Chamberlin D, Smith BC (1995) Query by humming: musical information retrieval in an audio database. In: ACM Multimedia, pp 231–236 Ghias A, Logan J, Chamberlin D, Smith BC (1995) Query by humming: musical information retrieval in an audio database. In: ACM Multimedia, pp 231–236
53.
Zurück zum Zitat Haussler D (1999) Convolution kernels on discrete structures. Technical report Haussler D (1999) Convolution kernels on discrete structures. Technical report
63.
Zurück zum Zitat Kashima H, Tsuda K, Inokuchi A (2003) Marginalized kernels between labeled graphs. In: Proceedings of the twentieth international conference on machine learning. AAAI Press, pp 321–328 Kashima H, Tsuda K, Inokuchi A (2003) Marginalized kernels between labeled graphs. In: Proceedings of the twentieth international conference on machine learning. AAAI Press, pp 321–328
66.
Zurück zum Zitat Kondor RI, Lafferty J (2002) Diffusion kernels on graphs and other discrete structures. In: Proceedings of the ICML, pp 315–322 Kondor RI, Lafferty J (2002) Diffusion kernels on graphs and other discrete structures. In: Proceedings of the ICML, pp 315–322
70.
Zurück zum Zitat Kuramochi M, Karypis G (2002) An efficient algorithm for discovering frequent subgraphs. Technical report, IEEE Transactions on Knowledge and Data Engineering Kuramochi M, Karypis G (2002) An efficient algorithm for discovering frequent subgraphs. Technical report, IEEE Transactions on Knowledge and Data Engineering
72.
Zurück zum Zitat Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions, and reversals. Technical Report 8 Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions, and reversals. Technical Report 8
74.
Zurück zum Zitat Livi L, Del Vescovo G, Rizzi A (2012) Graph recognition by seriation and frequent substructures mining. In: Proceeding of the first international conference on pattern recognition applications and methods 1:186–191. doi:10.5220/0003733201860191 Livi L, Del Vescovo G, Rizzi A (2012) Graph recognition by seriation and frequent substructures mining. In: Proceeding of the first international conference on pattern recognition applications and methods 1:186–191. doi:10.​5220/​0003733201860191​
75.
Zurück zum Zitat Livi L, Del Vescovo G, Rizzi A (2012) Inexact graph matching through graph coverage. In: Proceeding of the first international conference on pattern recognition applications and methods 1:269–272. doi:10.5220/0003732802690272 Livi L, Del Vescovo G, Rizzi A (2012) Inexact graph matching through graph coverage. In: Proceeding of the first international conference on pattern recognition applications and methods 1:269–272. doi:10.​5220/​0003732802690272​
76.
Zurück zum Zitat Livi L, Rizzi A (2012) Parallel algorithms for tensor product-based inexact graph matching. In: Proceeding of the 2012 IEEE International Joint Conference on Neural Networks. IEEE, Brisbane, Australia, pp 2276–2283. doi:10.1109/IJCNN.2012.6252681. ISBN 978-1-4673-1489-3 Livi L, Rizzi A (2012) Parallel algorithms for tensor product-based inexact graph matching. In: Proceeding of the 2012 IEEE International Joint Conference on Neural Networks. IEEE, Brisbane, Australia, pp 2276–2283. doi:10.​1109/​IJCNN.​2012.​6252681. ISBN 978-1-4673-1489-3
77.
Zurück zum Zitat Luxburg UV, Bousquet O (2003) Distance-based classification with Lipschitz functions. J Mach Learn Res 5:669–695MathSciNet Luxburg UV, Bousquet O (2003) Distance-based classification with Lipschitz functions. J Mach Learn Res 5:669–695MathSciNet
78.
Zurück zum Zitat Mascioli FMF, Rizzi A, Panella M, Martinelli G (2000) Scale-based approach to hierarchical fuzzy clustering. Signal Process 80(6):1001–1016MATHCrossRef Mascioli FMF, Rizzi A, Panella M, Martinelli G (2000) Scale-based approach to hierarchical fuzzy clustering. Signal Process 80(6):1001–1016MATHCrossRef
80.
Zurück zum Zitat Mercer J (1909) Functions of positive and negative type, and their connection with the theory of integral equations. In: Philosophical transactions of the royal society of London. Series A, containing papers of a mathematical or physical character, vol 209, pp 415–446. http://www.jstor.org/stable/91043 Mercer J (1909) Functions of positive and negative type, and their connection with the theory of integral equations. In: Philosophical transactions of the royal society of London. Series A, containing papers of a mathematical or physical character, vol 209, pp 415–446. http://​www.​jstor.​org/​stable/​91043
83.
Zurück zum Zitat Neuhaus M, Bunke H (2004) A probabilistic approach to learning costs for graph edit distance. In: Proceedings of the 17th international conference on pattern recognition, pp 389–393 Neuhaus M, Bunke H (2004) A probabilistic approach to learning costs for graph edit distance. In: Proceedings of the 17th international conference on pattern recognition, pp 389–393
84.
Zurück zum Zitat Neuhaus M, Bunke H (2005) Self-organizing maps for learning the edit costs in graph matching. IEEE Trans Syst Man Cybern B 35:503–514CrossRef Neuhaus M, Bunke H (2005) Self-organizing maps for learning the edit costs in graph matching. IEEE Trans Syst Man Cybern B 35:503–514CrossRef
85.
Zurück zum Zitat Neuhaus M, Bunke H (2006) A convolution edit kernel for error-tolerant graph matching. In: ICPR (4). IEEE Computer Society, pp 220–223 Neuhaus M, Bunke H (2006) A convolution edit kernel for error-tolerant graph matching. In: ICPR (4). IEEE Computer Society, pp 220–223
90.
Zurück zum Zitat Neuhaus M, Riesen K, Bunke H (2006) Fast suboptimal algorithms for the computation of graph edit distance. In: Structural, syntactic, and statistical pattern recognition. LNCS. Springer, pp 163–172 Neuhaus M, Riesen K, Bunke H (2006) Fast suboptimal algorithms for the computation of graph edit distance. In: Structural, syntactic, and statistical pattern recognition. LNCS. Springer, pp 163–172
95.
Zurück zum Zitat Rao I, Sarma K (2010) On tensor product of standard graphs. Int J Comput Cognit 8(3):99 Rao I, Sarma K (2010) On tensor product of standard graphs. Int J Comput Cognit 8(3):99
96.
Zurück zum Zitat Ren P, Wilson RC, Hancock ER (2009) Characteristic polynomial analysis on matrix representations of graphs. In: Torsello A, Escolano F, Brun L (eds) GbRPR. Lecture notes in computer science, vol 5534. Springer, pp 243–252 Ren P, Wilson RC, Hancock ER (2009) Characteristic polynomial analysis on matrix representations of graphs. In: Torsello A, Escolano F, Brun L (eds) GbRPR. Lecture notes in computer science, vol 5534. Springer, pp 243–252
101.
Zurück zum Zitat Rizzi A, Del Vescovo G (2006) Automatic image classification by a granular computing approach. In: Machine learning for signal processing, 2006. Proceedings of the 2006 16th IEEE signal processing society workshop, pp 33–38. doi:10.1109/MLSP.2006.275517 Rizzi A, Del Vescovo G (2006) Automatic image classification by a granular computing approach. In: Machine learning for signal processing, 2006. Proceedings of the 2006 16th IEEE signal processing society workshop, pp 33–38. doi:10.​1109/​MLSP.​2006.​275517
102.
Zurück zum Zitat Rizzi A, Panella M, Frattale Mascioli FM (2002) Adaptive resolution min-max classifiers. IEEE Trans Neural Netw 13:402–414CrossRef Rizzi A, Panella M, Frattale Mascioli FM (2002) Adaptive resolution min-max classifiers. IEEE Trans Neural Netw 13:402–414CrossRef
105.
Zurück zum Zitat Robles-Kelly A, Hancock ER (2007) A Riemannian approach to graph embedding. Pattern Recognit 40(3):1042–1056MATHCrossRef Robles-Kelly A, Hancock ER (2007) A Riemannian approach to graph embedding. Pattern Recognit 40(3):1042–1056MATHCrossRef
106.
Zurück zum Zitat Sakoe H (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoust Speech Signal Process 26:43–49MATHCrossRef Sakoe H (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoust Speech Signal Process 26:43–49MATHCrossRef
109.
Zurück zum Zitat Sanfeliu A, Fu KS (1983) A distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybern 13(3):353–362MATHCrossRef Sanfeliu A, Fu KS (1983) A distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybern 13(3):353–362MATHCrossRef
114.
Zurück zum Zitat Smola AJ, Kondor RI (2003) Kernels and regularization on graphs. In: Scholkopf B, Warmuth MK (eds) Computational learning theory and kernel machines, 16th annual conference on computational learning theory and 7th Kernel workshop, COLT/Kernel 2003. Lecture notes in computer science, vol 2777. Springer, Washington, pp 144–158. ISBN 3-540-40720-0 Smola AJ, Kondor RI (2003) Kernels and regularization on graphs. In: Scholkopf B, Warmuth MK (eds) Computational learning theory and kernel machines, 16th annual conference on computational learning theory and 7th Kernel workshop, COLT/Kernel 2003. Lecture notes in computer science, vol 2777. Springer, Washington, pp 144–158. ISBN 3-540-40720-0
123.
Zurück zum Zitat Vishwanathan SVN, Borgwardt KM, Kondor RI, Schraudolph NN (2010) Graph kernels. J Mach Learn Res 11:1201–1242MathSciNetMATH Vishwanathan SVN, Borgwardt KM, Kondor RI, Schraudolph NN (2010) Graph kernels. J Mach Learn Res 11:1201–1242MathSciNetMATH
124.
Zurück zum Zitat Vishwanathan SVN, Smola AJ (2002) Fast kernels for string and tree matching. In: Neural information processing systems, pp 569–576 Vishwanathan SVN, Smola AJ (2002) Fast kernels for string and tree matching. In: Neural information processing systems, pp 569–576
126.
Zurück zum Zitat Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, Cambridge Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, Cambridge
127.
Zurück zum Zitat Watkins C (1999) Kernels from matching operations. Technical report, CSD-TR 98-07, University of London, Computer Science Department, Royal Holloway Watkins C (1999) Kernels from matching operations. Technical report, CSD-TR 98-07, University of London, Computer Science Department, Royal Holloway
Metadaten
Titel
The graph matching problem
verfasst von
Lorenzo Livi
Antonello Rizzi
Publikationsdatum
01.08.2013
Verlag
Springer London
Erschienen in
Pattern Analysis and Applications / Ausgabe 3/2013
Print ISSN: 1433-7541
Elektronische ISSN: 1433-755X
DOI
https://doi.org/10.1007/s10044-012-0284-8

Weitere Artikel der Ausgabe 3/2013

Pattern Analysis and Applications 3/2013 Zur Ausgabe