Skip to main content
SpringerLink
Log in

Classifying Me Softly: A Novel Graph Neural Network Based on Features Soft-Alignment

  • 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))

Abstract

Graph neural networks are increasingly becoming the framework of choice for graph-based machine learning. In this paper we propose a new graph neural network architecture based on the soft-alignment of the graph node features against sets of learned points. In each layer of the network the input node features are transformed by computing their similarity with respect to a set of learned features. The similarity information is then propagated to other nodes in the network, effectively creating a message passing-like mechanism where each node of the graph individually learns what is the optimal message to pass to its neighbours. We perform an ablation study to evaluate the performance of the network under different choices of its hyper-parameters. Finally, we test our model on standard graph-classification benchmarks and we find that it outperforms widely used alternative approaches, including both graph kernels and 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

References

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

    Google Scholar 

  2. Bai, L., Cui, L., Jiao, Y., Rossi, L., Hancock, E.: Learning backtrackless aligned-spatial graph convolutional networks for graph classification. IEEE Trans. Pattern Anal. Mach. Intell. 44, 783–798 (2020)

    Google Scholar 

  3. 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 

  4. 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 

  5. 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 

  6. 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 

  7. Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst.Ttechnol. 2(3), 1–27 (2011)

    Article  Google Scholar 

  8. Cosmo, L., Kazi, A., Ahmadi, S.-A., Navab, N., Bronstein, M.: Latent-graph learning for disease prediction. In: Martel, A., et al. (eds.) MICCAI 2020. LNCS, vol. 12262, pp. 643–653. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59713-9_62

    Chapter  Google Scholar 

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

  10. 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. 130, 1–20 (2022)

    Google Scholar 

  11. 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 

  12. Di, X., Yu, P., Bu, R., Sun, M.: Mutual information maximization in graph neural networks. In: 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1–7. IEEE (2020)

    Google Scholar 

  13. Dwivedi, V.P., Joshi, C.K., Laurent, T., Bengio, Y., Bresson, X.: Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 (2020)

  14. Eliasof, M., Haber, E., Treister, E.: PDE-GCN: novel architectures for graph neural networks motivated by partial differential equations. In: 34th Proceedings of the Conference on Advances in Neural Information Processing Systems (2021)

    Google Scholar 

  15. Errica, F., Podda, M., Bacciu, D., Micheli, A.: A fair comparison of graph neural networks for graph classification. In: Proceedings of the 8th International Conference on Learning Representations (ICLR) (2020)

    Google Scholar 

  16. Feng, A., You, C., Wang, S., Tassiulas, L.: KerGNNs : interpretable graph neural networks with graph kernels. arXiv preprint arXiv:2201.00491 (2022)

  17. 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 

  18. Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: 30th Proceedings of Conference on Advances in Neural Information Processing Systems (2017)

    Google Scholar 

  19. Irwin, J.J., Sterling, T., Mysinger, M.M., Bolstad, E.S., Coleman, R.G.: Zinc: a free tool to discover chemistry for biology. J. Chem. Inf. Model. 52(7), 1757–1768 (2012)

    Article  Google Scholar 

  20. Kazi, A., Cosmo, L., Ahmadi, S.A., Navab, N., Bronstein, M.: Differentiable graph module (DGM) for graph convolutional networks. IEEE Trans. Pattern Anal. Mach. Intell. Early Access (2022)

    Google Scholar 

  21. Kersting, K., Kriege, N.M., Morris, C., Mutzel, P., Neumann, M.: Benchmark data sets for graph kernels (2016). https://ls11-www.cs.tu-dortmund.de/staff/morris/graphkerneldatasets

  22. 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 

  23. Kriege, N., Mutzel, P.: Subgraph matching kernels for attributed graphs. arXiv preprint arXiv:1206.6483 (2012)

  24. 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 

  25. Luzhnica, E., Day, B., Liò, P.: On graph classification networks, datasets and baselines. arXiv preprint arXiv:1905.04682 (2019)

  26. Minello, G., Rossi, L., Torsello, A.: Can a quantum walk tell which is which? a study of quantum walk-based graph similarity. Entropy 21(3), 328 (2019)

    Article  MathSciNet  Google Scholar 

  27. 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 

  28. Nikolentzos, G., Vazirgiannis, M.: Random walk graph neural networks. Adv. Neural. Inf. Process. Syst. 33, 16211–16222 (2020)

    Google Scholar 

  29. Ralaivola, L., Swamidass, S.J., Saigo, H., Baldi, P.: Graph kernels for chemical informatics. Neural Netw. 18(8), 1093–1110 (2005)

    Article  Google Scholar 

  30. 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 

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

    Article  Google Scholar 

  32. 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 

  33. Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: Proceedings of the 12th International Conference on Artificial Intelligence and Statistics, pp. 488–495. PMLR (2009)

    Google Scholar 

  34. Simonovsky, M., Komodakis, N.: Dynamic edge-conditioned filters in convolutional neural networks on graphs. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3693–3702 (2017)

    Google Scholar 

  35. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph attention networks .In: International Conference on Learning Representations (2018)

    Google Scholar 

  36. Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Philip, S.Y.: A comprehensive survey on graph neural networks. IEEE Trans. Neural Netw. Learn. Syst. 32(1), 4–24 (2020)

    Article  MathSciNet  Google Scholar 

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

  38. Ying, R., You, J., Morris, C., Ren, X., Hamilton, W.L., Leskovec, J.: Hierarchical graph representation learning with differentiable pooling. arXiv preprint arXiv:1806.08804 (2018)

  39. 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. Ca’ Foscari University of Venice, Venice, Italy

    Alessandro Bicciato, Luca Cosmo, Giorgia Minello & Andrea Torsello

  2. IESE Business School, Barcelona, Spain

    Giorgia Minello

  3. Queen Mary University of London, London, UK

    Luca Rossi

Authors
  1. Alessandro Bicciato
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luca Cosmo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giorgia Minello
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Luca Rossi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. 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

Bicciato, A., Cosmo, L., Minello, G., Rossi, L., Torsello, A. (2022). Classifying Me Softly: A Novel Graph Neural Network Based on Features Soft-Alignment. 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_5

Download citation

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

  • 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