Also approximate matching via spectral methods is polynomial. You basically take eigendecomposition of graph adjacency matrix and take inner product of eigenvec

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.