Top

Pattern Analysis and Applications

Published in:

01-08-2013 | Survey

The graph matching problem

Authors: Lorenzo Livi, Antonello Rizzi

Published in: Pattern Analysis and Applications | Issue 3/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

next article Real-time vision-based eye state detection for driver alertness monitoring

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Aggarwal C, Wang H (2010) Managing and mining graph data. Advances in Database Systems. Springer. http://books.google.com/books?id=Ox39uLyYh-wC

Aizerman A, Braverman EM, Rozoner LI (1964) Theoretical foundations of the potential function method in pattern recognition learning. Automat Remote Control 25:821–837

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

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

Bargiela A, Pedrycz W (2003) Granular computing: an introduction. No. v. 2002 in Kluwer international series in engineering and computer science. Kluwer Academic Publishers. http://books.google.com/books?id=F_3t7XTMhBkC

Berg C, Christensen J, Ressel P (1984) Harmonic analysis on semigroups: theory of positive definite and related functions. Graduate texts in mathematics. Springer-Verlag http://books.google.com/books?id=zz2DQgAACAAJ

Bernard M, Boyer L, Habrard A, Sebban M (2008)Learning probabilistic models of tree edit distance. Pattern Recognit. 41:2611–2629. doi:10.1016/j.patcog.2008.01.011. http://portal.acm.org/citation.cfm?id=1367147.1367314

Bernstein D (2009) Matrix mathematics: theory, facts, and formulas. Princeton University Press. http://books.google.com/books?id=jgEiuHlTCYcC

Bille P (2005) A survey on tree edit distance and related problems. Theor Comput Sci 337:217–239. doi:10.1016/j.tcs.2004.12.030. http://dx.doi.org/10.1016/j.tcs.2004.12.030

10.

Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D (2006) Complex networks: structure and dynamics. Phys. Rep. 424(4–5):175–308. doi:10.1016/j.physrep.2005.10.009. http://dx.doi.org/10.1016/j.physrep.2005.10.009

11.

Bollobás B (1998) Modern graph theory. Graduate texts in mathematics. Springer. http://books.google.ca/books?id=SbZKSZ-1qrwC

12.

Borg I, Groenen P (2005) Modern multidimensional scaling: theory and applications. Springer series in statistics. Springer. http://books.google.com/books?id=duTODldZzRcC

13.

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

14.

Borgwardt KM, Ong CS, Schönauer S, Vishwanathan SVN, Smola AJ, Kriegel HP (2005) Protein function prediction via graph kernels. Bioinformatics 21:47–56. http://dx.doi.org/10.1093/bioinformatics/bti1007

15.

Boser BE, Guyon IM, Vapnik VN (1992) A training algorithm for optimal margin classifiers. In: Proceedings of the fifth annual workshop on computational learning theory, COLT ’92. ACM, New York, NY, USA, pp 144–152. doi:10.1145/130385.130401. http://doi.acm.org/10.1145/130385.130401

16.

Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press. http://books.google.com/books?id=mYm0bLd3fcoC

17.

Bunke H, Allermann G (1983) Inexact graph matching for structural pattern recognition. Pattern Recognit Lett 1(4):245–253 (1983). doi:10.1016/0167-8655(83)90033-8. http://www.sciencedirect.com/science/article/B6V15-48MPV00-1K/2/6f816d072c71e50b1a80858a8b488463

18.

Bunke H, Bühler U (1993) Applications of approximate string matching to 2D shape recognition. Pattern Recognit 26(12):1797–1812. doi:10.1016/0031-3203(93)90177-X. http://www.sciencedirect.com/science/article/B6V14-48MPPK4-1V6/2/c7f7a4bd6aae48534f11137815852e32

19.

Bunke H, Shearer K (1998) A graph distance metric based on the maximal common subgraph. Pattern Recognit. Lett. 19:255–259. doi:10.1016/S0167-8655(97)00179-7.

