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

CC BY-SA 3.0
2015-06-27T03:02:19.267Z
2015-06-27T09:32:49.053Z
2015-06-27T09:32:49.053Z
HdM
<p>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)|| &gt; r$ for some given $r$.
One could also view this problem as embedding a unit disc graph back into the euclidean space.</p>

<p>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. </p>

<p>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$.</p>

<p>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.</p>

<p>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.</p>

<p>Can anyone give me some pointers to work describing this approach?</p>

CC BY-SA 3.0
2015-06-02T20:16:41.527Z
So what is your question?
cody
CC BY-SA 3.0
2015-06-02T20:23:19.943Z
I'm mainly looking for some paper introducing this approach. Any literature would be appreciated.
HdM
CC BY-SA 3.0
2015-06-03T20:16:41.033Z
Maybe MDS? http://en.wikipedia.org/wiki/Multidimensional_scaling.)
Sariel Har-Peled
CC BY-SA 3.0
2015-06-03T21:42:44.367Z
Could you expand on that? I know of MDS, do you see a way to incorporate the above approach in some multi dimensional scaling?
HdM
<reference-request><graph-algorithms><linear-programming><embeddings>
Embedding a graph in the euclidean space
HdM
# Embedding a graph in the euclidean space

(Asked by: username_0 on 2015-06-02)

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?

**Tags:** reference-request, graph-algorithms, linear-programming, embeddings

> **Comments:**
> **username_1**: So what is your question?  
> **username_0**: I'm mainly looking for some paper introducing this approach. Any literature would be appreciated.  
> **username_2**: Maybe MDS? http://en.wikipedia.org/wiki/Multidimensional_scaling.)  
> **username_0**: Could you expand on that? I know of MDS, do you see a way to incorporate the above approach in some multi dimensional scaling?  

---

## 1 answers

### Answer by username_0 on 2015-06-27. Score: 1 | Accepted answer

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.


---

