# Graph Neural Networks and Arithmetic Circuits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 27 Feb 2024.

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

- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [The Descriptive Complexity of Graph Neural Networks](https://mlsanity.com/paper/2303.04613/) (2023)
- [Some Might Say All You Need Is Sum](https://mlsanity.com/paper/2302.11603/) (2023)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [On the Correspondence Between Monotonic Max-Sum GNNs and Datalog](https://mlsanity.com/paper/2305.18015/) (2023)
- [On the expressive power of message-passing neural networks as global feature map transformers](https://mlsanity.com/paper/2203.09555/) (2022)
- [Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions](https://mlsanity.com/paper/2305.11833/) (2023)

## Built on by (most cited first, 3 of 3)

- [A Logical View of GNN-Style Computation and the Role of Activation Functions](https://mlsanity.com/paper/2512.19332/) (2025)
- [Recurrent Graph Neural Networks and Arithmetic Circuits](https://mlsanity.com/paper/2603.05140/) (2026)
- [Average Attention Transformers and Arithmetic Circuits](https://mlsanity.com/paper/2605.04683/) (2026)

## Abstract (arXiv)

We characterize the computational power of neural networks that follow the graph neural network (GNN) architecture, not restricted to aggregate-combine GNNs or other particular types. We establish an exact correspondence between the expressivity of GNNs using diverse activation functions and arithmetic circuits over real numbers. In our results the activation function of the network becomes a gate type in the circuit. Our result holds for families of constant depth circuits and networks, both uniformly and non-uniformly, for all common activation functions.