  It is well known that almost all graphs are canonizable by a simple
combinatorial routine known as color refinement. With high probability, this
method assigns a unique label to each vertex of a random input graph and,
hence, it is applicable only to asymmetric graphs. The strength of
combinatorial refinement techniques becomes a subtle issue if the input graphs
are highly symmetric. We prove that the combination of color refinement with
vertex individualization produces a canonical labeling for almost all circulant
digraphs (Cayley digraphs of a cyclic group). To our best knowledge, this is
the first application of combinatorial refinement in the realm of
vertex-transitive graphs. Remarkably, we do not even need the full power of the
color refinement algorithm. We show that the canonical label of a vertex $v$
can be obtained just by counting walks of each length from $v$ to an
individualized vertex. Our analysis also implies that almost all circulant
graphs are canonizable by Tinhofer's canonization procedure. Finally, we show
that a canonical Cayley representation can be constructed for almost all
circulant graphs by the 2-dimensional Weisfeiler-Leman algorithm.
