EUVIMEDEUVIMED entdecken
Crossref

Decidability of Graph Neural Networks via Logical Characterizations

Michael Benedikt, Chia-Hsuan Lu, Tony Tan

ACM Transactions on Computational Logic · 30.04.2026 · 27 (2) · 1-65

DOI: 10.1145/3800944 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 17.04.2026. Verfasst von Michael Benedikt und 2 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben. Gefördert von: Engineering and Physical Sciences Research Council, UKRI.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Engineering and Physical Sciences Research Council
  • UKRI

Zitieren

APA

Benedikt, M., Lu, C., & Tan, T. (2026). Decidability of Graph Neural Networks via Logical Characterizations. ACM Transactions on Computational Logic, 27(2), 1-65. https://doi.org/10.1145/3800944

Vancouver

Benedikt M, Lu C, Tan T. Decidability of Graph Neural Networks via Logical Characterizations. ACM Transactions on Computational Logic. 2026;27(2):1-65. doi:10.1145/3800944

BibTeX
@article{Benedikt2026,
  author = {Benedikt, Michael and Lu, Chia-Hsuan and Tan, Tony},
  title = {Decidability of Graph Neural Networks via Logical Characterizations},
  journal = {ACM Transactions on Computational Logic},
  year = {2026},
  volume = {27},
  number = {2},
  pages = {1--65},
  doi = {10.1145/3800944}
}
Kostenlos starten →