Polynomial Algorithm for checking if graph is Weisfeiler Leman isomorphism test counterexample

Question

I am currently working on isomorphism tests between graphs, however. Is there a polynomial algorithm for determining whether a graph is a potential 1-WL counterexample? By counterexample I mean graphs that WL cannot distinguish. I know that there are some families of graphs for which the problem is GI complete. Thus, if such a list is complete (is it? ) one can check whether the graph falls into one of these families. Is there a different algorithm?

Answer 1

I don't think such an algorithm is known, but there are large classes of graphs for which 1-WL fails. Here are some examples:

• Regular graphs. Take for instance, $C_{6}$ vs. $2K_{3}$.
• Two graphs are 1-WL indistinguishable if and only if they are fractionally isomorphic.
• The CFI graphs, which require WL-dimension $\Omega(n)$: https://people.cs.umass.edu/~immerman/pub/opt.pdf
• Multipedes, which are not captured by $k$-WL for any fixed constant $k$: https://www.jstor.org/stable/2275675
• Neuen & Schweitzer exhibit an exponential-time lower bound against individualization + $k$-WL refinement. They combine the CFI and multipede constructions to obtain hard instances. In their work, they cite a conference paper of Miyazaki (which I could not find) who establishes an analogous result against nauty. Note that nauty is built on 1-WL + engineering techniques. See (https://arxiv.org/abs/1705.03283).

Related to what you are asking, Kiefer & McKay have examples to show that 1-WL requires $n-1$ iterations to stabilize. Note that 1-WL requires $\leq n-1$ rounds to stabilize. See: https://arxiv.org/abs/2005.10182

The power of 1-WL is that it identifies almost all graphs (which is why practical graph isomorphism packages such as nauty, traces, saucy, bliss, etc., are built on low-dimensional WL). So Graph Isomorphism is practically solved. Note that 2-WL identifies almost all regular graphs, though it notably fails on strongly regular graphs. The isomorphism problem for strongly regular graphs (via Latin square graphs) includes problems such as Group Isomorphism, and so we do not expect Weisfeiler--Leman to identify all strongly regular graphs. (And to add, strongly regular graphs are easier than Graph Isomorphism under computable functorial reductions. Babai showed, in 2014 I believe-- so recently; that there is no computable functorial reduction from Graph Isomorphism to isomorphism testing of strongly regular graphs.)

When the groups are given by their multiplication tables, Group Isomorphism is strictly easier than Graph Isomorphism under $\textsf{AC}^{0}$-reductions (which are weaker than polynomial-time reductions). Nonetheless, the best we know how to do in general is $n^{(1/4)\log(n) + O(1)}$. There has been considerable work on efficient algorithms for special cases of Group Isomorphism over the last 12 or so years, and Weisfeiler--Leman has only recently been brought to bear on this problem.

Update: Deciding if the WL-dimension is at most $k$ is $\textsf{NP}$-hard. The preprint is here (https://arxiv.org/abs/2402.11531).