# The logic of rational graph neural networks

arXiv: https://arxiv.org/abs/2310.13139 · HTML: https://mlsanity.com/paper/2310.13139/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 21 references that are in the map.
- First posted on arXiv 19 Oct 2023.

## Builds on (most cited first, 14 of 14)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Graph neural networks for materials science and chemistry](https://mlsanity.com/paper/2208.09481/) (2022)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Rational neural networks](https://mlsanity.com/paper/2004.01902/) (2020)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm](https://mlsanity.com/paper/2203.00638/) (2022)
- [Graph Neural Network Reinforcement Learning for Autonomous Mobility-on-Demand Systems](https://mlsanity.com/paper/2104.11434/) (2021)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)
- [Some Might Say All You Need Is Sum](https://mlsanity.com/paper/2302.11603/) (2023)
- [Decoding the Protein-ligand Interactions Using Parallel Graph Neural Networks](https://mlsanity.com/paper/2111.15144/) (2021)
- [On the power of graph neural networks and the role of the activation function](https://mlsanity.com/paper/2307.04661/) (2023)

## Abstract (arXiv)

The expressivity of Graph Neural Networks (GNNs) can be described via appropriate fragments of the first order logic. Any query of the two variable fragment of graded modal logic (GC2) interpreted over labeled graphs can be expressed using a Rectified Linear Unit (ReLU) GNN whose size does not grow with graph input sizes [Barcelo & Al., 2020]. Conversely, a GNN expresses at most a query of GC2, for any choice of activation function. In this article, 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, answering a open question formulated by [Grohe, 2021]. This result is also in contrast with the efficient universal approximation properties of rational feedforward neural networks investigated by [Boull'e & Al., 2020]. 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.