9
$\begingroup$

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$)?

$\endgroup$
2
  • 1
    $\begingroup$ Maybe this paper/preprint could be relevant for you: Babel, Baumann, Ludecke, Tinhhofer: STABCOL -- Graph isomorphism testing based on the Weisfeiler-Leman algorithm. $\endgroup$ Sep 30, 2015 at 9:49
  • $\begingroup$ Both the original paper and its translation are now available here. iti.zcu.cz/wl2018/wlpaper.html $\endgroup$
    – Daniel
    Aug 24, 2020 at 8:55

1 Answer 1

3
$\begingroup$

A standard reference is "On Construction and Identification of Graphs", ed. by: B.Weisfeiler, Springer Lect. Notes Math. Vol. 558 (1976) ISBN: 978-3-540-08051-0

There you will find details on Weisfeiler-Lehman algorithm (called stabilization there, IIRC). Although it's not an easy read.

A modern reference with some details on various "generalised" isomorphisms is here.

$\endgroup$
2
  • $\begingroup$ The link in the last sentence seems not to work anymore. Could you please update it or provide the title of the work you mention? $\endgroup$
    – Daniel
    Aug 24, 2020 at 8:51
  • $\begingroup$ I most probably meant a version of dl.acm.org/doi/10.1145/2371656.2371662 - not 100% sure though. $\endgroup$ Aug 24, 2020 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.