The Descriptive Complexity of Graph Neural Networks
This work provides a theoretical foundation for understanding the expressiveness of GNNs, which is crucial for researchers in machine learning and graph theory, though it is incremental in linking GNNs to established complexity classes.
The paper analyzes the computational power of graph neural networks (GNNs) by proving that polynomial-size bounded-depth GNN families exactly compute graph queries definable in the guarded fragment GFO+C of first-order logic with counting, placing them in the circuit complexity class TC^0, and shows that with standard features like random initialization and global readout, they match bounded-depth Boolean circuits with threshold gates.
We analyse the power of graph neural networks (GNNs) in terms of Boolean circuit complexity and descriptive complexity. We prove that the graph queries that can be computed by a polynomial-size bounded-depth family of GNNs are exactly those definable in the guarded fragment GFO+C of first-order logic with counting and with built-in relations. This puts GNNs in the circuit complexity class (non-uniform) $\text{TC}^0$. Remarkably, the GNN families may use arbitrary real weights and a wide class of activation functions that includes the standard ReLU, logistic "sigmoid", and hyperbolic tangent functions. If the GNNs are allowed to use random initialisation and global readout (both standard features of GNNs widely used in practice), they can compute exactly the same queries as bounded depth Boolean circuits with threshold gates, that is, exactly the queries in $\text{TC}^0$. Moreover, we show that queries computable by a single GNN with piecewise linear activations and rational weights are definable in GFO+C without built-in relations. Therefore, they are contained in uniform $\text{TC}^0$.