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. The proof relies on tools from the algebra of symmetric
polynomials. 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. Our results
imply a strict separation between bounded and unbounded size GNNs, answering an
open question formulated by [Grohe, 2021]. We next prove 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.

活动函数不同，图神经网络在两层迭代中可以区分两个非同构树的根节点，但是若网络的大小被限制，其区分能力将受到限制。