Pith. sign in

REVIEW 3 major objections 3 minor 45 references

A Logical View of GNN-Style Computation and the Role of Activation Functions

T0 review · 3 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read ReLU-MPLang, the logical language corresponding to ReLU graph neural networks, numerically strictly contains every MPLang variant with eventually constant activations on coloured graphs with at least two colours.

desk verdict The ReLU vs eventually-constant separation is unproven as written: the tree family T[r,b,k] is inconsistent and Lemma 6.6 fails at boundary nodes; the rest of the paper is solid but the headline needs a real fix. read the letter →

arxiv 2512.19332 v2 pith:5L6EADCK submitted 2025-12-22 cs.LG cs.LO

Pablo Barceló , Floris Geerts , Matthias Lanzinger , Klara Pakhomenko , Jan Van den Bussche This is my paper · ORCID
classification cs.LGcs.LO
keywords MPLanggraphneuralnetworksactivationfunctionsReLUexpressivepowerwalk-sumnormalformsBooleanquerieseventuallyconstant
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies MPLang, a declarative language that captures the computation of graph neural networks through linear message passing plus an activation function. It shows that the activation-free fragment of MPLang has a complete normal form in terms of walk counts and walk-summed features, and that its Boolean queries are not closed under conjunction or modal iteration. For bounded, eventually constant activations (truncated ReLU, sign, bool), the paper proves that all such activations yield the same numerical and Boolean expressive power over coloured graphs. The central result is a strict separation: with ReLU, MPLang can express numerical queries—starting from ReLU(^red − ^blue)—that no eventually-constant-activated variant can express, even when linear layers are allowed. If correct, this pins the expressive advantage of modern GNNs on the choice of an unbounded activation function.

What carries the argument

The red–blue symmetric tree T[r,b,k] is a rooted tree of height k whose root is a white node with r red and b blue children, with red and blue nodes sitting between alternating white types (r red, b blue, or swapped). The paper classifies the functions arising from bool-MPLang evaluations on this family: a 'nice' function is a finite sum of polynomials multiplied by simple symmetric step functions. Lemma 6.6 shows by structural induction that every bool-MPLang expression of ^-depth at most k evaluates at white root-type nodes to F(r,b) + α(r,b) + β(r,b), with F nice, α affine, and β simple; red and blue node values are symmetric nice functions. Lemma 6.7 is the technical heart: it proves—via

What would settle it

Search for a bool-MPLang expression e such that e evaluates at the root of T[r,b,k] to |r−b| for all natural r,b—equivalently, run an exhaustive enumeration of bool-MPLang expressions up to a fixed ^-depth on small trees T[r,b,k] and check whether evaluation matches |r−b|. Any such expression, or any pair (r,b) where a claimed 'nice plus affine plus simple' form fails, would overturn Lemma 6.7 and with it Theorem 6.8.

Watch

Extended reading notes

Core claim

The main discovery is a strict expressive separation for numerical queries on k-coloured graphs with k ≥ 2: rational ReLU-MPLang numerically strictly contains rational Σ-MPLang for every finite set Σ of uneven eventually constant activations. The witness query is Q := ReLU(^red − ^blue), which computes how many more red than blue neighbours a node has, truncated below at zero. The paper proves Q is not definable in bool-MPLang by evaluating bool-expressions on a family of red–blue symmetric trees T[r,b,k]. There, every bool-MPLang expression of ^-depth at most k evaluates at the root to a function of the rigid form 'nice function plus affine function plus simple step function', and the paper

Load-bearing premise

The proof that every bool-MPLang expression on the red–blue symmetric trees collapses to a 'nice plus affine plus simple' function, and that no such function can match |r−b|; if even one expression escapes this rigid form, the ReLU-versus-bounded separation collapses.

Editorial extensions

