On the Power of Graph Neural Networks and the Role of the Activation Function
Sammy Khalife, Amitabh Basu · SIAM Journal on Applied Algebra and Geometry · 2026
Abstract. In this article we present new results about the expressivity of graph neural networks (GNNs). We prove that for any GNN with piecewise polynomial activations, whose architecture size does not grow with the graph input sizes, there exists a pair of nonisomorphic rooted trees of depth two such that the GNN cannot distinguish their root vertex up to an arbitrary number of iterations. In contrast, it was already known that unbounded GNNs (those whose size is allowed to change with the graph sizes) with piecewise polynomial activations can distinguish these vertices in only two iterations. It was also known prior to our work that with ReLU (piecewise linear) activations, bounded GNNs are weaker than unbounded GNNs [A. Aamand et al., Exponentially improving the complexity of simulating the Weisfeiler-Lehman test with graph neural networks, in Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS 2022), Adv. Neural Inform. Process. Syst. 35, Curran Associates, 2022, pp. 27333–27346]. Our approach adds to this result by extending it to handle any piecewise polynomial activation function, which goes towards answering an open question formulated by Grohe more completely [M. Grohe, The logic of graph neural networks, in LICS ’21: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2021, pp. 1–17]. Our second result states that if one allows activations that are not piecewise polynomial, then in two iterations a single neuron perceptron can distinguish the root vertices of any pair of nonisomorphic trees of depth two (our results hold for activations like the sigmoid, hyperbolic tan, and others). This shows how the power of GNNs can change drastically if one changes the activation function of the neural networks. The proof of this result utilizes the Lindemann–Weierstrauss theorem from transcendental number theory.