NeurIPS 2024poster2 citations
Graph Neural Networks and Arithmetic Circuits
Timon Barlag, Vivian Holzapfel, Laura Strieker, Jonni Virtema, Heribert Vollmer
Abstract
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.
Machine LearningGraph Neural NetworksArithmetic CircuitsComputational Complexity
BibTeX
@inproceedings{
barlag2024graph,
title={Graph Neural Networks and Arithmetic Circuits},
author={Timon Barlag and Vivian Holzapfel and Laura Strieker and Jonni Virtema and Heribert Vollmer},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=0ZeONp33f0}
}