Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats

• URL: http://arxiv.org/abs/2405.14606v4
• Date: Fri, 02 May 2025 10:39:23 GMT
• Title: Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
• Authors: Veeti Ahvonen, Damian Heiman, Antti Kuusisto, Carsten Lutz,
• Abstract summary: 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.
• Score: 6.176021290715425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In pioneering work from 2019, Barcel\'o and coauthors identified logics that precisely match the expressive power of constant iteration-depth graph neural networks (GNNs) relative to properties definable in first-order logic. In this article, we give exact logical characterizations of recurrent GNNs in two scenarios: (1) in the setting with floating-point numbers and (2) with reals. 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, also with counting. These results give exact matches between logics and GNNs in the recurrent setting without relativising to a background logic in either case, but using some natural assumptions about floating-point arithmetic. Applying our characterizations, we also prove that, relative to graph properties definable in monadic second-order logic (MSO), our infinitary and rule-based logics are equally expressive. This implies that recurrent GNNs with reals and floats have the same expressive power over MSO-definable properties and shows that, for such properties, also recurrent GNNs with reals are characterized by a (finitary!) rule-based modal logic. In the general case, in contrast, the expressive power with floats is weaker than with reals. In addition to logic-oriented results, we also characterize recurrent GNNs, with both reals and floats, via distributed automata, drawing links to distributed computing models.

Related papers

• Logic-Parametric Neuro-Symbolic NLI: Controlling Logical Formalisms for Verifiable LLM Reasoning [13.291627429657412]
  We propose a logic-parametric framework for neuro-symbolic natural language inference.<n>We embed a range of classical and non-classical formalisms into higher-order logic.<n>We show that logic-internal strategies can consistently improve performance.
  arXiv  Detail & Related papers  (2026-01-09T10:47:30Z)
• 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)
• Expressive Power of Graph Transformers via Logic [7.89576199021427]
  We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson ( 2020) and GPS-networks by Ramp'asek et al. (2022)<n>With reals, we show that GPS-networks have the same expressive power as graded modal logic (GML) with the global modality.<n>With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality.
  arXiv  Detail & Related papers  (2025-08-01T20:59:13Z)
• Logical Characterizations of GNNs with Mean Aggregation [7.582794029746496]
  We study the expressive power of graph neural networks (GNNs) with mean as the aggregation function.<n>In the non-uniform setting, we show that such GNNs have exactly the same expressive power as ratio modal logic.<n>In the uniform setting, we show that the expressive power relative to MSO is exactly that of alternation-free modal logic.
  arXiv  Detail & Related papers  (2025-07-24T07:21:49Z)
• The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics [4.096453902709292]
  We study the logical characterisation of temporal GNNs by connecting them to two-dimensional product logics.<n>We show that the expressive power of temporal GNNs depends on how graph and temporal components are combined.
  arXiv  Detail & Related papers  (2025-05-17T09:34:57Z)
• 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 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) 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)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  We prove that the graph queries that can be computed by a bounded-depth family of GNNs are definable in the guarded GFO+C fragment of first-order logic with counting and with built-in relations. 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)
• 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)
• Neuro-Symbolic Inductive Logic Programming with Logical Neural Networks [65.23508422635862]
  We propose learning rules with the recently proposed logical neural networks (LNN) Compared to others, LNNs offer strong connection to classical Boolean logic. Our experiments on standard benchmarking tasks confirm that LNN rules are highly interpretable.
  arXiv  Detail & Related papers  (2021-12-06T19:38:30Z)
• Logic-Driven Context Extension and Data Augmentation for Logical Reasoning of Text [65.24325614642223]
  We propose to understand logical symbols and expressions in the text to arrive at the answer. Based on such logical information, we put forward a context extension framework and a data augmentation algorithm. Our method achieves the state-of-the-art performance, and both logic-driven context extension framework and data augmentation algorithm can help improve the accuracy.
  arXiv  Detail & Related papers  (2021-05-08T10:09:36Z)
• Logical Neural Networks [51.46602187496816]
  We propose a novel framework seamlessly providing key properties of both neural nets (learning) and symbolic logic (knowledge and reasoning) Every neuron has a meaning as a component of a formula in a weighted real-valued logic, yielding a highly intepretable disentangled representation. Inference is omni rather than focused on predefined target variables, and corresponds to logical reasoning.
  arXiv  Detail & Related papers  (2020-06-23T16:55:45Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  We study the task of logical generalization using graph neural networks (GNNs) Our benchmark suite, GraphLog, requires that learning algorithms perform rule induction in different synthetic logics. We find that the ability for models to generalize and adapt is strongly determined by the diversity of the logical rules they encounter during training.
  arXiv  Detail & Related papers  (2020-03-14T05:45:55Z)

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.