The equivalence between the discriminative power of GNNs and the WL test has been shown in the aforementioned works [1]}, [2]}. A strengthened version of the theorem of [1]}, where the same combine function \(\phi \)  is used in all iterations (i.e., \(\phi =\phi ^{(k)}\)  for all \(k\) ) appeared in the survey [4]}. Many works since have studied various representational issues in GNNs; we refer the reader to excellent surveys 
[4]}, [6]}, [7]}, [8]}.
In particular, [9]} established connections between GNNs and distributed computing models such as LOCAL and CONGEST, and derived lower bounds for several computational tasks based on this connection.
[10]} drew a connection between the expressiveness of GNNs in graph isomorphism testing and in function approximation.
[11]} studied the expressiveness of GNNs in computing Boolean node classifiers, and [12]} studied the expressiveness of graph convolutional networks (GCNs).
