Recently came across this beautiful paper [1] about embedding graphs in hyperbolic space. Graph embedding algorithms for euclidean space are flawed because you essentially need to add an additional dimension for every node. Of course there are techniques you can use to reduce the number of dimensions by graph clustering etc, but fundamentally the dimensions scale with the size of your graph.
Hyperbolic space, on the other hand, enables you to embed hierarchical information in a single dimension due to the curvature itself (yes this is hand-wavey mainly because I still barely understand it, read the paper). This is very conducive to embedding graphs, and especially structured graphs (or trees).