# On the power of graph neural networks and the role of the activation function

arXiv: https://arxiv.org/abs/2307.04661 · HTML: https://mlsanity.com/paper/2307.04661/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 29 references that are in the map.
- First posted on arXiv 10 Jul 2023.

## Builds on (most cited first, 21 of 21)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Cognitive Graph for Multi-Hop Reading Comprehension at Scale](https://mlsanity.com/paper/1905.05460/) (2019)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)

## Built on by (most cited first, 8 of 8)

- [Weisfeiler Leman for Euclidean Equivariant Machine Learning](https://mlsanity.com/paper/2402.02484/) (2024)
- [A Logical View of GNN-Style Computation and the Role of Activation Functions](https://mlsanity.com/paper/2512.19332/) (2025)
- [DiGRAF: Diffeomorphic Graph-Adaptive Activation Function](https://mlsanity.com/paper/2407.02013/) (2024)
- [Graph Neural Networks Need Cluster-Normalize-Activate Modules](https://mlsanity.com/paper/2412.04064/) (2024)
- [A note on the VC dimension of 1-dimensional GNNs](https://mlsanity.com/paper/2410.07829/) (2024)
- [The logic of rational graph neural networks](https://mlsanity.com/paper/2310.13139/) (2023)
- [Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks](https://mlsanity.com/paper/2603.14846/) (2026)
- [Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture](https://mlsanity.com/paper/2610.16993/) (2026)

## Abstract (arXiv)

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 non-isomorphic 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 [ACI+22]. 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 [2021, Grohe] more completely. 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 graph neural networks 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.