World's most popular travel blog for travel bloggers.

# Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices

, ,
Problem Detail:

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.

###### Answered By : Thomas Klimpel

Yes, there is such a theorem, more or less. It basically states that the k-dimensional Weisfeiler-Lehman procedure subsumes (i.e. dominates) all known combinatorial approaches to graph isomorphism testing. (Your concrete proposal should be subsumed by the 2-dimensional Weisfeiler-Lehman procedure, if I am not mistaken.) For each fixed k, there is a class of counterexamples to the k-dimensional Weisfeiler-Lehman procedure known as the Cai-Fürer-Immmerman construction.

I first learned the basics of the Weisfeiler-Lehman procedure and the Cai-Fürer-Immmerman construction from

http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

There is much more to learn about the Weisfeiler-Lehman procedure than described there, but at least the treatment of the Cai-Fürer-Immmerman construction is complete and sufficient for your purpose. "The Weisfeiler-Lehman Procedure", by Vikraman Arvind is a recent brief essay meant as an invitation to the topic.

Perhaps the crucial point to take away from my answer is that if you would find a purely combinatorial isomorphism testing method (like the one describe in your question), which is not subsumed (i.e. dominated) by the k-dimensional Weisfeiler-Lehman procedure, then this would be a breakthrough by itself, independent of whether the method would be actually useful.