{"id":"e51e39b4-e218-4462-8276-218068c7a618","arxiv_id":"2508.06091","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Aggregate-combine-readout GNNs are strictly more expressive than the two-variable counting logic C2 over both undirected and directed graphs.","lead":"The paper proves that graph neural networks with an aggregate-combine-readout architecture can distinguish more graphs than can be expressed in the counting logic C2. This settles an open problem about the logical limits of graph neural networks posed in 2020.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Full proof is absent from manuscript; without it, the claimed strict separation from C2 cannot be checked, and the result hinges on the exact readout definition.","rationale":"The reader correctly marks the paper UNVERDICTED because only the abstract was available. My stress-test agrees that the central claim is unverifiable in the current artifact, and additionally flags that the missing proof is a silent omission—no mathematical argument is present to scrutinize. The reader's concern about the precise readout definition is a plausible subcase of this omission: if the readout is nonstandard, the separation might not solve the open problem posed by Barceló et al. However, without the full text, this remains a hypothesis rather than a demonstrated flaw. Therefore I do not alter the verdict; the paper stays UNVERDICTED pending full-text inspection. The proposed concrete test—retrieving the full text and checking the GNN definition and one separating property—is the minimal check that would turn the abstract into a verifiable claim.","tokens_in":1859,"tokens_out":5614,"duration_ms":69610,"concrete_test":"Retrieve the full text from arXiv:2508.06091 and inspect the proof of the main theorem. Verify that the GNN architecture used in the construction has the same aggregate-combine-readout semantics as in Barceló et al. (2020)—specifically a fixed global readout such as sum over all node features with standard real-valued features and fixed-depth layers—and that the separating graph pair is finite and recognized by this GNN. Then independently confirm the C2 inexpressibility of the separating invariant, e.g., by checking that the pair is not distinguished by any C2 formula using a small-model exhaustive test or a C2 model-checking algorithm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that aggregate-combine-readout GNNs are strictly more expressive than C2—depends entirely on a proof that is not present in the submitted content. Only the abstract and references appear; there is no theorem statement, no construction of a GNN capturing a C2-inexpressible property, and no demonstration of C2 inexpressibility. The abstract mentions that the result holds over directed and undirected graphs and yields infinitary-logic insights, but the actual argument is unverifiable. The most specific technical concern is whether the 'readout' in the GNN architecture is the standard global sum aggregation used in Barceló et al.'s open question. If the readout is instead a more powerful operator (e.g., arbitrary multiset functions or graph-size-dependent operations), the strict separation could be trivial or not address the open problem. Since we cannot inspect the proof, the claim is currently unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":2073,"tokens_out":2864,"duration_ms":34501,"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":[{"comment":"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.","section":"Full text"},{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Definitions / readout"}],"minor_comments":[{"comment":"There is a typo: 'has been been initialised' should read 'has been initialised'.","section":"Abstract"},{"comment":"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.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"As submitted, this is an abstract-only manuscript with no technical content. I have recommended major revision because the missing proof is a fixable omission in principle, but the editor may want to confirm that this is the intended submission. If a full paper exists, it should be submitted in its entirety; otherwise, the claim should not be treated as established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nI read the submission as it stands: an abstract and a reference list, with no body. The claim is that aggregate-combine-readout GNNs are strictly more expressive than C2, settling an open problem posed by Barceló et al. (2020). If that is actually proved, it is a genuinely useful result for the GNN-logic community. But I can't verify anything, because the proof is not in the manuscript I have. There is no theorem statement, no construction, no C2-inexpressibility argument, no definition of the readout. The entire evaluation rests on the abstract.\n\nWhat the paper does well: it identifies the exact open problem, states a clean separation (not just a characterization), says it holds over directed and undirected graphs, and mentions an infinitary-logic consequence. The reference list includes the expected prior work—Cai-Fürer-Immerman, Weisfeiler-Leman, the Barceló paper, and recent GNN-logic papers. The framing is sensible.\n\nThe soft spot is as large as it gets: no proof. More specifically, the separation depends entirely on the readout definition. If the readout is the standard global sum aggregation used in the open problem, the construction has to be subtle. If it's something more powerful, the separation might not be about the same architecture. The abstract doesn't clarify. There's also a minor typo (\"been been\"), but that's irrelevant.\n\nWho is this for? People working on logical characterizations of GNNs. If the proof is correct, it would be worth citing. But right now I wouldn't cite it as a proven result, and I wouldn't base anything on it. I'd want to see the full version. My take: ask the authors for the complete manuscript. If it has the proof, send it to a serious referee—it's important enough to spend referee time on. If the full submission is what I saw, it's an extended abstract, not a paper.","headline":"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.","tokens_in":2521,"tokens_out":5915,"would_cite":false,"duration_ms":64061,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03B70","68R10","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"Aggregate-combine-readout GNNs are strictly more expressive than the counting logic C2.","keywords":["graph neural networks","logical expressiveness","C2 logic","two-variable counting logic","aggregate-combine-readout","finite model theory","infinitary logic","directed graphs"],"falsifier":"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.","tokens_in":1789,"feed_emoji":"🧠","tokens_out":6516,"duration_ms":75944,"temperature":0.7,"pith_summary":"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.","feed_headline":"Readout-equipped GNNs out-logic C2","feed_subtitle":"A 2020 open problem falls: global readout adds real expressiveness in undirected and directed graphs.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[],"fun_headline_variants":["GNNs with readout beat counting logic C2","ACR GNNs exceed C2's logical reach","Open problem solved: readout GNNs outpower logic C2","Aggregate-combine-readout GNNs transcend C2 logic","Why readout GNNs escape logic C2's grasp"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["GNNs with readout beat counting logic C2","ACR GNNs exceed C2's logical reach","Open problem solved: readout GNNs outpower logic C2","Aggregate-combine-readout GNNs transcend C2 logic","Why readout GNNs escape logic C2's grasp"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000162,"raw_usage":{"total_tokens":1051,"prompt_tokens":692,"completion_tokens":359,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":436,"completion_tokens_details":{"reasoning_tokens":271}},"tokens_in":436,"tokens_out":359,"duration_ms":3569,"temperature":1.0,"reasoning_tokens":271,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T22:55:15.022385+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}