  Recent work shows that the expressive power of Graph Neural Networks (GNNs)
in distinguishing non-isomorphic graphs is exactly the same as that of the
Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test
can be simulated by GNNs. However, those simulations involve neural networks
for the 'combine' function of size polynomial or even exponential in the number
of graph nodes $n$, as well as feature vectors of length linear in $n$.
  We present an improved simulation of the WL test on GNNs with
\emph{exponentially} lower complexity. In particular, the neural network
implementing the combine function in each node has only a polylogarithmic
number of parameters in $n$, and the feature vectors exchanged by the nodes of
GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds
for the feature vector length and the size of the neural networks, showing the
(near)-optimality of our construction.
