Testing $Tr(A^k) = Tr(B^k)$ for $k=1..n$ and $n\times n$ matrices ensures their similarity - existence of orthogonal matrix $OO^T =I$, such that $A=OBO^T$.
In graph isomorphism problem we ask if such space of possible $O$ matrices contains a permutation. Since 2015 (Babai) it is known that it can be done in quasi-polynomial ($\exp(\log(n)^c)$) time, the question remains if it can be done in polynomial time. Standard approaches are combinatorial (Weisfeiler-Lehman), let's try to look at it from algebraic perspective.
While $Tr(A^k)$ can be imagined as length $k$ cycle with summations where each index appears twice, building analogously invariants using higher degree vertices: with index appearing 3 or more times, they remain invariant to permutations, but no longer to general orthogonal matrices.
For example for orthogonal $O$, sum $\sum_d O_{ad} O_{bd} O_{cd} = \delta_{ab} \delta_{ac}$ allows to conclude that O is a permutation.
Hence testing $O(n^2)$ such invariants, what can be easily done in polynomial time, should determine matrix $A$ modulo permutation ... if only they are independent enough - the question is how to prove it?
Here are some diagrams - the bottom two families ($t(A)$ and $\overline{A}$) experimentally distinguish at least some strongly regular graphs (the hardest cases, more details at the end of https://arxiv.org/pdf/1703.04456 ):
Any ideas how to prove that agreement of such family of invariants restricts the space of similarity matrices to permutations only?