Let's assume that monotonocity of pair-wise distances are preserved.
Without knowing the details of how the paper solved the problem, my first attempt would be to find the diametrically distant pair of points in the two different embeddings and assume that the pair is the same pair. Then find the next distant pairs and so on.
After sufficiently many such pairs have been found, find that scaled rigid body transformation that makes the corresponding pairs coincide. Proceeding this way ought to be less work than solving a generic graph isomorphism problem.
Without knowing the details of how the paper solved the problem, my first attempt would be to find the diametrically distant pair of points in the two different embeddings and assume that the pair is the same pair. Then find the next distant pairs and so on.
After sufficiently many such pairs have been found, find that scaled rigid body transformation that makes the corresponding pairs coincide. Proceeding this way ought to be less work than solving a generic graph isomorphism problem.
Note this is version 4 of the paper and the original post was version 1 (I think?)
OpenReview (for NeurIPS) for the curious: https://openreview.net/forum?id=jiCLUPq5xv