It is already all but known to be quasi-polynomial, thanks to László Babai: https://www.quantamagazine.org/graph-isomorphism-vanquished-...

Also approximate matching via spectral methods is polynomial. You basically take eigendecomposition of graph adjacency matrix and take inner product of eigenvectors, because spectrum is invariant under permutation of node labels. Works well on noise free and large graphs, because you are unlikely to be unlucky enough to land on isospectral graphs.

Graph isomorphism is actually not known to be NP-complete. Many complexity theorists believe it isn't, since if it is, then the polynomial hierarchy collapses.

I'm imagining a number of use cases for something like this in the information security domain but don't know enough about graph theory to chew into this paper. Would it be possible to do something like k-means with this to identify patterns in existing graphs as well?