20.

Burges CJC (1998) A tutorial on support vector machines for pattern recognition. Data Min Knowl Disc 2:121–167CrossRef

21.

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.

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.

Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching In pattern recognition. Int J Pattern Recognit Artif Intell 18:265–298. doi:10.1142/S0218001404003228

24.

Cook D, Holder L (2007) Mining graph data. Wiley-Interscience. http://books.google.com/books?id=jp8ZIpMVB54C

25.

Cortes C, Vapnik V (1995) Support-vector networks. Mach Learn 20:273–297. http://dx.doi.org/10.1023/A:1022627411411.10.1023/A:1022627411411

26.

Cox T, Cox M (2001) Multidimensional scaling. No. v. 1 in Monographs on statistics and applied probability. Chapman & Hall/CRC. http://books.google.com/books?id=SKZzmEZqvqkC

27.

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

28.

Del Vescovo G, Rizzi A (2007) Automatic classification of graphs by symbolic histograms. In: Proceedings of the 2007 IEEE international conference on granular computing, GRC ’07. IEEE Computer Society, pp 410–416. doi:10.1109/GRC.2007.46. http://dx.doi.org/10.1109/GRC.2007.46

29.

Del Vescovo G, Rizzi A (2007) Online handwriting recognition by the symbolic histograms approach. In: Proceedings of the 2007 IEEE international conference on granular computing, GRC ’07. IEEE Computer Society, Washington, DC, USA, p 686. doi:10.1109/GRC.2007.116. http://dx.doi.org/10.1109/GRC.2007.116

30.

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

31.

Diestel R (2006) Graph theory. Graduate texts in mathematics. Springer. http://books.google.com/books?id=aR2TMYQr2CMC

32.

Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1:269–271 http://dx.doi.org/10.1007/BF01386390.10.1007/BF01386390

33.

Dorfler F, Bullo F (2011) Kron reduction of graphs with applications to electrical networks. ArXiv e-prints

34.

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

35.

Emms, D., Wilson, R.C., Hancock, E. (2007) Graph embedding using quantum commute times. In: Proceedings of the 6th IAPR-TC-15 international conference on graph-based representations in pattern recognition, GbRPR’07. Springer-Verlag, Berlin, Heidelberg, pp 371–382. http://portal.acm.org/citation.cfm?id=1769371.1769412

36.

Eshera MA, Fu KS (1984) A graph distance measure for image analysis. IEEE Trans Syst Man Cybern 14(3):398–408MATHCrossRef

37.

Faloutsos C, Lin KI (1995) FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. SIGMOD Rec 24:163–174. doi:10.1145/568271.223812. http://doi.acm.org/10.1145/568271.223812

38.

Fankhauser S, Riesen K, Bunke H (2011) Speeding up graph edit distance computation through fast bipartite matching. In: Jiang X, Ferrer M, Torsello A (eds) Graph-based representations in pattern recognition. Lecture notes in computer science, vol 6658. Springer, Berlin, pp 102–111. http://dx.doi.org/10.1007/978-3-642-20844-7_11.10.1007/978-3-642-20844-7_11

39.

Fortune S, Wyllie J (1978) Parallelism in random access machines. In: Proceedings of the tenth annual ACM symposium on Theory of computing, STOC ’78. ACM, New York, NY, USA, pp 114–118. doi:10.1145/800133.804339. http://doi.acm.org/10.1145/800133.804339

40.

Gao X, Xiao B, Tao D, Li X (2008) Image categorization: graph edit direction histogram. Pattern Recognit 41(10):3179–3191. doi:10.1016/j.patcog.2008.03.025 http://www.sciencedirect.com/science/article/pii/S0031320308001246

41.

Gao X, Xiao B, Tao D, Li X (2010) A survey of graph edit distance. Pattern Anal Appl 13(1):113–129MathSciNetCrossRef

42.

