A common approach to decide whether two given graphs are isomorphic is to compute the so-called canonical label (alternatively, canonical graph) of each graph and to check whether those match or not.
Tools such as Nauty compute the canonical graph via search trees that are pruned using some clever ideas that rely, among other, on graph automorphisms. Because of this, Nauty allows one to compute a generator of the graph automorphism group. However, as far as I understood the ideas behind Nauty, the computation of the canonical graph does not require one to compute a generator of the graph automorphism group in general.
My question is therefore: is there a formal complexity-theoretical relation between GI and the computation of a generator set of the graph automorphism group?
Many thanks.
I realize this is an old question. With that said, I wanted to add an answer.
First, $\textsf{Graph Isomorphism}$ $(\textsf{GI})$ is equivalent to computing the automorphism group of a given graph. Furthermore, $\textsf{GI}$ is equivalent to $\#\textsf{GI}$, the latter of which asks for the number of isomorphisms.
The problem you are asking about is the canonization problem. In general, isomorphism testing reduces to computing canonical forms for the reasons that you stated. If one can efficiently compute canonical forms, then we can compute the canonical forms for $G$ and $H$ and test whether the forms are equal. It is not known if there is a reduction in the other direction.
Practical tools like Nauty rely on iteratively individualizing vertices followed by a color-refinement process such as low-dimensional Weisfeiler--Leman (usually $1$-WL or $2$-WL). In practice, Nauty works quite well. There is theoretical evidence as to why. First, $1$-WL identifies almost all graphs [1]. Furthermore, the fraction of graphs not identified by $1$-WL is exponentially small in the number of vertices [2].
It is well-known in the Weisfeiler--Leman community that if $k$-WL identifies a family of graphs, then $(k+1)$-WL detects orbits. In particular, $(k+1)$-WL can be used to obtain a canonical labeling. Immerman & Lander [3] gave the predecessor to the more general canonization procedure found in [4].
[1] https://epubs.siam.org/doi/abs/10.1137/0209047?journalCode=smjcat
[2] https://ieeexplore.ieee.org/document/4567999/
[3] https://people.cs.umass.edu/~immerman/pub/canon.pdf
[4] https://arxiv.org/abs/1901.10330