If this is right

  • ReLU-GNNs with linear layers compute numerical node queries that no truncated-ReLU-, sign-, or bool-activated GNN with linear layers can compute, on coloured graphs with at least two colours.
  • Because every uneven eventually constant activation is numerically equivalent to bool over coloured graphs, no combination of bounded activations can close the gap against ReLU.
  • The walk-based normal form for the activation-free fragment shows that linear (identity-only) GNNs see only walk counts and endpoint-feature sums, so non-linearities are necessary to reach modal-logic-level Boolean expressiveness.
  • Adding identity layers to an eventually-constant-activated GNN strictly increases its Boolean expressiveness, even though the specific bounded activation used does not matter.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The separation is proved for numerical queries; the paper leaves open whether a Boolean query (one whose answer is just the sign of a numerical output) also separates ReLU from bounded activations. A plausible route is to take the same tree family and threshold Q at zero, but the paper does not claim this.
  • The main theorems are stated with rational coefficients in the language. Since the paper's own negation result for A-MPLang relies on irrational Liouville coefficients, it is possible that the containment direction behaves differently with arbitrary real coefficients—an extension that is not established here.
  • The 'nice function' classification suggests a general template: compare any two activation functions by the shape of the functions they induce on a family of symmetric trees. The same template could be applied to other unbounded activations such as GELU or ELU to test whether unboundedness is the operative property.
  • The walk-sum normal form implies that the separation might be rephrased in linear-algebraic terms: ReLU can apply a non-linear gate to a walk-count affine form, while bounded activations, on trees of unbounded depth, reduce to rigid piecewise-polynomial forms that cannot reproduce absolute differences.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies MPLang, a declarative language that captures GNN-style message passing with linear aggregation and activation functions. It gives a walk-based normal form for the affine fragment A-MPLang, proves that over coloured graphs all uneven eventually constant activations are numerically equivalent to bool-MPLang (in the rational-coefficient fragment), and then aims to prove that ReLU-MPLang is numerically strictly more expressive than any eventually constant activation even in the presence of linear/identity layers. The main separation is Theorem 6.8, which claims that the query Q = ReLU(^red − ^blue) is not expressible in bool-MPLang, via an analysis of evaluations on red–blue symmetric trees T[r,b,k] and a polynomial-parity argument (Lemma 6.7).

Significance. If the main separation were fully established, it would be a valuable result: it would give the first numerical expressiveness gap between ReLU-GNNs and GNNs with eventually constant activations when identity/linear layers are allowed, and it would strengthen the logic-based understanding of GNN expressivity. The paper also contains useful positive results: the walk normal form for A-MPLang (Theorem 4.2) and the closure/Booleanisation results for eventually constant activations (Section 5). Lemma 6.7, an independent polynomial argument showing that 'nice' functions cannot encode |x−y|, is a solid technical contribution. However, the main separation is not yet reliably established: the tree lemma used in the proof has a boundary flaw, and the theorem statements around the ReLU/bool containment are too strong and, in one reading, false.

