  Graphs and network data are ubiquitous across a wide spectrum of scientific
and application domains. Often in practice, an input graph can be considered as
an observed snapshot of a (potentially continuous) hidden domain or process.
Subsequent analysis, processing, and inferences are then performed on this
observed graph. In this paper we advocate the perspective that an observed
graph is often a noisy version of some discretized 1-skeleton of a hidden
domain, and specifically we will consider the following natural network model:
We assume that there is a true graph ${G^*}$ which is a certain proximity graph
for points sampled from a hidden domain $\mathcal{X}$; while the observed graph
$G$ is an Erd$\"{o}$s-R$\'{e}$nyi type perturbed version of ${G^*}$.
  Our network model is related to, and slightly generalizes, the
much-celebrated small-world network model originally proposed by Watts and
Strogatz. However, the main question we aim to answer is orthogonal to the
usual studies of network models (which often focuses on characterizing /
predicting behaviors and properties of real-world networks). Specifically, we
aim to recover the metric structure of ${G^*}$ (which reflects that of the
hidden space $\mathcal{X}$ as we will show) from the observed graph $G$. Our
main result is that a simple filtering process based on the \emph{Jaccard
index} can recover this metric within a multiplicative factor of $2$ under our
network model. Our work makes one step towards the general question of
inferring structure of a hidden space from its observed noisy graph
representation. In addition, our results also provide a theoretical
understanding for Jaccard-Index-based denoising approaches.

Computational Geometry