Why is graph automorphism sometimes easier than canonical labeling (for current software)? László Babai recently hinted that graph isomorphism is solved for all practical purposes:

It seems, for all practical purposes, the Graph Isomorphism problem is solved; a suite of remarkably efficient programs is available (nauty, saucy, Bliss, conauto, Traces). The article by McKay and Piperno [McP] gives a detailed comparison of methods and performance.

Because it was unclear to me, whether this statement only applies to isomorphism testing (and automorphism group computation), or also to canonical labeling, I worked through Practical Graph Isomorphism, II (presentation), read (parts of) Practical graph isomorphism, II (preprint), and clicked through an online version of the details of the experiments. It seems that most of the time, computing a canonical labeling is not significantly slower than computing the automorphism group. But for some challenging graph classes, computing a canonical labeling appears to be nearly infeasible, while most programs seem to have no problems computing the corresponding automorphism group:

Automorphism group of Miyazaki (augmented) graphs
  
  Canonical labeling of Miyazaki (augmented) graphs
  

...

Automorphism group of (non-disjoint) union of tripartite graphs
  
  Canonical labeling of (non-disjoint) union of tripartite graphs
  

Only Traces seems to always take nearly the same time for computing the automorphism group as for computing a canonical labeling, despite being the only program where the preprint explicitly mentioned that a more efficient strategy was used for computing the automorphism group:

When Traces is only looking for the automorphism group, and not for a canonical labelling, it employs another strategy which is sometimes much faster.

Do the other programs also use special strategies when only computing the automorphism group, or does the depth first traversal of the search tree automatically allows to exit early without any need for a special strategy? And is there any specific reason why the other programs are faster than Traces when computing the automorphism group of (non-disjoint) union of tripartite graphs, but nearly break down completely when they try to compute a corresponding canonical labeling?
 A: This is not a simple question. One thing to know about the pictures above is that the Miyazaki graphs are hard for nauty because Miyazaki studied how nauty operates and designed the graphs to be as hard as possible for nauty.
In order to find the automorphism group you can take any convenient leaf of the search tree and find enough leaves equivalent to it.  You can prune any paths in the tree which cannot lead to such an equivalent leaf.  To get a canonical labelling you need to find the "best" leaf. It is a different type of search problem so the times can easily be worse.  This description doesn't apply so
well to Traces, but Traces uses a different way to handle the lowest levels of its BFS tree basically for the same reason. The details are in the paper.
Theoretically, it is unknown whether canonical labelling is harder than graph automorphism. Babai's new algorithm for automorphisms probably will extend to canonical labelling, according to him, but the details have not been worked out last time I heard.  Anyway it won't impact the practical side of the problem.
