In order to show a lower bound on the number of units needed to implement a successful WL iteration, we rely on prior work lower bounding the number of linear regions induced by a ReLU network (for instance [1]}). In particular, these works show that ReLU networks induce a partition of the input space into \(N\)  convex regions (where \(N\)  is a function of the size of the network) such that the network acts as a linear function restricted to any given region. Using these results, we describe a fixed graph and a distribution over inputs to the neural network \(S_u^{(k-1)}\)  for all \(u \in V\)  (sums of the labels from the previous round) which includes \(O(F)\)  potential special pairs of nodes (where \(F\)  is defined such that inputs \(S_u^{(k-1)} \in [F]^t\)  for some \(t\) ).
For each such pair \(u, v\) , their neighborhoods \(N(u), N(v)\)  have different multisets of inputs, but both multisets of inputs sum to the same value.
We show that if the number of linear regions is small, \(N = o(F)\) , then it is relatively likely that \(u, v\)  will be in the same linear region and thus their sums will collide: \(S_u^{(k)} = S_v^{(k)}\)  even while their neighborhoods had distinct inputs in the \((k-1)\) st round.
