Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide if there is an assignment of vertices to points in Euclidean space, i.e. a function $f: V(G) \to \mathbb{R}^d$ such that $|f(x)-f(y)| = w( \{x,y \})$ whenever $\{ x, , y\} \in E$, where $|.|$ is the Euclidean norm? There is no harm in insisting that the weight function $d$ respect the triangle inequality.

The question I am most interested in is efficiently deciding whether there exists such a function $f$, for a given graph $G$ and weight function $d$, but it might also be interesting to know how to try to find a map that does the job but with "small distortion". For example, quadratic optimization tells us something...

Cases of special interest: (1) We have a complete graph $G=K_n$, i.e. a finite metric space. (2) The weight function $f$ is constant, i.e. we want to know: is $G$ a unit distance graph in $\mathbb{R}^d$? (Sometimes people want "unit distance graph" to also mean that $f$ is injective, but for my purposes it is fine for vertices to lie on top of each other.) Even the case of $f$ constant and $d=2$ is interesting, as this could be useful for a computational attack on the Hadwiger-Nelson unit coloring problem.

I've noticed that this question is equivalent to asking if a certain real algebraic variety of degree $2$ is nonempty, but I'm not sure if that is a helpful observation, other than it guarantees, for example, that is it algorithmically decidable.

up vote 12 down vote accepted

Let's say the graph is complete, and has weights on edges that satisfy triangle inequality. If you want an isometric embedding (which your original question indicates), then there's a necessary and sufficient characterization: the squares of the distances must be of negative type: specifically, given the $D_{ij} = d^2_{ij}$ values, then they must satisfy the inequality

$$ \sum_{i,j} b_i b_j D_{ij} \le 0, \sum_i b_i = 0$$ for all such $b_i$. All of this is discussed rather well in the book by Deza and Laurent.

It gets really interesting when you allow for some distortion. The special case where G is the complete graph and the weights (while not being constant) satisfy the triangle inequality is the well known metric embedding problem, which has been studied extensively in the theoretical computer science community because of connections to multicommodity flows, and also for data mining problems. A great source is the paper by Linial, London and Rabinovich

Let the distortion be the largest value of $w(x,y)/d(x,y)$ (wlog we can assume the embedding always shrinks distances)

  1. there's always an embedding into Euclidean space that ensures a distortion $O(\log n)$. The dimension of the space can then be brought down to $O(\log n)$ by applying the Johnson-Lindenstrauss Lemma. This result is due to Bourgain, and the algorithm itself is quite simple: pick $K$ subsets of the input at random, each of size $\log n$, and for each point, let its $i^{th}$ coordinate in the embedding be its distance to the $i^{th}$ such subset. The original proof uses $K = \log^2 n$, and then we use the JL lemma to reduce the dimension back to $\log n$.

1a. this basic construction also works for all $\ell_p$-norms for $1 \le p \le 2$, but the dimensionality reduction of course doesn't.

1b. The construction is tight: the lower bound comes from considering the shortest path metric induced by a constant-degree expander.

The case when you only care to preserve some of the distances is more interesting. While I'm not sure what has been considered for this case, there's another whole body of work that considers the induced shortest path metrics for special graphs (trees, series parallel graphs, planar graphs and so on). One of the most interesting conjectures in this area whether the metric space induced by planar graphs admits a constant-factor distortion embedding into Euclidean space.

  • Correct me if I am wrong : Doesn't section 2.6 of the paper "Local-Global Tradeoffs in Metric Embedding" by Moses-Yury-Konstantin supersede Linial-London-Rabinovich? (It would be great if you could compare the two papers and what is the most recent thing known in this direction!) – Anirbit Aug 26 '15 at 1:17
  • What is the name of the paper by Linial, London and Rabinovich? I think that the link is broken now? Thank you! – real Nov 18 '15 at 15:46
  • Found it. It must be the "The geometry of graphs and some of its algorithmic applications". – real Nov 18 '15 at 16:04

One may always be able to find a graph embedding in Euclidean space, if we consider dot product instead of euclidean norm.

If the distance matrix $D_G$ is a diagonalizable matrix, than we can perform eigenvalue decomposition as $D_G=U\Sigma U^T = U\Sigma^{1/2} \Sigma^{1/2}U^{T}=K^{T}K$. Now, each row $K$ can be treated as a euclidean representation of graph vertex whose dot product with other any row yield the corresponding weight of an edge.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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