Corollary REF  follows easily from Theorem REF  and the fact that there are known limitations to the expressiveness of each of the listed GNN extensions. In the case of a standard GNN, two small cycles of different lengths are already a simple example for indistinguishability [1]}. For the 3-WL algorithm (and hence equivalently, PPGN), the Rook \(4\!\! \times \!\!4\)  and Shrikhande graphs are a well-known example on 16 nodes that are not distinguishable. For GSN and DropGNN, the analysis of [2]} describes an example construction that cannot be distinguished without preprocessing structures of size \(\Theta (\Delta )\)  or removing \(\Theta (\Delta )\)  nodes. Hence for any fixed parametrization of GSN or DropGNN (preprocessing substructures of fixed size, or removing a fixed number of nodes), there exists a pair of neighborhoods that cannot be distinguished by GSN or DropGNN. These example graphs have \(\Delta +1\)  nodes, so they can still be distinguished by AgentNet in \(\ell = 2 \cdot \Delta -1\)  steps.
