No. Consider a square (with graph shortest path distances) for example. All euclidean embeddings have a minimum error of 20-40% or so. If you try to embed any

No. Consider a square (with graph shortest path distances) for example. All euclidean embeddings have a minimum error of 20-40% or so. If you try to embed any graph containing that subgraph (embedding friends, advertisers, words, ...), you'll similarly have guaranteed error. Relaxing the square to a squircle, you'll see that error even for a really simple manifold. Riemannian manifolds are a bit more special.