This is an interesting paper from the graph embedding domain. Graph embedding deals with mapping the vertices of a graph to points in a space such that the metric distance in that space between vertices corresponds to actual edges of the embedded graph. A proper embedding allows for the easy computation of properties such as communities and path lengths, much quicker than using traditional graph algorithms.

Traditionally, the approach has been to use Euclidean embeddings. However, real-world graphs demonstrate larger community structures due to the dependent nature of edges that cannot be captured by such embeddings. Recently, better results have been obtained by embedding graphs into a hyperbolic space (for reference, a hyperbolic geometry is Euclidean with the exception of Euclid’s fifth postulate allowing multiple lines to be parallels to a given one). Unfortunately, good hyperbolic embeddings are computationally complex to obtain. This paper shows how to obtain hyperbolic embeddings in quasi-linear runtime, contributing to the state of the art. The basic idea is to use a “spring” model: vertices are assumed to be connected by springs on their edges pulling them together, while all disconnected vertices push them away. The main modification from a similar approach in Euclidean space is to use independent springs on the radial and angular coordinates. The final objective is to maximize the log-likelihood that the original graph would be generated given a probability distribution of generating an edge as a function of hyperbolic distance.

This paper is extremely math-heavy and likely inaccessible to practitioners in graph processing. However, the final results look especially useful for greedy routing. This suggests that the technique might be useful as a kernel for problems such as dynamic shortest path routing queries on large graphs with, for example, 100000 vertices.