major comments (3)
  1. [§6.1, Lemma 6.6 / definition of T[r,b,k]] Lemma 6.6 is false as stated because T[r,b,k] is a finite rooted tree of height k, so its boundary nodes do not satisfy the uniform neighbourhood conditions used in the induction. For example, when k=3 and r=b=1, a red node at depth 1 has two white neighbours (one w-type, one w′-type), while a red leaf at depth 3 has only one white neighbour. The expression e = bool(^1 − 3/2) evaluates to 1 at the depth-1 red node and to 0 at the depth-3 red leaf, so no single symmetric function S_r(r,b) can describe all red nodes, contradicting Lemma 6.6. The proof of Lemma 6.6 explicitly uses that red/blue nodes have exactly one w-type and one w′-type white neighbour, which fails at the boundary. Since Theorem 6.8 applies Lemma 6.6 with k equal to the ^-depth of e*, and the structural induction passes through boundary nodes, the proof of Theorem 6.8 has a genuine gap. A repair would need to evaluate on
  2. [§6, Proposition 6.2] Proposition 6.2 states that ReLU-MPLang numerically strictly contains bool-MPLang. The proof only shows that one particular query, Q = ReLU(^red − ^blue), is in ReLU-MPLang and not in bool-MPLang; it does not prove the containment direction bool-MPLang ⊆ ReLU-MPLang. This is not just a missing detail: for full real-coefficient bool-MPLang the containment is false. Let r be a Liouville number as in Lemma A.2 and consider the bool-MPLang expression bool(r·^red − ^blue). On star graphs with a red and b blue neighbours this query must output 1 when r a − b > 0 and 0 when r a − b ≤ 0, a discontinuous function of the linear input (a,b). Any ReLU-MPLang expression, built from addition, scalar multiplication, neighbourhood summation, and the continuous function ReLU, evaluates to a continuous piecewise-affine function of the input values, so it cannot equal this discontinuous Boolean-valued func
  3. [§5.2 / §6, Theorem 5.5 and Theorem 6.1] Theorem 6.1 is stated for arbitrary sets Σ of uneven eventually constant functions, but the proof route through Theorem 5.5 and Proposition 6.2 does not support this generality. Theorem 5.5 says that the rational fragment of Σ-MPLang is numerically equivalent to bool-MPLang, where the simulating bool expression may use real coefficients because the values σ(ℓ/d), σ(t−), σ(t+) of the eventually constant function need not be rational. The subsequent containment in rational ReLU-MPLang is therefore not obtained. In fact, Theorem 6.1 is false as stated: let σ be the uneven eventually constant function with σ(x)=√2 for x>0 and σ(x)=0 for x≤0. On coloured graphs the expression σ(1) in rational Σ-MPLang evaluates to √2 at every node, but every rational ReLU-MPLang expression evaluates to a rational number at every node of every coloured graph (by a straightforward induction, since ReLU preserve
minor comments (3)
  1. [Abstract / §5.2] The abstract and the introduction omit the rational-coefficient qualifier when describing the equivalence of eventually constant activations. Theorem 5.5 is explicitly about the rational fragment, and the abstract should match the theorem statement.
  2. [§6, before Proposition 6.2] The sentence 'Combined with Theorem 5.5, which shows that all eventually constant activation functions are equivalent to TrReLU' is inaccurate: Theorem 5.5 establishes equivalence with bool-MPLang, not with TrReLU. This wording should be corrected.
  3. [§6.2] The remark that on graphs of bounded depth the query of Theorem 6.8 is expressible, with proof omitted, is relevant to understanding why the construction needs unbounded depth. If this fact is used to justify the proof strategy, a proof or reference should be supplied.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central ReLU-vs-bounded separation is proved by an independent structural/polynomial argument, not by fitting data or by citing the target result.

full rationale

The main new claim, Theorem 6.8, rests on a self-contained inexpressibility proof. It assumes a bool-MPLang expression for Q := ReLU(^red - ^blue), forms a companion expression e*, and reaches a contradiction using Lemma 6.6 and Lemma 6.7. Lemma 6.6 is a structural induction on the syntax of bool-MPLang over the symmetric trees T[r,b,k]; Lemma 6.7 is an independent pigeonhole/polynomial-parity argument. Neither lemma assumes the conclusion, and no parameter is fitted to data. The supporting results (A-MPLang normal form, Theorem 4.2; eventual-constant equivalence, Theorem 5.5; the L-MP2 containment, Proposition 5.7) are proved in the text. The few self-citations are contextual: Proposition 3.1 cites the authors' earlier MPLang/GNN translation [24], and Theorem 3.3 cites [5,8] for the known GML-in-GNN containment. These are prior, externally checkable results and are not the target of the new separation, so under the stated rules they do not raise the circularity score. Two correctness risks exist but are not circularity: Lemma 6.6 may have an unhandled boundary case for odd k because red/blue nodes at distance k in T[r,b,k] may lack one white-neighbour type, and Theorem 6.8 writes e* := e - e' as defining |^red - ^blue|, whereas ReLU(x)-ReLU(-x) = x and the absolute value would come from ReLU(x)+ReLU(-x). Either issue is a proof gap or typo, not an input-as-output reduction. The explicit 'proof omitted' remark in Section 6.2 is likewise a missing proof, not a circular step. Overall, no step of the derivation is equivalent by construction to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted parameters or invented physical entities. The central proofs are pure derivations relying on finite-coloured-graph semantics, uneven eventually constant activations, rational-coefficient fragments, and standard polynomial/approximation facts.

assumptions (5)
  • domain assumption Finite undirected graphs and one-hot colour embeddings; walk counts are integer-valued.
    Section 2 defines graphs/embeddings; all expressiveness results are over this class.
  • domain assumption Uneven eventually constant activation functions, with σ(t-) ≠ σ(t+).
    Definition 5.4; Theorem 5.5 and Theorem 6.1 rely on non-degenerate saturation.
  • domain assumption Rational coefficients for the main equivalence/containment results.
    Section 3.1 defines rational Σ-MPLang. Theorem 5.5 and Theorem 6.1 as proven really concern rational fragments, though the paper states some results without this qualifier.
  • standard math Standard polynomial identity facts and existence of Liouville numbers.
    Used in Lemma 6.7 (polynomial identity from infinite coincidences) and Proposition 4.7 (Liouville approximation); standard theorems.
  • standard math ReLU-MPLang expressions define continuous piecewise-linear functions on real-valued inputs.
    Implicit in assessing full-language containment; relevant to whether bool can be simulated by ReLU with arbitrary real coefficients.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Logical View of GNN-Style Computation and the Role of Activation Functions." pith.science (2026). https://pith.science/paper/5L6EADCK

@misc{pith2026251219332,
  author       = {Pith},
  title        = {Pith review of: A Logical View of GNN-Style Computation and the Role of Activation Functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5L6EADCK}},
  note         = {Machine review of arXiv:2512.19332}
}
read the original abstract

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 - numerical and Boolean - and 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.

