Hardness of Computing Weisfeiler-Lehman labels
The problem of deciding whether two graphs have equivalent labelings and hence also the problem of computing the canonical labeling are PTIME complete. See 

M. Grohe,  Equivalence in finite-variable logics is complete for polynomial time.
Combinatorica 19:507-532, 1999. (Conference version in FOCS'96.)

Note that colour refinement equivalence corresponds to equivalence in the logic C^2.

-Martin