Graph Neural Networks and Arithmetic Circuits
Not on the map. Why?
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.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 10 of its 30 references that are in the map. First posted on arXiv 27 Feb 2024.
Builds on
10 of 30 references.
References · 10
- 2017Neural Message Passing for Quantum Chemistrycited by 3,460
- 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
- 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
- 2023The Descriptive Complexity of Graph Neural Networkscited by 26
- 2023Some Might Say All You Need Is Sumcited by 21
- 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
- 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
- 2023On the Correspondence Between Monotonic Max-Sum GNNs and Datalogcited by 12
- 2022On the expressive power of message-passing neural networks as global feature map transformerscited by 8
- 2023Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functionscited by 3
Built on by
Citing papers per year: 2025: 1; 2026: 2.
3 papers.