Pith. sign in

REVIEW 3 major objections 2 minor 1 cited by

Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2

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

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

Pith's one-line read Aggregate-combine-readout GNNs are strictly more expressive than the counting logic C2.

desk verdict The abstract promises a major separation result, but the manuscript contains only the abstract and references—so the proof is absent and the claim is currently unverifiable. read the letter →

arxiv 2508.06091 v1 pith:KZZKV72N submitted 2025-08-08 cs.AI

Stan P Hauke , Przemys{l}aw Andrzej Wa{l}ęga This is my paper · ORCID
classification cs.AI MSC 03B7068R1068T07
keywords graphneuralnetworkslogicalexpressivenessC2logictwo-variablecountingaggregate-combine-readoutfinitemodeltheoryinfinitarydirectedgraphs
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 settles a question left open since a 2020 result first linked graph neural networks to counting logic: does adding a global readout keep these networks exactly as expressive as C2, or does the readout add power? It proves the readout adds power. There is a graph property that an aggregate-combine-readout GNN computes but no sentence of C2 can define, and the same separation holds over undirected and directed graphs. The result matters because C2 was the best known logical description of these networks, so the true boundary must be drawn at a stronger logic.

What carries the argument

The object doing the work is the aggregate-combine-readout computation itself: each node updates a feature by combining its previous feature with an aggregate of neighboring features, and after all layers one global readout function summarizes the multiset of final node features into a graph-level verdict. The proof uses this final readout as the source of extra power, producing a graph invariant that separates two graphs even though their local recursive computations are indistinguishable by C2.

What would settle it

Take the graph property used in the separation proof. If a single C2 sentence can be written that has exactly the same truth value as the GNN's readout on every graph, the strict separation fails. Concretely, on the paper's constructed graph family, check whether there is a pair of graphs that agree on every C2 sentence but receive different readout values from the GNN; finding such a pair confirms the claim, while showing every GNN-distinguished pair is also C2-distinguished would refute it.

Watch

Extended reading notes

Core claim

The central claim is that aggregate-combine-readout GNNs are not exactly captured by C2. C2 is the two-variable fragment of first-order logic with counting quantifiers, and it was the strongest logic previously proposed as a characterization of such networks. The paper constructs a graph property that a network of this form decides but that no C2 sentence expresses, and shows the construction works whether edges are undirected or directed. Because the separating property exists, C2 cannot be the final logical characterization of these GNNs. The proof also yields a purely logical consequence: new limits on what infinitary logics can express on finite graphs.

Load-bearing premise

The separation rests on the specific formal definition of the global readout; if the permitted aggregation were different, the constructed network might no longer count as an aggregate-combine-readout GNN and the proof would not apply.

Editorial extensions

If this is right

  • The open problem from the 2020 characterization result is closed: C2 cannot exactly characterize aggregate-combine-readout GNNs.
  • Because the separation holds for both undirected and directed graphs, the extra expressiveness is not an artifact of edge orientation.
  • Any future logical characterization of these GNNs must use a language strictly stronger than C2, at least on finite graphs.
  • The proof yields limits on infinitary logics that are independent of the neural network motivation.

Reading between the lines

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

  • An untested extension is that other global-pooling models, such as graph transformers, may inherit similar extra expressiveness because their attention layers also pool information across all nodes.
  • If the precise aggregation function in the readout is the load-bearing choice, then sum, mean, and max readouts could yield different logical boundaries, forming a spectrum of expressiveness worth mapping.
  • The separating property likely turns on a global cardinality or global-sum condition, which would explain why a local counting logic like C2 misses it; identifying the exact counting-logic fragment that captures these GNNs would sharpen the boundary further.
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 / 2 minor

Summary. The paper's abstract announces a solution to a known open problem: aggregate-combine-readout graph neural networks (GNNs) are claimed to be strictly more expressive than the counting two-variable logic C2, over both undirected and directed graphs, with additional consequences for infinitary logics. The submitted manuscript, however, contains only an abstract and a reference list. No definitions, theorem statements, constructions, or proof are present, so the central claim cannot be checked from the submitted content.

Significance. If the claim is correct, it would resolve a prominent open problem in the logical characterisation of GNNs, going beyond the aggregate-combine case of Barceló et al. (2020). It would also be a rare separation between a counting logic with a global readout and full C2, with potential implications for finite-variable counting logics and infinitary logics. These would be significant contributions. However, because the technical content is entirely absent, the significance is currently conditional on a proof that is not verifiable in this submission.

major comments (3)
  1. [Full text] The manuscript contains no body: no definitions, no theorem statement, and no proof. The central claim—that aggregate-combine-readout GNNs strictly exceed C2—is therefore unsupported. The authors must supply the full technical development: precise definitions of aggregate-combine-readout GNNs, the relevant fragment of C2, the construction separating them, and a rigorous proof of inexpressibility. Without these, the announced result cannot be checked.
  2. [Abstract] The abstract claims results for both undirected and directed graphs, and also mentions insights into infinitary logics. No statements of these results are given. Directed graph extensions often require different arguments (e.g., oriented color refinement or different bisimulation notions), and the infinitary-logic consequences need explicit model-theoretic proofs. These are load-bearing subclaims that must be stated and proved, not merely mentioned.
  3. [Definitions / readout] The expressiveness separation depends on the precise global readout allowed in the GNN architecture. The abstract does not say whether the readout is the standard sum/aggregation over all node states, as in Barceló et al.'s open question, or a more powerful operator such as arbitrary multiset functions or graph-size-dependent operations. If the readout is stronger than the standard one, the strict separation may be trivial or not address the intended problem. The proof must fix the readout definition and demonstrate the separation under that exact definition.
