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

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 $n+\mathcal{O}(1)$-bit precision and $\mathcal{O}(n)$ encoded size that accepts a node exactly when its out-degree is even and below $2^n$, while every equivalent GMSC or GGMSC program has binary-encoded size $\Theta (n{2}^n)$. The same family requires exponentially many graded modalities even for any fixed fidelity above $1/2$ 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-$\mathcal{O}(n)$ feedforward GNN of encoded size $m=\mathcal{O}(n^2)$ yields a $2^{\Omega (\sqrt{m})}$ gap, while a depth-one weighted-threshold GNN with $m=\Theta (n)$ yields a $2^{\Omega (m)}$ gap and extends a known graded-modal-logic separation to recursive GMSC. We also prove a $2^n$ state lower bound for counting message-passing automata on a property with an $\mathcal{O}(n)$-size GMSC program and a $\mathrm{poly}(n)$-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.