Figures

Figures reproduced from arXiv: 2512.19332 by the authors.

Figure 1
Figure 1. Graphs and Boolean queries used to show non-closure of [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Simulation of 𝜎(𝑒) by a bool-MPLang expression 𝑒 ′ as described in the proof of Theorem 5.5. within bool-MPLangB . More precisely, for bool-MPLang-expressions 𝑒1 and 𝑒2, we abbreviate: 𝑒1 ∨ 𝑒2 := bool(𝑒1) + bool(𝑒2), 𝑒1 ∧ 𝑒2 := bool(𝑒1) + bool(𝑒2) − 1, ¬𝑒1 := 1 − bool(𝑒1), 𝑒1 > 𝑒2 := bool(𝑒1 − 𝑒2), 𝑒1 ≤ 𝑒2 := ¬(𝑒1 > 𝑒2), 𝑒1 = 𝑒2 := ¬ [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. The red–blue symmetric tree 𝑇 [𝑟, 𝑏, 3]. Red–blue symmetric trees. Our argument uses a family of highly symmetric trees whose root can “see” the imbalance between red and blue children through the numerical power of ReLU. For readability, we will introduce white nodes as a third colour, but note that the following proof is exactly analogous if all of the white nodes in the construction get coloured red. Fix 𝑟, 𝑏, 𝑘 … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 9 canonical work pages

  1. [8]

    Michael Benedikt, Chia-Hsuan Lu, Boris Motik, and Tony Tan. 2024. Decidability of Graph Neural Networks via Logical Characterizations. InProceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 297). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 127:1–127:20. https://doi.org/10.4230/ LIPIcs.ICALP.2024.127

    2024

  2. [1]

    Veeti Ahvonen, Damian Heiman, Antti Kuusisto, and Carsten Lutz. 2024. Logical characterizations of recurrent graph neural networks with reals and floats. InProceedings of the Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS). https://openreview.net/forum?id=atDcnWqG5n

    2024

  3. [3]

    Pablo Barceló. 2013. Querying graph databases. InProceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). Association for Computing Machinery, 175–188. https://doi.org/10.1145/ 16 Pablo Barceló, Floris Geerts, Matthias Lanzinger, Klara Pakhomenko, and Jan Van den Bussche 2463664.2465216

    arXiv 2013

  4. [4]

    Pablo Barceló, Diego Figueira, and Miguel Romero. 2019. Boundedness of Conjunctive Regular Path Queries. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 104:1–104:15. https://doi.org/10.4230/LIPIcs.ICALP.2019.104

    work page doi:10.4230/lipics.icalp.2019.104 2019

  5. [5]

    Kostylev, Mikaël Monet, Jorge Pérez, Juan L

    Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. 2020. The Logical Expressiveness of Graph Neural Networks. InProceedings of the 8th International Conference on Learning Representations (ICLR). OpenReview.net. https://openreview.net/forum?id=r1lZ7AEKvB

    2020

  6. [6]

    Lin, and Peter T

    Pablo Barceló, Leonid Libkin, Anthony W. Lin, and Peter T. Wood. 2012. Expressive Languages for Path Queries over Graph-Structured Data.ACM Trans. Database Syst.37, 4 (2012), 31:1–31:46. https://doi.org/10.1145/2389241.2389250

    arXiv 2012

  7. [7]

    Timon Barlag, Vivian Holzapfel, Laura Strieker, Jonni Virtema, and Heribert Vollmer. 2024. Graph Neural Networks and Arithmetic Circuits. InProceedings of the Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS). https://openreview.net/forum?id=0ZeONp33f0

    2024

  8. [9]

    Robert Brijder, Floris Geerts, Jan Van Den Bussche, and Timmy Weerwag. 2019. On the Expressive Power of Query Languages for Matrices.ACM Trans. Database Syst.44, 4, Article 15 (2019), 31 pages. https://doi.org/10.1145/3331445

    doi:10.1145/3331445 2019

