Given a graph $G=(V,E)$, find a mapping $f\colon V \rightarrow \mathbb R^d$ such that for every edge $(u,v) \in E$ we have that $||f(u)-f(v)|| \leq r$; and for every $(u,v) \not \in E$, we have the opposite $||f(u)-f(v)|| > r$ for some given $r$. One could also view this problem as embedding a unit disc graph back into the euclidean space.

Now I have been told that - while the problem is NP-complete - the usual way to do it is as follows. This is where the hearsay starts, so excuse me if I am a little vague.

The proposed approach places an arbitrary node at $0$. Then, run a linear (or quadratic?) program that maximizes $\sum_{v \in V} g(f(v))$ under the side condition stated above, i.e. for all edges $(u,v) \in E$, $(f(u) - f(v))^2 \leq r^2$. $g$ is probably some norm, maybe $L_1$ or $L_2$.

This is how I more or less understood it. The general gist was to fix the position of an initial node and then "spread" the graph apart using the linear program.

I tried to find some sources on that, maybe a paper that introduced this approach, but so far my efforts failed - there are just too many ways to embed a graph in the $\mathbb R^d$. In particular, I am interested in how this approach deals with noisy data. For example, consider a grid graph of size $n \times n$ which should be perfectly embeddable in the euclidean plane. Now, add an edge from $(0,0)$ to $(n,n)$. Intuitively, in an embedding I would like to ignore the edge since the rest of the graph is a perfect grid. The approach above, however, would most likely produce a weird embedding.

Can anyone give me some pointers to work describing this approach?

  • 1
    $\begingroup$ So what is your question? $\endgroup$
    – cody
    Commented Jun 2, 2015 at 20:16
  • $\begingroup$ I'm mainly looking for some paper introducing this approach. Any literature would be appreciated. $\endgroup$
    – HdM
    Commented Jun 2, 2015 at 20:23
  • $\begingroup$ Maybe MDS? en.wikipedia.org/wiki/Multidimensional_scaling.) $\endgroup$ Commented Jun 3, 2015 at 20:16
  • $\begingroup$ Could you expand on that? I know of MDS, do you see a way to incorporate the above approach in some multi dimensional scaling? $\endgroup$
    – HdM
    Commented Jun 3, 2015 at 21:42

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.