  Given a graph or similarity matrix, we consider the problem of recovering a
notion of true distance between the nodes, and so their true positions. We show
that this can be accomplished in two steps: matrix factorisation, followed by
nonlinear dimension reduction. This combination is effective because the point
cloud obtained in the first step lives close to a manifold in which latent
distance is encoded as geodesic distance. Hence, a nonlinear dimension
reduction tool, approximating geodesic distance, can recover the latent
positions, up to a simple transformation. We give a detailed account of the
case where spectral embedding is used, followed by Isomap, and provide
encouraging experimental evidence for other combinations of techniques.
