  Finding optimal matchings in dense graphs is of general interest and of
particular importance in social, transportation and biological networks. While
developing optimal solutions for various matching problems is important, the
running times of the fastest available optimal matching algorithms are too
costly. However, when the vertices of the graphs are point-sets in $R^d$ and
edge weights correspond to the euclidean distances, the available optimal
matching algorithms are substantially faster. In this paper, we propose a novel
network embedding based heuristic algorithm to solve various matching problems
in dense graphs. In particular, using existing network embedding techniques, we
first find a low dimensional representation of the graph vertices in $R^d$ and
then run faster available matching algorithms on the embedded vertices. To the
best of our knowledge, this is the first work that applies network embedding to
solve various matching problems. Experimental results validate the efficacy of
our proposed algorithm.