minor comments (2)
  1. [Abstract] There is a typo: 'has been been initialised' should read 'has been initialised'.
  2. [References] The reference list formatting is inconsistent; author names, titles, and venues are run together without proper spacing in several entries. This should be corrected to conform to the journal style.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reasoning identifiable; the abstract states a theorem but the submitted text contains no derivation chain to audit.

full rationale

The submitted content consists only of the abstract and a reference list; there is no theorem statement, construction, proof, or equation in the manuscript for this version. The abstract's central claim—that aggregate-combine-readout GNNs strictly exceed C2 in logical expressiveness—is asserted as a theorem against external, independently defined notions (C2 and GNN architectures from Barceló et al. 2020). No part of the provided text defines a target notion in terms of the conclusion, fits a parameter and then renames it as a prediction, or imports a load-bearing uniqueness argument from the present authors' own prior work. The reference list is dominated by external work; even where researchers with overlapping communities appear (e.g., Lutz), no specific self-citation is invoked to justify the claimed separation. The absence of the actual proof is a serious completeness or verifiability concern, but it is not circularity: lack of evidence of circular reasoning is not itself circular reasoning. Under the rule that circularity must be exhibited by quotation and specific reduction, no such step can be identified, so the appropriate finding is no significant circularity, score 0.

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

The paper is a theoretical proof, so no free parameters or invented entities are expected. The main axioms are the definitions of the GNN variant and the logic C2, both standard in the literature. The proof likely assumes these definitions as given.

assumptions (2)
  • domain assumption Definitions of aggregate-combine-readout GNNs follow Barceló et al. (2020).
    The separation proof compares against a specific GNN architecture; if the architecture is not the standard one, the conclusion may not hold.
  • standard math C2 is the two-variable fragment of first-order logic with counting quantifiers, with standard finite model theory semantics.
    The paper references Barceló et al. for the background; this is a standard logical language.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2." pith.science (2026). https://pith.science/paper/KZZKV72N

@misc{pith2026250806091,
  author       = {Pith},
  title        = {Pith review of: Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KZZKV72N}},
  note         = {Machine review of arXiv:2508.06091}
}
read the original abstract

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 been initialised by an influential result of Barcel\'o 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 full 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 the logical expressiveness of aggregate-combine-readout GNNs strictly exceeds that of 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    cs.LG 2025-12 conditional novelty 7.0 of 10

    GNNs with ReLU can compute numerical graph queries that GNNs with bounded, saturating activations cannot, even when both use linear layers.

Reference graph

Works this paper leans on

6 extracted references · 5 canonical work pages · cited by 1 Pith paper

  1. [1]

    Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats

    Ahvonen,V.;Heiman,D.;Kuusisto,A.;andLutz,C.2025. LogicalCharacterizationsofRecurrentGraphNeuralNet- workswithRealsandFloats. arXiv:2405.14606. Babai, L.; and Kucera, L

    work page Pith review arXiv 2025

  2. [5]

    Tena Cucala, D

    Logical Characteriza- tions of GNNs with Mean Aggregation.arXiv preprint arXiv:2507.18145. Tena Cucala, D. J.; and Cuenca Grau, B

    arXiv

  3. [6]

    Ying, R.; He, R.; Chen, K.; Eksombatchai, P.; Hamilton, W.L.;andLeskovec,J.2018

    How PowerfulareGraphNeuralNetworks? In Proc.ofICLR . Ying, R.; He, R.; Chen, K.; Eksombatchai, P.; Hamilton, W.L.;andLeskovec,J.2018. GraphConvolutionalNeural NetworksforWeb-ScaleRecommenderSystems. In Proc. ofKDD,974–983. Zhang, M.; and Chen, Y

    work page 2018

  4. [1992]

    Comb.,12

    An Opti- malLowerBoundonTheNumberofVariablesforGraph Identification. Comb.,12. Chen,C.;Wu,Y.;Dai,Q.;Zhou,H.;Xu,M.;Yang,S.;Han, X.;andYu,Y.2024. ASurveyonGraphNeuralNetworks and Graph Transformers in Computer Vision: A Task- Oriented Perspective. IEEE Trans. Pattern Anal. Mach. Intell.,46(12):10297–10318. Derrow-Pinion, A.; She, J.; Wong, D.; Lange, O.; He...

    work page 2024

  5. [2019]

    InProc.ofAAAI ,4602–4609

    Weisfeiler and Le- man Go Neural: Higher-Order Graph Neural Networks. InProc.ofAAAI ,4602–4609. Nunn, P.; Sälzer, M.; Schwarzentruber, F.; and Troquard, N.2024.ALogicforReasoningaboutAggregate-Combine GraphNeuralNetworks. In Proc.ofIJCAI ,3532–3540. Pflueger, M.; Cucala, D. T.; and Kostylev, E. V

    work page 2024

  6. [2025]

    Trans.Mach.Learn.Res

    Link Prediction with Relational Hypergraphs. Trans.Mach.Learn.Res. Libkin,L.2004. ElementsofFiniteModelTheory .Springer. Lutz,C.;Sattler,U.;andWolter,F.2001. ModalLogicand theTwo-VariableFragment. In Proc.ofCSL ,247–261. Morris,C.;Ritzert,M.;Fey,M.;Hamilton,W.L.;Lenssen, J. E.; Rattan, G.; and Grohe, M

    work page 2004

Pith tools

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