Garey MR, Johnson DS (1990) Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, NY, USA

43.

Gärtner T (2008) Kernels for structured data. No v 72 in kernels for structured data. World Scientific. http://books.google.com/books?id=ykomKZ5rD1gC

44.

Gartner T, Flach P, Wrobel S (2003) On graph kernels: hardness results and efficient alternatives. Lecture notes in computer science, pp 129–143

45.

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

46.

Gibert J, Valveny E, Bunke H (2011) Dimensionality reduction for graph of words embedding. In: Jiang X, Ferrer M, Torsello A (eds) Graph-based representations in pattern recognition. Lecture notes in computer science, vol 6658. Springer Berlin, pp 22–31. http://dx.doi.org/10.1007/978-3-642-20844-7_3.10.1007/978-3-642-20844-7_3

47.

Giuliani A, Benigni R, Zbilut JP, Webber Jr CL, Sirabella P, Colosimo A (2002) Nonlinear signal analysis methods in the Elucidation of protein sequence—structure relationships. ChemInform 33(28). doi:10.1002/chin.200228300. http://dx.doi.org/10.1002/chin.200228300

48.

Goldfarb L (1984) A unified approach to pattern recognition. Pattern Recognit 17(5):575–582. doi:10.1016/0031-3203(84)90056-6. http://www.sciencedirect.com/science/article/B6V14-48MPJHK-J1/2/b156c1fd23bfed84bd0db8f8ec523c88

49.

Goldschlager LM (1982) A universal interconnection pattern for parallel computers. J ACM 29:1073–1086 doi:10.1145/322344.322353. http://doi.acm.org/10.1145/322344.322353

50.

Gori M, Maggini M, Sarti L (2004) Graph matching using random walks. In: Proceedings of the pattern recognition, 17th international conference on (ICPR’04) volume 3, vol 03, ICPR ’04. IEEE Computer Society, Washington, DC, USA , pp 394–397. doi:10.1109/ICPR.2004.422. http://dx.doi.org/10.1109/ICPR.2004.422

51.

Hagmann P, Cammoun L, Gigandet X, Meuli R, Honey CJ, Sporns O (2008) Mapping the structural core of human cerebral cortex. PLoS Biol 6(7):e159. doi:10.1371/journal.pbio.0060159. http://dx.doi.org/10.1371/journal.pbio.0060159

52.

Hart P, Nilsson N, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100–107. doi:10.1109/TSSC.1968.300136. http://dx.doi.org/10.1109/TSSC.1968.300136

53.

Haussler D (1999) Convolution kernels on discrete structures. Technical report

54.

Hell P, Nesšetřil J (2004) Graphs and homomorphisms. Oxford lecture series in mathematics and its applications. Oxford University Press. http://books.google.it/books?id=bJXWV-qK7kYC

55.

Hopcroft JE, Wong JK (1974) Linear time algorithm for isomorphism of planar graphs (Preliminary Report). In: Proceedings of the sixth annual ACM symposium on Theory of computing, STOC ’74. ACM, New York, NY, USA, pp 172–184. doi:10.1145/800119.803896. http://doi.acm.org/10.1145/800119.803896

56.

Imrich W, Klavžar S (2000) Product graphs, structure and recognition. Wiley-Interscience series in discrete mathematics and optimization. Wiley. http://books.google.com/books?id=EOnuAAAAMAAJ

57.

Izenman A (2008) Modern multivariate statistical techniques: regression, classification, and manifold learning. Springer texts in statistics. Springer. http://books.google.com/books?id=1CuznRORa3EC

58.

Jain B, Obermayer K (2011) Maximum likelihood for Gaussians on graphs. In: Jiang X, Ferrer M, Torsello A (eds) Graph-based representations in pattern recognition. Lecture notes in computer science, vol 6658. Springer, Berlin, pp 62–71. http://dx.doi.org/10.1007/978-3-642-20844-7_7.10.1007/978-3-642-20844-7_7

