Graph Neural Networks and Arithmetic Circuits
This provides a foundational theoretical understanding of GNNs, which is incremental as it builds on existing circuit theory to analyze neural network architectures.
The paper tackles the problem of characterizing the computational power of graph neural networks (GNNs) by establishing an exact correspondence between GNN expressivity and arithmetic circuits over real numbers, with activation functions mapping to gate types, applicable to constant depth circuits and networks for all common activation functions.
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.