I just thought of the following incomplete algorithm for deciding whether two graphs are isomorphic:
Let $A$ and $A'$ be adjacency matrices of two graphs. Then for some unitary $U,U’$ and diagonals $D,D’$ (in which the diagonals are sorted) we have:
$U^tAU=D$ and $U’^tA’U’=D’$.
If $D \neq D'$, the graphs are not isomorphic.
If $D=D’$, then for $V=UU'^t$, we have:
$V^tAV=A’$.
If $V$ is a permutation matrix, then the graphs are isomorphic. If not, then the graphs may or may not be isomorphic.
Is there an easy way to fix the incomplete part of the algorithm? If so, then please explain how. If not, then please explain why not.
Addendum: The problem is when the graph has lots of repeated eigenvalues. Then $V$ will not necessarily be a permutation matrix and converting it into a permutation matrix which satisfies the equation $V^tAV=A'$ seems to be hard.
If the adjacency matrices of two graphs are similar, the graphs are said to be cospectral (and there is a large literature on the topic). Basically you are asking how to solve the graph isomorphism problem when your inputs are cospectral. No method for graph isomorphism is known that can make effective use of cospectrality.
Since we can decide in polynomial time if two graphs are cospectral, and since we have not been able to solve graph isomorphism in polynomial time, I do no think there will be any simple way to complete your "algorithm".
It is known that if we consider graphs where the multiplicity of any eigenvalue is at most $m$, then graph isomorphism can be solved in polynomial time.