59.

Jain BJ, Obermayer K (2009) Structure spaces. J Mach Learn Res 10:2667–2714. http://portal.acm.org/citation.cfm?id=1577069.1755876

60.

Jain BJ, Wysotzki F (2004) Central clustering of attributed graphs. Mach Learn 56:169–207. doi:10.1023/B:MACH.0000033119.52532.ce. http://portal.acm.org/citation.cfm?id=1007760.1007768

61.

Jiang X, Müunger A, Bunke H (2001) On median graphs: properties, algorithms, and applications. IEEE Trans Pattern Anal Mach Intell 23:1144–1151. doi:10.1109/34.954604. http://dx.doi.org/10.1109/34.954604

62.

Jolliffe I (2002) Principal component analysis. Springer series in statistics. Springer. http://books.google.com/books?id=_olByCrhjwIC

63.

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

64.

Kazius J, McGuire R, Bursi R (2005) Derivation and validation of toxicophores for mutagenicity prediction. J Med Chem 48(1):312–320. doi:10.1021/jm040835a. http://pubs.acs.org/doi/abs/10.1021/jm040835a

65.

Kohonen T (2001) Self-organizing maps. Springer series in information sciences. Springer. http://books.google.com/books?id=e4igHzyf078C

66.

Kondor RI, Lafferty J (2002) Diffusion kernels on graphs and other discrete structures. In: Proceedings of the ICML, pp 315–322

67.

Kruskal J (1962) Nonmetric multidimensional scaling: a numerical method. Psychometrika 29(2):115–129. http://ideas.repec.org/a/spr/psycho/v29y1964i2p115-129.html

68.

Kruskal J, Wish M (1978) Multidimensional scaling. Quantitative applications in the social sciences. Sage Publications. http://books.google.com/books?id=ZzmIPcEXPf0C

69.

Kullback S, Leibler RA (1951) On information and sufficiency. Ann Math Stat 22(1):79–86MathSciNetMATHCrossRef

70.

Kuramochi M, Karypis G (2002) An efficient algorithm for discovering frequent subgraphs. Technical report, IEEE Transactions on Knowledge and Data Engineering

71.

Leslie C, Kuang R (2004) Fast string kernels using inexact matching for protein sequences. J Mach Learn Res 5: 1435–1455. http://dl.acm.org/citation.cfm?id=1005332.1044708

72.

Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions, and reversals. Technical Report 8

73.

Levi G (1973) A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo 9:341–352. http://dx.doi.org/10.1007/BF02575586.10.1007/BF02575586

74.

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.

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.

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.

Luxburg UV, Bousquet O (2003) Distance-based classification with Lipschitz functions. J Mach Learn Res 5:669–695MathSciNet

78.

Mascioli FMF, Rizzi A, Panella M, Martinelli G (2000) Scale-based approach to hierarchical fuzzy clustering. Signal Process 80(6):1001–1016MATHCrossRef

79.

Menchetti S, Costa F, Frasconi P (2005) Weighted decomposition kernels. In: Proceedings of the 22nd international conference on Machine learning, ICML ’05. ACM, New York, NY, USA, pp 585–592. doi:10.1145/1102351.1102425. http://doi.acm.org/10.1145/1102351.1102425

80.

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

81.

Munkres J (1957) Algorithms for the assignment and transportation problems. J Soc Ind Appl Math 5(1):32–38. http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJMAP000005000001000032000001&idtype=cvips&gifs=yes

82.

Munkres J (2000) Topology. Prentice Hall. http://books.google.com/books?id=XjoZAQAAIAAJ

83.

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.

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.

Neuhaus M, Bunke H (2006) A convolution edit kernel for error-tolerant graph matching. In: ICPR (4). IEEE Computer Society, pp 220–223

86.

