Metric recovery from directed unweighted graphs

Tatsunori B. Hashimoto, Yi Sun, Tommi S. Jaakkola

We analyze directed, unweighted graphs obtained from $x_i\in {\mathbb{R}}^d$ by connecting vertex $i$ to $j$ iff $|x_i-x_j|<\epsilon (x_i)$. Examples of such graphs include $k$-nearest n…