{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T13:12:26Z","timestamp":1778764346749,"version":"3.51.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"ANID - Millennium Science Initiative Program","award":["ICN17002"],"award-info":[{"award-number":["ICN17002"]}]},{"name":"National Center for Artificial Intelligence CENIA","award":["FB210017"],"award-info":[{"award-number":["FB210017"]}]},{"name":"FWO","award":["G019222N"],"award-info":[{"award-number":["G019222N"]}]},{"name":"Flanders AI Program","award":["-"],"award-info":[{"award-number":["-"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["[10.47379\\\/ICT2201, 10.47379\\\/VRG18013]"],"award-info":[{"award-number":["[10.47379\\\/ICT2201, 10.47379\\\/VRG18013]"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,12]]},"abstract":"<jats:p>We study the numerical and Boolean expressiveness of MPLang, a declarative language that captures the computation of graph neural networks (GNNs) through linear message passing and activation functions. We begin with A-MPLang, the fragment without activation functions, and give a characterization of its expressive power in terms of walk-summed features. For bounded activation functions, we show that (under mild conditions) all eventually constant activations yield the same expressive power\u2014numerical and Boolean\u2014and that it subsumes previously established logics for GNNs with eventually constant activation functions but without linear layers. Finally, we prove the first expressive separation between unbounded and bounded activations in the presence of linear layers: MPLang with ReLU is strictly more powerful for numerical queries than MPLang with eventually constant activation functions, e.g., truncated ReLU. This hinges on subtle interactions between linear aggregation and eventually constant non-linearities, and it establishes that GNNs using ReLU are more expressive than those restricted to eventually constant activations and linear layers.<\/jats:p>","DOI":"10.1145\/3801914","type":"journal-article","created":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:50:22Z","timestamp":1778763022000},"page":"1-19","source":"Crossref","is-referenced-by-count":0,"title":["A Logical View of GNN-Style Computation and the Role of Activation Functions"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2293-2653","authenticated-orcid":false,"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"Institute for Mathematical and Computational Engineering, Pontifical Catholic University of Chile &amp;#38; IMFD &amp;#38; CENIA, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8967-2473","authenticated-orcid":false,"given":"Floris","family":"Geerts","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Antwerp, Antwerp, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7601-3727","authenticated-orcid":false,"given":"Matthias","family":"Lanzinger","sequence":"additional","affiliation":[{"name":"Institute for Logic and Computation, TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-9715-2214","authenticated-orcid":false,"given":"Klara","family":"Pakhomenko","sequence":"additional","affiliation":[{"name":"Data Science Institute, Universiteit Hasselt, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0072-3252","authenticated-orcid":false,"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[{"name":"Data Science Institute, Universiteit Hasselt, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.52202\/079017-3311"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.104"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 8th International Conference on Learning Representations (ICLR). OpenReview.net. https:\/\/openreview.net\/forum?id=r1lZ7AEKvB","author":"Barcel\u00f3 Pablo","year":"2020","unstructured":"Pablo Barcel\u00f3, Egor V. Kostylev, Mika\u00ebl Monet, Jorge P\u00e9rez, Juan L. Reutter, and Juan Pablo Silva. 2020. The Logical Expressiveness of Graph Neural Networks. In Proceedings of the 8th International Conference on Learning Representations (ICLR). OpenReview.net. https:\/\/openreview.net\/forum?id=r1lZ7AEKvB"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_2_1_7_1","unstructured":"Pablo Barcel\u00f3 Floris Geerts Matthias Lanzinger Klara Pakhomenko and Jan Van den Bussche. 2025. A Logical View of GNN-Style Computation and the Role of Activation Functions. arXiv:2512.19332 [cs.LG] https:\/\/arxiv.org\/abs\/2512.19332"},{"key":"e_1_2_1_8_1","volume-title":"Graph Neural Networks and Arithmetic Circuits. In The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS). https:\/\/openreview.net\/forum?id=0ZeONp33f0","author":"Barlag Timon","year":"2024","unstructured":"Timon Barlag, Vivian Holzapfel, Laura Strieker, Jonni Virtema, and Heribert Vollmer. 2024. Graph Neural Networks and Arithmetic Circuits. In The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS). https:\/\/openreview.net\/forum?id=0ZeONp33f0"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.127"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331445"},{"key":"e_1_2_1_11_1","volume-title":"Maurizio Lenzerini, and Moshe Y. Vardi.","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of Conjunctive Regular Path Queries with Inverse. In Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR). Morgan Kaufmann, 176-185."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298591"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38749"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64187-0_3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2024.22"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2020.9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2020\/38"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-21(1:21)2025"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725237"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524167"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2023.1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.01.008"},{"key":"e_1_2_1_24_1","unstructured":"Floris Geerts and Juan L Reutter. 2022. Expressiveness and approximation properties of graph neural networks. In ICLR. OpenReview.net."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-11321-5_2"},{"key":"e_1_2_1_26_1","first-page":"1263","article-title":"Neural Message Passing for Quantum Chemistry. In ICML (Proceedings of Machine Learning Research, Vol. 70)","author":"Gilmer Justin","year":"2017","unstructured":"Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. In ICML (Proceedings of Machine Learning Research, Vol. 70). PMLR, 1263-1272.","journal-title":"PMLR"},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"The Logic of Graph Neural Networks","author":"Grohe Martin","year":"2021","unstructured":"Martin Grohe. 2021. The Logic of Graph Neural Networks. In LICS. IEEE, 1-17.","journal-title":"LICS. IEEE"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.46298\/theoretics.24.25"},{"key":"e_1_2_1_29_1","unstructured":"William L. Hamilton Rex Ying and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NeurIPS. 1025\u20131035."},{"key":"e_1_2_1_30_1","unstructured":"Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. https:\/\/www.w3.org\/TR\/sparql11-query\/. W3C Recommendation."},{"key":"e_1_2_1_31_1","volume-title":"Hauke and Przemyslaw Andrzej Walega","author":"Stan","year":"2025","unstructured":"Stan P. Hauke and Przemyslaw Andrzej Walega. 2025. Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2. CoRR, Vol. abs\/2508.06091 (2025)."},{"key":"e_1_2_1_32_1","volume-title":"On the power of graph neural networks and the role of the activation function. CoRR","author":"Khalife Sammy","year":"2023","unstructured":"Sammy Khalife and Amitabh Basu. 2023. On the power of graph neural networks and the role of the activation function. CoRR, Vol. abs\/2307.04661 (2023)."},{"key":"e_1_2_1_33_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR. OpenReview.net."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_2_1_36_1","unstructured":"Matthew Morris and Ian Horrocks. 2025. Sound Logical Explanations for Mean Aggregation Graph Neural Networks. In NeurIPS. OpenReview.net."},{"key":"e_1_2_1_37_1","unstructured":"R.R. Nerem et al. 2025. Graph neural networks extrapolate out-of-distribution for shortest paths. arXiv:2503.19173."},{"key":"e_1_2_1_38_1","volume-title":"A logic for reasoning about aggregate-combine graph neural networks. arXiv preprint arXiv:2405.00205","author":"Nunn Pierre","year":"2024","unstructured":"Pierre Nunn, Marco S\u00e4lzer, Fran\u00e7ois Schwarzentruber, and Nicolas Troquard. 2024. A logic for reasoning about aggregate-combine graph neural networks. arXiv preprint arXiv:2405.00205 (2024)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9676-2"},{"key":"e_1_2_1_40_1","first-page":"1","article-title":"The homomorphism problem for regular graph patterns","author":"Romero Miguel","year":"2017","unstructured":"Miguel Romero, Pablo Barcel\u00f3, and Moshe Y. Vardi. 2017. The homomorphism problem for regular graph patterns. In LICS. IEEE Computer Society, 1-12.","journal-title":"LICS. IEEE Computer Society"},{"key":"e_1_2_1_41_1","volume-title":"Przemyslaw Andrzej Walega, and Martin Lange","author":"S\u00e4lzer Marco","year":"2025","unstructured":"Marco S\u00e4lzer, Przemyslaw Andrzej Walega, and Martin Lange. 2025. The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics. In NeurIPS. OpenReview.net."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1013"},{"key":"e_1_2_1_44_1","unstructured":"Arie Soeteman and Balder ten Cate. 2025. Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization. In NeurIPS. OpenReview.net."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patter.2021.100273"},{"key":"e_1_2_1_46_1","unstructured":"Solveig Wittig Antonis Vasileiou Robert R. Nerem Timo Stoll Floris Geerts Yusu Wang and Christopher Morris. 2026. Which Algorithms Can Graph Neural Networks Learn? arXiv:2602.13106. https:\/\/arxiv.org\/abs\/2602.13106"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801914","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:51:08Z","timestamp":1778763068000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3801914"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,12]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,12]]}},"alternative-id":["10.1145\/3801914"],"URL":"https:\/\/doi.org\/10.1145\/3801914","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,12]]}}}