Neuhaus M, Bunke H (2006) A random walk kernel derived from graph edit distance. In: Yeung DY, Kwok J, Fred A, Roli F, de Ridder D (eds) Structural, syntactic, and statistical pattern recognition. Lecture notes in computer science, vol 4109. Springer, Berlin, pp 191–199. http://dx.doi.org/10.1007/11815921_20.10.1007/11815921_20

87.

Neuhaus M, Bunke H (2007) A quadratic programming approach to the graph edit distance problem. In: Proceedings of the 6th IAPR-TC-15 international conference on Graph-based representations in pattern recognition, GbRPR’07. Springer-Verlag, Berlin, pp 92–102. http://portal.acm.org/citation.cfm?id=1769371.1769382

88.

Neuhaus M, Bunke H (2007) Automatic learning of cost functions for graph edit distance. Inf Sci 177(1):239–247MathSciNetMATHCrossRef

89.

Neuhaus M, Bunke H (2007) Bridging the gap between graph edit distance and kernel machines. Series in machine perception and artificial intelligence. World Scientific. http://books.google.com/books?id=xM_5hvL1AlkC

90.

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

91.

Nocedal J, Wright S (2006) Numerical optimization. Springer series in operations research. Springer. http://books.google.com/books?id=eNlPAAAAMAAJ

92.

Pekalska E, Duin R (2005) The dissimilarity representation for pattern recognition: foundations and applications. Series in machine perception and artificial intelligence. World Scientific. http://books.google.com/books?id=YPPr6eypHFwC

93.

Peris G (2002) Fast cyclic edit distance computation with weighted edit costs in classification. In: Proceedings of the 16th international conference on pattern recognition (ICPR’02) volume 4, vol 4. ICPR ’02. IEEE Computer Society, Washington, DC, USA, pp 40,184. http://portal.acm.org/citation.cfm?id=846227.848570

94.

Qiu H, Hancock ER (2006) Graph matching and clustering using spectral partitions. Pattern Recognit 39:22–34. doi:10.1016/j.patcog.2005.06.014.. http://portal.acm.org/citation.cfm?id=1220964.1221155

95.

Rao I, Sarma K (2010) On tensor product of standard graphs. Int J Comput Cognit 8(3):99

96.

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

97.

Riesen K, Bunke H (2008) IAM graph database repository for graph based pattern recognition and machine learning. In: Proceedings of the 2008 joint IAPR international workshop on structural, syntactic, and statistical pattern recognition, SSPR & SPR ’08. Springer-Verlag, Berlin, pp 287–297. doi:10.1007/978-3-540-89689-0_33.. http://dx.doi.org/10.1007/978-3-540-89689-0_33

98.

Riesen K, Bunke H (2009) Approximate graph edit distance computation by means of bipartite graph matching. Image Vis Comput 27:950–959. doi:10.1016/j.imavis.2008.04.004. http://portal.acm.org/citation.cfm?id=1534927.1534959

99.

Riesen K, Bunke H (2009) Reducing the dimensionality of dissimilarity space embedding graph kernels. Eng Appl Artif Intell 22:48–56. doi:10.1016/j.engappai.2008.04.006.. http://portal.acm.org/citation.cfm?id=1497654.1498530

100.

Riesen K, Bunke H (2010) Graph classification and clustering based on vector space embedding. Series in Machine Perception and Artificial Intelligence. World Scientific Pub Co Inc. http://books.google.com/books?id=hKr9QwAACAAJ

101.

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.

Rizzi A, Panella M, Frattale Mascioli FM (2002) Adaptive resolution min-max classifiers. IEEE Trans Neural Netw 13:402–414CrossRef

103.

Robles-Kelly A, Hancock E (2009) String edit distance, random walks and graph matching. In: Caelli T, Amin A, Duin RPW, Ridder D, Kamel M (eds) Structural, syntactic, and statistical pattern recognition. Lecture notes in computer science 2396, chap 10. Springer, Berlin, Berlin, pp. 107–129. doi:10.1007/3-540-70659-3_10.. http://dx.doi.org/10.1007/3-540-70659-3_10

