A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given coherent algebras $\mathcal{A}$ and $\mathcal{B}$, a weak isomorphism from $\mathcal{A}$ to $\mathcal{B}$ is a bijective linear map $\varphi$ satisfying:
- $\varphi(MN) = \varphi(M)\varphi(N)$;
- $\varphi(M \circ N) = \varphi(M) \circ \varphi(N)$ (where $\circ$ denotes the Schur product);
- $\varphi(M^*) = \varphi(M)^*$ where $^*$ denotes conjugate transpose;
- $\varphi(J) = J$.
Given a graph $G$ with adjacency matrix $A$, the coherent algebra of $G$ is defined as the intersection of all coherent algebras containing $A$. In this paper they define two graphs $G$ and $H$ to be equivalent if there exists a weak isomorphism between their corresponding coherent algebras that also maps the adjacency matrix of $G$ to the adjacency matrix of $H$. In the paper they say that there exists a polynomial time algorithm for testing whether two graphs are equivalent and cite Weisfeiler and Lehman's paper.
I gather that the Weisfeiler-Lehman algorithm is closely related to coherent algebras, but have so far only been able to find references which describe the algorithm in a purely combinatorial manner, i.e. in terms of graphs not coherent algebras. The paper of Weisfeiler and Lehman linked above is not available to me and is anyways written in Russian. I am wondering if there is a direct connection with the definition of graph equivalence given above, and the Weisfeiler-Lehman algorithm for distinguishing graphs. More specifically, is it true that two graphs are equivalent if and only if they cannot be distinguished by ($k$-dimensional) Weisfeiler-Lehman (for some [specific] $k$)?
