The connection between GNNs and the WL test has spawned a wave of new results studying GNN variants that either match the distinguishing power of the WL test or adopt new methods beyond message passing on the edges of the input graph to overcome this barrier (see the excellent surveys [1]}, [2]}, [3]} for an overview of this area).
However, the results in the original as well the follow up works mostly focus on qualitative questions (how expressive GNNs are) as opposed to quantitative questions such as the network complexity. In particular, while Xu et al. [4]} show that there exist GNN architectures that can simulate the WL coloring procedure as long as the aggregation step is injective, they rely on the universal approximation theorem to show that there exists a neural network that can simulate the hash function used in WL.
As a result, the size of the network could be exponential in the number of nodes \(n\) . In contrast, the construction of Morris et al. [1]} uses networks of size polynomial in \(n\) . However, the weights of the network implementing \(\phi ^{(k)}\)  in their construction depend on the structure of the underlying graph, which
suffices for node classification, but is not sufficient for the context of graph classification.
