The Polynomial Counting Capabilities of Message Passing Neural Networks

• URL: http://arxiv.org/abs/2605.10393v1
• Date: Mon, 11 May 2026 11:38:11 GMT
• Title: The Polynomial Counting Capabilities of Message Passing Neural Networks
• Abstract summary: We study the counting capabilities of MPNN beyond linear arithmetic.<n>We show that global counting constraints in node-labelled graphs can be checked using mean MPNN.<n>We also show how formulas with nested modalities can be captured by mean MPNN over graphs with tree-like structures.
• Score: 4.61988967916659
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks [11.313331046805365]
  We show that each formula can be transformed into an equivalent graph neural network (GNN)<n>We also show that the satisfiability problem is PSPACE-complete.
  arXiv  Detail & Related papers  (2024-04-30T21:16:38Z)
• Recurrent Neural Language Models as Probabilistic Finite-state Automata [66.23172872811594]
  We study what classes of probability distributions RNN LMs can represent. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata. These results present a first step towards characterizing the classes of distributions RNN LMs can represent.
  arXiv  Detail & Related papers  (2023-10-08T13:36:05Z)
• On the Correspondence Between Monotonic Max-Sum GNNs and Datalog [19.288835943223816]
  We study data transformations based on graph neural networks (GNNs) We study the expressivity of monotonic max-sum GNNs, which cover a subclass of GNNs with max and sum aggregation functions.
  arXiv  Detail & Related papers  (2023-05-29T11:13:38Z)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  We show that graph queries can be computed by a bounded-size family of graph neural networks (GNNs)<n>GNNs are definable in the guarded fragment of first-order logic with counting and with built-in relations.<n>We show that queries computable by a single GNN with piecewise linear activations and rational weights are definable in GFO+C without built-in relations.
  arXiv  Detail & Related papers  (2023-03-08T14:32:59Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNN is a universal framework to scale up any convolution-based GNNs using Vector Quantization (VQ) without compromising the performance. Our framework avoids the "neighbor explosion" problem of GNNs using quantized representations combined with a low-rank version of the graph convolution matrix.
  arXiv  Detail & Related papers  (2021-10-27T11:48:50Z)
• Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
  Graph Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs. In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues, the MPNN is theoretically more powerful than the 1-WL test.
  arXiv  Detail & Related papers  (2021-06-08T13:26:56Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
  arXiv  Detail & Related papers  (2020-12-06T03:42:54Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  We study the power of graph neural networks (GNNs) via their ability to count attributed graph substructures. We distinguish between two types of substructure counting: inducedsubgraph-count and subgraphcount-count, and both positive and negative answers for popular GNN architectures.
  arXiv  Detail & Related papers  (2020-02-10T18:53:30Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  Markov Logic Networks (MLNs) can be used to address many knowledge graph problems. Inference in MLN is computationally intensive, making the industrial-scale application of MLN very difficult. We propose a graph neural network (GNN) variant, named ExpressGNN, which strikes a nice balance between the representation power and the simplicity of the model.
  arXiv  Detail & Related papers  (2020-01-29T23:34:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.