On Counting Graphs for Modal Logic with Counting

Avijeet Ghosh; François Schwarzentruber

cs.AIOct 19, 2026

On Counting Graphs for Modal Logic with Counting

Authors: Avijeet Ghosh, François Schwarzentruber

Organizations: MC2, LIP, ENS de Lyon, France

Abstract

In this paper, we study the theoretical computational complexity of counting trees and graphs that are classified positively by a graph neural networks, or said equivalently that satisfy a given formula of modal logic with counting. We also study convergence.

Figures & tables

	$n$ unary	$n$ binary
Trees	$\#\mbox{\sc Pspace}$
	Pspace -complete
Graphs	$\#\mbox{\sc P}$ -complete	$\#\mbox{\sc Exptime}$
		Pspace -hard

Figure 1: Complexity results about counting trees (

n

is the branching factor) or graphs (

n

is then the number of vertices).

Panel of Figure 2 — Figure 2: Values of $\mu^{\mathcal{T}}_{n}(\#\varphi_{e}\geq\#\varphi_{o})$ depending on the branching factor $n$ .

GNN Expressivity

Graph neural network expressivity studies which graph structures and functions a model can distinguish or represent, and how its design shapes those limits.

See all 55 papers

The Polynomial Counting Capabilities of Message Passing Neural Networks
May 11, 2026Marco Sälzer, Pascal Bergsträßer, Anthony W. LinGraph Neural Networks Message Passing Neural Networks
1RPTU University Kaiserslautern-Landau · 2Max Planck Institute for Software Systems (MPI-SWS)
Structural Preservation and the Logical Expressiveness of Graph Neural Networks
Jun 16, 2026Przemysław Andrzej Wałęga, Bernardo Cuenca GrauGNN Expressivity
Queen Mary University of London · University of Oxford
The Logical Expressiveness of Topological Neural Networks
Apr 21, 2026Amirreza Akbari, Amauri H. Souza, Vikas GargGraph Neural Networks GNN Expressivity
Aalto University · Federal Institute of Cear´a, 2δ AI · YaiYai Ltd

May 11, 2026J/K move · Enter open · S save

The Polynomial Counting Capabilities of Message Passing Neural Networks

Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin

1RPTU University Kaiserslautern-Landau · 2Max Planck Institute for Software Systems (MPI-SWS)

Graph Neural Networks Message Passing Neural Networks Neural Network Expressivity

Open paper AskPDF arXiv

The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshold or more generally satisfy a linear arithmetic constraint. In this paper, we study the counting capabilities of MPNN beyond linear arithmetic, primarily utilising local and global mean aggregations. In particular, our goal is to tease out conditions required to express extensions of graded modal logic with polynomial counting constraints. We show that global polynomial counting constraints in node-labelled graphs can be checked using mean MPNN under mild assumptions. Checking local constraints is also possible, if we consider formulas with no nested modalities and additionally either (i) permit sum/max aggregations, or (ii) only restrict to regular graphs. We also show how formulas with nested modalities can be captured by mean MPNN over graphs with tree-like structures and similar assumptions.

Abstract

GNN Expressivity

Explore similar work

The Polynomial Counting Capabilities of Message Passing Neural Networks

Structural Preservation and the Logical Expressiveness of Graph Neural Networks

The Logical Expressiveness of Topological Neural Networks