  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.
