2026-07-25T23:33:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25048 2026-03-19T12:49:41Z ddc:004 open_access

Foundations of Graph Neural Networks (A Logician’s View) (Invited Paper) Kostylev, Egor V. Graph Neural Networks Expressivity Logic Graph Neural Networks (GNNs) are a family of neural architectures that are naturally suited to learning functions on graphs. They are now used in a wide range of applications. It has been observed that GNNs share many similarities with classical computer science (CS) formalisms, such as the Weisfeiler-Leman graph isomorphism test, bisimulation, and logic. Most notably, both GNNs and these formalisms deal with functions on graphs and graph-like structures. This observation opens up an opportunity to compare GNN architectures with these formalisms in terms of different kinds of expressibility, thus positioning these architectures within the well-established landscape of theoretical CS. This, in turn, helps us better understand the fundamental capabilities and limitations of various GNN architectures, enabling more informed choices about which architecture to use - if any at all. In these lecture notes, I give an introduction to the state-of-the-art foundations of GNNs - specifically, our current understanding of their expressibility in terms of the classical formalisms, considering several notions of expressive power. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Egor V. Kostylev 2025 Is Part Of OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.RW.2024/2025.3 urn:nbn:de:0030-drops-250486 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.3 eng https://creativecommons.org/licenses/by/4.0/legalcode