  Graph embedding approaches attempt to project graphs into geometric entities,
i.e, manifolds. The idea is that the geometric properties of the projected
manifolds are helpful in the inference of graph properties. However, if the
choice of the embedding manifold is incorrectly performed, it can lead to
incorrect geometric inference. In this paper, we argue that the classical
embedding techniques cannot lead to correct geometric interpretation as they
miss the curvature at each point, of manifold. We advocate that for doing
correct geometric interpretation the embedding of graph should be done over
regular constant curvature manifolds. To this end, we present an embedding
approach, the discrete Ricci flow graph embedding (dRfge) based on the discrete
Ricci flow that adapts the distance between nodes in a graph so that the graph
can be embedded onto a constant curvature manifold that is homogeneous and
isotropic, i.e., all directions are equivalent and distances comparable,
resulting in correct geometric interpretations. A major contribution of this
paper is that for the first time, we prove the convergence of discrete Ricci
flow to a constant curvature and stable distance metrics over the edges. A
drawback of using the discrete Ricci flow is the high computational complexity
that prevented its usage in large-scale graph analysis. Another contribution of
this paper is a new algorithmic solution that makes it feasible to calculate
the Ricci flow for graphs of up to 50k nodes, and beyond. The intuitions behind
the discrete Ricci flow make it possible to obtain new insights into the
structure of large-scale graphs. We demonstrate this through a case study on
analyzing the internet connectivity structure between countries at the BGP
level.
