patternMinor
Recovering a point embedding from a graph with edges weighted by point distance
Viewed 0 times
edgesgraphpointrecoveringwithweighteddistanceembeddingfrom
Problem
Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the distance between the points.
Your goal is to reconstruct the relative positions of the points, given only the available distances (represented by the edge weights). For example, if I gave you $d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$, then you know the points are the vertices of a tetrahedron. You don't know where it is relative to the origin, or its orientation, or if it's been mirrored, but you can tell it's a tetrahedron.
In general, the problem is easy if I give you all of the edge lengths. Just arbitrarily pick a point $p_0$ to be at $(0,0,0)$, then pick a neighboring point $p_1$ and place it at $(d_{0,1},0,0)$, then a common neighbor $p_2$ gets triangulated onto the XY plane, then a final common neighbor $p_3$ gets triangulated into the half-space $z > 0$ and breaks the remaining symmetry (assuming you didn't pick degenerate points). You can use those four points to triangulate all the remaining ones.
On the other hand, when some edge lengths are missing it may not be possible to recover the embedding. For example, if there's a vertex that disconnects the graph when cut, then the two components it would separate if removed can swing around relative to each other.
Which raises the questions:
Your goal is to reconstruct the relative positions of the points, given only the available distances (represented by the edge weights). For example, if I gave you $d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$, then you know the points are the vertices of a tetrahedron. You don't know where it is relative to the origin, or its orientation, or if it's been mirrored, but you can tell it's a tetrahedron.
In general, the problem is easy if I give you all of the edge lengths. Just arbitrarily pick a point $p_0$ to be at $(0,0,0)$, then pick a neighboring point $p_1$ and place it at $(d_{0,1},0,0)$, then a common neighbor $p_2$ gets triangulated onto the XY plane, then a final common neighbor $p_3$ gets triangulated into the half-space $z > 0$ and breaks the remaining symmetry (assuming you didn't pick degenerate points). You can use those four points to triangulate all the remaining ones.
On the other hand, when some edge lengths are missing it may not be possible to recover the embedding. For example, if there's a vertex that disconnects the graph when cut, then the two components it would separate if removed can swing around relative to each other.
Which raises the questions:
- How expensive is it to find a solution?
- How do you determine if a solution is unique, up to translation/rotation/mirroring? Is 3-connectedness sufficient? Necessary?
- What sorts of conditions make the problem trivial?
- If I don't promise the edge weights actually correspond to point distances in 3d, how expensive is it to determine if an embedding is possible at all?
Solution
One algorithmic approach to solving this problem: treat this as a set of nodes, connected by springs, then let them settle/relax into shape.
Each edge $(v,w)$ corresponds to a spring; if the distance between points $v$ and $w$ is supposed to be $d_{v,w}$, then the spring is chosen so it ideally wants to be of length $d_{v,w}$ (it can be longer or shorter, but this costs energy). We now want to solve for a set of positions that minimize the total energy. Suppose each vertex $v$ is placed at point $x_v \in \mathbb{R}^3$. Then the total energy of this arrangement will be
$$E(x) = \sum_{(v,w) \in E} (\text{distance}(x_v,x_w) - d_{v,w})^2.$$
Here the $d_{v,w}$'s are given (they are the weights on the edges), and we want to solve for the $x_v$'s (they are the coordinates of the points).
We can solve for an arrangement $x$ that minimizes this total energy. This arrangement then provides a reasonable candidate for the positions of the points. This is an optimization problem, and there are standard techniques for solving this kind of optimization problem. See, e.g., the article Network Solutions by Erica Klarreich.
I don't think there any guarantee this will provide the correct desired solution. It's possible that the optimization problem might settle to a different optimum that doesn't reflect the actual arrangement of points you were looking for. However, if your graph is sufficiently dense, I suspect it might often work and give you the desired solution.
Footnote: Of course even in the best case we can only solve this problem up to translation, rotation, and reflection since those transformations preserve all distances. Thus, you can't expect a unique solution -- but you might hope that the solution is unique up to translation, rotation, and reflection.
Finally, there's a lot of work on embedding graphs into $\ell_2$ space, while minimizing the distortion of the embedding. That's very related; you are basically asking for a zero-distortion embedding into $\ell_2$. Thus, the techniques developed in that context might be useful for your problem, too. Typically, that work focuses on finding a low-distortion embedding, because that work focuses on the case where there is no perfect embedding that makes all the distances match exactly, so instead it looks for a low-distortion solution (one where most edge distances match pretty well) -- so that work is focused on a slightly different problem. However, it's possible that their techniques might be effective in your situation as well. It's worth a try.
Each edge $(v,w)$ corresponds to a spring; if the distance between points $v$ and $w$ is supposed to be $d_{v,w}$, then the spring is chosen so it ideally wants to be of length $d_{v,w}$ (it can be longer or shorter, but this costs energy). We now want to solve for a set of positions that minimize the total energy. Suppose each vertex $v$ is placed at point $x_v \in \mathbb{R}^3$. Then the total energy of this arrangement will be
$$E(x) = \sum_{(v,w) \in E} (\text{distance}(x_v,x_w) - d_{v,w})^2.$$
Here the $d_{v,w}$'s are given (they are the weights on the edges), and we want to solve for the $x_v$'s (they are the coordinates of the points).
We can solve for an arrangement $x$ that minimizes this total energy. This arrangement then provides a reasonable candidate for the positions of the points. This is an optimization problem, and there are standard techniques for solving this kind of optimization problem. See, e.g., the article Network Solutions by Erica Klarreich.
I don't think there any guarantee this will provide the correct desired solution. It's possible that the optimization problem might settle to a different optimum that doesn't reflect the actual arrangement of points you were looking for. However, if your graph is sufficiently dense, I suspect it might often work and give you the desired solution.
Footnote: Of course even in the best case we can only solve this problem up to translation, rotation, and reflection since those transformations preserve all distances. Thus, you can't expect a unique solution -- but you might hope that the solution is unique up to translation, rotation, and reflection.
Finally, there's a lot of work on embedding graphs into $\ell_2$ space, while minimizing the distortion of the embedding. That's very related; you are basically asking for a zero-distortion embedding into $\ell_2$. Thus, the techniques developed in that context might be useful for your problem, too. Typically, that work focuses on finding a low-distortion embedding, because that work focuses on the case where there is no perfect embedding that makes all the distances match exactly, so instead it looks for a low-distortion solution (one where most edge distances match pretty well) -- so that work is focused on a slightly different problem. However, it's possible that their techniques might be effective in your situation as well. It's worth a try.
Context
StackExchange Computer Science Q#28642, answer score: 5
Revisions (0)
No revisions yet.