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:
Tackling the Abstraction and Reasoning Corpus (ARC) with Object-Centric Models and the MDL Principle Read chapter Read first chapter

2024 | OriginalPaper | Chapter

Subgraph Mining for Graph Neural Networks

Authors : Adem Kikaj, Giuseppe Marra, Luc De Raedt

Published in: Advances in Intelligent Data Analysis XXII

Publisher: Springer Nature Switzerland

Log in

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

search-config
loading …

Abstract

While Graph Neural Networks (GNNs) are state-of-the-art models for graph learning, they are only as expressive as the first-order Weisfeiler-Leman graph isomorphism test algorithm. To enhance their expressiveness one can incorporate complex structural information as attributes of the nodes in input graphs. However, this typically demands significant human effort and specialised domain knowledge. We demonstrate the feasibility of automatically extracting such information through subgraph mining and feature selection. Our experimental evaluation, conducted across graph classification tasks, reveals that GNNs extended with automatically selected features obtained using subgraph mining can achieve comparable or even superior performance to GNNs relying on manually crafted features.

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 Equivariant Parameter Sharing for Porous Crystalline Materials
next chapter Super-Resolution Analysis for Landfill Waste Classification
Footnotes
Literature
1.
Alsentzer, E., Finlayson, S., Li, M., Zitnik, M.: Subgraph neural networks. In: NeurIPS, vol. 33, pp. 8017–8029 (2020)
2.
Bodnar, C., et al.: Weisfeiler and lehman go topological: message passing simplicial networks. In: ICML, pp. 1026–1037. PMLR (2021)
3.
Bouritsas, G., Frasca, F., Zafeiriou, S., Bronstein, M.M.: Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trans. Pattern Anal. Mach. Intell. 45(1), 657–668 (2022)CrossRef
4.
5.
Chen, T., Guestrin, C.: XGBoost: a scalable tree boosting system. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785–794 (2016)
6.
Cheng, H., Yan, X., Han, J.: Mining graph patterns. In: Frequent Pattern Mining, pp. 307–338 (2014)
7.
Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub) graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367–1372 (2004)CrossRef
8.
Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. In: ICML, pp. 1263–1272. PMLR (2017)
9.
Huang, N.T., Villar, S.: A short tutorial on the Weisfeiler-Lehman test and its variants. In: ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8533–8537. IEEE (2021)
10.
11.
Jin, N., Young, C., Wang, W.: GAIA: graph classification using evolutionary computation. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, pp. 879–890 (2010)
12.
Ketkar, N.S., Holder, L.B., Cook, D.J.: Subdue: compression-based frequent pattern discovery in graph data. In: Proceedings of the 1st International Workshop on Open Source Data Mining: Frequent Pattern Mining Implementations, pp. 71–76 (2005)
13.
14.
Leman, A., Weisfeiler, B.: A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya 2(9), 12–16 (1968)
15.
Liu, H., Setiono, R.: Chi2: feature selection and discretization of numeric attributes. In: Proceedings of 7th IEEE ICTAI, pp. 388–391. IEEE (1995)
16.
Maron, H., Ben-Hamu, H., Serviansky, H., Lipman, Y.: Provably powerful graph networks. In: NeurIPS, vol. 32 (2019)
17.
18.
Meilicke, C., Chekol, M.W., Ruffinelli, D., Stuckenschmidt, H.: Anytime bottom-up rule learning for knowledge graph completion. In: IJCAI, pp. 3137–3143 (2019)
19.
Morris, C., Kriege, N.M., Bause, F., Kersting, K., Mutzel, P., Neumann, M.: TUDataset: a collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:​2007.​08663 (2020)
20.
Morris, C., et al.: Weisfeiler and Leman go neural: higher-order graph neural networks. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 4602–4609 (2019)
21.
22.
Nijssen, S., Kok, J.N.: The Gaston tool for frequent subgraph mining. Electron. Notes Theor. Comput. Sci. 127(1), 77–87 (2005)CrossRef
23.
Ribeiro, P., Paredes, P., Silva, M.E., Aparicio, D., Silva, F.: A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Comput. Surv. (CSUR) 54(2), 1–36 (2021)CrossRef
24.
Saigo, H., Nowozin, S., Kadowaki, T., Kudo, T., Tsuda, K.: gBoost: a mathematical programming approach to graph classification and regression. Mach. Learn. 75, 69–89 (2009)CrossRef
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)CrossRef
26.
Sun, Q., et al.: SUGAR: subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism. In: Proceedings of the Web Conference 2021, pp. 2081–2091 (2021)
27.
28.
Yan, X., Han, J.: gSpan: graph-based substructure pattern mining. In: 2002 IEEE International Conference on Data Mining, Proceedings, pp. 721–724. IEEE (2002)
29.
Zeman, V., Kliegr, T., Svátek, V.: RDFRules: making RDF rule mining easier and even more efficient. Semant. Web 12(4), 569–602 (2021)CrossRef
30.
Zhang, M., Li, P.: Nested graph neural networks. In: NeurIPS, vol. 34, pp. 15734–15747 (2021)
31.
Zhao, L., Jin, W., Akoglu, L., Shah, N.: From stars to subgraphs: uplifting any GNN with local structure awareness. arXiv preprint arXiv:​2110.​03753 (2021)
Metadata
Title
Subgraph Mining for Graph Neural Networks
Authors
Adem Kikaj
Giuseppe Marra
Luc De Raedt
Copyright Year
2024
Book
Advances in Intelligent Data Analysis XXII

Print ISBN: 978-3-031-58546-3

Electronic ISBN: 978-3-031-58547-0

Copyright Year: 2024

DOI
https://doi.org/10.1007/978-3-031-58547-0_12

Premium Partner

    Image Credits