Can you find a counter-example for this proposed Graph Isomorphism algorithm?

Question

As D. Eppstein pointed out here regarding proposed poly-time algorithms for Graph Isomorphism:

... it is easy to define algorithms for graph isomorphism that attempt to amplify some sort of subtle asymmetry in the graph to the point where it is obvious how to match the vertices to each other, and it is hard to find counterexamples for these algorithms, but that is very different from having a clear proof of correctness that works for all graphs.

As a (hopefully fun) exercise, here is such an algorithm. Can you find a counterexample?

input: two connected undirected graphs $G_1=(V_1, E_1)$, $G_2=(V_2, E_2)$
output: 'yes' if $G_1$ and $G_2$ are isomorphic, 'no' otherwise (with high probability)

1. let $U=\{0,1,\ldots, 2^n-1\}$; let $h: U\times U \rightarrow U$ be a universal hash function
2. for every pair of vertices $v_1\in V_1$ and $v_2\in V_2$:
3. $~~~$ let $\ell_0(v_1) = \ell_0(v_2) = 1$ and $\ell_0(v) = 0$ for $v\in V_1\cup V_2\setminus\{v_1, v_2\}$
4. $~~~$ for $t \gets 1, 2, \ldots, T$, where $T=n^2$:
5. $~~~~~~$ for each vertex $v\in V_1 \cup V_2$:
6. $~~~~~~~~~$ let $u_1, \ldots, u_d$ be $v$'s neighbors, ordered so $\ell_{t-1}(u_1) \le \ell_{t-1}(u_2) \le \cdots \le \ell_{t-1}(u_d)$
7. $~~~~~~~~~$ let $\ell_t(v) = h(\ell_{t-1}(u_d), h(\ell_{t-1}(u_{d-1}), h(\ldots, h(\ell_{t-1}(u_{2}), h(\ell_{t-1}(u_1), \ell_{t-1}(v))\ldots)))$
8. $~~~$ let $u_1, u_2, \ldots, u_n$ be the vertices in $V_1$, ordered so $\ell_T(u_1) \le \ell_T(u_2) \le \cdots \le \ell_T(u_n)$
9. $~~~$ let $w_1, w_2, \ldots, w_n$ be the vertices in $V_2$, ordered so $\ell_T(w_1) \le \cdots \le \ell_T(w_n)$
10. $~~~$ if the bijection given by $u_i \leftrightarrow w_i$ is an isomorphism, return 'yes'
11. return 'no'

Note that we are only considering isomorphism of connected graphs. Line 2 "guesses" that there is an isomorphism that maps $v_1$ to $v_2$; the body of the loop looks for such an isomorphism. Line 7 defines $\ell_t(v)$ to be a hash of $\ell_{t-1}(v)$ and the multiset of $\ell_{t-1}(w)$'s for the neighbors $w$ of $v$.

The algorithm hashes polynomially many values into an exponentially large universe $U$, so the probability of a collision is exponentially small. (By a "collision", we mean that, among the hashes $h(x_i, y_i)$ that the algorithm computes, there are $h(x_i, y_i)$ and $h(x_j, y_j)$ such that $(x_i, y_i) \ne (x_j, y_j)$ but $h(x_i, y_i) = h(x_j, y_j)$.)

Assuming there are no such collisions, $\ell_T(v)$ uniquely identifies the $T$-neighborhood of $v$, where the $t$-neighborhood of $v$ consists of the pair formed by the $(t-1)$-neighborhood of $v$ and the multiset of $(t-1)$-neighborhoods of $v$'s neighbors. As a base case, the $0$-neighborhoods of $v_1$ and $v_2$ are each $1$, while the $0$-neighborhood of each $v\not\in\{v_1,v_2\}$ is 0. If $G_1$ and $G_2$ are isomorphic by an isomorphism $f$ such that $f(v_1)=v_2$, then the $t$-neighborhoods of vertices $u\in V_1$ and $w\in V_2$ such that $f(u) = w$ will be the same for all $t$. The underlying question is to what extent the converse holds.

By inspection the algorithm returns 'yes' only if $G_1$ and $G_2$ are isomorphic. To make it fail, one approach is to find a connected graph $G$ such that for every pair of vertices $v_1$ and $v_2$ (as chosen in Line 2) such that $G$ has an automorphism that maps $v_1$ to $v_2$, there are two vertices $u$ and $w$ with the same $T$-neighborhoods but where no such automorphism maps $u$ to $w$. (Then, given two copies of $G$, the algorithm could incorrectly return 'no', because $u$ and $w$ can be ordered one way in Line 8 and the other way in Line 9.) I would consider such a graph $G$ as an acceptable answer to the question.

It seems that such a graph $G$ should exist, for otherwise the (hashed) $T$-neighborhoods could give a poly-sized (albeit randomized) witness certifying that $G$ has no non-trivial automorphism. It seems unlikely that this is possible.

p.s. It seems likely that this or a similar algorithm has already been studied. (E.g., it would be natural to replace the use of a hash to encode the $t$-neighborhood of $v$ by a signature that encodes the set of vertices $w$ that have different $t$-neighborhoods...) If so, please leave a comment to let me know, thanks.

Answer 1

Even without the hash function, this is basically just 1-dimensional Weisfeiler-Leman with individualization of a single vertex. Neuen & Schweitzer (STOC '18, arXiv) gave examples with an exponential $2^{\Omega(n)}$ lower bound for a much stronger family of algorithms, namely those for which one can iteratively individualize & refine, and even use $k$-dimensional WL for the refinement.