Surprised to know there are two $O(n^3)$ isomorphic algorithms for **simple and undirected graphs** based on distance matrix.

DOI 10.16383/j.aas.c230025. 
Wang Zhuo, Wang Cheng-Hong "[Isomorphism determination methods for simple undirected graphs](https://dds.sciengine.com/cfs/files/pdfs/0254-4156/E4E524DF79EA41CB90588C3A6099FBDA.pdf)", Acta Automatica Sinica, 2023, 49(9): 1878-1888

After read it carefully, a much simpler method is invented based on 
$$
Fg :=Ag + M + r \cdot I
$$
where
* $Ag$ is the adjacency matrix,
* $M$ is a $n\times n$ matrix whose entries are equal to $m$ 
* $m$, $r$ are free variables.

Under the above conditions, then
$$
\det(Fg) = \det(Fh) \iff g\text{ and }h\text{ are isomorphic.}
$$
Note that 
* this is true for all undirected graphs (except for one unknown case: $g$ has different number loop for nodes).
* It's similar to Jones polynomial generalized to HOMFLY for knot theory (by introducing a second variable $m$). 

Though it is strong, but for digraphs, it is not always true even with more constrains.