nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Subgraph Mining for Graph Neural Networks

verfasst von : Adem Kikaj, Giuseppe Marra, Luc De Raedt

Erschienen in: Advances in Intelligent Data Analysis XXII

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Equivariant Parameter Sharing for Porous Crystalline Materials

Nächstes Kapitel Super-Resolution Analysis for Landfill Waste Classification

https://github.com/ademkikaj/AutoGSN.

Alsentzer, E., Finlayson, S., Li, M., Zitnik, M.: Subgraph neural networks. In: NeurIPS, vol. 33, pp. 8017–8029 (2020)

Bodnar, C., et al.: Weisfeiler and lehman go topological: message passing simplicial networks. In: ICML, pp. 1026–1037. PMLR (2021)

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

Breiman, L.: Random forests. Mach. Learn. 45, 5–32 (2001)CrossRef

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)

Cheng, H., Yan, X., Han, J.: Mining graph patterns. In: Frequent Pattern Mining, pp. 307–338 (2014)

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

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)

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.

Jegelka, S.: Theory of graph neural networks: representation and learning. arXiv preprint arXiv:2204.07697 (2022)

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.

Kraskov, A., Stögbauer, H., Grassberger, P.: Estimating mutual information. Phys. Rev. E 69(6), 066138 (2004)MathSciNetCrossRef

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.

McKay, B.: http://users.cecs.anu.edu.au/~bdm/data/graphs.html

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.

NetworkX. https://networkx.org/documentation/stable/reference/algorithms/isomorphism.vf2.html#subgraph-isomorphism

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.

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

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)

Titel: Subgraph Mining for Graph Neural Networks
verfasst von: Adem Kikaj
Giuseppe Marra
Luc De Raedt
Verlag: Springer Nature Switzerland
Buch: Advances in Intelligent Data Analysis XXII
Print ISBN: 978-3-031-58546-3

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner