Weisfeiler-Lehman variant Isomorphism test counterexample

Question

I am currently working on isomorphism tests between graphs. I came up with a variant of the Wesifeiler-Lehman algorithm and I am looking for a pair of graphs which would trick the test. Such pair of graphs $(G, H)$ would satisfy following property at the $n$-th iteration of the algorithm:

There exists a bijection between the nodes of $G$ and $H$ such that the increasing sequence of the number of $n$-walks between $u$ and other nodes (including $u$) is identical for both graphs for any node $u$.

To be more precise, given a vertex indexing of $G$, one can compute the power of the adjacency matrix $A_G^n$. For any $1\le i, j \le |V_G|$, it is well known that $(A_G^n)_{ij}$ is the number of $n$-walks between $i$ and $j$. I consider the multiset

$$ \{\!\{ \{\!\{(A_G^n)_{ij} | 1\le j\le |V_G| \}\!\}| 1\le i\le |V_G| \}\!\} $$

which would be identical for $G$ and $H$ for let's say $n\le N$. Has anyone an idea for a counterexample?

A positive example of the algorithm

The graphs $H_1$ and $H_2$ are indistinguishable by the $1$-WL algorithm but can be distinguished by the previous algorithm. At the third iteration of the algorithm, we compute that each vertex $u$ of $H_1$ has two 3-cycles compared to zero for the bipartite graph $H_2$, furthermore there are nine 3-walks between opposite nodes for $H_2$ which leaves no ambiguity in the multiset.

Answer 1

Distance-regular graphs with the same intersection array are counter examples. From https://arxiv.org/abs/1410.6294 :

The smallest intersection array (smallest in terms of the number of vertices) that corresponds to more than one graph is $\{6, 3; 1, 2\}$; it corresponds to the Hamming graph $H(2, 4)$ (also known as the lattice graph $L_2(4)$) and the Shrikhande graph.

Answer 2

Let $G(a,b,c)$ be the graph in which three paths of lengths $a,b,c$ respectively meet at a common vertex. Then this isomorphism test will fail to distinguish $G(a,b,c)$ from $G(a',b',c')$ provided $a+b+c = a'+b'+c'$, for $n$ up to somewhere around $\frac12 \min\{a,b,c,a',b',c'\}$.

The idea is that in $G(a,b,c)$, the sequence of numbers of walks of length up to $n$ from a vertex $u$ can identify $u$ as one of:

• A vertex at some distance $d<n$ from the central vertex (we can identify $d$), or
• A vertex at some distance $d<n$ from one of the leaves (again, we can identify $d$), or
• A vertex at distance at least $n$ from any of these "notable features".

As long as $a$, $b$, and $c$ are at least $2n$, we will have a bunch of vertices in the third category, and we will not know how many of them belong to each path.

---

Another, similar approach to examples is to let $G,H$ be two regular graphs with girth $g$. For $n \le \frac{g-1}{2}$, this isomorphism test will fail to distinguish $G$ from $H$, because the subgraph within distance $n$ of any vertex will just look like a tree in which every vertex reached so far has the same degree.

This paper proposes a method for generating many random $k$-regular graphs with logarithmic girth (which is best possible for $k \ge 3$, up to the constant factor). So there are plenty of examples to be found of such $G$ and $H$, though not explicit ones.