consider isomap

[maxheld83]

this takes the geodesic distances on weighted graphs, that might work.
Still no direction though?

• https://en.wikipedia.org/wiki/Isomap