104.

Robles-Kelly A, Hancock ER (2005) Graph edit distance from spectral seriation. IEEE Trans Pattern Anal Mach Intell 27:365–378. doi:10.1109/TPAMI.2005.56. http://dx.doi.org/10.1109/TPAMI.2005.56

105.

Robles-Kelly A, Hancock ER (2007) A Riemannian approach to graph embedding. Pattern Recognit 40(3):1042–1056MATHCrossRef

106.

Sakoe H (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoust Speech Signal Process 26:43–49MATHCrossRef

107.

Sammon JW (1969) A nonlinear mapping for data structure analysis. IEEE Trans Comput 18:401–409. doi:10.1109/T-C.1969.222678. http://dx.doi.org/10.1109/T-C.1969.222678

108.

Sampathkumar E (1975) On tensor product graphs. J Aust Math Soc Ser A 20(03):268–273MathSciNetMATHCrossRef

109.

Sanfeliu A, Fu KS (1983) A distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybern 13(3):353–362MATHCrossRef

110.

Schenker A, Bunke H, Last M, Kandel A (2005) Graph-theoretic techniques for web content mining 62. World Scientific Pub. http://books.google.com/books?hl=en&lr=&id=hNJozkPJAEwC&oi=fnd&pg=PP1&dq=Graph-Theoretic+Techniques+for+Web+Content+Mining&ots=PPVMc-VCA1&sig=d6Fok33vLb-WBFstYIpr7ijn4jM

111.

Schölkopf B, Smola A (2002) Learning with kernels: support vector machines, regularization, optimization, and beyond. Adapt Comput Mach Learn. MIT Press. http://books.google.com/books?id=y8ORL3DWt4sC

112.

Schölkopf B, Tsuda K, Vert J (2004) Kernel methods in computational biology. Comput Mol Biol. MIT Press. http://books.google.it/books?id=SwAooknaMXgC

113.

Shawe-Taylor J, Cristianini N (2004) Kernel methods for pattern analysis. Cambridge University Press. http://books.google.com/books?id=9i0vg12lti4C

114.

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

115.

Tang J, Zhang C, Luo B (2006) A new approach to graph seriation. In: Proceedings of the first international conference on innovative computing, information and control, vol 3, ICICIC ’06. IEEE Computer Society, Washington, DC, USA, pp 625–628. doi:10.1109/ICICIC.2006.385. http://dx.doi.org/10.1109/ICICIC.2006.385

116.

Teo CH, Vishwanathan SVN (2006) Fast and space efficient string kernels using suffix arrays. In: Proceedings of the 23rd international conference on Machine learning, ICML 2006. ACM, New York, NY, USA , pp 929–936. doi:10.1145/1143844.1143961.. http://doi.acm.org/10.1145/1143844.1143961

117.

Theodoridis S, Koutroumbas K (2006) Pattern recognition. Elsevier, Academic Press. http://books.google.com/books?id=gAGRCmp8Sp8C

118.

Thomas LT, Valluri SR, Karlapalem K (2006) Margin: maximal frequent subgraph mining. In: Proceedings of the sixth international conference on data mining, ICDM’06. IEEE Computer Society, Washington, pp 1097–1101. doi:10.1109/ICDM.2006.102. http://dx.doi.org/10.1109/ICDM.2006.102. ISBN 0-7695-2701-9

119.

Torsello A, Hancock ER (2007) Graph embedding using tree edit-union. Pattern Recognit 40:1393–1405 doi:10.1016/j.patcog.2006.09.006. http://portal.acm.org/citation.cfm?id=1224549.1224568

120.

Torsello A, Robles-Kelly A, Hancock ER (2007) Discovering shape classes using tree edit-distance and pairwise clustering. Int J Comput Vis 72:259–285. doi:10.1007/s11263-006-8929-y.. http://portal.acm.org/citation.cfm?id=1210315.1210321

121.

Tun K, Dhar P, Palumbo M, Giuliani A (2006) Metabolic pathways variability and sequence/networks comparisons. BMC Bioinf 7(1):24. doi:10.1186/1471-2105-7-24. http://www.biomedcentral.com/1471-2105/7/24

122.

Valiant LG (1990) A bridging model for parallel computation. Commun. ACM 33:103–111. doi:10.1145/79173.79181. http://doi.acm.org/10.1145/79173.79181

123.

Vishwanathan SVN, Borgwardt KM, Kondor RI, Schraudolph NN (2010) Graph kernels. J Mach Learn Res 11:1201–1242MathSciNetMATH

124.

Vishwanathan SVN, Smola AJ (2002) Fast kernels for string and tree matching. In: Neural information processing systems, pp 569–576

125.

Washio T, Motoda H (2003) State of the art of graph-based data mining. SIGKDD Explor. Newsl 5:59–68. doi:10.1145/959242.959249. http://doi.acm.org/10.1145/959242.959249

126.

Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, Cambridge

127.

Watkins C (1999) Kernels from matching operations. Technical report, CSD-TR 98-07, University of London, Computer Science Department, Royal Holloway

128.

Weaver N (1999) Lipschitz algebras. World Scientific. http://books.google.com/books?id=45rnwyVjg_QC

129.

Xiao B, Gao X, Tao D, Li X (2008) HMM-based graph edit distance for image indexing. Int J Imaging Syst Technol 18(2–3):209–218. doi:10.1002/ima.20146.. http://dx.doi.org/10.1002/ima.20146

130.

Yan X, Han J (2002) gSpan: graph-based substructure pattern mining. In: Proceedings of the 2002 IEEE international conference on data mining, ICDM ’02. IEEE Computer Society, Washington, pp. 721–724. http://dl.acm.org/citation.cfm?id=844380.844811. ISBN 0-7695-1754-4

131.

Yan X, Han J (2003) CloseGraph: mining closed frequent graph patterns. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’03. ACM, New York, NY, USA, pp 286–295. doi:10.1145/956750.956784. http://doi.acm.org/10.1145/956750.956784

132.

Yu H, Hancock ER (2006) String kernels for matching seriated graphs. In: Proceedings of the 18th international conference on pattern recognition, vol 04, ICPR ’06. IEEE Computer Society, Washington, DC, USA, pp 224–228. doi:10.1109/ICPR.2006.1081. http://dx.doi.org/10.1109/ICPR.2006.1081

133.

Zadeh LA (1965) Fuzzy sets. Inf Control 8(3):338–353. doi:10.1016/S0019-9958(65)90241-X. http://dx.doi.org/10.1016/S0019-9958(65)90241-X

134.

Zinman GE, Zhong S, Bar-Joseph Z (2011) Biological interaction networks are conserved at the module level. BMC Syst Biol 5(1):134+. doi:10.1186/1752-0509-5-134.. http://dx.doi.org/10.1186/1752-0509-5-134

Title: The graph matching problem
Authors: Lorenzo Livi
Antonello Rizzi
Publication date: 01-08-2013
Publisher: Springer London
Published in: Pattern Analysis and Applications / Issue 3/2013
Print ISSN: 1433-7541
Electronic ISSN: 1433-755X
DOI: https://doi.org/10.1007/s10044-012-0284-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2013

Classification using distances from samples to linear manifolds

Advanced leaf image retrieval via Multidimensional Embedding Sequence Similarity (MESS) method

Automatic classification of seam pucker images based on ordinal quality grades

Real-time vision-based eye state detection for driver alertness monitoring

Detection of artificial and scene text in images and video frames

On the smoothing of multinomial estimates using Liouville mixture models and applications

Premium Partner