2026-07-28T19:12:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20270 2024-07-02T07:52:55Z ddc:004 open_access

Decidability of Graph Neural Networks via Logical Characterizations Benedikt, Michael Lu, Chia-Hsuan Motik, Boris Tan, Tony Logic Graph Neural Networks We present results concerning the expressiveness and decidability of a popular graph learning formalism, graph neural networks (GNNs), exploiting connections with logic. We use a family of recently-discovered decidable logics involving "Presburger quantifiers". We show how to use these logics to measure the expressiveness of classes of GNNs, in some cases getting exact correspondences between the expressiveness of logics and GNNs. We also employ the logics, and the techniques used to analyze them, to obtain decision procedures for verification problems over GNNs. We complement this with undecidability results for static analysis problems involving the logics, as well as for GNN verification problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Benedikt and Chia-Hsuan Lu and Boris Motik and Tony Tan 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.127 urn:nbn:de:0030-drops-202708 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.127 eng https://creativecommons.org/licenses/by/4.0/legalcode