  Network embedding techniques aim at representing structural properties of
graphs in geometric space. Those representations are considered useful in
downstream tasks such as link prediction and clustering. However, the number of
graph embedding methods available on the market is large, and practitioners
face the non-trivial choice of selecting the proper approach for a given
application. The present work attempts to close this gap of knowledge through a
systematic comparison of eleven different methods for graph embedding. We
consider methods for embedding networks in the hyperbolic and Euclidean metric
spaces, as well as non-metric community-based embedding methods. We apply these
methods to embed more than one hundred real-world and synthetic networks. Three
common downstream tasks -- mapping accuracy, greedy routing, and link
prediction -- are considered to evaluate the quality of the various embedding
methods. Our results show that some Euclidean embedding methods excel in greedy
routing. As for link prediction, community-based and hyperbolic embedding
methods yield overall performance superior than that of Euclidean-space-based
approaches. We compare the running time for different methods and further
analyze the impact of different network characteristics such as degree
distribution, modularity, and clustering coefficients on the quality of the
different embedding methods. We release our evaluation framework to provide a
standardized benchmark for arbitrary embedding methods.
