Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the graph isomorphism problem, determining whether two given graphs correspond vertex-for-vertex and edge-for-edge.
The graph automorphism problem is the problem of testing whether a graph has a nontrivial automorphism.