Hyperbolic embedding of a directed acyclic graph defined over strings

Question

For integer $n$ and alphabet $\Sigma$ we construct a DAG (directed acyclic graph) $G=(V,E)$ over strings $s\in\Sigma^\star$ as follows: $$V = \{s\in\Sigma^\star\colon |s|\le n\}$$ $$E = \{(s_1,s_2)\colon s_1=\text{insert}(s_2,p,c), c\in\Sigma, 0\le p\le |s_1|\}$$ in which $insert(s,p,c)$ takes string $s$ and inserts character $c$ in position $p$ of string $s$, and gives the result as output.

Finally we define the undirected distance between two nodes as: $$d(s_1,s_2) = \text{length of shortest path between } s_1 \text{ and } s_2 \text{ discarding edge directions}$$

For a given $n$ and alphabet $\Sigma$ is it possible to embed $G$ in a Poincare disk with dimension $d$, such that the geodesic distance between each pair $u,v$ is close to $d(u,v)$? I know that there is a hyperbolic embedding due to Gromov for trees. But are there similar results for DAGs? If yes, what are the assumptions about DAGs that must hold?

Illustration:

Here you can see the graph for $n=3$ and $\Sigma=\{A,B\}$: In this case for example $d(AAA,BAA)=2$ and the shortest undirected path is: $AAA-AA-BAA$. As another example $d(AAA,BBA)=4$ and the shortest path is: $AAA-AA-A-BA-BBA$.

The question would then be: can we embed this graph in a hyperbolic space such that the geodesic distances would be close to the shortest path distances? If the answer is negative, are there a number of edges that can be removed (or added) that can make the graph more embeddable?

Answer 1

Hyperbolic geometry is usually good for embedding Gromov hyperbolic graphs. Trees are Gromov hyperbolic graphs, but DAGs are not necessarily Gromov hyperbolic.

If you take, for example, $\mathbb{N}^2$ as the set of vertices, and $(x,y)$ leads to $(x+1,y)$ and $(x,y+1)$, then this DAG is not Gromov hyperbolic, and it does not embed in the hyperbolic plane well. This one can be easily embedded in Euclidean plane (we could say informally it is an Euclidean graph).

If you take $\mathbb{N}$ as the set of vertices, and $x$ leads to $2x$ and $x+1$, then this DAG is not a tree but it is Gromov hyperbolic, and indeed it embeds greatly in hyperbolic geometry. (In fact, I would say it embeds even better than a tree -- if you draw it, it is kind of similar to a binary tree but with extra edges connecting nearest vertices on the same level, and the nature of the hyperbolic plane is very similar to that.)

In general, if you know that a graph is directed and acyclic, it does not help in embedding (you could make any graph into a DAG by ordering the vertices and then directing edges according to $i<j$). It is important the graph should have a hierarchical structure. There is research on embedding (undirected) scalefree networks, and some other networks of hierarchical nature. Unfortunately, it appears to me that your graph is not "hierarchical" -- it would be hierarchical (and also Gromov hyperbolic) if you could, say, insert new letters at one of the 10 last places, because then you have the empty word in the center, from where you have words starting with "a", then words starting with "ab", etc., and if you go far enough from the center, the adjacent words would be in the same branch. In particular, if you take the subgraph constructed from words of form $a^nb^m$, it is isomorphic to the "informally Euclidean" graph I have mentioned above, so it is clearly not Gromov hyperbolic. I think this graph is too complicated to be embedded (both in Euclidean and hyperbolic geometry).

As far as I know, in most graph embedding applications of hyperbolic geometry, adding more dimensions does not help much. (The intuition is that if you embed something in hyperbolic geometry, it is similar to a tree, and thus it embeds in the hyperbolic plane as well. I must check how well hyperbolic 3D honeycombs embed in a hyperbolic plane.) Euclidean space in $n$ dimensions is less complex than Euclidean space in $n+1$ dimensions, hyperbolic plane is more complex than any Euclidean space, but adding more dimensions does not help. (Euclidean space is like $\mathbb{Z}^n$, the free Abelian group with $n$ generators; hyperbolic space is like $F_n$, the free (non-Abelian!) group with $n$ generators, and it is known that $F_2$ has any $F_n$ as a subgroup, and any $\mathbb{Z}^n$ as a quotient of a subgroup.) Also using the Poincaré model is often a mistake, Minkowski hyperboloid is better for most computations.