On another note, it would be interesting to obtain efficiently computable subquadratic reductions from groups to graphs, but we are not aware of such a construction.

=\[draw,shape=circle, inner sep=0, minimum height= 0.6cm\] (-7.5,-1.5) node (p1) [$g$]{} (-7.5, 0) node (p2) [a]{} (-5.5,-1.5) node (p3) [$h$]{} (-5.5,0) node (p4) [b]{} (-4.5,0) node (p5) [c]{} (-3.5,0) node (p6) [d]{} (-3.5,-1.5) node (p7) [$gh$]{}; (p1) – (p2) (p2) – (p4) (p3) – (p4) (p2) – (p4) (p5) – (p4) (p5) – (p6) (p6) – (p7);

For fixed $k$, each version of the WL-algorithm gives rise to a polynomial-time (possibly) partial isomorphism test on pairs of finite groups. Indeed, marked isomorphism of $k$-tuples in a group $G$ can be checked in time $\mathcal{O}(|G|\log(|G|))$ so we can compute initial colors in time $\mathcal{O}(|G|^{k+1}\log(|G|))$ for Versions I and II. The refinement steps are the same as for graphs and thus we obtain the same $\mathcal{O}(|G|^{k+1}\log(|G|))$ bound for the rest of the computation. For Version III we have a quadratic blowup yielding time $\mathcal{O}(|G|^{2k+1}\log(|G|))$.

Groups $G$ and $H$ are equivalent with respect to $k$-WL in Version $J\in\{\text{{\textup{I}},{\textup{II}},{\textup{III}}}\}$, in symbols $G\equiv_{WL_k^J} H$, if there is a bijection $f\colon G^k\to H^k$ preserving final colors of the respective color-refinement procedure. 