Skip to main content
SpringerLink
Log in

Median Graph Computation by Means of Graph Embedding into Vector Spaces

  • Chapter
  • First Online:
Graph Embedding for Pattern Analysis

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    For clarity, in the remainder, we will refer to the projection of M into n-dimensional space as M n .

References

  1. Bajaj C (1988) The algebraic degree of geometric optimization problems. Discrete Comput Geom 3(2):177–191

    Article  MathSciNet  MATH  Google Scholar 

  2. Bunke H, Allerman G (1983) Inexact graph matching for structural pattern recognition. Pattern Recogn Lett 1(4):245–253

    Article  MATH  Google Scholar 

  3. Bunke H, Günter S (2001) Weighted mean of a pair of graphs. Computing 67(3):209–224

    Article  MathSciNet  MATH  Google Scholar 

  4. Caelli T, Kosinov S (2004) Inexact graph matching using eigen-subspace projection clustering. IJPRAI 18(3):329–354. DOI http://dx.doi.org/10.1142/S0218001404003186

    Google Scholar 

  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–298

    Article  Google Scholar 

  6. Cover TM, Thomas JA (1991) Elements of information theory. Wiley-Interscience, New York

    Book  MATH  Google Scholar 

  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–222

    Article  Google Scholar 

  8. Duda R, Hart P, Stork D (2000) Pattern classification, 2nd edn. Wiley Interscience, New York

    Google Scholar 

  9. Dunn J (1974) Well separated clusters and optimal fuzzy partitions. J Cibernet 4:95–104

    Article  MathSciNet  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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.

    Article  MATH  Google Scholar 

  14. Friedman M, Kandel A (1999) Introduction to pattern recognition. World Scientific, New York

    Google Scholar 

  15. Gibert J, Valveny E, Bunke H (2012) Graph embedding in vector spaces by node attribute statistics. Pattern Recogn 45(9):3072–3083. DOI 10.1016/j.patcog.2012.01.009. URL http://dx.doi.org/10.1016/j.patcog.2012.01.009

    Google Scholar 

  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

    Google Scholar 

  17. Hakimi SL (2000) Location theory. CRC, West Palm Beach

    Google Scholar 

  18. de la Higuera C, Casacuberta F (2000) Topology of strings: Median string is NP-complete. Theor Comput Sci 230(1–2):39–48

    Article  MATH  Google Scholar 

  19. Hlaoui A, Wang S (2006) Median graph computation for graph clustering. Soft Comput 10(1):47–53

    Article  Google Scholar 

  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

    Google Scholar 

  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–1151

    Article  Google Scholar 

  22. Jouili S, Tabbone S (2010) Graph embedding using constant shift embedding. In: Proceedings of the 20th international conference on recognizing patterns in signals, speech, images, and videos, ICPR’10. Springer, Berlin, pp 83–92. URL http://dl.acm.org/citation.cfm?id=1939170.1939183

  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–1214

    Article  Google Scholar 

  24. Kramer S, Raedt LD (2001) Feature construction with version spaces for biochemical applications. In: Proceedings of the eighteenth international conference on machine learning, ICML ’01. Morgan Kaufmann Publishers Inc., San Francisco, pp 258–265. URL http://dl.acm.org/citation.cfm?id=645530.655667

  25. Luo B, Wilson RC, Hancock ER (2003) Spectral embedding of graphs. Pattern Recogn 36(10):2213–2230

    Article  MATH  Google Scholar 

  26. Mitchell TM (1997) Machine learning. McGraw-Hill, New York

    MATH  Google Scholar 

  27. Münger A (1998) Synthesis of prototype graphs from sample graphs. Diploma thesis, University of Bern (in German)

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  30. Pekalska E, Duin R (2005) The dissimilarity representation for pattern recognition – foundations and applications. World Scientific, Singapore

    MATH  Google Scholar 

  31. Pekalska E, Duin RPW, Paclík P (2006) Prototype selection for dissimilarity-based classifiers. Pattern Recogn 39(2):189–208

    Article  MATH  Google Scholar 

  32. Rand WM (1971) Objective criteria for the evaluation of clustering methods. J Am Stat Assoc 66:846–850

    Article  Google Scholar 

  33. Ren P, Wilson RC, Hancock ER (2011) Graph characterization via ihara coefficients. IEEE Trans Neural Networks 22(2):233–245

    Article  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  36. Riesen K, Bunke H (2009) Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput 27(7):950–959

    Article  Google Scholar 

  37. Riesen K, Bunke H (2010) Graph classification and clustering based on vector space embedding. World Scientific, Singapore

    MATH  Google Scholar 

  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

    Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  41. Schenker A, Bunke H, Last M, Kandel A (2005) Graph-theoretic techniques for web content mining. World Scientific, Singapore

    MATH  Google Scholar 

  42. Shokoufandeh A, Macrini D, Dickinson S, Siddiqi K, Zucker SW (2005) Indexing hierarchical structures using graph spectra. IEEE Trans Pattern Anal Mach Intell 27(7):1125–1140. DOI 10.1109/TPAMI.2005.142. URL http://dx.doi.org/10.1109/TPAMI.2005.142

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  46. Wilson RC, Hancock ER, Luo B (2005) Pattern vectors from algebraic graph theory. IEEE Trans Pattern Anal Mach Intell 27(7):1112–1124

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DAMA-UPC, Universitat Politècnica de Catalunya - BarcelonaTech, Barcelona, Spain

    Miquel Ferrer

  2. Institut de Robòtica i Informàtica Industrial, CSIC-UPC, Universitat Politècnica de Catalunya - BarcelonaTech, Barcelona, Spain

    Itziar Bardají

  3. Centre de Visió per Computador, Universitat Autònoma de Barcelona, Bellaterra, Spain

    Ernest Valveny & Dimosthenis Karatzas

  4. NICTA, Vistoria Research Laboratory, The University of Melbourne, Parkville, Victoria, Australia

    Horst Bunke

Authors
  1. Miquel Ferrer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Itziar Bardají
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ernest Valveny
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dimosthenis Karatzas
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Horst Bunke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Miquel Ferrer .

Editor information

Editors and Affiliations

  1. , Dept. of ECE, College of Engineering, Northeastern University, 403 Dana Research Center, 360 Huntington Ave, Boston, 02115, Massachusetts, USA

    Yun Fu

  2. Honeywell, Douglas Drive North 1985, Golden Valley, 55422, USA

    Yunqian Ma

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer Science+Business Media New York

About this chapter

Cite this chapter

Ferrer, M., Bardají, I., Valveny, E., Karatzas, D., Bunke, H. (2013). Median Graph Computation by Means of Graph Embedding into Vector Spaces. In: Fu, Y., Ma, Y. (eds) Graph Embedding for Pattern Analysis. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-4457-2_3

Download citation

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

  • Published:

  • Publisher Name: Springer, New York, NY

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

  • Online ISBN: 978-1-4614-4457-2

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation