<p>Even without the hash function, this is basically just 1-dimensional Weisfeiler-Leman with individualization of a single vertex. Neuen &amp; Schweitzer (<a href="https://doi.org/10.1145/3188745.3188900" rel="noreferrer">STOC '18</a>, <a href="https://arxiv.org/abs/1705.03283" rel="noreferrer">arXiv</a>) gave examples with an exponential <span class="math-container">$2^{\Omega(n)}$</span> lower bound for a much stronger family of algorithms, namely those for which one can iteratively individualize &amp; refine, and even use <span class="math-container">$k$</span>-dimensional WL for the refinement.</p>

CC BY-SA 4.0
2020-09-19T08:43:14.953Z
2020-09-19T08:43:14.953Z
Joshua Grochow
<p>As D. Eppstein pointed out <a href="https://cstheory.stackexchange.com/a/1065/8237">here</a> regarding proposed poly-time algorithms for Graph Isomorphism:</p>
<blockquote>
<p>... 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.</p>
</blockquote>
<p>As a (hopefully fun) exercise, here is such an algorithm.  Can you find a counterexample?</p>
<p><strong>input:</strong> two <em>connected</em> undirected graphs <span class="math-container">$G_1=(V_1, E_1)$</span>, <span class="math-container">$G_2=(V_2, E_2)$</span><br />
<strong>output:</strong> 'yes' if <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> are isomorphic, 'no' otherwise (with high probability)</p>
<ol>
<li>let <span class="math-container">$U=\{0,1,\ldots, 2^n-1\}$</span>; let <span class="math-container">$h: U\times U \rightarrow U$</span> be a universal hash function</li>
<li>for every pair of vertices <span class="math-container">$v_1\in V_1$</span> and <span class="math-container">$v_2\in V_2$</span>:</li>
<li><span class="math-container">$~~~$</span> let <span class="math-container">$\ell_0(v_1) = \ell_0(v_2) = 1$</span> and <span class="math-container">$\ell_0(v) = 0$</span> for <span class="math-container">$v\in V_1\cup V_2\setminus\{v_1, v_2\}$</span></li>
<li><span class="math-container">$~~~$</span> for <span class="math-container">$t \gets 1, 2, \ldots, T$</span>, where <span class="math-container">$T=n^2$</span>:</li>
<li><span class="math-container">$~~~~~~$</span> for each vertex <span class="math-container">$v\in V_1 \cup V_2$</span>:</li>
<li><span class="math-container">$~~~~~~~~~$</span> let <span class="math-container">$u_1, \ldots, u_d$</span> be <span class="math-container">$v$</span>'s neighbors, ordered so <span class="math-container">$\ell_{t-1}(u_1) \le \ell_{t-1}(u_2) \le \cdots \le \ell_{t-1}(u_d)$</span></li>
<li><span class="math-container">$~~~~~~~~~$</span> let <span class="math-container">$\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)))$</span></li>
<li><span class="math-container">$~~~$</span> let <span class="math-container">$u_1, u_2, \ldots, u_n$</span> be the vertices in <span class="math-container">$V_1$</span>, ordered so <span class="math-container">$\ell_T(u_1) \le \ell_T(u_2) \le \cdots \le \ell_T(u_n)$</span></li>
<li><span class="math-container">$~~~$</span> let <span class="math-container">$w_1, w_2, \ldots, w_n$</span> be the vertices in <span class="math-container">$V_2$</span>, ordered so <span class="math-container">$\ell_T(w_1) \le \cdots \le \ell_T(w_n)$</span></li>
<li><span class="math-container">$~~~$</span> if the bijection given by <span class="math-container">$u_i \leftrightarrow w_i$</span> is an isomorphism, return 'yes'</li>
<li>return 'no'</li>
</ol>
<p>Note that we are only considering isomorphism of <em>connected</em> graphs.  Line 2 &quot;guesses&quot; that there is an isomorphism that maps <span class="math-container">$v_1$</span> to <span class="math-container">$v_2$</span>; the body of the loop looks for such an isomorphism.  Line 7 defines <span class="math-container">$\ell_t(v)$</span> to be a hash of <span class="math-container">$\ell_{t-1}(v)$</span> and the multiset of <span class="math-container">$\ell_{t-1}(w)$</span>'s for the neighbors <span class="math-container">$w$</span> of <span class="math-container">$v$</span>.</p>
<p>The algorithm hashes polynomially many values into an exponentially large universe <span class="math-container">$U$</span>, so the probability of a collision is exponentially small. (By a &quot;collision&quot;, we mean that, among the hashes <span class="math-container">$h(x_i, y_i)$</span> that the algorithm computes, there are <span class="math-container">$h(x_i, y_i)$</span> and <span class="math-container">$h(x_j, y_j)$</span> such that <span class="math-container">$(x_i, y_i) \ne (x_j, y_j)$</span> but <span class="math-container">$h(x_i, y_i) = h(x_j, y_j)$</span>.)</p>
<p>Assuming there are no such collisions, <span class="math-container">$\ell_T(v)$</span> uniquely identifies the <em><span class="math-container">$T$</span>-neighborhood</em> of <span class="math-container">$v$</span>, where the <span class="math-container">$t$</span>-neighborhood of <span class="math-container">$v$</span> consists of the pair formed by the <span class="math-container">$(t-1)$</span>-neighborhood of <span class="math-container">$v$</span> and the multiset of <span class="math-container">$(t-1)$</span>-neighborhoods of <span class="math-container">$v$</span>'s neighbors. As a base case, the <span class="math-container">$0$</span>-neighborhoods of <span class="math-container">$v_1$</span> and <span class="math-container">$v_2$</span> are each <span class="math-container">$1$</span>, while the <span class="math-container">$0$</span>-neighborhood of each <span class="math-container">$v\not\in\{v_1,v_2\}$</span> is 0.  If <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> are isomorphic by an isomorphism <span class="math-container">$f$</span> such that <span class="math-container">$f(v_1)=v_2$</span>, then the <span class="math-container">$t$</span>-neighborhoods of vertices <span class="math-container">$u\in V_1$</span> and <span class="math-container">$w\in V_2$</span> such that <span class="math-container">$f(u) = w$</span> will be the same for all <span class="math-container">$t$</span>.  The underlying question is to what extent the converse holds.</p>
<p>By inspection the algorithm returns 'yes' only if <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> are isomorphic.  To make it  fail, one approach is to find a connected graph <span class="math-container">$G$</span> such that for every pair of vertices <span class="math-container">$v_1$</span> and <span class="math-container">$v_2$</span> (as chosen in Line 2) such that <span class="math-container">$G$</span> has an automorphism that maps <span class="math-container">$v_1$</span> to <span class="math-container">$v_2$</span>, there are two vertices <span class="math-container">$u$</span> and <span class="math-container">$w$</span> with the same <span class="math-container">$T$</span>-neighborhoods but where no such automorphism maps <span class="math-container">$u$</span> to <span class="math-container">$w$</span>.  (Then, given two copies of <span class="math-container">$G$</span>, the algorithm could incorrectly return 'no', because <span class="math-container">$u$</span> and <span class="math-container">$w$</span> can be ordered one way in Line 8 and the other way in Line 9.)  I would consider such a graph <span class="math-container">$G$</span> as an acceptable answer to the question.</p>
<p>It seems that such a graph <span class="math-container">$G$</span> should exist, for otherwise the (hashed) <span class="math-container">$T$</span>-neighborhoods could give a poly-sized (albeit randomized) witness certifying that <span class="math-container">$G$</span> has no non-trivial automorphism.  It <a href="https://cstheory.stackexchange.com/questions/3064/conp-certificate-for-graph-isomorphism">seems unlikely</a> that this is possible.</p>
<p><em>p.s.</em> 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 <span class="math-container">$t$</span>-neighborhood of <span class="math-container">$v$</span> by a signature that encodes the set of vertices <span class="math-container">$w$</span> that have different <span class="math-container">$t$</span>-neighborhoods...)  If so, please leave a comment to let me know, thanks.</p>

CC BY-SA 4.0
2020-09-17T00:45:23.697Z
Even without the hash function, this is basically just 1-d Weisfeiler-Leman with individualization of a single vertex. The Cai-Furer-Immerman graphs should give a pretty strong counterexample
Joshua Grochow
CC BY-SA 4.0
2020-09-17T00:51:07.983Z
@JoshuaGrochow: Perfect, thanks.  If you want to post that as an answer I will accept it.
Neal Young
CC BY-SA 4.0
2020-09-17T00:58:20.440Z
Well, I have to think for a few minutes about the individualization part, but won't be able to get to that for a bit.
Joshua Grochow
CC BY-SA 4.0
2020-09-17T13:51:26.457Z
Here's a link to (a translation of) the Weisfeller-Leman paper: https://scholar.google.com/scholar?hl=en&as_sdt=1%2C22&q=THE+REDUCTION+OF+A+GRAPH+TO+CANONICAL+FORM+AND+THE+ALGEBRA+WHICH+APPEARS+THEREIN
Neal Young
CC BY-SA 4.0
2020-09-19T18:12:03.280Z
Indeed, I'm still not sure if the CFI graphs alone would be a counterexample to your approach bc of the individualization part. But the Neuen-Schweitzer paper in my answer shows how to build even stronger counterexamples using CFI as (roughly) a starting point.
Joshua Grochow
<graph-isomorphism><puzzles>
Can you find a counter-example for this proposed Graph Isomorphism algorithm?
Neal Young
# Can you find a counter-example for this proposed Graph Isomorphism algorithm?

(Asked by: username_0 on 2020-09-16)

As D. Eppstein pointed out [here](https://cstheory.stackexchange.com/a/1065/8237) 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](https://cstheory.stackexchange.com/questions/3064/conp-certificate-for-graph-isomorphism) 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.

**Tags:** graph-isomorphism, puzzles

> **Comments:**
> **username_1**: Even without the hash function, this is basically just 1-d Weisfeiler-Leman with individualization of a single vertex. The Cai-Furer-Immerman graphs should give a pretty strong counterexample  
> **username_0**: @JoshuaGrochow: Perfect, thanks.  If you want to post that as an answer I will accept it.  
> **username_1**: Well, I have to think for a few minutes about the individualization part, but won't be able to get to that for a bit.  
> **username_0**: Here's a link to (a translation of) the Weisfeller-Leman paper: https://scholar.google.com/scholar?hl=en&as_sdt=1%2C22&q=THE+REDUCTION+OF+A+GRAPH+TO+CANONICAL+FORM+AND+THE+ALGEBRA+WHICH+APPEARS+THEREIN  
> **username_1**: Indeed, I'm still not sure if the CFI graphs alone would be a counterexample to your approach bc of the individualization part. But the Neuen-Schweitzer paper in my answer shows how to build even stronger counterexamples using CFI as (roughly) a starting point.  

---

## 1 answers

### Answer by username_1 on 2020-09-19. Score: 7 | Accepted answer

Even without the hash function, this is basically just 1-dimensional Weisfeiler-Leman with individualization of a single vertex. Neuen & Schweitzer ([STOC '18](https://doi.org/10.1145/3188745.3188900), [arXiv](https://arxiv.org/abs/1705.03283)) 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.


---

