Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Multilevel Analysis of Attributed Graphs for Explicit Graph Embedding in Vector Spaces Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Median Graph Computation by Means of Graph Embedding into Vector Spaces

Authors : Miquel Ferrer, Itziar Bardají, Ernest Valveny, Dimosthenis Karatzas, Horst Bunke

Published in: Graph Embedding for Pattern Analysis

Publisher: Springer New York

Log in

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

search-config
loading …

Abstract

In pattern recognition [8, 14], a key issue to be addressed when designing a system is how to represent input patterns. Feature vectors is a common option. That is, a set of numerical features describing relevant properties of the pattern are computed and arranged in a vector form. The main advantages of this kind of representation are computational simplicity and a well sound mathematical foundation. Thus, a large number of operations are available to work with vectors and a large repository of algorithms for pattern analysis and classification exist. However, the simple structure of feature vectors might not be the best option for complex patterns where nonnumerical features or relations between different parts of the pattern become relevant.

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
previous chapter Feature Grouping and Selection Over an Undirected Graph
next chapter Patch Alignment for Graph Embedding
Footnotes
1
For clarity, in the remainder, we will refer to the projection of M into n-dimensional space as M n .
 
Literature
1.
2.
Bunke H, Allerman G (1983) Inexact graph matching for structural pattern recognition. Pattern Recogn Lett 1(4):245–253MATHCrossRef
3.
4.
5.
Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching in pattern recognition. Int J Pattern Recogn Artif Intell 18(3):265–298CrossRef
6.
7.
Demirci MF, Shokoufandeh A, Keselman Y, Bretzner L, Dickinson SJ (2006) Object recognition as many-to-many feature matching. Int J Comput Vision 69(2):203–222CrossRef
8.
Duda R, Hart P, Stork D (2000) Pattern classification, 2nd edn. Wiley Interscience, New York
9.
10.
Ferrer M (2008) Theory and algorithms on the median graph. Application to graph-based classification and clustering. PhD Thesis, Universitat Autònoma de Barcelona
11.
Ferrer M, Serratosa F, Sanfeliu A (2005) Synthesis of median spectral graph. 2nd Iberian Conference on Pattern Recognition and Image Analysis. Estoril, Portugal. Lecture Notes in Computer Science, Springer-Verlag, vol 3523, pp 139–146
12.
Ferrer M, Valveny E, Serratosa F, Bardají I, Bunke H (2009a) Graph-based -means clustering: A comparison of the set median versus the generalized median graph. In: Jiang X, Petkov N (eds) CAIP. Lecture notes in computer science, vol 5702. Springer, Berlin, pp 342–350
13.
Ferrer M, Valveny E, Serratosa F, Riesen K, Bunke H (2010) Generalized median graph computation by means of graph embedding in vector spaces. Pattern Recognition 43(4): pp. 1642–1655.MATHCrossRef
14.
Friedman M, Kandel A (1999) Introduction to pattern recognition. World Scientific, New York
15.
16.
Grauman K, Darrell T (2004) Fast contour matching using approximate earth mover’s distance. In: Proceedings of the IEEE conference on Computer Vision and Pattern Recognition Washington, DC, pp 220–227
17.
Hakimi SL (2000) Location theory. CRC, West Palm Beach
18.
de la Higuera C, Casacuberta F (2000) Topology of strings: Median string is NP-complete. Theor Comput Sci 230(1–2):39–48MATHCrossRef
19.
Hlaoui A, Wang S (2006) Median graph computation for graph clustering. Soft Comput 10(1):47–53CrossRef
20.
Indyk P (2001) Algorithmic applications of low-distortion geometric embeddings. FOCS ’01 Proceedings of the 42nd IEEE symposium on Foundations of Computer Science. IEEE Computer Society Washington, DC, USA, pp 10–33
21.
Jiang X, Münger A, Bunke H (2001) On median graphs: Properties, algorithms, and applications. IEEE Trans Pattern Anal Mach Intell 23(10):1144–1151CrossRef
22.
23.
Justice D, Hero AO (2006) A binary linear programming formulation of the graph edit distance. IEEE Trans Pattern Anal Mach Intell 28(8):1200–1214CrossRef
24.
25.
Luo B, Wilson RC, Hancock ER (2003) Spectral embedding of graphs. Pattern Recogn 36(10):2213–2230MATHCrossRef
26.
27.
Münger A (1998) Synthesis of prototype graphs from sample graphs. Diploma thesis, University of Bern (in German)
28.
Neuhaus M, Bunke H (2004) An error-tolerant approximate matching algorithm for attributed planar graphs and its application to fingerprint classification. In: Fred ALN, Caelli T, Duin RPW, Campilho AC, de Ridder D (eds) SSPR/SPR. Lecture notes in computer science, vol 3138. Springer, Berlin, pp 180–189
29.
Neuhaus M, Riesen K, Bunke H (2006) Fast suboptimal algorithms for the computation of graph edit distance. In Proc. Joint IAPR Workshops on Structural and Syntactic Pattern Recognition and Statistical Techniques in Pattern Recognition. Lecture Notes on Computer Science, Springer-Verlag, Vol 4109, pp 163–172
30.
Pekalska E, Duin R (2005) The dissimilarity representation for pattern recognition – foundations and applications. World Scientific, SingaporeMATH
31.
Pekalska E, Duin RPW, Paclík P (2006) Prototype selection for dissimilarity-based classifiers. Pattern Recogn 39(2):189–208MATHCrossRef
32.
Rand WM (1971) Objective criteria for the evaluation of clustering methods. J Am Stat Assoc 66:846–850CrossRef
33.
Ren P, Wilson RC, Hancock ER (2011) Graph characterization via ihara coefficients. IEEE Trans Neural Networks 22(2):233–245CrossRef
34.
Riesen K, Bunke H (2008a) IAM graph database repository for graph based pattern recognition and machine learning. In N. da Vitoria Lobo et al., (eds) SSPR&SPR. Lecture Notes in Computer Science, Springer-Verlag, vol 5342, pp 287–297
35.
Riesen K, Bunke H (2008b) Kernel k-means clustering applied to vector space embeddings of graphs. In: Prevost L, Marinai S, Schwenker F (eds) ANNPR. Lecture notes in computer science, vol 5064. Springer, Berlin, pp 24–35
36.
Riesen K, Bunke H (2009) Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput 27(7):950–959CrossRef
37.
Riesen K, Bunke H (2010) Graph classification and clustering based on vector space embedding. World Scientific, SingaporeMATH
38.
Riesen K, Neuhaus M, Bunke H (2007) Graph embedding in vector spaces by means of prototype selection. In: 6th IAPR-TC-15 international workshop, GbRPR 2007. Lecture notes in computer science, vol 4538. Springer, Berlin, pp 383–393
39.
Robles-Kelly A, Hancock ER (2007) A Riemannian approach to graph embedding. Pattern Recogn 40(3):1042–1056MATHCrossRef
40.
Sanfeliu A, Fu K (1983) A distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybernet 13(3):353–362MATHCrossRef
41.
Schenker A, Bunke H, Last M, Kandel A (2005) Graph-theoretic techniques for web content mining. World Scientific, SingaporeMATH
42.
43.
Strehl A, Ghosh J, Mooney R (2000) Impact of similarity measures on web-page clustering. In: Proceedings of the 17th national conference on artificial intelligence: workshop of artificial intelligence for web search, (AAAI 2000), Austin, Texas, 30–31 July 2000, pp 58–64
44.
Weiszfeld E (1937) Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Math J (43):355–386
45.
White D, Wilson RC (2006) Mixing spectral representations of graphs. In: 18th international conference on pattern recognition (ICPR 2006). IEEE Computer Society, Hong Kong, China, 20–24 August 2006, pp 140–144
46.
Wilson RC, Hancock ER, Luo B (2005) Pattern vectors from algebraic graph theory. IEEE Trans Pattern Anal Mach Intell 27(7):1112–1124CrossRef
Metadata
Title
Median Graph Computation by Means of Graph Embedding into Vector Spaces
Authors
Miquel Ferrer
Itziar Bardají
Ernest Valveny
Dimosthenis Karatzas
Horst Bunke
Copyright Year
2013
Publisher
Springer New York
Book
Graph Embedding for Pattern Analysis

Print ISBN: 978-1-4614-4456-5

Electronic ISBN: 978-1-4614-4457-2

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4614-4457-2_3