Graph Neural Networks and Arithmetic Circuits

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.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Barlag et al. "Graph Neural Networks and Arithmetic Circuits." Neural Information Processing Systems, 2024. doi:10.52202/079017-0175

Markdown

[Barlag et al. "Graph Neural Networks and Arithmetic Circuits." Neural Information Processing Systems, 2024.](https://mlanthology.org/neurips/2024/barlag2024neurips-graph/) doi:10.52202/079017-0175

BibTeX

@inproceedings{barlag2024neurips-graph,
  title     = {{Graph Neural Networks and Arithmetic Circuits}},
  author    = {Barlag, Timon and Holzapfel, Vivian and Strieker, Laura and Virtema, Jonni and Vollmer, Heribert},
  booktitle = {Neural Information Processing Systems},
  year      = {2024},
  doi       = {10.52202/079017-0175},
  url       = {https://mlanthology.org/neurips/2024/barlag2024neurips-graph/}
}