Skip to main content
SpringerLink
Log in

A Novel Graph Kernel Based on the Wasserstein Distance and Spectral Signatures

  • Conference paper
  • First Online:
Structural, Syntactic, and Statistical Pattern Recognition (S+SSPR 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13813))

  • 526 Accesses

Abstract

Spectral signatures have been used with great success in computer vision to characterise the local and global topology of 3D meshes. In this paper, we propose to use two widely used spectral signatures, the Heat Kernel Signature and the Wave Kernel Signature, to create node embeddings able to capture local and global structural information for a given graph. For each node, we concatenate its structural embedding with the one-hot encoding vector of the node feature (if available) and we define a kernel between two input graphs in terms of the Wasserstein distance between the respective node embeddings. Experiments on standard graph classification benchmarks show that our kernel performs favourably when compared to widely used alternative kernels as well as graph neural networks.

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

Notes

  1. 1.

    https://ysig.github.io/GraKeL/0.1a8/.

References

  1. Altschuler, J., Niles-Weed, J., Rigollet, P.: Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. In: Advances in Neural Information Processing Systems, vol. 30 (2017)

    Google Scholar 

  2. Atwood, J., Towsley, D.: Diffusion-convolutional neural networks. In: Advances in Neural Information Processing Systems, pp. 1993–2001 (2016)

    Google Scholar 

  3. Aubry, M., Schlickewei, U., Cremers, D.: The wave kernel signature: a quantum mechanical approach to shape analysis. In: 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 1626–1633. IEEE (2011)

    Google Scholar 

  4. Bai, L., Hancock, E.R.: Graph kernels from the Jensen-Shannon divergence. J. Math. Imaging Vis. 47(1), 60–69 (2013)

    Article  MATH  Google Scholar 

  5. Bai, L., Rossi, L., Torsello, A., Hancock, E.R.: A quantum Jensen-Shannon graph kernel for unattributed graphs. Pattern Recogn. 48(2), 344–355 (2015)

    Article  MATH  Google Scholar 

  6. Borgwardt, K.M., Kriegel, H.P.: Shortest-path kernels on graphs. In: Fifth IEEE International Conference on Data Mining (ICDM 2005), pp. 8-pp. IEEE (2005)

    Google Scholar 

  7. Borgwardt, K.M., Ong, C.S., Schönauer, S., Vishwanathan, S., Smola, A.J., Kriegel, H.P.: Protein function prediction via graph kernels. Bioinformatics 21(suppl_1), i47–i56 (2005)

    Google Scholar 

  8. Cosmo, L., Minello, G., Bronstein, M., Rodolà, E., Rossi, L., Torsello, A.: Graph kernel neural networks. arXiv preprint arXiv:2112.07436 (2021)

  9. Cosmo, L., Minello, G., Bronstein, M., Rodolà, E., Rossi, L., Torsello, A.: 3D shape analysis through a quantum lens: the average mixing kernel signature. Int. J. Comput. Vis. 1–20 (2022)

    Google Scholar 

  10. Cosmo, L., Minello, G., Bronstein, M., Rossi, L., Torsello, A.: The average mixing kernel signature. In: Vedaldi, A., Bischof, H., Brox, T., Frahm, J.-M. (eds.) ECCV 2020. LNCS, vol. 12365, pp. 1–17. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58565-5_1

    Chapter  Google Scholar 

  11. Debnath, A.K., Lopez de Compadre, R.L., Debnath, G., Shusterman, A.J., Hansch, C.: Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry 34(2), 786–797 (1991)

    Google Scholar 

  12. Errica, F., Podda, M., Bacciu, D., Micheli, A.: A fair comparison of graph neural networks for graph classification. arXiv preprint arXiv:1912.09893 (2019)

  13. Fröhlich, H., Wegner, J.K., Sieker, F., Zell, A.: Optimal assignment kernels for attributed molecular graphs. In: Proceedings of the 22nd International Conference on Machine Learning, pp. 225–232 (2005)

    Google Scholar 

  14. Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. In: International Conference on Machine Learning, pp. 1263–1272. PMLR (2017)

    Google Scholar 

  15. Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, vol. 30 (2017)

    Google Scholar 

  16. Haussler, D.: Convolution kernels on discrete structures. Technical report, Department of Computer Science, University of California (1999)

    Google Scholar 

  17. Helma, C., King, R.D., Kramer, S., Srinivasan, A.: The predictive toxicology challenge 2000–2001. Bioinformatics 17(1), 107–108 (2001)

    Article  Google Scholar 

  18. Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized kernels between labeled graphs. In: Proceedings of the 20th International Conference on Machine Learning (ICML 2003), pp. 321–328 (2003)

    Google Scholar 

  19. Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations, ICLR 2017 (2017)

    Google Scholar 

  20. Kriege, N.M., Johansson, F.D., Morris, C.: A survey on graph kernels. Appl. Netw. Sci. 5(1), 1–42 (2020)

    Article  Google Scholar 

  21. Lima, A., Rossi, L., Musolesi, M.: Coding together at scale: github as a collaborative social network. In: Eighth International AAAI Conference on Weblogs and Social Media (2014)

    Google Scholar 

  22. Morris, C., et al.: Weisfeiler and leman go neural: higher-order graph neural networks. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4602–4609 (2019)

    Google Scholar 

  23. Ong, C.S., Mary, X., Canu, S., Smola, A.J.: Learning with non-positive kernels. In: Proceedings of the Twenty-First International Conference on Machine Learning, p. 81 (2004)

    Google Scholar 

  24. Rossi, L., Torsello, A., Hancock, E.R.: Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence. Phys. Rev. E 91(2), 022815 (2015)

    Article  MathSciNet  Google Scholar 

  25. Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: The graph neural network model. IEEE Trans. Neural Networks 20(1), 61–80 (2008)

    Article  Google Scholar 

  26. Shervashidze, N., Schweitzer, P., Van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-Lehman graph kernels. J. Mach. Learn. Res. 12(9) (2011)

    Google Scholar 

  27. Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: Artificial Intelligence and Statistics, pp. 488–495. PMLR (2009)

    Google Scholar 

  28. Sun, J., Ovsjanikov, M., Guibas, L.: A concise and provably informative multi-scale signature based on heat diffusion. In: Computer Graphics Forum, vol. 28, pp. 1383–1392. Wiley Online Library (2009)

    Google Scholar 

  29. Togninalli, M., Ghisu, E., Llinares-López, F., Rieck, B., Borgwardt, K.: Wasserstein Weisfeiler-Lehman graph kernels. In: Advances in Neural Information Processing Systems, vol. 32 (2019)

    Google Scholar 

  30. Villani, C.: Optimal Transport: Old and New, vol. 338. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-71050-9

    Book  MATH  Google Scholar 

  31. Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018)

  32. Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., Leskovec, J.: Hierarchical graph representation learning with differentiable pooling. In: Advances in Neural Information Processing Systems, vol. 31 (2018)

    Google Scholar 

  33. Zhang, M., Cui, Z., Neumann, M., Chen, Y.: An end-to-end deep learning architecture for graph classification. In: Thirty-Second AAAI Conference on Artificial Intelligence (2018)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Beijing University of Posts and Telecommunications, Beijing, China

    Yantao Liu

  2. Queen Mary University of London, London, UK

    Yantao Liu & Luca Rossi

  3. Ca’ Foscari University of Venice, Venice, Italy

    Andrea Torsello

Authors
  1. Yantao Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luca Rossi
    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 Luca Rossi .

Editor information

Editors and Affiliations

  1. Concordia University, Montreal, QC, Canada

    Adam Krzyzak

  2. Concordia University, Montreal, QC, Canada

    Ching Y. Suen

  3. Ca Foscari University of Venice, Venezia, Italy

    Andrea Torsello

  4. Concordia University, Montreal, QC, Canada

    Nicola Nobile

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Liu, Y., Rossi, L., Torsello, A. (2022). A Novel Graph Kernel Based on the Wasserstein Distance and Spectral Signatures. In: Krzyzak, A., Suen, C.Y., Torsello, A., Nobile, N. (eds) Structural, Syntactic, and Statistical Pattern Recognition. S+SSPR 2022. Lecture Notes in Computer Science, vol 13813. Springer, Cham. https://doi.org/10.1007/978-3-031-23028-8_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-23028-8_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-23027-1

  • Online ISBN: 978-3-031-23028-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation