Skip to main content
SpringerLink
Log in

Transitive Assignment Kernels for Structural Classification

  • Conference paper
  • First Online:
Book cover Similarity-Based Pattern Recognition (SIMBAD 2015)

Part of the book series: Lecture Notes in Computer Science ((LNIP,volume 9370))

Included in the following conference series:

Abstract

Kernel methods provide a convenient way to apply a wide range of learning techniques to complex and structured data by shifting the representational problem from one of finding an embedding of the data to that of defining a positive semi-definite kernel. One problem with the most widely used kernels is that they neglect the locational information within the structures, resulting in less discrimination. Correspondence-based kernels, on the other hand, are in general more discriminating, at the cost of sacrificing positive-definiteness due to their inability to guarantee transitivity of the correspondences between multiple graphs. In this paper we adopt a general framework for the projection of (relaxed) correspondences onto the space of transitive correspondences, thus transforming any given matching algorithm onto a transitive multi-graph matching approach. The resulting transitive correspondences can then be used to provide a kernel that both maintains locational information and is guaranteed to be positive-definite. Experimental evaluation validates the effectiveness of the kernel for several structural classification tasks.

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 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight 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

References

  1. Siddiqi, K., Shokoufandeh, A., Dickinson, S., Zucker, S.: Shock graphs and shape matching. Int. J. Comput. Vis. 35, 13–32 (1999)

    Article  Google Scholar 

  2. Jeong, H., Tombor, B., Albert, R., Oltvai, Z., Barabási, A.: The large-scale organization of metabolic networks. Nature 407, 651–654 (2000)

    Article  Google Scholar 

  3. Ito, T., Chiba, T., Ozawa, R., Yoshida, M., Hattori, M., Sakaki, Y.: A comprehensive two-hybrid analysis to explore the yeast protein interactome. Proc. Natl. Acad. Sci. 98, 4569 (2001)

    Article  Google Scholar 

  4. Kalapala, V., Sanwalani, V., Moore, C.: The structure of the united states road network. Preprint, University of New Mexico (2003)

    Google Scholar 

  5. Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. IJPRAI 18, 265–298 (2004)

    Google Scholar 

  6. Luo, B., Wilson, R.C., Hancock, E.R.: Spectral embedding of graphs. Pattern Recogn. 36, 2213–2230 (2003)

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

  8. Gasparetto, A., Minello, G., Torsello, A.: A non-parametric spectral model for graph classification. In: Proceedings of the International Conference on Pattern Recognition Applications and Methods, pp. 312–319 (2015)

    Google Scholar 

  9. Torsello, A., Gasparetto, A., Rossi, L., Bai, L., Hancock, E.R.: Transitive state alignment for the quantum Jensen-Shannon kernel. In: Fränti, P., Brown, G., Loog, M., Escolano, F., Pelillo, M. (eds.) S+SSPR 2014. LNCS, vol. 8621, pp. 22–31. Springer, Heidelberg (2014)

    Google Scholar 

  10. Livi, L., Rizzi, A.: The graph matching problem. Pattern Anal. Appl. 16, 253–283 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  11. Scholkopf, B., Smola, A.J.: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge (2001)

    Google Scholar 

  12. Gärtner, T., Flach, P.A., Wrobel, S.: On graph kernels: hardness results and efficient alternatives. In: Schölkopf, B., Warmuth, M.K. (eds.) COLT/Kernel 2003. LNCS (LNAI), vol. 2777, pp. 129–143. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  13. Haussler, D.: Convolution kernels on discrete structures. Technical Report UCS-CRL-99-10, University of California at Santa Cruz, Santa Cruz, CA, USA (1999)

    Google Scholar 

  14. Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized kernels between labeled graphs. In: ICML, pp. 321–328 (2003)

    Google Scholar 

  15. Borgwardt, K.M., Kriegel, H.P.: Shortest-path kernels on graphs. In: Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM 2005), Washington, DC, USA, pp. 74–81. IEEE Computer Society (2005)

    Google Scholar 

  16. Shervashidze, N., Schweitzer, P., van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-lehman graph kernels. J. Mach. Learn. Res. 12, 2539–2561 (2011)

    MathSciNet  MATH  Google Scholar 

  17. Kriege, N., Mutzel, P.: Subgraph matching kernels for attributed graphs. In: ICML. icml.cc/Omnipress (2012)

    Google Scholar 

  18. Neumann, M., Patricia, N., Garnett, R., Kersting, K.: Efficient graph kernels by randomization. In: Flach, P.A., De Bie, T., Cristianini, N. (eds.) ECML PKDD 2012, Part I. LNCS, vol. 7523, pp. 378–393. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  19. Ong, C.S., Canu, S., Smola, A.J.: Learning with non-positive kernels. In: Proceedings of the 21st International Conference on Machine Learning (ICML), pp. 639–646 (2004)

    Google Scholar 

  20. Jain, B.J., Geibel, Wysotzki, F.: SVM learning with the SH inner product. In: 12th European Symposium on Artificial Neural Networks, Bruges, Belgium

    Google Scholar 

  21. Jain, B.J., Geibel, P., Wysotzki, F.: SVM learning with the Schur-Hadamard inner product for graphs. Neurocomputing 64, 93–105 (2005)

    Article  Google Scholar 

  22. Schietgat, L., Ramon, J., Bruynooghe, M., Blockeel, H.: An efficiently computable graph-based metric for the classification of small molecules. In: Boulicaut, J.-F., Berthold, M.R., Horváth, T. (eds.) DS 2008. LNCS (LNAI), vol. 5255, pp. 197–209. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  23. Mohr, J., Jain, B.J., Sutter, A., ter Laak, A., Steger-Hartmann, T., Heinrich, N., Obermayer, K.: A maximum common subgraph kernel method for predicting the chromosome aberration test. J. Chem. Inf. Model. 50, 1821–1838 (2010)

    Article  Google Scholar 

  24. Hochreiter, S., Obermayer, K.: Support vector machines for dyadic data. Neural Comput. 18, 1472–1510 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  25. Fröhlich, H., Wegner, J.K., Sieker, F., Zell, A.: Optimal assignment kernels for attributed molecular graphs. In: de Raedt, L., Wrobel, S. (eds.) Proceedings of the 22nd International Conference on Machine Learning (ICML 2005), pp. 225–232. ACM Press, Bonn (2005)

    Google Scholar 

  26. Neuhaus, M., Bunke, H.: Edit distance-based kernel functions for structural pattern classification. Pattern Recogn. 39, 1852–1863 (2006)

    Article  MATH  Google Scholar 

  27. Vert, J.P.: The optimal assignment kernel is not positive definite. CoRR abs/0801.4061 (2008)

    Google Scholar 

  28. Williams, M.L., Wilson, R.C., Hancock, E.R.: Multiple graph matching with bayesian inference. Pattern Recogn. Lett. 18, 080 (1997)

    Article  Google Scholar 

  29. Solé-Ribalta, A., Serratosa, F.: Models and algorithms for computing the common labelling of a set of attributed graphs. Comput. Vis. Image Underst. 115, 929–945 (2011)

    Article  Google Scholar 

  30. Gold, S., Rangarajan, A.: A graduated assignment algorithm for graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 18, 377–388 (1996)

    Article  Google Scholar 

  31. Yan, J., Tian, Y., Zha, H., Yang, X., Zhang, Y., Chu, S.M.: Joint optimization for consistent multiple graph matching. In: Proceedings of the 2013 IEEE International Conference on Computer Vision, ICCV 2013, Washington, DC, USA, pp. 1649–1656. IEEE Computer Society (2013)

    Google Scholar 

  32. Yan, J., Wang, J., Zha, H., Yang, X., Chu, S.: Consistency-driven alternating optimization for multigraph matching: a unified approach. IEEE Trans. Image Process. 24, 994–1009 (2015)

    Article  MathSciNet  Google Scholar 

  33. Pachauri, D., Kondor, R., Singh, V.: Solving the multi-way matching problem by permutation synchronization. In: Burges, C.J.C., Bottou, L., Ghahramani, Z., Weinberger, K.Q. (eds.) NIPS, pp. 1860–1868 (2013)

    Google Scholar 

  34. Torsello, A., Rodolà, E., Albarelli, A.: Multiview registration via graph diffusion of dual quaternions. In: The 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, Colorado Springs, CO, USA, 20–25 June 2011, pp. 2441–2448. IEEE Computer Society (2011)

    Google Scholar 

  35. Hartley, R.I., Trumpf, J., Dai, Y., Li, H.: Rotation averaging. Int. J. Comput. Vis. 103, 267–305 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  36. Sun, J., Ovsjanikov, M., Guibas, L.: A concise and provably informative multi-scale signature based on heat diffusion. In: Proceedings of the Symposium on Geometry Processing, SGP 2009, Aire-la-Ville, Switzerland, Switzerland, pp. 1383–1392. Eurographics Association (2009)

    Google Scholar 

  37. Shervashidze, N., Schweitzer, P., van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-Lehman graph kernels. J. Mach. Learn. Res. 12, 2539–2561 (2011)

    MathSciNet  MATH  Google Scholar 

  38. Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: Proceedings of the International Workshop on Artificial Intelligence and Statistics (2009)

    Google Scholar 

  39. Borgwardt, K.M., peter Kriegel, H.: Shortest-path kernels on graphs. In: Proceedings of the 2005 International Conference on Data Mining, pp. 74–81 (2005)

    Google Scholar 

  40. Leordeanu, M., Hebert, M.: A spectral technique for correspondence problems using pairwise constraints. In: Tenth IEEE International Conference on Computer Vision, 2005, ICCV 2005, vol. 2, pp. 1482–1489 (2005)

    Google Scholar 

  41. Cho, M., Lee, J., Lee, K.M.: Reweighted random walks for graph matching. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part V. LNCS, vol. 6315, pp. 492–505. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  42. Debnath, A.K., de Com-padre, R.L.L., Debnath, G., Schusterman, A.J., Hansch, C.: Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Med. Chem. 34, 786–797 (1991)

    Article  Google Scholar 

  43. Jensen, L.J., Kuhn, M., Stark, M., Chaffron, S., Creevey, C., Muller, J., Doerks, T., Julien, P., Roth, A., Simonovic, M., et al.: String 8a global view on proteins and their functional interactions in 630 organisms. Nucleic Acids Res. 37, D412–D416 (2009)

    Article  Google Scholar 

  44. Li, G., Semerci, M., Yener, B., Zaki, M.J.: Effective graph classification based on topological and label attributes. Stat. Anal. Data Min. 5, 265–283 (2012)

    Article  MathSciNet  Google Scholar 

  45. Nene, S.A., Nayar, S.K., Murase, H.: Columbia object image library (COIL-20). Technical report, Department of Computer Science, Columbia University, New York (1996)

    Google Scholar 

  46. Biasotti, S., Marini, S., Mortara, M., Patané, G., Spagnuolo, M., Falcidieno, B.: 3D shape matching through topological structures. In: Nyström, I., Sanniti di Baja, G., Svensson, S. (eds.) DGCI 2003. LNCS, vol. 2886, pp. 194–203. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  47. Schomburg, I., Chang, A., Ebeling, C., Gremse, M., Heldt, C., Huhn, G., Schomburg, D.: Brenda, the enzyme database: updates and major new developments. Nucleic Acids Res. 32, D431–D433 (2004)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Università Ca’ Foscari Venezia, Venice, Italy

    Michele Schiavinato, Andrea Gasparetto & Andrea Torsello

Authors
  1. Michele Schiavinato
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrea Gasparetto
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andrea Torsello
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michele Schiavinato .

Editor information

Editors and Affiliations

  1. University of Copenhagen, Copenhagen, Denmark

    Aasa Feragen

  2. DAIS, Università Ca' Foscari Venezia, Venezia Mestre, Italy

    Marcello Pelillo

  3. Delft University of Technology, Delft, Zuid-Holland, The Netherlands

    Marco Loog

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Schiavinato, M., Gasparetto, A., Torsello, A. (2015). Transitive Assignment Kernels for Structural Classification. In: Feragen, A., Pelillo, M., Loog, M. (eds) Similarity-Based Pattern Recognition. SIMBAD 2015. Lecture Notes in Computer Science(), vol 9370. Springer, Cham. https://doi.org/10.1007/978-3-319-24261-3_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-24261-3_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-24260-6

  • Online ISBN: 978-3-319-24261-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation