Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2

• URL: http://arxiv.org/abs/2508.06091v1
• Date: Fri, 08 Aug 2025 07:35:35 GMT
• Title: Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2
• Authors: Stan P Hauke, Przemysław Andrzej Wałęga,
• Abstract summary: We prove that aggregate-combine-readout GNNs strictly exceed that of C2.<n>Our work also leads to purely logical insights on the expressive power of infinitary logics.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In recent years, there has been growing interest in understanding the expressive power of graph neural networks (GNNs) by relating them to logical languages. This research has been been initialised by an influential result of Barcel\'o et al. (2020), who showed that the graded modal logic (or a guarded fragment of the logic C2), characterises the logical expressiveness of aggregate-combine GNNs. As a ``challenging open problem'' they left the question whether full C2 characterises the logical expressiveness of aggregate-combine-readout GNNs. This question has remained unresolved despite several attempts. In this paper, we solve the above open problem by proving that the logical expressiveness of aggregate-combine-readout GNNs strictly exceeds that of C2. This result holds over both undirected and directed graphs. Beyond its implications for GNNs, our work also leads to purely logical insights on the expressive power of infinitary logics.

Related papers

• Position: Message-passing and spectral GNNs are two sides of the same coin [60.47572761832418]
  Graph neural networks (GNNs) are commonly divided into message-passing neural networks (MPNNs) and spectral graph neural networks (SGNs)<n>This paper argues that this divide is mostly artificial, hindering progress in the field.
  arXiv  Detail & Related papers  (2026-02-10T17:53:40Z)
• Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation [22.086161213961244]
  We propose Path-Neighbor enhanced GNN (PN-GNN) to enhance the logical expressive power of GNN.<n>First, we analyze the logical expressive power of existing GNN-based methods and point out the shortcomings of these methods.<n>Then, we theoretically investigate the logical expressive power of PN-GNN, showing that it not only has strictly stronger expressive power than C-GNN but also that its $(k+1)$-hop logical expressiveness is strictly superior to that of $k$-hop.
  arXiv  Detail & Related papers  (2025-11-11T08:59:10Z)
• The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic [8.430502131775723]
  We propose GNN architectures that correspond precisely to prominent fragments of first-order logic (FO)<n>Our results provide a unifying framework for understanding the logical expressiveness of GNNs within FO.
  arXiv  Detail & Related papers  (2025-05-12T19:45:45Z)
• Logical Distillation of Graph Neural Networks [47.859911892875346]
  We present a logic based interpretable model for learning on graphs and an algorithm to distill this model from a Graph Neural Network (GNN) Recent results have shown connections between the expressivity of GNNs and the two-variable fragment of first-order logic with counting quantifiers (C2)
  arXiv  Detail & Related papers  (2024-06-11T10:18:58Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain.<n>We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats [6.176021290715425]
  In this article, we give exact logical characterizations of recurrent graph neural networks (GNNs) in two scenarios.<n>For floats, the formalism matching recurrent GNNs is a rule-based modal logic with counting, while for reals we use a suitable infinitary modal logic.<n>Applying our characterizations, we prove that, relative to graph properties definable in monadic second-order logic, our infinitary and rule-based logics are equally expressive.
  arXiv  Detail & Related papers  (2024-05-23T14:19:21Z)
• 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)
• The logic of rational graph neural networks [0.7614628596146602]
  We prove that some GC2 queries of depth $3$ cannot be expressed by GNNs with any rational activation function. This shows that not all non-polynomial activation functions confer GNNs maximal expressivity. We also present a rational subfragment of the first order logic (RGC2), and prove that rational GNNs can express RGC2 queries uniformly over all graphs.
  arXiv  Detail & Related papers  (2023-10-19T20:32:25Z)
• Discourse-Aware Graph Networks for Textual Logical Reasoning [142.0097357999134]
  Passage-level logical relations represent entailment or contradiction between propositional units (e.g., a concluding sentence) We propose logic structural-constraint modeling to solve the logical reasoning QA and introduce discourse-aware graph networks (DAGNs) The networks first construct logic graphs leveraging in-line discourse connectives and generic logic theories, then learn logic representations by end-to-end evolving the logic relations with an edge-reasoning mechanism and updating the graph features.
  arXiv  Detail & Related papers  (2022-07-04T14:38:49Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• 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.