We next prove a lower bound on the number of ReLU units that we need to implement the WL test as a graph neural network. To do so, we will use that any neural network \(\phi : ^t\rightarrow ^\ell \)  which uses ReLU's as activation functions induces a partition of \(^t\)  into convex polytopes \(R_1,\dots ,R_N\)  such that \(\phi \)  restricted to each \(R_i\)  is just a linear function. Moreover, the number of such regions can be bounded using the following theorem.
[Proposition 4 in [1]}]
The number of linear regions of any ReLU network \(\phi :^t\rightarrow ^d\)  with a total of \(H\)  ReLU units is at most \(2^H\) .
