To achieve this result, our construction is randomized, i.e., some weights of the neural networks are selected at random, and the simulation of the WL test is correct with high probability \(1-1/\mbox{poly}(n)\) . Thus, our construction can be viewed as creating a distribution over neural networks computing the function \(\phi ^{(k)}\) .Note that selecting \(\phi ^{(k)}\)  at random is quite different from random node initialization, e.g., as investigated in [1]}. In particular, in our model all nodes use the same function \(\phi ^{(k)}\)  (with the same parameters), without breaking the permutation invariance property of GNNs, as in the standard GNN model. In particular, this implies that, for each graph, there exists a single neural network implementing \(\phi ^{(k)}\)  that accurately simulates WL on that graph.
The size of the network is exponentially smaller than in  [2]}, although the construction is probabilistic.
