Graph Neural Networks (GNNs) have become a popular tool for machine learning on graph-structured data, with applications in social network prediction [1]}, traffic prediction [2]}, recommender systems [3]}, drug discovery [4]}, computer vision [5]}, [6]}, [7]}, [8]}, and combinatorial optimization [9]}. Standard message passing GNNs use the topology of the input graph to define the network structure: in each step \(k\) , a node aggregates messages from each of its neighbors and combines them using a function \(\phi ^{(k)}\) , computed by a neural network, to determine its message for the next round. Crucially, the aggregation function must be symmetric, to ensure that the output of GNNs is invariant under node permutation. This restriction raised questions about how expressive such network architectures are, and in particular what classes of graphs are distinguishable using GNNs.
