Graph distances have proven quite useful in machine learning/statistics, particularly in the estimation of Euclidean or geodesic distances, and as such have been used to embed a graph (the multidimensional scaling problem). The talk will include a partial review of the literature and then present more recent developments, including on the minimax estimation of distances on a surface and consequences for manifold learning, on the estimation of curvature-constrained distances on a surface, and on the estimation of Euclidean distances based on an unweighted and noisy neighborhood graph.