If two nodes \(u,v\)  satisfy \(\mathcal {H}_u^{(k-1)}\ne \mathcal {H}_v^{(k-1)}\) , then WL assigns them distinct labels in iteration \(k\) , and therefore we want our construction to satisfy \(h_u^{(k)}\ne h_v^{(k)}\)  with probability at least \(1-p\)  (as per def:oneiteration). This can fail in two places: either due to summing (if \(\mathcal {S}_u^{(k)}=\mathcal {S}_v^{(k)}\)  even though \(\mathcal {H}_u^{(k-1)}\ne \mathcal {H}_v^{(k-1)}\) ) or due to hashing (if \(h_u^{(k)}=h_v^{(k)}\)  even though \(\mathcal {S}_v^{(k)}\ne \mathcal {S}_v^{(k)}\) ).
To avoid the first failure mode (summing), we use one-hot encodings for the node labels, meaning that for every node \(v\)  and iteration \(k\) , \(h_v^{(k)}\)  is a one-hot vector in \(\lbrace 0,1\rbrace ^F\)  (for \(F\)  to be determined shortly). This ensures that if \(\mathcal {H}_u^{(k-1)}\ne \mathcal {H}_v^{(k-1)}\)  then \(\mathcal {S}_u^{(k)}\ne \mathcal {S}_v^{(k)}\)  due to the linear independence of the one-hot vectors. To handle the second failure mode (hashing), we use random hashing into \(F=O(1/p)\)  buckets, rendering the collision probability no more than \(p\) . That is, we let \(h_v^{(k)}=\text{One-Hot}(g(\mathcal {S}_v^{(k)}))\)  where \(g:^F\rightarrow \lbrace 1,\ldots ,F\rbrace \)  is chosen at random from an (approximately) universal hash family. We use the simple hash function \(g(x)=\langle a,x \rangle \; \mathrm {mod} \; F\)  where \(a\)  is random vector. It can be implemented with a ReLU neural network, since the dot product is just a linear layer, and the mod operation can be implemented with constant width and logarithmic depth, by a reduction to the “triangular wave” construction due to Telgarsky [1]} (see sec:modF). Finally, we show that turning the index of the hash bucket into a one-hot vector can be done with \(O(F)\)  ReLU units and constant depth.
