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.
Best Answer
Distance-regular graphs with the same intersection array are counter examples. From https://arxiv.org/abs/1410.6294 :