1
$\begingroup$

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\}$: enter image description here 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?

$\endgroup$
  • $\begingroup$ What do you mean by "the shortest paths are preserved"? Do you mean that all shortest paths map to geodesics? Then the only connected graph with this property would be linear. $\endgroup$ – Misha Mar 26 '19 at 22:10
  • $\begingroup$ I mean the geodesic distance between the embeddings of $u$ and $v$ in Poincare disk is equal or close to $d(u,v)$ as defined above. $\endgroup$ – kvphxga Mar 26 '19 at 22:40
  • 1
    $\begingroup$ OK, then, as I said, only linear graphs admit such embeddings. This is because your definition forces local geodesics to map to (local) geodesics and geodesics in hyperbolic space cannot branch. $\endgroup$ – Misha Mar 26 '19 at 23:13
  • $\begingroup$ What about hyperbolic embeddings of a higher dimension in general? Is it possible to embed a non-tree graph such that shortest paths for a directed graph that might have undirected cycles? $\endgroup$ – kvphxga Mar 27 '19 at 12:25
  • $\begingroup$ Your question seems to be evolving. Now, you have to define what "close" means. If by any chance you have in mind a quasi-isometric embedding then it is a theorem of Bonk and Schramm that under reasonable assumptions on a graph (such as Gromov hyperbolicity, bounded valence, etc), it admits a quasi-isometric embedding in some real-hyperbolic space. $\endgroup$ – Misha Mar 28 '19 at 0:52
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks a lot! I guess I don't quite understand what the "hierarchical" means for Gromov hyperbolic graphs. I've added a simple illustration, and it looks to me like there is some hierarchy. Can you elaborate a bit what is missing here that this graph isn't Gromov hyperbolic? Also it is very helpful to know what modifications can be made to make it hyperbolically embeddable. For example do you think there is a minimal number of edges that can be removed to make it embeddable? $\endgroup$ – kvphxga Mar 27 '19 at 16:08
  • $\begingroup$ I did not mean anything well defined. Indeed it looks like there is some hierarchy, but I think it is not close to what is needed for hyperbolic embedding (a single "parent", or a bunch of parents who are similar). $\endgroup$ – Zeno Rogue Mar 27 '19 at 18:44
  • $\begingroup$ Gromov hyperbolicity means that the graph is similar to tree in that there are no shortcuts: if you go from point A to point B, and then from point B to point C (using shortest routes), then the any shortest route from A to C will not go far from the route you have taken (the triangle ABC is "thin"). In your graph you can go empty$(A) \rightarrow a^n (B) \rightarrow a^nb^n (C) \rightarrow b^n (D) \rightarrow (A)$, but the point D is not close to anything which is on your route from A to B to C. $\endgroup$ – Zeno Rogue Mar 27 '19 at 18:44
  • $\begingroup$ Close means, in distance at most $\delta$, where $\delta$ is small. I see the following solutions to make the graph more embeddable: (1) to add edges everywhere (not interesting), (2) only allow inserting letters on one of the last $k$ positions (where $k$ is a constant, the greater the $k$, the worse the quality of embedding). I think both solutions make it Gromov hyperbolic (with Gromov $\delta$ depending on $k$). $\endgroup$ – Zeno Rogue Mar 27 '19 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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