EUVIMEDEUVIMED entdecken
Crossref

Logical Characterizations of GNNs with Mean Aggregation

Moritz Schönherr, Carsten Lutz

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (30) · 25218-25225

DOI: 10.1609/aaai.v40i30.39713 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Moritz Schönherr und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the expressive power of graph neural networks (GNNs) with mean as the aggregation function, with the following results. In the non-uniform setting, such GNNs have exactly the same expressive power as ratio modal logic, which has modal operators expressing that at least a certain ratio of the successors of a vertex satisfies a specified property. In the uniform setting, the expressive power relative to MSO is exactly that of modal logic, and thus identical to the (absolute) expressive power of GNNs with max aggregation. The proof, however, depends on constructions that are not satisfactory from a practical perspective. This leads us to making the natural assumptions that combination functions are continuous and classification functions are thresholds. The resulting class of GNNs with mean aggregation turns out to be much less expressive: relative to MSO and in the uniform setting, it has the same expressive power as alternation-free modal logic. This is in contrast to the expressive power of GNNs with max and sum aggregation, which is not affected by these assumptions.

Zitieren

APA

Schönherr, M., & Lutz, C. (2026). Logical Characterizations of GNNs with Mean Aggregation. Proceedings of the AAAI Conference on Artificial Intelligence, 40(30), 25218-25225. https://doi.org/10.1609/aaai.v40i30.39713

Vancouver

Schönherr M, Lutz C. Logical Characterizations of GNNs with Mean Aggregation. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(30):25218-25225. doi:10.1609/aaai.v40i30.39713

BibTeX
@article{Schnherr2026,
  author = {Schönherr, Moritz and Lutz, Carsten},
  title = {Logical Characterizations of GNNs with Mean Aggregation},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {30},
  pages = {25218--25225},
  doi = {10.1609/aaai.v40i30.39713}
}
Kostenlos starten →