acceptodds
Under review as a conference paper at ICLR 2027

Exponential Succinctness of Finite-Precision GNNs over Graded Modal Substitution Calculus

Abstract

Expressive-equivalence results characterize which node properties different graph models can represent, but not how compactly they can represent them. We study this succinctness question for finite-precision recurrent graph neural networks (GNNs), graded modal substitution calculus (GMSC), its global-counting extension (GGMSC), and bounded finite counting message-passing automata (FCMPAs). Our main result gives an explicit six-dimensional recurrent GNN with -bit precision and encoded size that accepts a node exactly when its out-degree is even and below , while every equivalent GMSC or GGMSC program has binary-encoded size . The same family requires exponentially many graded modalities even for any fixed fidelity above under the uniform distribution over degrees below the cutoff, and the lower bounds hold on both directed and undirected graphs. The separation is not specific to recurrence: a depth- feedforward GNN of encoded size yields a gap, while a depth-one weighted-threshold GNN with yields a gap and extends a known graded-modal-logic separation to recursive GMSC. We also prove a state lower bound for counting message-passing automata on a property with an -size GMSC program and a -size GNN. Together, these results establish exponential succinctness gaps between GNNs and expressively equivalent logical or automata-based representations, driven by arithmetic on neighborhood multiplicities and by the cost of explicit state.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
graph neural networks, message passing, succinctness, graded modal logic, counting automata, descriptive complexity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_fXEhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies representation size among finite-precision GNNs, graded modal substitution calculi, and counting message-passing automata. Its main construction recognizes bounded degree parity using a six-dimensional recurrent GNN with O(n)O(n) encoded parameters, while equivalent threshold-counting programs require Θ(n2n)\Theta(n2^n) bits. Extensions cover approximation, undirected graphs, feedforward computation, and weighted counting. The central proofs withstand independent scrutiny, and executable finite-precision checks support the constructions. The results concern worst-case description length, not trained-model performance or efficient inference.

Critical strengths
  • Bounded parity yields an essentially tight threshold-logic representation bound that survives recursion, sharing, global counting, undirected edges, and fixed approximation fidelity above one half. These extensions rule out natural ways for the target language to evade the result.

  • Recurrent, layered, and depth-one networks separate temporal reuse from arithmetic aggregation. Precision and encoding costs are counted, and executable artifacts plus independent finite-float checks make the positive constructions unusually auditable.

Critical weaknesses
  • It uses growing precision and exponentially large degrees, and the recurrent construction may require exponentially many rounds. The approximation result concerns a prescribed hard distribution. Arithmetic or modular target languages can remove the relevant gap. These acknowledged restrictions limit implications for practical explanation extraction; they do not invalidate the descriptional theorem or create a requirement for unrelated trained-model benchmarks.

  • The weighted family extends an established separation, while the automata lower bound relies on increasing label width and measures explicit states rather than succinct machine descriptions. The paper distinguishes these cases, but they contribute less to the acceptance case than the central parity/recursive-logic result.

Questions for authors

Please see weaknesses

Reviewer_VJbbOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper considers the succinctness comparison between (particular type of) GNNs and corresponding logical calculi, as well as weighted automata. The expressive power results relating them have been established in the literature, but this paper makes a next step, by comparing how succinct they can represent particular properties of graphs. The paper is purely theoretical and shows several (exponential) gaps in succinctness.

Critical strengths

I find the topic of succinctness of GNNs very interesting. Some results regarding transformation between GNNs and logical formalisms are known from the expressive power proofs, but I do not know of any systematic research on succinctness.

Critical weaknesses

First, and most importantly, the paper is written in an inaccessible way. It is not because it is too complex, but because it does not provide details which are essential for a reader to understand the paper. On the other hand, the paper presents and uses a number of concepts that are never explained, which makes the reader confused. As a result I was not able to check the proofs and I find the current form not satisfying basic standards of a research paper.

As for the results, the fact that the results are theoretic is not a problem itself, but it would be interesting to see what is the impact of succinctness gaps. For example if it has any theoretical applications, or impact on practical performance.

In what follows I will mention some places in which paper has problems in writing, which make it very unclear, imprecise, and impossible to me to understand even though I have an expertise in this area.

The introduction uses a lot of unexplained notions, for example at this point it is not clear what does it mean that “Each graded modality tests one threshold in c.”, as it is not even explained what is cc and what is meant by thresholds. Similarly, “R-simple network” is unexplained and non-standard notion, so claiming some result about it is a mistake. The statement “The lower bound allows recursion, binary thresholds, directed acyclic graph (DAG) sharing, and global counting, and remains exponential” is completely unclear, as it is not clear what is “the lower bound” in this context, and what are all the mentioned components. The mentioned “logical gap” is unclear; I believe it is actually about succinctness gap. The statement “At depth one, weighted aggregation yields a 2Ω(m) separation by a two- dimensional slope argument.” is also unclear as it is not explained what “weighted aggregation” is, what does it mean that it yields “separation”, and what “two dimensional slope argument” is.

