I describe an approach to graph isomorphism which probably has false positives, and I am curious whether there is literature indicating that it does not work.
Given two adjacency matrices $G, H$, an admittedly naive method of checking for isomorphism is to check whether for each row $u$ of $G$, there is a row $v$ of $G$ which is a permutation of row $u$, denoted by $G[u] \sim H[v]$. Slightly more strict is the question, is there a "local isomorphism" $\pi$ for which $G[u] \sim H[\pi(u)]$ for all rows. Producing a local isomorphism can be done in polynomial time by building an $n\times n$ matrix $A$ with $A[u,v] = (G[u]\sim H[v])$; then $G$ and $H$ are locally isomorphic iff $A$ has a cycle cover, and every cycle cover is a local isomorphism.
All regular graphs fool this method, obviously, so a slightly less naive approach is to compute powers $G^2, H^2, G^3, H^3,\ldots$ of the matrices and checking them for local isomorphism, exploiting the fact that you have multiple matrices by setting $A[u,v] = 0$ when you find any power such that $G^k[u]\not\sim H^k[v]$, and checking for cycle cover only at the end. An even less naive approach is to find a set of polynomials, indeed a set of arithmetic circuits, and setting $A[u,v]=0$ when we find any polynomial $p$ with $p(G)[u]\not\sim p(H)[v]$.
This looks to me like an incredibly naive approach to graph isomorphism, so I am sure somebody has already investigated it and proved a theorem such as
Thm For infinitely many $n$ there are nonisomorphic $n\times n$ matrices $G, H$ and a permutation $\pi$ such that for every polynomial $p$, $p(G)$ and $p(H)$ are locally isomorphic by that permutation: $p(G)\overset{\pi}{\sim}p(H)$.
Question: Is there such a theorem? I have looked in the literature and cannot find it.
If there is a bound on the degree $k$ that is polynomial in $n$ such that for every two nonisomorphic matrices, local isomorphism is refuted by computing $G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$, or if there is an easily computable family of polynomials $p_1, \ldots ,p_k$, each having polynomially-bounded length but possibly exponential degree, then we have a P algorithm for graph isomorphism. If such polynomials (or arithmetic circuits) are easy to guess, then we have a coRP algorithm. If there always exists a (family of) arithmetic circuits to witness non local isomorphism, then this gives a coNP algorithm.
Note that we can avoid the problem that the entries of high-power matrices grow too large by computing the polynomials over small fields, e.g. by computing them modulo small primes. In a coNP algorithm, the prover can provide these primes.
