  In this paper, we propose algorithms for the graph isomorphism (GI) problem
that are based on the eigendecompositions of the adjacency matrices. The
eigenvalues of isomorphic graphs are identical. However, two graphs $ G_A $ and
$ G_B $ can be isospectral but non-isomorphic. We first construct a graph
isomorphism testing algorithm for friendly graphs and then extend it to
unambiguous graphs. We show that isomorphisms can be detected by solving a
linear assignment problem. If the graphs possess repeated eigenvalues, which
typically correspond to graph symmetries, finding isomorphisms is much harder.
By repeatedly perturbing the adjacency matrices and by using properties of
eigenpolytopes, it is possible to break symmetries of the graphs and
iteratively assign vertices of $ G_A $ to vertices of $ G_B $, provided that an
admissible assignment exists. This heuristic approach can be used to construct
a permutation which transforms $ G_A $ into $ G_B $ if the graphs are
isomorphic. The methods will be illustrated with several guiding examples.
