EUVIMEDEUVIMED entdecken
Crossref

Aggregate-Combine-Readout GNNs Can Express Logical Classifiers Beyond the Logic C2

Stan P Hauke, Przemysław Andrzej Wałęga

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (26) · 21594-21601

DOI: 10.1609/aaai.v40i26.39308 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Stan P Hauke und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In recent years, there has been growing interest in understanding the expressive power of graph neural networks (GNNs) by relating them to logical languages. This research has been initialised by an influential result of Barceló et al. (2020), who showed that the graded modal logic (or a guarded fragment of the logic C2), characterises the logical expressiveness of aggregate-combine GNNs. As a “challenging open problem” they left the question whether C2 characterises the logical expressiveness of aggregate-combine-readout GNNs. This question has remained unresolved despite several attempts. In this paper, we solve the above open problem by proving that aggregate-combine-readout GNNs can express logical classifiers beyond C2. This result holds over both undirected and directed graphs. Beyond its implications for GNNs, our work also leads to purely logical insights on the expressive power of infinitary logics.

Zitieren

APA

Hauke, S. P., & Wałęga, P. A. (2026). Aggregate-Combine-Readout GNNs Can Express Logical Classifiers Beyond the Logic C2. Proceedings of the AAAI Conference on Artificial Intelligence, 40(26), 21594-21601. https://doi.org/10.1609/aaai.v40i26.39308

Vancouver

Hauke SP, Wałęga PA. Aggregate-Combine-Readout GNNs Can Express Logical Classifiers Beyond the Logic C2. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(26):21594-21601. doi:10.1609/aaai.v40i26.39308

BibTeX
@article{Hauke2026,
  author = {Hauke, Stan P and Wałęga, Przemysław Andrzej},
  title = {Aggregate-Combine-Readout GNNs Can Express Logical Classifiers Beyond the Logic C2},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {26},
  pages = {21594--21601},
  doi = {10.1609/aaai.v40i26.39308}
}
Kostenlos starten →