How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following.
Given a graph $G = \{V,E\}$, we have a distance matrix (the shortest path matrix of $G$)
\begin{equation} \mathbf{D}_t=\{\theta_{u,v}|\forall v,u\in V\}, \end{equation} how to embed the graph $G$ into the $(k,d)$-kautz metric space, that is, optimize the coordinate $x_v$ of each node $v$ in the $(k,d)$-kautz metric space to minimize the difference between $\rho(x_v,x_u)$ and the distance matrix $\mathbf{D}_t$, as \begin{equation} \label{eq:kautz_mds} \min_{\{x_v|\forall v \in V\}} \sum_{\forall v,u\in V} |\rho(x_v,x_u) - \theta_{u,v}| \ \ (1) \end{equation} where the coordinate $x_v$ is a string of $k$ characters and $\rho(x_v,x_u)$ represents the distance between $x_v$ and $x_u$. In the coordinate string $x_v$, each character has $d$ choices, and the adjacent characters are different, which is formulated as \begin{equation*} \begin{split} &x_v = a_{1,v} a_{2,v} ...a_{2,v}...a_{k,v},\\ % \textrm{s.t.\ } &\textrm{where}\ \ \forall i\in[1,k-1], a_{i,v} \in [1,d], \ a_{i,v}\neq a_{i+1,v}. \end{split} \end{equation*} The distance $\rho(x_v,x_u)$ is the length of the longest common prefix and suffix between $x_v$ and $x_u$, which is formulated as \begin{equation} \rho(x_v,x_u)= k-\max(lcp(x_v,x_u), lcp(x_u,x_v)) \end{equation}
\begin{equation} lcp(x_v,x_u) = \max\ i,\ \ \textrm{s.t.}\ a_{1,v}... a_{i,v} = a_{k-i+1,u}... a_{k,u} \end{equation} The optimization problem in Eq. (1) is equivalent to \begin{equation} \label{eq:kautz_mds_transform} \min_{\hat V_s} \|\mathbf{D}_t-S(\mathbf{D}_s,\hat V_s)\|,\ \textrm{s.t.}\ \hat V_s \subset V_s, |\hat V_s| = |V| \ll |V_s|, (2) \end{equation} where $\mathbf{D}_s$ is the distance matrix of all feasible coordinates in the $(k,d)$-kautz metric space, \begin{equation} \mathbf{D}_s=\{\rho(x_v,x_u)|\forall v,u\in V_s\},\ \end{equation} $V_s$ is the set of all feasible coordinates in the $(k,d)$-kautz metric space, and $S$ is to select a sub-matrix $S(\mathbf{D}_s,\hat V_s)$ from $\mathbf{D}_s$, \ie the distance matrix of $\hat V_s$. The problem in Eq. (2) is to select some coordinates $\hat V_s\subset V_s$ as the coordinates of all nodes in the graph $G$ to minimize the difference between the target distance matrix $\mathbf{D}_t$ and the distance matrix $S(\mathbf{D}_s,\hat V_s)$ of $\hat V_s$.
