Graph Neural Networks and Arithmetic Circuits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910706247401472 |
|---|---|
| author | Barlag, Timon Holzapfel, Vivian Strieker, Laura Virtema, Jonni Vollmer, Heribert |
| author_facet | Barlag, Timon Holzapfel, Vivian Strieker, Laura Virtema, Jonni Vollmer, Heribert |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_17805 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph Neural Networks and Arithmetic Circuits Barlag, Timon Holzapfel, Vivian Strieker, Laura Virtema, Jonni Vollmer, Heribert Machine Learning Artificial Intelligence Computational Complexity F.1.1; F.1.3; I.2.m 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. |
| title | Graph Neural Networks and Arithmetic Circuits |
| topic | Machine Learning Artificial Intelligence Computational Complexity F.1.1; F.1.3; I.2.m |
| url | https://arxiv.org/abs/2402.17805 |