Embedding a graph in the euclidean space
I finally managed to ask the person that originally told me about this approach. It appears to be closely related to maximum variance unfolding (MVU), see also https://en.wikipedia.org/wiki/Semidefinite_embedding. The paper introducing this approach is "Learning a kernel matrix for nonlinear dimensionality reduction" by Weinberger, Sha, and Saul if I am not mistaken.