Pith. sign in

REVIEW 15 references

Towards Understanding the Expressive Power of GNNs with Global Readout

T0 review · reviewed 2026-05-09 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Sum aggregation plus readout in ACR-GNNs captures FO properties outside C2 on directed and undirected graphs, while bounded local aggregation or bounded degree restores exact match to graded modal logic with global counting.

arxiv 2604.22870 v1 submitted 2026-04-23 cs.LG cs.AIcs.LO

Maurice Funk , Daumantas Kojelis This is my paper · ORCID
classification cs.LGcs.AIcs.LO
keywords gnnsreadoutaggregationacr-gnnsexpressiveglobalpowerproperties
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

Graph neural networks update node features by sending messages along edges, combining them locally, and then reading out a global summary. The authors study which logical properties of graphs these networks can distinguish or compute. C2 is a restricted logic using only two variables plus counting quantifiers. They prove that when the local combination step uses ordinary sum and the final readout also sums, the networks can recognize certain first-order properties that no C2 formula can express. This holds for both directed and undirected graphs and improves on earlier work that required specially designed aggregation functions. They then show two natural restrictions that bring the networks back into exact alignment with a different logic: graded modal logic augmented with global counting modalities. One restriction limits how much local aggregation can mix information; the other limits each node to a bounded number of neighbors. Under either restriction the networks capture precisely the properties definable in that graded modal logic. The results therefore give both a lower bound showing how far GNNs can exceed C2 and an upper bound showing when they stay inside a well-understood fragment.
Extended reading notes

Core claim

sum aggregation and readout suffice for GNNs to capture FO properties that cannot be expressed in the logic C2 on both directed and undirected graphs

Load-bearing premise

That the standard sum functions (without special crafting) are used for both local aggregation and global readout, as opposed to the specially designed functions in the cited prior work

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

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

The paper rests on standard background results from first-order logic, modal logic, and graph theory; no free parameters, no invented entities, and no ad-hoc axioms beyond those already accepted in the field.

assumptions (1)
  • standard math Standard semantics of first-order logic with counting and graded modal logic on finite graphs
    Invoked throughout the characterizations of FO properties and C2 equivalence

how reviews work

0 comments
Cite this review

Pith. "Pith review of Towards Understanding the Expressive Power of GNNs with Global Readout." pith.science (2026). https://pith.science/paper/2604.22870

@misc{pith2026260422870,
  author       = {Pith},
  title        = {Pith review of: Towards Understanding the Expressive Power of GNNs with Global Readout},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.22870}},
  note         = {Machine review of arXiv:2604.22870}
}
read the original abstract

We study the expressive power of message-passing aggregate-combine-readout graph neural networks (ACR-GNNs). Particularly, we focus on the first-order (FO) properties expressible by this formalism. While a tight logical characterisation remains a difficult open question, we make two contributions towards answering it. First, we show that sum aggregation and readout suffice for GNNs to capture FO properties that cannot be expressed in the logic C2 on both directed and undirected graphs. This strengthens known results by Hauke and Wa{\l}{\k e}ga (2026) where aggregation and readout functions are specially crafted for the task. Second, we identify two natural ways of restoring characterisability (with regard to C2) for ACR-GNNs. One option is to limit local aggregation (without imposing restrictions on global readout), whilst the second is to run ACR-GNNs over graphs of bounded degree (but unbounded size). In both cases, the FO properties captured by GNNs are exactly those definable by a formula in graded modal logic with global counting modalities. Our results thus establish an innate lower- and upper-bound in terms of how far (fragments of) C2 can be taken to characterise GNNs, and imply that is indeed the unbounded interaction of aggregation and readout that pushes the logical expressive power of GNNs above C2.

Figures

Figures reproduced from arXiv: 2604.22870 by the authors.

