Motivation

Last year, I became interested in (approximate) isometric embeddings of graphs with the path distance metric into metric spaces whose elements can be represented by coordinates - like \(N \)-dimensional euclidean space , \( \mathbb{E}^N \).

Let’s consider an isometric mapping from a graph with a path distance metric to \(N\)-dimensional euclidean space for instance: \( f: G \rightarrow \mathbb{E}^N \). Isometric means that the distances between each two vertices \(v, w \in G\) is preserved by \(f\), i.e. \( d(v, w)_G = | f(v) - f(w) |_2 \). So, if we had such an isometry \( f: G \rightarrow \mathbb{E}^N \), we would have a neat way to compute distances between \(v, w\) in our original graph \(G\), just by computing the distances of the images \(f(v), f(w)\) in \(\mathbb{E}^N\). If our mapping is efficient this operation would be in \( \mathcal{O}(N) \) which is efficient as long as the dimension can be kept small.

The Problem with Euclidean Space

The tough truth about isometrically embedding graphs into euclidean space, however, is that there are simple counterexamples of graphs which don’t permit an isometric embedding into any \(N\)-dimensional euclidean space.

Counterexamples

Cycle of Order Four

One of these counterexamples is the undirected cycle of order \(4\), \(C_4\), i.e. the cycle contains four vertices \(v_0, v_1, v_2, v_3\) such that there is an undirected edge between \(v_i\) and \(v_{i+1}\), as well as, between \(v_3\) and \(v_0\).

cycle of order 4

We now consider the unweighted path metric on \(C_4\), i.e. the weight of each edge is one, and the distance between any two vertices is just the number of edges in the shortest path between these vertices.

The distance matrix for this metric can be easily verified to be the following: \[ \begin{pmatrix} 0 & 1 & 2 & 1 \\ 1 & 0 & 1 & 2 \\ 2 & 1 & 0 & 1 \\ 1 & 2 & 1 & 0\end{pmatrix}. \] Here the entry in row \( i \) and column \( j \) is the distance of \( v_i \) to \( v_j \). We see, that there are only distances 1, 2 (and 0). Now, we want to show that there exists no \(4\) points in any euclidean space, which have the same distance matrix with respect to the euclidean distance.

For this, we need Ptolemy’s Inequality which holds four any quadrilateral in any Euclidean Space. It states:

Given a quadrilateral with side lengths \(s_1, s_2, s_3, s_4\) and diagonals \(d_1, d_2\), then

\[s_1s_3 + s_2s_4 \geq d_1 d_2\].

In our case, we would take the images \(f(v_0), f(v_1), f(v_2), f(v_3) \) as the four vertices of the quadrilateral. Then the side lengths \(s_i\) have to be all one, because the edges have weight 1. The diagonals on the other hand need to have length 2.

Thus the inequality becomes:

\[ s_1s_3 + s_2s_4 = 1\cdot1 + 1\cdot1 = 2 \geq 4 = 2\cdot2 = d_1 d_2 \].

This is an obvious contradiction, hence there can’t be an isometric embedding of \(C_4\) into any euclidean space.

Star with Three Rays

Another counterexample is the star with three rays, \( K_{1, 3} \). star graphs with 3, 4, 5 and 6 rays It has one center vertex \( v_0 \) which is connected to three outer vertices \( v_1, v_2, v_3 \) and otherwise there are no edges.

Now, again we have only distances 1, 2 (and 0) when we consider the hop-metric. Let’s consider the images of the star vertices under a hypothetical isometry

\[ f: K_{1, 3} \rightarrow \mathbb{E}^N \].

We must have \( |f(v_0) - f(v_i) |_2 = 1 \) for \( i \in {1, 2, 3} \), as well as \( | f(v_i) - f(v_j) |_2 = 2 \), for \( i \neq j \in {1, 2, 3} \).

In euclidean space we also have the triangular inequality: \[ | f(v_i) - f(v_j) |_2 \leq | f(v_i) - f(v_0) |_2 + | f(v_0) - f(v_j) |_2. \] In fact in our case, the triangular inequalities become equalities. This can only happen, if \( f(v_i), f(v_j), f(v_0) \) are collinear, i.e. on a line.

More specifically, we must even have \( f(v_0) = \frac{f(v_i) + f(v_j)}{2} \). But this has to hold for all \( i \neq j \) which are not \( 0 \). Hence we ge for instance \[ \frac{f(v_1) + f(v_2)}{2} = f(v_0) = \frac{f(v_2) + f(v_3)}{2}. \] Subtracting \( \frac{f(v_2)}{2} \) on the outer-left and outer right, we get \[ \frac{f(v_1)}{2} = \frac{f(v_3)}{2} \] which means that the images of \(v_1, v_3\) have to be equal and have distance \(0\). This can’t be, so there can’t be an isometry from \( K_{1, 3} \) to any euclidean space.

Conclusion

We have seen the appeal of embedding graphs isometrically into euclidean space. However, there are simple examples of graphs which can’t possibly embedded into euclidean space.

Now, there are some fixes for that. The most popular one seems to be to try to embed graphs into hyperbolic space. I will try to follow up in a future post with a different solution though, which is the so called power transform of finite metric spaces.