Part of my dissertation research was on the graph matching problem. For solving this problem in real settings, it is useful to think of vertices as elements of a space with the edges determining some sort of locality, (I guess this can be formalized with topology ). Then the graph/vertex matching problem becomes sort of a point cloud matching problem where you don’t know where the points are , just the neighborhood relationships between them ( several manifold learning uses these relationships to find the manifolds defined by the points ). That is why embedding the vertices of the two graph using dissimilarities between vertex pairs can be used to match graphs. This is how we have used JOFC for seeded graph matching.
The same paradigm works with point cloud registration or matching manifolds. For example, see this paper by Facebook researchers for matching between monolingual word embeddings in different languages. They start by finding a rigid transformation between the two word embeddings in different languages (say english and french), based on closest matches using Procrustes method. They then modify the distance between an english vector mapped french and a french vector to solve the point density problem: hub words (that are common words in either corpora) will have emeddings that are close to many other words will be matched to many other words , and easily confused . I think this also applies to hub vertices that are connected to many other vertices in graph matching. The distance modification uses the number of words in the neighborhood of a common word , so that more dense regions of the embedding spaces will see this cross-domain distance increase. Another possible solution to this nonhomogenous point density in the embedding spaces may be using hyperbolic embeddings which I will summarize in another post.