Our main result is a highly efficient construction of a GNN architecture that is capable of simulating the WL test. For graphs with \(n\)  nodes, it can simulate \(\mbox{poly}(n)\)  steps of the WL test, such that the neural network implementing \(\phi ^{(k)}\)  in each round has \((n)\)  parameters, and the messages exchanged by the nodes of the GNN in each round consist of \(O(\log n)\)  bits.
This offers at least an exponential improvement over the prior bounds obtained in [1]}, [2]} (see Table REF ), extending the equivalence between the WL test and the expressive power of GNNs to neural networks of reasonable (in fact, quite small) size. Furthermore, our architecture is simple, using vector sum for aggregation and ReLU units for the combine function \(\phi ^{(k)}\) . Finally, our construction can be generalized to yield a depth-size tradeoff: for any integer \(t>0\) , we can can construct a neural network of depth \(O(t)\)  and size \(n^{O(1/t)} (n)\) .
