Problem Formulation

Our interest in low-distortion embedding is motivated by its ability to transform the problem of many-to-many matching in finite graphs to the problem of geometric point matching in low-dimensional vector spaces. For graphs, the problem of low-distortion embedding is a challenging one. Let $G_1=({\cal A}_1,E_1,{\cal D}_1)$, $G_2=({\cal A}_2,E_2,{\cal D}_2)$ denote two graphs on vertex sets ${\cal A}_1$ and ${\cal A}_2$, edge sets $E_1$ and $E_2$, under distance metrics ${\cal D}_1$ and ${\cal D}_2$, respectively (${\cal D}_i$ represents the distances between all pairs of nodes in $G_i$). Ideally, we seek a single embedding mechanism that can map each graph to the same vector space, in which the two embeddings can be directly compared. We will tackle the problem in two steps. Given a $d$-dimensional target space ${\mathbb{R}}^d$, we will seek low-distortion embeddings $f_i$ that map sets ${\cal A}_i$ to sets ${\cal B}_i$ under distance function $\vert\vert.\vert\vert _k$, $i\in\{1,2\}$. The fixed-dimension embedding is based on a novel spherical coding of the shortest-path metric on a tree. To apply this embedding to our directed acyclic graphs therefore requires that we map them to trees with low distortion. It is here that we introduce the concept of relative scale to the points, allowing us to match hierarchical graphs. Using these mappings, the problem of many-to-many hierarchical vertex matching between $G_1$ and $G_2$ is reduced to that of computing a mapping ${\cal M}$ between subsets of ${\cal B}_1$ and ${\cal B}_2$. It is known that a minimum-distortion embedding of a metric tree into the $d$-dimensional Euclidean space will have distortion of $O(L^{\frac{1}{d-1}}{\sqrt{\min(\log L, d)}})$, where $L$ is the number of leaves in the tree [8]. Observe that as the dimension $d$ of the target space decreases, the distortion of the embedding increases. We would therefore like to strike a good balance between distortion and dimension.