  In practice symmetries of combinatorial structures are computed by
transforming the structure into an annotated graph whose automorphisms
correspond exactly to the desired symmetries. An automorphism solver is then
employed to compute the automorphism group of the constructed graph. Such
solvers have been developed for over 50 years, and highly efficient sequential,
single core tools are available. However no competitive parallel tools are
available for the task. We introduce a new parallel randomized algorithm that
is based on a modification of the individualization-refinement paradigm used by
sequential solvers. The use of randomization crucially enables parallelization.
We report extensive benchmark results that show that our solver is competitive
to state-of-the-art solvers on a single thread, while scaling remarkably well
with the use of more threads. This results in order-of-magnitude improvements
on many graph classes over state-of-the-art solvers. In fact, our tool is the
first parallel graph automorphism tool that outperforms current sequential
tools.