Figure 1
Figure 1. A strict linear order G (left) over vertices {1, 2, 3} and its gadgetisation Ge (right). Vertex colourings indicate the features attributed by fe. tv components. We think of edges in Ee involving tv as in￾coming, and edges having sv as outgoing from v. The ver￾tices Veid help identifying which pairs of Ves × Vet correspond to a single vertex in V . The feature embedding fekeeps track of of which vertex is in which o… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    How Expressive Are Graph Neural Networks in the Presence of Node Identifiers? Tena Cucala, D.; Cuenca Grau, B.; Motik, B.; and Kostylev, E. V . 2023. On the Correspondence between Monotonic Max-Sum GNNs and Datalog. InProceedings of the 20th International Conference on Principles of Knowledge Rep- resentation and Reasoning, KR 2023, 658–667. Wał˛ ega, P. ...

    work page arXiv 2023

  2. [2]

    , u(k) 1 ∈V 1 withk≤c there is some distinctu (1) 2 ,

    (forth) for every distinctu (1) 1 , . . . , u(k) 1 ∈V 1 withk≤c there is some distinctu (1) 2 , . . . , u(k) 2 ∈V 2 s.t.(v 1, u(i) 1 )∈ E1 iff(v 2, u(i) 2 )∈E 2, andG 1, u(i) 1 ≡L−1,c G2, u(i) 2

    work page

  3. [3]

    in the middle

    (back) for every distinctu (1) 2 , . . . , u(k) 2 ∈V 2 withk≤c there is someu (1) 1 , . . . , u(k) 1 ∈V 1 s.t.(v 1, u(i) 1 )∈E 1 iff (v2, u(i) 2 )∈E 2, andG 1, u(i) 1 ≡L−1,c G2, u(i) 2 ; it being understood thatL≥0,c≥1and the back and forth conditions apply only whenL≥1. In the literature, the above relation is commonly referred to as theL-turn 2-pebblec-...

    work page 1996

  4. [4]

    Then,φmust be invari- ant under∼ L,c,∗ ∃ , whereLis the number of layers inN (Lemma 16)

    Supposeφis captured by an ACR-GNNNwithc- bounded aggregation functions. Then,φmust be invari- ant under∼ L,c,∗ ∃ , whereLis the number of layers inN (Lemma 16)

    work page

  5. [5]

    predictably

    Every graphG= (V, E, f)has a companion graph bG= (V, bE, f)such thatG, u∼ L,c,∗ ∃ bG, ufor allu∈Vand in which elements behave “predictably”. Thus,G, v|=φ iff bG, v|=φ(Lemmas 18, 19, 32, and 33)

    work page

  6. [6]

    canonical

    Havingφinvariant under∼ L,c,∗ ∃ we obtain invariance un- der∼ L,c,q′ ∃ as follows. Taking any(G 1, v1),(G 2, v2)as- sume thatG 1, v1 ∼L,c,q′ ∃ G2, v2, it being understood that G1, v1 |=φ. We produce a companion graph bG1 forG 1 such thatbG1, v1 |=φ. Having this, we carefully construct a companion graph bG2 forG 2 (Lemma 35) such that bG1, v1 and bG2, v2 a...

    work page

  7. [7]

    ifn G(v) = 1and(v, w)∈E ⋆, then for eachw ′ ∈V withtp G ∼L,c[w′] = tp G ∼L,c[w]andn G(w′)< n G(w)we have(v, w ′)∈E ⋆

    work page

  8. [8]

    Proof.Let us fix anyv∈Vhavingn G(v) = 1and let G′ be the graphGbut withE ′ :=E\ {(v, u)|u∈ V}

    ifn G(v) = 1and(v, w)∈E ⋆ withn G(w)≥c, then (v, w′)∈E ⋆ for allw ′ ∈Vhavingtp G ∼L,c[w′] = tpG ∼L,c[w]; for allv, w∈V. Proof.Let us fix anyv∈Vhavingn G(v) = 1and let G′ be the graphGbut withE ′ :=E\ {(v, u)|u∈ V}. That is to say,G ′ is the graphGbut with outgoing edges ofvremoved. We completeG ′ so that it satisfies conditions 1–3 with respect tovas foll...

    work page

Show all 15 references
  1. [9]

    iftp G ∼L,c[v]=tpG ∼L,c[u], then(v, w)∈ bE⇔(u, w)∈ bE

  2. [10]

    if(v, w)∈ bE, then for eachw ′ ∈Vwithtp G ∼L,c[w′] = tpG ∼L,c[w]andn G(w′)< n G(w)we have(v, w ′)∈ bE

  3. [11]

    Proof.LetG ⋆ be the graph obtained fromGby applying Lemma 32

    if(v, w)∈ bEandn G(w)≥c, then(v, w ′)∈ bEfor all w′ ∈Vhavingtp G ∼L,c[w′] = tpG ∼L,c[w]; for allu, v, w∈V. Proof.LetG ⋆ be the graph obtained fromGby applying Lemma 32. Notice that Conditions 1, 3, and 4 are already met forv∈Vhavingn G(v) = 1. Fixing some such v∈Vlet us take a...

  4. [12]

    bG2 satisfies the requirements of Lemma 33 with respect toG 2 2.G 1, u1 ∼L,c,q′ ∃ G2, u2 iff bG1, u1 ∼L,c,q′ ∃ bG2, u2

  5. [13]

    if|N bG1,λ out (u1)|< candtp bG1 ∼L,c(u1) = tp bG2 ∼L,c(u2)then |N bG1,λ out (u1)|=|N bG2,λ out (u2)|

  6. [14]

    Proof.We begin by providing an analogue of Lemma 32 for G2

    if|N bG1,λ out (u1)| ≥candtp bG1 ∼L,c(u1) = tp bG2 ∼L,c(u2)then N bG2,λ out (u2) =V λ 2 ; for eachu 1 ∈V 1,u 2 ∈V 2 andλ∈∼ L,c. Proof.We begin by providing an analogue of Lemma 32 for G2. For this purpose, fix someu2 ∈V 2 havingn G2(u2) = 1 and letG ′ 2 be the graphG 2 but wit...

    2004

  7. [15]

    By 1 and (†) we haveG 1, v1 ∼L,c G2, v2

    for eachχ∈X L,c, the number of vertices verticesu 2 ∈ V2 such thatG 2, u2 |=χis exactly|V χ 1 |or at leastc. By 1 and (†) we haveG 1, v1 ∼L,c G2, v2. From 2 we see that at least|V χ 1 |=|V χ 2 |or|V χ 1 |,|V χ 2 | ≥cfor any choice ofχ∈X L,c. By (†) it is then immediate thatG 1...

Pith tools

Reviewed May 9, 2026 · model on record in the stance chip above.