The description of the main results in Table 1 are unclear and at this stage cannot be understood by a reader as the symbols and notions used therein are not explained.

The setting used in the paper is not explained well. Description of GMSC is incomplete and lacks precision. For example \varphi and \psi are not described, and it is essential. It should be explained that for every XX a program has a base and induction rules. Notions like “rounds” or “graded indices” are used but not explained. Global-counting extension is also not clear as it is not clear where the additional modality can occur and what is \varphi.

Similarly GNN[F] is not well defined; for example it is unclear what is SUM_S, what is x_v^0. Also dd is not defined and it is not clear how \lambda is taken into account by a GNN. Statement “reads out after its finite sequence of transitions” is very imprecise as it is not clear what does it mean to “read out” and what are “transitions”, and what are their sequences. Also, I do not understand the whole paragraph about “encoded parameter size”; it is not explained what is “straight-line circuit over the inputs [p ∈λ(v)]”, what is “clipped-ReLU gate over S” or what are “parity networks”. “Automata witness” occurs also unexplained, so I am not sure what object it is.

Automaton description is also imprecise. For example it is not clear what “distinguished node” is, as it is not specified. The notion of bounded automaton is not precisely formulated. The sentence “The bound excludes small state spaces under every encoding, not compact circuits for π, δ, or F.” remains unclear to me.

I find formulations of the theoretical results imprecise. For example what is a “breakpoint”, the main notion in the first result, is not even described. Also, what are tree and DAG syntax, which were never explained? As a result, in the current form it cannot be understood what Lemma 3.1 claims.

Other results and proofs have similar problems. For example the notion of a GNNs “clock” was not explained but it is heavily used, which makes Theorem 3.2 not accessible. The notion of “Under the explicit-feedforward convention” was never explained. Corollary 3.3 is very unclear too. It seems to refer to the previous theorem but it is unreadable in its current form. For example “For the recurrent family, source size m = Θ(n) forces GMSC size 2Ω(m)” is completely unclear.

Questions for authors

I would be interested to hear your thoughts on the significance of succinctness gaps and how they might be used in future theoretical or experimental research?

Reviewer_VvqjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper compares the succinctness, i.e., how compact a formalism can describe a node property, of recurrent graph neural networks (GNNs) in comparison to graded modal substitution calculus (GMSC) and its global-counting extension as well as message-passing automata. It is shown that GNNs are exponentially more succinct than GMSC and automata for certain properties related to the node degrees.

Critical strengths
  • Interesting research direction: The paper investigates the size of (recurrent) GNNs that is sufficient to express certain node properties. It is useful to understand how the size of architectures compares to other formalisms with equivalent expressive power, as this might have implications on the tractability of, e.g., explainability methods based on such formalisms.
Critical weaknesses
  • Clarity: The paper regularly uses key concepts and terms that are not formally introduced, making it difficult to follow and assess the theoretical contributions. For example, the concept of a clock is never defined, but heavily used throughout the paper. Similarly, Lemma 3.1 uses the terms verdict and breakpoint, which both remain undefined; language is often imprecise (e.g., line 912 it is unclear to which theorem "the theorem" refers to, cc is undefined in line 916, cpc_p and cqc_q are undefined in Table 1). There are also several sentences that are not fully clear to me (e.g., line 953 what does "once the decoder is counted" mean, line 1183 what is the "simple reference implementation", what is a "teacher" in the context of the work).

As a result of the clarity issues, I am not able to judge the soundness of the results (which is also why I chose the score "1").

  • Limitation of theoretical results: The results seem to only hold for specific properties/constructions. For instance, from my current understanding, Theorem 3.2 lets us conclude that GNNs can be more succinct than GMSC, but not that they always are, while line 71 states: "We prove that recurrent finite-precision GNNs are exponentially more succinct than [...] GMSC". It would also help to better understand the implications of your results: If GNNs can represent the same function as their equivalently expressive logic counterparts but at a lower representational cost, could we say anything about, e.g., the (in)tractability of logic-based explanation methods?

Due to my difficulties in judging the soundness of the paper and the actual depth of the theoretical contribution, I am currently not able to accept this paper. However, I am open to changing my score if the soundness of the contribution is confirmed and the clarity issues are resolved.

Questions for authors
  • Does the succinctness for the shown properties allow us to conclude any more general succinctness results? In the paper it is often stated that GNNs are more succinct, but then the bounds are all shown for specific properties.
  • Is nn independent of the graph size? Do the results hold uniformly for graphs of different sizes?
  • Could you explain the significance of the computational study?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.