Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
edited tags
Link
Pete
  • 91
  • 1
Source Link
Pete
  • 91
  • 1

Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

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:

  1. $\varphi(MN) = \varphi(M)\varphi(N)$;
  2. $\varphi(M \circ N) = \varphi(M) \circ \varphi(N)$ (where $\circ$ denotes the Schur product);
  3. $\varphi(M^*) = \varphi(M)^*$ where $^*$ denotes conjugate transpose;
  4. $\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$)?