Show all 45 references
  1. [10]

    2004.Approximation by algebraic numbers

    Yann Bugeaud. 2004.Approximation by algebraic numbers. Vol. 160. Cambridge University Press. https://doi.org/10. 1112/S0024609305215163

    2004

  2. [11]

    Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of Conjunctive Regular Path Queries with Inverse. InProceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR). Morgan Kaufmann...

    2000

  3. [12]

    Consens and Alberto O

    Mariano P. Consens and Alberto O. Mendelzon. 1990. GraphLog: a Visual Formalism for Real Life Recursion. InPro- ceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). Association for Computing Machinery, 404–416. https://doi.org/10.1...

    1990

  4. [13]

    Cruz, Alberto O

    Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood. 1987. A graphical query language supporting recursion. In Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data (SIGMOD). Association for Computing Machinery, 323–330. https://doi.org/10.1145/...

    1987

  5. [14]

    Dannert and Erich Grädel

    Katrin M. Dannert and Erich Grädel. 2021. Semiring Provenance for Guarded Logics. InHajnal Andréka and István Németi on Unity of Science: From Computing to Relativity Theory Through Algebraic Logic. Springer, 53–79. https: //doi.org/10.1007/978-3-030-64187-0_3

    2021 doi

  6. [15]

    Cristina Feier, Tomasz Gogacz, and Filip Murlak. 2024. Evaluating Graph Queries Using Semantic Treewidth. In Proceedings of the 27th International Conference on Database Theory (ICDT) (LIPIcs, Vol. 290). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 22:1–22:20. https://do...

    2024 doi

  7. [16]

    Diego Figueira. 2020. Containment of UC2RPQ: The Hard and Easy Cases. InProceedings of the 23rd International Conference on Database Theory (ICDT) (LIPIcs, Vol. 155). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 9:1–9:18. https://doi.org/10.4230/LIPIcs.ICDT.2020.9

    2020 doi

  8. [17]

    Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner

    Diego Figueira, Adwait Godbole, S. Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner. 2020. Containment of Simple Conjunctive Regular Path Queries. InProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR). 371–380...

    2020 doi

  9. [18]

    Diego Figueira and Rémi Morvan. 2025. Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries. Logical Methods in Computer Science21, 1 (2025). https://doi.org/10.46298/lmcs-21(1:21)2025

    2025 doi

  10. [19]

    Diego Figueira, Rémi Morvan, and Miguel Romero. 2025. Minimizing Conjunctive Regular Path Queries.Proc. ACM Manag. Data3, 2, Article 100 (2025), 25 pages. https://doi.org/10.1145/3725237

    2025 doi

  11. [20]

    Diego Figueira and Varun Ramanathan. 2022. When is the Evaluation of Extended CRPQ Tractable?. InProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). Association for Computing Machinery, 203–212. https://doi.org/10.1145/3517804.3524167

    2022

  12. [21]

    Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoč. 2023. A Researcher’s Digest of GQL. InProceedings of the 26th International Conference on Database Theory (ICD...

    2023 doi

  13. [22]

    Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018. Cypher: An Evolving Query Language for Property Graphs. InProceedings of the 2018 International Conference...

    2018

  14. [23]

    Freydenberger and Nicole Schweikardt

    Dominik D. Freydenberger and Nicole Schweikardt. 2013. Expressiveness and static analysis of extended conjunctive regular path queries.J. Comput. System Sci.79, 6 (2013), 892–909. https://doi.org/10.1016/j.jcss.2013.01.008

    2013 doi

  15. [24]

    Floris Geerts and Juan L. Reutter. 2022. Expressiveness and approximation properties of graph neural networks. InProceedings of the 10th International Conference on Learning Representations (ICLR). OpenReview.net. https: //openreview.net/forum?id=wIzUeM3TAU

    2022

  16. [25]

    Floris Geerts, Jasper Steegmans, and Jan Van den Bussche. 2022. On the Expressive Power of Message-Passing Neural Networks as Global Feature Map Transformers. InProceedings of the 12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS) (Lecture...

    2022 doi

  17. [26]

    Schoenholz, Patrick F

    Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. InProceedings of the 34th International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research, Vol. 70). JMLR...

    2017

  18. [27]

    Martin Grohe. 2024. The Descriptive Complexity of Graph Neural Networks.TheoretiCS3 (2024). https://doi.org/10. 46298/theoretics.24.25

    2024

  19. [28]

    Hamilton, Zhitao Ying, and Jure Leskovec

    William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. InProceedings of the Thirty-first Annual Conference on Neural Information Processing Systems (NeurIPS). 1024–1034. https://proceedings.neurips.cc/paper/2017/hash/5dd9d...

    2017

  20. [29]

    Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. https://www.w3.org/TR/sparql11-query/ W3C Recommendation

    2013

  21. [30]

    Hauke and Przemyslaw Andrzej Walega

    Stan P. Hauke and Przemyslaw Andrzej Walega. 2026. Aggregate-Combine-Readout GNNs Are More Expressive Than Logic𝐶2. InProceedings of the Fortieth AAAI Conference on Artificial Intelligence (AAAI). AAAI Press. https: //arxiv.org/pdf/2508.06091

    2026 arXiv

  22. [31]

    Sammy Khalife and Amitabh Basu. 2024. On the power of graph neural networks and the role of the activation function. (2024). arXiv:2307.04661 [cs.LG] https://arxiv.org/abs/2307.04661

    2024 arXiv

  23. [32]

    Sammy Khalife and Josué Tonelli-Cueto. 2025. Is uniform expressivity too restrictive? Towards efficient expressivity of GNNs. InProceedings of the 13th International Conference on Learning Representations (ICLR). OpenReview.net. https://openreview.net/forum?id=lsvGqR6OTf

    2025

  24. [33]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations (ICLR). OpenReview.net. https://openreview. net/forum?id=SJU4ayYgl

    2017

  25. [34]

    Leonid Libkin, Wim Martens, and Domagoj Vrgoč. 2016. Querying Graphs with Data.J. ACM63, 2, Article 14 (2016), 53 pages. https://doi.org/10.1145/2850413

    2016 doi

  26. [35]

    Joseph Liouville. 1851. Sur des classes très-étendues de quantités dont la valeur n’est ni algébrique, ni même réductible à des irrationnelles algébriques.Journal de mathématiques pures et appliquées16 (1851), 133–142. https: //www.numdam.org/item/JMPA_1851_1_16__133_0/

  27. [36]

    Mendelzon and Peter T

    Alberto O. Mendelzon and Peter T. Wood. 1995. Finding Regular Simple Paths in Graph Databases.SIAM J. Comput. 24, 6 (1995), 1235–1258. https://doi.org/10.1137/S009753979122370X

    1995 doi

  28. [37]

    Matthew Morris and Ian Horrocks. 2025. Sound Logical Explanations for Mean Aggregation Graph Neural Networks. InProceedings of the Thirty-ninth Annual Conference on Neural Information Processing Systems. https://openreview. net/forum?id=7TY89cqLfE

    2025

  29. [38]

    Nerem, Samantha Chen, Sanjoy Dasgupta, and Yusu Wang

    Robert R. Nerem, Samantha Chen, Sanjoy Dasgupta, and Yusu Wang. 2025. Graph neural networks extrapolate out-of-distribution for shortest paths. arXiv:2503.19173 [cs.LG] https://arxiv.org/abs/2503.19173

    2025 arXiv

  30. [39]

    Pierre Nunn, Marco Sälzer, François Schwarzentruber, and Nicolas Troquard. 2024. A Logic for Reasoning about Aggregate-Combine Graph Neural Networks. InProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI). ijcai.org, 3532–3540. http...

    2024 doi

  31. [40]

    Reutter, Miguel Romero, and Moshe Y

    Juan L. Reutter, Miguel Romero, and Moshe Y. Vardi. 2017. Regular Queries on Graph Databases.Theory of Computing Systems61, 1 (2017), 31–83. https://doi.org/10.1007/s00224-016-9676-2

    2017 doi

  32. [41]

    Miguel Romero, Pablo Barceló, and Moshe Y. Vardi. 2017. The homomorphism problem for regular graph patterns. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society, 1–12. https://doi.org/10.1109/LICS.2017.8005106

    2017

  33. [42]

    Marco Sälzer, Przemyslaw Andrzej Walega, and Martin Lange. 2025. The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics. InProceedings of the Thirty-ninth Annual Conference on Neural Information Processing Systems (NeurIPS). https://openreview.net/forum...

    2025

  34. [43]

    Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2009. The Graph Neural Network Model.IEEE Transactions on Neural Networks20, 1 (2009), 61–80. https://doi.org/10.1109/TNN.2008.2005605

    2009

  35. [44]

    Hava Tova Siegelmann and Eduardo D. Sontag. 1995. On the Computational Power of Neural Nets.J. Comput. System Sci.50, 1 (1995), 132–150. https://doi.org/10.1006/jcss.1995.1013 18 Pablo Barceló, Floris Geerts, Matthias Lanzinger, Klara Pakhomenko, and Jan Van den Bussche

    1995

  36. [45]

    Arie Soeteman and Balder ten Cate. 2025. Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization. InProceedings of the Thirty-ninth Annual Conference on Neural Information Processing Systems (NeurIPS). https://openreview.net/forum?id=yvGnOqy0Zf

    2025

  37. [46]

    Petar Veličković and Charles Blundell. 2021. Neural algorithmic reasoning.Patterns2, 7 (2021). https://doi.org/10. 1016/j.patter.2021.100273 A Deferred Proofs for Section 4 Theorem 4.2.Let 𝑒 be anA-MPLang-expression over 𝑑-embeddings of ^-depth𝑛. Then, over the class of𝑑-embed...

    2021

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.