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

arXiv:2307.04661v3 Announce Type: replace
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 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 …

abstract architecture article arxiv cs.lg function gnn gnns graph graph neural networks networks neural networks polynomial power prove results role type