# A quest to unravel the metric structure behind perturbed networks

Srinivasan Parthasarathy  Computer Science and Engineering Dept., The Ohio
State University, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>David
Sivakoff  Statistics and Mathematics Depts., The Ohio State University, USA
<EMAIL_ADDRESS>Minghao Tian  Computer Science and Engineering Dept.,
The Ohio State University, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Yusu Wang
Computer Science and Engineering Dept., The Ohio State University, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

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ös-Ré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 _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.

##  1 Introduction

Graphs and networks are ubiquitous across a wide spectrum of scientific and
application domains. Analyzing various types of graphs and network data play a
fundamental role in modern data science. In the past several decades, there
has been a large amount of research studying various aspects of graphs,
ranging from developing efficient algorithms to process graphs, to information
retrieval and inference based on graph data.

In many cases, we can view an input graph as an observed (discrete) 1-skeleton
of a (potentially continuous) hidden domain or process. Subsequent analysis,
processing, and inferences are then performed on this observed graph, with the
ultimate goal being to understand the hidden space where the graph is sampled
from. Many beautiful generative models for graphs have been proposed [9, 19],
aiming to understand this transition process from a hidden space to the
observed 1-skeleton, and to facilitate further tasks performed on graphs.

One line of such generative graph models assumes that an observed network is
obtained by adding random perturbation to a specific type of underlying
“structured graph” (such as a grid or a ring). For example, the much-
celebrated small-world model by Watts and Strogatz [25] generates a graph by
starting with a $k$-nearest neighbor graph spanned by nodes regularly
distributed along a ring. It then randomly “rewires” some of the edges
connecting neighboring points to instead connect nodes possibly far away.
Watts and Strogatz showed that this simple model can generate networks that
possess features of both a random graph and a proximity graph, and display two
important characteristics often seen in real networks: low diameter in
shortest path metric and high clustering coefficients. There have since been
many variants of this model proposed so as to generate networks with different
properties, such as adding random edges in a distance-dependent manner [22,
15], or extending similar ideas to incorporate hierarchical structures in
networks; e.g, [16, 24]. There have also been numerous studies on
characterizing statistical summaries, such as the average path lengths or the
degree distributions, of small-world like networks; e.g [5, 11]; see [23, 6]
for a survey.

#### Our work.

In this paper, we take the perspective that an observed graph can be viewed as
a noisy snapshot of the discretized 1-skeleton of a hidden domain of interest,
and propose the following network model: Assume that the hidden space that
generates data is a “nice” measure $\mu$ supported on a compact metric space
$\mathcal{X}=(X,d_{X})$ (e.g, the uniform measure supported on an embedded
smooth low-dimensional Riemannian manifold). Suppose that the data points $V$
are sampled i.i.d from this measure $\mu$, and the “true graph” ${G_{r}^{*}}$
connecting them is the $r$-neighborhood graph spanned by $V$ (i.e, two points
$u,v$ are connected if their distance $d_{X}(u,v)\leq r$). The observed graph
$G$ however is only a noisy version of the true proximity graph ${G_{r}^{*}}$,
and we model this noise by an Erdös-Rényi (ER) type perturbation – each edge
in the true graph ${G_{r}^{*}}$ can be deleted with probability $p$, while a
“short-cut” edge between two unconnected nodes $u,v$ could be inserted to $G$
with probability $q$.

To motivate this model, imagine in a social network a person typically makes
friends with other persons that are close to herself in the unknown feature
space modeled by our metric space $\mathcal{X}$. The distribution of people
(graph nodes) is captured by the measure $\mu$ on $\mathcal{X}$. However,
there are always (or may be even many) exceptions – friends could be
established by chance, and two seemingly similar persons (say, close
geographically and in tastes) may not develop friendship. Thus it is
reasonable to model an observed social network $G$ as an ER-type perturbation
of the proximity graph ${G_{r}^{*}}$ to account for such exceptions.

The general question we hope to address is how to recover various properties
of the hidden domain $\mathcal{X}$ from the observed graph $G$. In this paper
we investigate a specific problem: how to recover the metric structure of
${G_{r}^{*}}$ (induced by the shortest path distances in ${G_{r}^{*}}$) from
the noisy observation $G$. As we show in Theorem 2.5, the metric structure of
${G_{r}^{*}}$ “approximates” that of the hidden domain $\mathcal{X}$. Note
that a few inserted “short-cuts” could significantly change the shortest path
metric, one potential factor leading to the small-world phenomenon. Our main
result is that a simple filtering procedure based on the so-called _Jaccard
index_ can recover the shortest path metric of ${G_{r}^{*}}$ within a
multiplicative factor of $2$ (with high probabilities). We also provide some
preliminary experimental results.

#### Remarks and discussion.

The problem of recovering ${G_{r}^{*}}$ from the observed graph $G$ is
different and orthogonal to the usual studies on similar network models: Those
studies often focus on characterizing the graphs generated by such models and
whether those characteristics match with real networks. We instead aim to
recover metric structure of a hidden true graph ${G_{r}^{*}}$ from a given
graph $G$. There are different motivations for this task. For example, it
could be that the true graph ${G_{r}^{*}}$ is the real object of interest, and
we wish to “denoise” the observed graph $G$ to get a more accurate
representation of ${G_{r}^{*}}$. Indeed, in [12], Godberg and Roth empirically
show how to use small-world model to help remove false edges in protein-
protein interaction (PPI) networks. See [4] for more examples.

Furthermore, even if the observed graph $G$ is of interest itself, we may
still want to recover information about the domain $\mathcal{X}$ where $G$ is
generated from. For example, suppose we are given two networks $G_{1}$ and
$G_{2}$ modeling say the collaboration networks from two different
disciplines, and our goal is to compare the hidden collaboration structures
behind the two disciplines. Comparing the precise graph structures of observed
graphs $G_{1}$ and $G_{2}$ could be misleading, as even if they are generated
from the same hidden space $\mathcal{X}$, they could still look different due
to the random generation process. It is more robust if we can compare the two
hidden spaces generating them instead.

Finally, we remark that similar to the small-world network models, our model
also overlays a random perturbation over a “structured” network. Indeed, our
network model in some sense generalizes the small-world network model by Watts
and Strogatz. Specifically, in the model by Watts and Strogatz (and some later
variants), the underlying “structured” network is a ring (or lattice). In our
case, we assume that graph nodes $P$ are sampled from a measure $\mu$ and
using the $r$-neighborhood proximity graph ${G_{r}^{*}}$ to model this
underlying “structured” network. This setup adds generality to our model: For
example, it allows us to produce non-uniform and more complex degree
distributions than those previously produced by starting with lattice
vertices. At the same time, by putting conditions on the measure $\mu$, it
still gives us sufficient structure to relate ${G_{r}^{*}}$ and $G$, as we
will show in this paper. We also point out that the theoretical results hold
for graphs across a range of density, where the number of edges could range
from $\Theta(n\log n)$ to $\Theta(n^{2})$.

##  2 Model for Perturbed Network

We now introduce a general model to generate an observed network $G$. Suppose
we are given a compact geodesic metric space $\mathcal{X}=(X,d_{X})$ 111A
geodesic metric space is a metric space where any two points in it are
connected by a path whose length equals the distance between them. Riemannian
manifolds or path-connected compact sets in the Euclidean space are all
geodesic metric spaces. [7]. Intuitively, we view an observed graph $G=(V,E)$
as a noisy 1-skeleton of $\mathcal{X}$, where graph nodes $V$ of $G$ are
sampled from this hidden metric space. More precisely, we will assume that $V$
is sampled i.i.d. from a measure $\mu$ supported on $X$.

######  Definition 2.1 (Measure)

Given a topological space $X$, a _measure_ $\mu$ on $X$ is simply a function
that maps every Borel subset $B$ of $X$ to a non-negative number $\mu(B)$,
such that $\mu(\emptyset)=0$ and $\mu$ is $\sigma$-additive: that is the
measure of a countable family of pairwise-disjoint Borel subsets of $X$ equals
the sum of their respective measures.

In this paper, a measure is always a _probability measure_ , meaning that
$\mu(X)=1$. To provide sufficient structure to the observed graph $G$ so that
it is not completely arbitrary, we want to assert some reasonable conditions
on $\mu$. To this end, we consider doubling measures:

######  Definition 2.2 (Doubling measure [13])

Given a metric space $\mathcal{X}=(X,d_{X})$, let $\mathrm{B}(x,r)\subset X$
denotes the open metric ball $\mathrm{B}(x,r)=\\{y\in X\mid d_{X}(x,y)<r\\}$.
A measure $\mu$ on $\mathcal{X}$ is said to be _doubling_ if balls have finite
and positive measure and there is a constant $L=L(\mu)$ s.t. for all $x\in X$
and any $r>0$, we have $\mu(\mathrm{B}(x,2r))\leq L\cdot\mu(\mathrm{B}(x,r))$.
We call $L$ the _doubling constant_ and say $\mu$ is an _$L$ -doubling
measure_.

These conditions on the measure also implies conditions on the underlying
space $X$ supporting the measure. Specifically, it is known that any metric
space supporting a doubling measure has to be doubling as well, with its
doubling constant depending on that of the measure [13].

#### Network model.

We now describe our network model. Given a compact metric space
$\mathcal{X}=(X,d_{X})$ and an ${L}$-doubling measure $\mu$ supported on $X$,
let $V$ be a set of $n$ points sampled i.i.d. from $\mu$. We assume that the
_true graph ${G_{r}^{*}}=(V,E^{*})$_ is the $r$-neighborhood graph for some
parameter $r>0$; that is, $E({G^{*}})=E^{*}=\\{(u,v)\mid d_{X}(u,v)\leq
r,u,v\in V\\}$.

###### Definition 2.3

The _observed graph $G(r,p,q)=(V,E)$_ is based on ${G_{r}^{*}}=(V,E^{*})$, but
with the following two types of random perturbations:

$p$-deletion: For each edge $(u,v)\in E^{*}$, $(u,v)$ is in the observed graph
$G(r,p,q)$ with probability $1-p$ (that is, an edge in $E^{*}$ is deleted with
probability $p$).

$q$-insertion: For any pair of nodes $u,v\in V$ s.t. $(u,v)\notin E^{*}$, we
have that $(u,v)\in E$ with probability $q$.

Intuitively, in our model, the observed network $G$ is a random geometric
graph sampled from the metric space $\mathcal{X}$ which then undergoes Erdös-
Rényi type perturbation. In what follows, we often omit the parameters $r,p,q$
from the notations ${G_{r}^{*}}$ and $G(r,p,q)$, when their choices are clear
from the context. Note that both ${G^{*}}$ and $G$ are unweighted graphs (that
is, all edges have weight $1$). We now equip each graph with its shortest path
metric, and obtain two discrete metric space $(V,{d_{{G^{*}}}})$ and
$(V,{d_{G}})$ induced by ${G^{*}}$ and $G$, respectively.

#### Problem statement and main results.

Adding short-cuts (via $q$-insertions) could significantly distort the
shortest path metric in ${G^{*}}$. Our ultimate goal is to infer information
about both $\mathcal{X}$ and $\mu$ where points are sampled from, through the
study of the observed graph $G$. In this paper we aim to recover the metric
structure of ${G^{*}}$ (as a reflection of metric structure of $\mathcal{X}$)
from $G$. Specifically, we show that a simple filtering process based on the
so-called Jaccard index can remove sufficient “bad edges” in $G$ so as to
recover the shortest path metric of ${G^{*}}$ up to a factor of $2$ w.h.p.

######  Definition 2.4 (Jaccard index)

Given an arbitrary graph $G$, let $N_{G}(u)$ denote the set of neighbors of
$u$ in $G$ (i.e. nodes connected to $u\in V(G)$ by edges in $E(G)$). Given any
edge $(u,v)\in E(G)$, the _Jaccard index $\rho_{u,v}$_ of this edge is defined
as

$\displaystyle\rho_{u,v}(G)$ $\displaystyle=\frac{|N_{G}(u)\cap
N_{G}(v)|}{|N_{G}(u)\cup N_{G}(v)|}.$ (1)

We remark that Jaccard index is a popular way to measure similarity between a
pair of nodes connected by an edge in a graph [17], and has been commonly used
in practice for denoising and sparsification purposes [21, 20]. Our results
provide a theoretical understanding for such empirical Jaccard-based denoising
approaches.

The main result is stated in Theorem 4.4. To show how this is established, we
show two results on the influence of the shortest path under the $p$-deletion
(Theorem 3.4) and under the $q$-insertion (Theorem 3.7), respectively. The
proof for Theorem 4.4 combines the ideas for proofs of these two results.

Metric structures for ${G_{r}^{*}}$ versus for $\mathcal{X}$.  Our main
results recover the shortest path metric for ${G_{r}^{*}}$ approximately. In
some sense, the metric of a proximity graph provides an approximation of that
of $X$, the domain where input graph nodes are sampled from; see e.g, [1, 8]
for the case where $X$ is a smooth Riemannian manifold embedded in Euclidean
space. We make this relationship precise for our setting as follows. The proof
of this result is standard (see e.g, the proof of Theorem 5.2 of [8]). For
completeness, we include the proof in Appendix A.

###### Theorem 2.5

Let $(X,d_{X})$ be a compact geodesic metric space and $\mu$ a doubling
measure supported on $X$. Let $V_{n}$ be a set of $n$ points sampled i.i.d.
from $\mu$, and ${G_{r}^{*}}$ the $r$-neighborhood graph constructed on
$V_{n}$ (each edge in ${G_{r}^{*}}$ has equal weight $1$) with the associated
shortest path metric $d_{G_{r}^{*}}$. For any sample $V_{n}$, consider the
distance between $r\cdot d_{G_{r}^{*}}$ ($d_{G_{r}^{*}}$ scaled by $r$) and
$d_{X}$ restricted to the sample $V_{n}$; that is,

$\|r\cdot d_{G_{r}^{*}}-d_{X}|_{V_{n}}\|_{\infty}:=\max_{v,v^{\prime}\in
V_{n}}|r\cdot d_{G_{r}^{*}}(v,v^{\prime})-d_{X}(v,v^{\prime})|.$

Then we have that for a fixed $r$, $\limsup_{n\to\infty}\|r\cdot
d_{G_{r}^{*}}-d_{X}|_{V_{n}}\|_{\infty}\leq r$ almost surely.

##  3 Recovering the shortest path metric of ${G^{*}}$

To illustrate the main idea, we first consider the deletion-only and
insertion-only perturbation of the true graph ${G^{*}}$ in Sections 3.1 and
3.2, respectively. As we will see below, the main difficulty lies in handling
insertions (short-cuts). We then combine the two cases and present our main
result, Theorem 4.4. First, we describe one (natural) assumption on $r$ that
we will use later in all our statements.

Note that as $r$ tends to $0$, the corresponding $r$-neighborhood graph may be
very sparse, and a sparse graph ${G_{r}^{*}}$ is quite sensitive to random
deletions and insertions. We would like to consider $r$ in a range where is
meaningful. We make the following assumption, asserting a lower-bound on the
mass contained inside any metric ball of radius $r/2$:

[Assumption-R]: The parameter $r$ is large enough such that for any $x\in X$,
$\mu(\mathrm{B}(x,\frac{r}{2}))\geq{\mathrm{s}}$ where ${\mathrm{s}}$
satisfies ${\mathrm{s}}\geq\frac{12\ln n}{n-2}(=\Omega(\frac{\ln n}{n})).$

Intuitively, $r$ is large enough such that with high probability each vertex
$v$ in ${G_{r}^{*}}$ has degree $\Omega(\ln n)$. Note that requiring $r$ to be
large enough to have an $\Omega(\ln n/n)$ lower bound on the measure of any
metric ball is natural. For example, for a random geometric graph $G(r,n)$
constructed as the $r$-neighborhood graph for points sampled i.i.d. from a
uniform measure on a Euclidean cube, asymptotically this is the same
requirement so that the resulting $r$-neighborhood graph is connected with
high probability [19].

###### Lemma 3.1

Under Assumption-R, with probability at least $1-n^{-5/3}$, all vertices in
${G_{r}^{*}}$ have more than $\frac{s(n-1)}{3}>4\ln n$ neighbors.

###### Proof.

For a fixed vertex $v\in V$, let $n_{v}$ be the number of points in
$(V-\\{v\\})\cap\mathrm{B}(v,r)$. The expectation of $n_{v}$ is
$(n-1)\cdot\mu(\mathrm{B}(v,r))\geq(n-1)\cdot\mu(B(v,\frac{r}{2}))\geq
s(n-1)$. By Chernoff bounds, we thus have that

$\displaystyle\mathrm{P}[n_{v}<\frac{s(n-1)}{3}]$
$\displaystyle\leq\mathrm{P}[n_{v}<\frac{1}{3}(n-1)\mu(\mathrm{B}(v,r))]\leq
e^{-\frac{(\frac{2}{3})^{2}}{2}(n-1)\mu(\mathrm{B}(v,r))}\leq e^{-\frac{8\ln
n}{3}}=n^{-\frac{8}{3}}$

It then follows from the union bound that the probability that all $n$
vertices in $V$ have degree larger than $s(n-1)/3$ is at least $1-n\cdot
n^{-\frac{8}{3}}=1-n^{-5/3}$. ∎

Since $\mu$ is a doubling measure, any two neighbors $(u,v)$ in the
$r$-neighborhood graph ${G_{r}^{*}}$ would share many neighbors. Specifically,
if $(u,v)$ is an edge in ${G_{r}^{*}}$, that is, $d_{X}(u,v)\leq r$, then
$\mathrm{B}(u,r)\cap\mathrm{B}(v,r)$ must contain a metric ball of radius
$r/2$ (say centered at midpoint $z$ of a shortest path connecting $u$ to $v$
in $X$; see Figure 1 (a)). Thus by a similar argument as the proof of Lemma
3.1, we obtain the following bound on the number of common neighbors between
the nodes $u,v$ if edge $(u,v)\in{G^{*}}$.

###### Corollary 3.2

Assume that the graph nodes $V$ of ${G_{r}^{*}}$ are sampled i.i.d from an
$L$-doubling measure $\mu$ supported on a compact geodesic metric space
$(X,d_{X})$. Then under Assumption-R, with probability at least $1-n^{-2/3}$,
any two neighbors $(u,v)\in{G_{r}^{*}}$ have $\frac{s(n-1)}{3}>4\ln
n=\Omega(\ln n)$ number of common neighbors.

###  3.1 Deletion only

In this case, we assume that we will remove each edge in ${G^{*}}$
independently with probability $p$ to obtain an observed empirical graph
${\widehat{G}}$. Our goal is to relate the shortest path metrics
${d_{{G^{*}}}}$ of ${G^{*}}$ and $d_{{\widehat{G}}}$ of ${\widehat{G}}$
respectively. Deletion-only means that shortest path distances in
${\widehat{G}}$ are larger than those in ${G^{*}}$. Furthermore, since any two
nodes $u,v$ connected in ${G^{*}}$ share sufficient number ($\Omega(\ln n)$)
of common neighbors, intuitively, evan after removing a constant fraction of
edges in ${G^{*}}$, we can still guarantee that w.h.p. $u$ and $v$ will have
some common neighbors left, and thus $u$ and $v$ can be connected through that
common neighbor by a path of length $2$ in ${\widehat{G}}$. Hence overall,
w.h.p. the distortion in shortest path distance is at most a factor of $2$.

###### Definition 3.3

Let $G$ and $G^{\prime}$ be two graphs on the same set of nodes $V$, and
equipped with graph shortest path metric $d_{G}$ and $d_{G^{\prime}}$,
respectively. By $d_{G}\leq cd_{G^{\prime}}$, we mean that for any two nodes
$u,v\in V$, we have that $d_{G}(u,v)\leq cd_{G^{\prime}}(u,v)$. We say that
$d_{G^{\prime}}$ is _a $c$-approximation of $d_{G}$_ if $\frac{1}{c}d_{G}\leq
d_{G^{\prime}}\leq cd_{G}$.

######  Theorem 3.4 (Random deletion)

Let $V$ be $n$ points sampled i.i.d. from a probability measure $\mu:X\to{\rm
I\\!R}^{+}$ supported on a compact metric space $(X,d_{X})$. Let ${G^{*}}$ be
the $r$-neighborhood graph for $V$; and ${\widehat{G}}$ a graph obtained by
removing each edge in ${G^{*}}$ independently with probability $p$. Under
Assumption-R and for $p<\frac{1}{2}e^{-\frac{9\ln n}{s(n-1)}}$, we have with
probability at least $1-\frac{1}{n^{\Omega(1)}}$, the shortest path metric
$d_{{\widehat{G}}}$ is a $2$-approximation of the shortest path metric
${d_{{G^{*}}}}$.

Since $s>\frac{12\ln n}{n-1}$, the statement holds for $p<\frac{1}{2e^{3/4}}$.
As $s$ becomes larger, the upper bound on $p$ gets closer to $1/2$.

###### Proof.

For a node $u\in V$, let $N_{G^{*}}(u)$ and $N_{{\widehat{G}}}(u)$ denote the
set of neighbors of $u$ in graph ${G^{*}}$ and graph ${\widehat{G}}$,
respectively.

Since deletion cannot decrease the length of shortest paths, we have
$d_{{G^{*}}}\leq d_{{\widehat{G}}}$. We now show that $d_{\widehat{G}}\leq
2d_{G^{*}}$.

Consider $(u,v)\in E({G^{*}})$. Assume that $u$ and $v$ share $k_{u,v}$ number
of common neighbors; that is, $k_{u,v}=|N_{G^{*}}(u)\cap N_{G^{*}}(v)|$. The
probability that $N_{\widehat{G}}(u)\cap N_{\widehat{G}}(v)=\emptyset$ (i.e,
$u$ and $v$ have no common neighbor in graph ${\widehat{G}}$) is thus at most
$(2p)^{k_{u,v}}$.

On the other hand, by Corollary 3.2, with probability at least $1-n^{-2/3}$ we
have that $k_{u,v}\geq s(n-1)/3$ for all $(u,v)\in E({G^{*}})$. Therefore, the
probability that there exists $(u,v)\in E({G^{*}})$ with
$N_{{\widehat{G}}}(u)\cap N_{\widehat{G}}(v)=\emptyset$ is at most
$n^{-2/3}+n^{2}(2p)^{s(n-1)/3}<n^{-2/3}+n^{2}(e^{-3\ln n})<n^{-1/3}$, where we
used the bound on $p$ to derive the first inequality.

Hence with probability at least $1-n^{-1/3}$, we have that for all edges
$(u,v)\in E({G^{*}})$, their distance in ${\widehat{G}}$ satisfies
$d_{\widehat{G}}(u,v)\leq 2$ (via one of their common neighbor in
$N_{\widehat{G}}(u)\cap N_{\widehat{G}}(v)$). This in turn implies that with
probability at least $1-n^{-1/3}$, for any path $\pi=\langle
v_{1},\ldots,v_{m}\rangle$ in ${G^{*}}$ with length $m$, we can find a path of
length at most $2m$ in ${\widehat{G}}$ to connect $v_{1}$ to $v_{m}$ (as each
edge $(v_{i},v_{i+1})$ in $\pi$ corresponds to a path of length at most $2$ in
${\widehat{G}}$). If $u$ and $v$ are disconnected in ${G^{*}}$, then obviously
they are still disconnected in ${\widehat{G}}$. Hence, for any two $u,v\in V$,
$d_{\widehat{G}}(u,v)\leq 2d_{G^{*}}(u,v)$, and the theorem follows. ∎

###  3.2 Insertion only

Now assume that the observed graph ${\widehat{G}}$ is generated from the true
graph ${G^{*}}$ where all edges in ${G^{*}}$ also exist in ${\widehat{G}}$,
and for any $u,v\in V$ with $(u,v)\notin E({G^{*}})$, we have $(u,v)\in
E({\widehat{G}})$ with probability $q$. In this case, the shortest path metric
can be significantly altered in $d_{\widehat{G}}$. Hence to recover the metric
$d_{G^{*}}$, instead of operating on $\widehat{G}$ directly, we will construct
_another graph_ ${\tilde{G}}$ from $\widehat{G}$ whose shortest path metric
$d_{{\tilde{G}}}$ approximates $d_{G^{*}}$.

We propose the following Jaccard-Index-based filtering process, which we call
a $\tau$-Jaccard filtering, as it uses a parameter $\tau$. (Recall the
definition of Jaccard index in Def. 2.4). We represent the output filtered
(denoised) graph as ${\tilde{G}}_{\tau}$:

$\tau$-Jaccard filtering: Given graph ${\widehat{G}}$, for each edge $(u,v)\in
E({\widehat{G}})$, we insert the edge $(u,v)$ into $E({\tilde{G}}_{\tau})$ if
and only if $\rho_{u,v}({\widehat{G}})\geq\tau$. That is,
$V({\tilde{G}}_{\tau})=V({\widehat{G}})$ and
$E({\tilde{G}}_{\tau}):=\\{(u,v)\in
E({\widehat{G}})\mid\rho_{u,v}({\widehat{G}})\geq\tau\\}$.

Below we first show that w.h.p., all “good” edges in the true $r$-neighborhood
graph ${G^{*}}$ will have a large Jaccard index, so that they will be kept in
${\tilde{G}}_{\tau}$ after a $\tau$-Jaccard filtering procedure with
appropriate $\tau$. We provide some discussions on the bounds of the
parameters after the proof of this lemma.

###### Lemma 3.5

Let $V$ be a set of $n$ points sampled i.i.d. from an $L$-doubling probability
measure $\mu$ supported on a compact geodesic metric space
$\mathcal{X}=(X,d_{X})$. If Assumption-R holds and $q\leq c{\mathrm{s}}$, then
for $\forall{\tau}\leq\frac{1}{(6+\frac{1}{\ln{n}}+12c)L^{2}}$, we have with
probability at least $1-n^{-2/3}$, that $\rho_{u,v}({\widehat{G}})\geq{\tau}$
for _all_ pairs of nodes $u,v\in V$ with $d_{X}(u,v)\leq r$.

For example, if $c=\frac{1}{2}$ (i.e, $q\leq\frac{{\mathrm{s}}}{2}$), then the
bound on $\rho_{u,v}$ holds for $\tau\leq\frac{1}{13L^{2}}$. Note $c$ may not
be a constant and can depend on $n$; as $c$ increases, the upper bound on
$\tau$ decreases.

###### Proof.

Consider a fixed pair of nodes $u,v\in V$, and let $F=F(u,v)$ be the event
that $d_{X}(u,v)\leq r$. Set ${\alpha}_{*}=|N_{G^{*}}(u)\cap N_{G^{*}}(v)|$ to
be the number of common neighbors of $u$ and $v$ in ${G^{*}}$. Let
${\beta}=|N_{\widehat{G}}(u)\cup N_{\widehat{G}}(v)|$ denote the total number
of neighbors of $u$ and $v$ in the perturbed graph ${\widehat{G}}$.

Since ${\widehat{G}}$ can have only more edges than ${G^{*}}$,
$|N_{\widehat{G}}(u)\cap N_{\widehat{G}}(v)|\geq|N_{G^{*}}(u)\cap
N_{G^{*}}(v)|={\alpha}_{*}$ and thus
$\rho_{u,v}({\widehat{G}})\geq\frac{{\alpha}_{*}}{{\beta}}$. In what follows,
we prove that $\frac{{\alpha}_{*}}{{\beta}}\geq{\tau}\cdot I_{F}$ (which
implies that $\rho_{u,v}({\widehat{G}})\geq{\tau}\cdot I_{F}$) with
probability at least $1-2n^{-8/3}$. (Here, we use $I_{A}$ to denote the
indicator random variable of the event $A$, and the conventions that
$\rho_{u,v}({\widehat{G}})=0$ if $(u,v)\notin{\widehat{G}}$ and $0/0=0$.)

Note that ${\alpha}_{*}$ is a random variable, which equals the number of
(i.i.d. sampled) points from $V-\\{u,v\\}$ that fall in the region
$\mathrm{B}(u,r)\cap\mathrm{B}(v,r)$. That is, conditional on $u$ and $v$,
${\alpha}_{*}$ is drawn from a binomial distribution
$Bin(n-2,p_{{\alpha}_{*}})$ with
$p_{{\alpha}_{*}}=\mu(\mathrm{B}(u,r)\cap\mathrm{B}(v,r))$, and the
conditional expectation of ${\alpha}_{*}$ given $u$ and $v$ is
$\delta_{{\alpha}_{*}}=(n-2)\cdot p_{{\alpha}_{*}}$.

Now observe that, conditional on $u$ and $v$, the random variable ${\beta}-2$
(see footnote222The subtraction of $2$ in ${\beta}-2$ accounts for points $u$
and $v$, which are in $N_{\widehat{G}}(u)\cup N_{\widehat{G}}(v)$. Similarly,
in the binomial distribution we will have only $n-2$, accounting for points in
$V-\\{u,v\\}$.) has distribution $Bin(n-2,p_{{\beta}})$ with
$p_{\beta}=p_{{\beta}_{*}}+(1-p_{{\beta}_{*}})(2q-q^{2})$, where
$p_{{\beta}_{*}}=\mu(\mathrm{B}(u,r)\cup\mathrm{B}(v,r))$. Indeed, observe
that, conditional on $u$ and $v$, points contributing to ${\beta}$ can be
generated as follows. Let $U=\mathrm{B}(u,r)\cup\mathrm{B}(v,r)$.
Independently, for each $i=1,\ldots,n-2$, we draw a point $x_{i}$ randomly
from $\mu$ and we also perform an independent coin flip for this point, with
probability of heads equal to $1-(1-q)^{2}=2q-q^{2}$. This quantity is the
probability for a point outside $U$ to be connected to either $u$ or $v$ under
edge-insertion probability $q$. We set the indicator variable $y_{i}=1$ iff
either $x_{i}\in U$, or $x_{i}\notin U$ and the $i^{\text{th}}$ coin flip is
heads. Conditional on $u$ and $v$, the resulting $n-2$ indicator random
variables $y_{1},\ldots,y_{n-2}$ are i.i.d. with $\mathrm{P}[y_{i}=1\mid
u,v]=p_{{\beta}_{*}}+(1-p_{{\beta}_{*}})(2q-q^{2})=p_{\beta}$. Therefore,
given $u$ and $v$, the distribution of $\beta-2=\sum y_{i}$ is
$Bin(n-2,p_{\beta})$. The conditional expectation of ${\beta}$ given $u$ and
$v$, denoted $\delta_{\beta}$, satisfies

$(n-2)\cdot p_{{\beta}_{*}}\leq\delta_{{\beta}}=(n-2)\cdot
p_{\beta}+2\leq(n-2)\cdot p_{{\beta}_{*}}+(n-2)\cdot 2q+2.$ (2)

Let us for now assume that
$\frac{c_{1}\delta_{{\alpha}_{*}}}{c_{2}\delta_{{\beta}}}\geq{\tau}I_{F}$ a.s.
for constants $c_{1}=1-\sigma_{1}$ and $c_{2}=1+\sigma_{2}$ with
$0<\sigma_{1}<1$ and $0<\sigma_{2}$ to be set shortly.

If $d_{X}(u,v)\leq r$, then $\mathrm{B}(u,r)\cap\mathrm{B}(v,r)$ contains at
least one metric ball of radius $r/2$ (say $\mathrm{B}(z,r/2)$ with $z$ being
the mid-point of a shortest path between $u$ and $v$ in $\mathcal{X}$; see
Figure 1 (a)).

|  |
---|---|---
(a) |  | (b)
Figure 1: In these figures, we draw metric balls as Euclidean balls just for
illustration purpose. (a) illustrates the bound
$p_{{\alpha}*}\geq\mu(\mathrm{B}(z,r/2))$ which follows from
$\mathrm{B}(z,r/2)\subseteq\mathrm{B}(u,r)\cap\mathrm{B}(v,r)$. (b) Key
observation for Lemma 3.6: as $d_{X}(u,v)>r$, we have that the region
$[B(u,r)\cup B(v,r)]\setminus[B(u,r)\cap B(v,r)]$ contains at least two metric
balls, each of radius $r/2$.

Hence by Assumption-R, on the event $d_{X}(u,v)\leq r$, we have

$\delta_{{\alpha}_{*}}\geq(n-2)\cdot\mu(\mathrm{B}(z,r/2))\geq(n-2)\cdot\frac{12\ln
n}{n-2}=12\ln n.$

Similarly, using (2), the conditional expectation of ${\beta}$ satisfies

$\displaystyle\delta_{{\beta}}\geq(n-2)\cdot p_{{\beta}_{*}}$
$\displaystyle\geq(n-2)\cdot\mu(\mathrm{B}(u,r))\geq 12\ln n.$ (3)

We now set $\sigma_{1}=2/3$ and $\sigma_{2}=1$. It then follows from Chernoff
bounds that

$\mathrm{P}[{\alpha}_{*}<c_{1}\delta_{{\alpha}_{*}}\mid
u,v,F]+\mathrm{P}[{\beta}>c_{2}\delta_{{\beta}}\mid u,v]\leq
e^{-\frac{\sigma_{1}^{2}}{2}\delta_{{\alpha}_{*}}}+e^{-\frac{\sigma_{2}}{3}\delta_{{\beta}}}~{}\leq
n^{-\frac{8}{3}}+n^{-4}.$

Taking expectation of the above with respect to $u$ and $v$ gives

$\mathrm{P}[{\alpha}_{*}<c_{1}\delta_{{\alpha}_{*}}\mid
F]+\mathrm{P}[{\beta}>c_{2}\delta_{{\beta}}]\leq 2n^{-\frac{8}{3}}.$ (4)

On the other hand, since $\frac{{\alpha}_{*}}{{\beta}}\geq 0$, we have

$\displaystyle\mathrm{P}[\frac{{\alpha}_{*}}{{\beta}}<{\tau}I_{F}]$
$\displaystyle\leq\mathrm{P}[\frac{{\alpha}_{*}}{{\beta}}<{\tau}\mid({\alpha}_{*}\geq
c_{1}\delta_{{\alpha}_{*}})\wedge({\beta}\leq c_{2}\delta_{{\beta}})\wedge F]$
(5) $\displaystyle\hskip
10.0pt+\mathrm{P}[(\\{{\alpha}_{*}<c_{1}\delta_{{\alpha}_{*}}\\}\vee\\{{\beta}>c_{2}\delta_{{\beta}}\\})\wedge
F].$

Since we assumed that
$\frac{c_{1}\delta_{{\alpha}_{*}}}{c_{2}\delta_{{\beta}}}\geq{\tau}I_{F}$, if
${\alpha}_{*}\geq c_{1}\delta_{{\alpha}_{*}}$ and ${\beta}\leq
c_{2}\delta_{{\beta}}$ and $d_{X}(u,v)\leq r$, then we have
$\frac{{\alpha}_{*}}{{\beta}}\geq\frac{c_{1}\delta_{{\alpha}_{*}}}{c_{2}\delta_{\beta}}\geq{\tau}$.
This means that

$\mathrm{P}[\frac{{\alpha}_{*}}{{\beta}}<{\tau}\mid({\alpha}_{*}\geq
c_{1}\delta_{{\alpha}_{*}})\wedge({\beta}\leq c_{2}\delta_{{\beta}})\wedge
F]=0.$

Hence the first term in the right-hand side of (5) is 0. Together with (4),
and recalling $\rho_{u,v}({\widehat{G}})\geq\frac{{\alpha}_{*}}{{\beta}}$, we
have

$\displaystyle\mathrm{P}[\rho_{u,v}({\widehat{G}})$
$\displaystyle<{\tau}I_{F}]\leq\mathrm{P}[\frac{{\alpha}_{*}}{{\beta}}<{\tau}I_{F}]\leq
2n^{-\frac{8}{3}}.$

By the union bound, the probability that $\rho_{u,v}({\widehat{G}})\geq{\tau}$
for all pairs of nodes $u,v\in V$ such that $d_{X}(u,v)\leq r$ is thus at
least $1-\frac{1}{2}n^{2}(2n^{-\frac{8}{3}})=1-n^{-\frac{2}{3}}$.

Finally, we need to verify that
$\frac{c_{1}\delta_{{\alpha}_{*}}}{c_{2}\delta_{{\beta}}}=\frac{\delta_{{\alpha}_{*}}}{6\delta_{\beta}}\geq{\tau}I_{F}$
holds for a.e. $u$ and $v$. This holds automatically if $d_{X}(u,v)>r$, so
assume $d_{X}(u,v)\leq r$. Recall that $\delta_{\beta}\leq(n-2)\cdot
p_{{\beta}_{*}}+(n-2)\cdot 2q+2$ by (2). Since $q\leq c{\mathrm{s}}$, we have
$(n-2)2q\leq 2(n-2)c{\mathrm{s}}$. On the other hand, by Assumption-R,
$p_{{\beta}_{*}}\geq\mu(\mathrm{B}(u,r))\geq{\mathrm{s}}$, hence $2(n-2)q\leq
2(n-2)c\cdot p_{{\beta}_{*}}$. Combining this with the fact that
$(n-2)p_{{\beta}_{*}}\geq 12\ln{n}$ from (3) (which also implies that
$2\leq\frac{(n-2)p_{{\beta}_{*}}}{6\ln n}$), it then follows that

$\displaystyle\frac{\delta_{{\alpha}_{*}}}{6\delta_{\beta}}\geq\frac{\delta_{{\alpha}_{*}}}{6((n-2)(1+\frac{1}{6\ln{n}})p_{{\beta}_{*}}+2(n-2)c\cdot
p_{{\beta}_{*}})}=\frac{p_{{\alpha}_{*}}}{p_{{\beta}_{*}}}\cdot\frac{1}{6+\frac{1}{\ln{n}}+12c}.$
(6)

Now let $z$ be the midpoint of a geodesic connecting $u$ and $v$; see Figure 1
(a). Observe that $p_{{\alpha}_{*}}\geq\mu(\mathrm{B}(z,r/2))$,
$p_{{\beta}_{*}}\leq\mu(\mathrm{B}(z,2r))$ and since $\mu$ is $L$-doubling, we
have:

$\displaystyle p_{{\beta}_{*}}\leq\mu(\mathrm{B}(z,2r))\leq
L\mu(\mathrm{B}(z,r))\leq L^{2}\mu(\mathrm{B}(z,r/2))\leq
L^{2}p_{{\alpha}_{*}}.$ (7)

Combining equations (6) and (7), we have that if
${\tau}\leq\frac{1}{(6+\frac{1}{\ln{n}}+12c)L^{2}}$, then
$\frac{\delta_{{\alpha}_{*}}}{6\delta_{\beta}}\geq{\tau}$ is satisfied. This
proves the lemma. ∎

#### Discussion on the bounds of parameters.

Lemma 3.5 implies that, with high probability, we will not remove any good
edges if the doubling constant $L$ of the measure is at most
$O(\frac{1}{\sqrt{\tau}})$ and the insertion probability is small ($q\leq
cs$). The requirement that $L=O(\frac{1}{\sqrt{\tau}})$ is rather mild; we now
inspect the requirement $q\leq cs$: Since $sn$ lower-bounds the degree of a
node in the true graph ${G^{*}}$ (by Lemma 3.1), it is reasonable that the
insertion probability $q$ is required to be small compared to $s$; as
otherwise, the “noise” (inserted edges) will overwhelm the signal (original
edges). Furthermore, it is important to note that $c$ is not necessarily a
constant – It can depend on $n$, but as $c$ increases, the upper bound of the
admissible range for parameter $\tau$ decreases.

The following result complements Lemma 3.5 by stating that for insertion
probability $q\leq cs$, all “really bad” edges in ${\widehat{G}}$ will have
small Jaccard index, and thus will be removed by our $\tau$-filtering process.

In particular, we define an edge $(u,v)\in E({\widehat{G}})\setminus
E({G^{*}})$ in the observed graph ${\widehat{G}}$ to be _really-bad_ if
$N_{{G^{*}}}(u)\cap N_{{G^{*}}}(v)=\emptyset$. Note that $(u,v)\notin
E({G^{*}})$ is equivalent to $d_{X}(u,v)>r$.

###### Lemma 3.6

Let $V$ be a set of $n$ points sampled i.i.d. from an $L$-doubling probability
measure $\mu$ supported on a compact metric space $\mathcal{X}=(X,d_{X})$. If
Assumption-R holds and $q\leq c{\mathrm{s}}$, then for
$\forall{\tau}\geq(c+2)q+2(c+2)\sqrt{\frac{\ln{n}}{s(n-2)}}$, we have with
probability at least $1-n^{-2}$, $\rho_{u,v}({\widehat{G}})<{\tau}$ for _all_
pairs of nodes $u,v\in V$ such that $(u,v)$ is really-bad.

For example, if $c=1$ and ${\mathrm{s}}\cdot n=\omega(\ln{n})$, then the
condition on ${\tau}$ is that ${\tau}>3q+o(1)$.

###### Proof.

Consider a fixed pair of nodes $u,v\in V$, and let $F=F(u,v)$ be the event
that $N_{{G^{*}}}(u)\cap N_{{G^{*}}}(v)=\emptyset$ and $d_{X}(u,v)>r$. Let
${\alpha}=|N_{\widehat{G}}(u)\cap N_{\widehat{G}}(v)|$,

$\displaystyle{\alpha}_{I}$ $\displaystyle=\big{|}\\{x\in N_{G^{*}}(u)\cup
N_{G^{*}}(v)\,:\,x~{}\text{is connected to
both}~{}u~{}\text{and}~{}v~{}\text{in}~{}{\widehat{G}}\\}\big{|},~{}\text{and}$
$\displaystyle{\alpha}_{o}$ $\displaystyle=\big{|}\\{x\notin N_{G^{*}}(u)\cup
N_{G^{*}}(v)\,:\,x~{}\text{is connected to
both}~{}u~{}\text{and}~{}v~{}\text{in}~{}{\widehat{G}}\\}\big{|}.$

Then we have ${\alpha}={\alpha}_{I}+{\alpha}_{o}$. Set
${\beta}_{*}=|N_{G^{*}}(u)\cup N_{G^{*}}(v)|$, so we have
$|N_{\widehat{G}}(u)\cup
N_{\widehat{G}}(v)|\geq{\beta}_{*}+{\alpha}_{o}=:{\beta}$. It is easy to see
that

$\rho_{u,v}({\widehat{G}})=\frac{{\alpha}}{|N_{\widehat{G}}(u)\cup
N_{\widehat{G}}(v)|}\leq\frac{{\alpha}}{{\beta}_{*}+{\alpha}_{o}}=\frac{{\alpha}}{{\beta}}.$

We aim to show that with high probability
$\frac{{\alpha}}{{\beta}}I_{F}<\tau$, which would then imply that
$\rho_{u,v}({\widehat{G}})I_{F}<\tau$.

Similar to the proof of Lemma 3.5, we wish to understand the conditional
distribution of random variables ${\alpha}$ and ${\beta}$ given $u$, $v$ and
$F$. A slight complication here is that it is possible that $B(u,r)\cap
B(v,r)\neq\emptyset$. However, if $(u,v)$ is really-bad, we have
$N_{{G^{*}}}(u)\cap N_{{G^{*}}}(v)=\emptyset$, meaning that there is no sample
point from $V$ falls inside $B(u,r)\cap B(v,r)$ even if the region $B(u,r)\cap
B(v,r)\neq\emptyset$. We claim that, conditional on the locations of $u$ and
$v$ and the event $F$, the distribution of ${\alpha}$ is $Bin(n-2,p_{\alpha})$
with
$p_{\alpha}=\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q+\frac{1-p_{{\beta}_{*}}}{1-p^{\prime}}q^{2}$
where $p_{{\beta}_{*}}=\mu(B(u,r)\cup B(v,r))$ and $p^{\prime}=\mu(B(u,r)\cap
B(v,r))$. (Note, $p^{\prime}$ is $0$ if $B(u,r)\cap B(v,r)=\emptyset$.)
Indeed, we can imagine that, conditional on $u$, $v$ and $F$, points
contributing to ${\alpha}$ can be generated as follows:

Let $U=[B(u,r)\cup B(v,r)]\setminus[B(u,r)\cap B(v,r)]$. Define the measure
$\mu^{\prime}:X\setminus[B(u,r)\cap B(v,r)]\to{\rm I\\!R}$ to be the re-
normalization of the probability distribution $\mu|_{X\setminus[B(u,r)\cap
B(v,r)]}$ restricted to the domain outside $B(u,r)\cap B(v,r)$; that is, for
any region $R\subset X\setminus[B(u,r)\cap B(v,r)]$,
$\mu^{\prime}(R)=\mu(R)/(1-p^{\prime})$.

We now draw a point $x_{i}$ randomly from the measure $\mu^{\prime}$. The
reason to exclude $B(u,r)\cap B(v,r)$ is because by our assumption,
$N_{{G^{*}}}(u)\cap N_{{G^{*}}}(v)=\emptyset$; meaning ${\alpha}$ is
conditioned on $V\cap[B(u,r)\cap B(v,r)]=\emptyset$. We next flip two coins:
For the first coin, the probability for head equals to $q$; while for the
second one, the probability for head is $q^{2}$. We set the indicator variable
$y_{i}=1$ if

(i) $x_{i}$ falls in $U$ and the first coin flip returns head, corresponding
to the case where $x_{i}$ contributes to ${\alpha}_{I}$, or

(ii) $x_{i}$ does not fall in $U$ but the second coin flip returns head,
corresponding to the case where $x_{i}$ contributes to ${\alpha}_{o}$.

Conditional on $u$, $v$ and $F$, the resulting $n-2$ indicator random
variables $y_{1},\cdots,y_{n-2}$ are i.i.d. with
$\mathrm{P}[y_{i}=1]=\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q+\frac{1-p_{{\beta}_{*}}}{1-p^{\prime}}q^{2}=p_{\alpha}$.
Therefore, given $u$, $v$ and $F$, the distribution of ${\alpha}=\sum y_{i}$
is $Bin(n-2,p_{\alpha})$.

By a similar argument, we claim that the conditional distribution of ${\beta}$
is $Bin(n-2,p_{\beta})$ with
$p_{\beta}=\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}+\frac{1-p_{{\beta}_{*}}}{1-p^{\prime}}q^{2}.$

If $d_{X}(u,v)>r$, the region $[B(u,r)\cup B(v,r)]\setminus[B(u,r)\cap
B(v,r)]$ contains at least two metric balls of radius $r/2$; see Figure 1 (b).
Therefore, $p_{{\beta}_{*}}-p^{\prime}\geq 2\mu(B(\frac{r}{2}))\geq 2s$. The
conditional expectation of ${\alpha}$ given $u$, $v$ and $F$, denoted by
$\delta_{\alpha}(=(n-2)p_{\alpha})$, satisfies:

$\displaystyle(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q\leq\delta_{{\alpha}}=(n-2)[\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q+\frac{1}{1-p^{\prime}}q^{2}]\leq(c/2+1)(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q$
(8)

where the last inequality uses that $q\leq cs\leq
c\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{2}$. The conditional expectation of
${\beta}$ given $u$, $v$ and $F$, denoted by $\delta_{\beta}$, satisfies:

$\displaystyle\delta_{\beta}=(n-2)p_{\beta}\geq(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}.$
(9)

Let us for now assume that
$\frac{c_{1}\delta_{{\alpha}}}{c_{2}\delta_{{\beta}}}I_{F}\leq\tau$ a.s. for
$c_{1}=1+\epsilon$ and some constant $c_{2}=1-\sigma$ with
$\epsilon=\frac{2}{q}\sqrt{\frac{\ln{n}}{s(n-2)}}$ and some $0<\sigma<1$ to be
set later.

If $q\leq 2\sqrt{\frac{\ln{n}}{s(n-2)}}$, then we have $\epsilon\geq 1$. In
this case, combining Chernoff bounds with (8) and the fact that
$p_{{\beta}_{*}}-p^{\prime}\geq 2\mu(B(\frac{r}{2}))\geq 2s$ obtained earlier,
we have:

$\displaystyle\mathrm{P}[{\alpha}\geq(1+\epsilon)\delta_{{\alpha}}\mid
u,v,F]\leq
e^{-\frac{\epsilon}{3}\delta_{{\alpha}}}=e^{-\frac{2}{3q}\sqrt{\frac{\ln{n}}{s(n-2)}}\delta_{{\alpha}}}\leq
e^{-\frac{2}{3q}\sqrt{\frac{\ln{n}}{s(n-2)}}(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q}$
$\displaystyle\leq e^{-\frac{4}{3}\sqrt{(n-2)(\ln{n})s}}\leq
e^{-\frac{4}{3}\sqrt{(n-2)(\ln{n})\frac{12\ln{n}}{n-2}}}=n^{-\frac{8\sqrt{3}}{3}}.$
(10)

Otherwise, we have $q>2\sqrt{\frac{\ln{n}}{s(n-2)}}$, then $0<\epsilon<1$. In
this case, by Chernoff bounds

$\displaystyle\mathrm{P}[{\alpha}\geq(1+\epsilon)\delta_{{\alpha}}\mid
u,v,F]\leq e^{-\frac{1}{2}\epsilon^{2}\delta_{{\alpha}}}$ $\displaystyle\leq
e^{-2\frac{\ln{n}}{{\mathrm{s}}(n-2)}\frac{1}{q^{2}}(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q}$
$\displaystyle=e^{-2\frac{\ln{n}(p_{{\beta}_{*}}-p^{\prime})}{{\mathrm{s}}q}}\leq
e^{-2\ln{n}\cdot\frac{2{\mathrm{s}}}{{\mathrm{s}}q}}\leq n^{-4}.$ (11)

On the other hand, by Chernoff bounds, we have $\mathrm{P}[{\beta}\leq
c_{2}\delta_{{\beta}}\mid u,v,F]\leq
e^{-\frac{\sigma^{2}}{2}\delta_{{\beta}}}.$ Note that
$\delta_{{\beta}}\geq(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}\geq(n-2)\cdot
2s\geq 24\ln{n}$. We now set $\sigma=1/2$ so $c_{2}=1-\sigma=1/2$. By taking
expectation with respect to $u$ and $v$, we have

$\displaystyle\mathrm{P}[{\alpha}\geq c_{1}\delta_{{\alpha}}\mid
F]+\mathrm{P}[{\beta}\leq c_{2}\delta_{{\beta}}\mid F]\leq 2n^{-4}.$ (12)

Since $\tau>0$, we have that

$\displaystyle\mathrm{P}[\frac{{\alpha}}{{\beta}}I_{F}\geq{\tau}]$
$\displaystyle\leq\mathrm{P}[\frac{{\alpha}}{{\beta}}\geq{\tau}\mid({\alpha}<c_{1}\delta_{{\alpha}})\wedge({\beta}>c_{2}\delta_{{\beta}})\wedge
F]$ (13) $\displaystyle\hskip 15.0pt+\mathrm{P}[\\{({\alpha}\geq
c_{1}\delta_{{\alpha}})\vee({\beta}\leq c_{2}\delta_{{\beta}})\\}\wedge F].$

Under our assumption that
$\frac{c_{1}\delta_{{\alpha}}}{c_{2}\delta_{{\beta}}}I_{F}\leq{\tau}$ a.s., if
${\alpha}<c_{1}\delta_{{\alpha}}$, ${\beta}>c_{2}\delta_{{\beta}}$ and
$d_{X}(u,v)>r$, then
$\frac{{\alpha}}{{\beta}}<\frac{c_{1}\delta_{{\alpha}}}{c_{2}\delta_{B}}\leq{\tau}$.
Therefore, the first term on the right side of (13) is
$\mathrm{P}[\frac{{\alpha}}{{\beta}}\geq{\tau}\mid({\alpha}<c_{1}\delta_{{\alpha}})\wedge({\beta}>c_{2}\delta_{{\beta}})\wedge
F]=0$. It then follows from (12) that:

$\displaystyle\mathrm{P}[\frac{{\alpha}}{{\beta}}I_{F}\geq{\tau}]\leq\mathrm{P}[({\alpha}\geq
c_{1}\delta_{{\alpha}})\vee({\beta}\leq c_{2}\delta_{{\beta}})\mid F]\leq
2n^{-4}$

Since $\rho_{u,v}({\widehat{G}})\leq\frac{{\alpha}}{{\beta}}$, we have
$\mathrm{P}[\rho_{u,v}({\widehat{G}})I_{F}\geq{\tau}]\leq\mathrm{P}[\frac{{\alpha}}{{\beta}}I_{F}\geq{\tau}]\leq
2n^{-4}.$ By union bound, the probability that
$\rho_{u,v}({\widehat{G}})<{\tau}$ for all pairs of nodes $u,v\in V$
satisfying the required conditions is thus at least
$1-\frac{1}{2}n^{2}(2n^{-4})=1-n^{-2}$.

Finally, for the above argument to hold, we need to verify that
$\frac{c_{1}\delta_{{\alpha}}}{c_{2}\delta_{{\beta}}}I_{F}\leq{\tau}$ holds
for a.e. $u$ and $v$, where $c_{1}=1+{\varepsilon}$ and $c_{2}=1/2$. This
holds automatically if event $F$ doesn’t happen, so assume $F$ happens. Recall
that
$\delta_{{\alpha}}\leq(c/2+1)\cdot(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q$
and
$\delta_{{\beta}}\geq(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}$
from (8) and (9). This implies that:

$\displaystyle\frac{2\cdot\big{(}1+\frac{2}{q}\sqrt{\frac{\ln{n}}{{\mathrm{s}}(n-2)}}\big{)}\cdot\delta_{{\alpha}}}{\delta_{{\beta}}}$
$\displaystyle\leq\frac{2[(c/2+1)(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q+(c+2)\sqrt{\frac{\ln{n}}{{\mathrm{s}}(n-2)}}(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}]}{(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}}$
$\displaystyle=(c+2)q+2(c+2)\sqrt{\frac{\ln{n}}{{\mathrm{s}}(n-2)}}.$ (14)

We then have that as long as
${\tau}\geq(c+2)q+2(c+2)\sqrt{\frac{\ln{n}}{{\mathrm{s}}(n-2)}}$, then
$\frac{(1+\frac{2}{q}\sqrt{\frac{\ln{n}}{s(n-2)}})\delta_{{\alpha}}}{c_{2}\delta_{{\beta}}}\leq{\tau}$
is satisfied. The lemma then follows. ∎

The above result implies that after Jaccard filtering, although there still
may be some extra edges remaining in ${\tilde{G}}_{\tau}$, each such edge
$(u,v)$ is not really-bad. In fact, $N_{G^{*}}(u)\cap
N_{G^{*}}(v)\neq\emptyset$ for each such extra remaining edge $(u,v)$,
implying that $d_{G^{*}}(u,v)\leq 2$. This, combined with Lemma 3.5,
essentially leads to the following result. To simplify our statement, we
assume ${\mathrm{s}}n=\omega(\ln{n})$ in the following result; a more
complicated form can be obtained without this assumption (similar to the
statement in Lemma 3.6).

######  Theorem 3.7 (Random Insertion)

Let $V$ be a set of $n$ points sampled i.i.d. from an $L$-doubling measure
$\mu:X\to{\rm I\\!R}^{+}$ supported on a compact metric space $(X,d_{X})$. Let
${G^{*}}$ be the resulting $r$-neighborhood graph for $V$; and ${\widehat{G}}$
a graph obtained by inserting each edge not in ${G^{*}}$ independently with
probability $q$. Let ${\tilde{G}_{\tau}}$ be the graph after $\tau$-Jaccard
filtering of ${\widehat{G}}$. Then, if Assumption-R holds, $q\leq
c{\mathrm{s}}$ and ${\mathrm{s}}n=\omega(\ln{n})$, then for
$\forall\frac{1}{(6+\frac{1}{\ln{n}}12c)L^{2}}\geq{\tau}\geq(c+2)q+o(1)$, with
high probability the shortest path distance metric $d_{{\tilde{G}}_{\tau}}$
satisfies: $\frac{1}{2}d_{G^{*}}\leq d_{\tilde{G}_{\tau}}\leq d_{G^{*}}$; that
is, $d_{\tilde{G}_{\tau}}$ is a $2$-approximation for $d_{G^{*}}$ with high
probability.

###### Proof.

Define $\mathcal{E}_{1}$ to be the event when all the edges in ${G^{*}}$ are
present in ${\tilde{G}}_{\tau}$. By Lemma 3.5, event $\mathcal{E}_{1}$ happens
with probability at least $1-n^{-2/3}$. Hence with at least this probability,
$d_{{\tilde{G}}_{\tau}}\leq d_{G^{*}}$. We now prove the lower bound for
$d_{\tilde{G}_{\tau}}$.

Let $\mathcal{E}_{2}$ be the event where for all edges $(u,v)\in
E({\tilde{G}_{\tau}})\setminus E({G^{*}})$, $(u,v)$ is not really-bad. Lemma
3.6 says that event $\mathcal{E}_{2}$ happens with probability at least
$1-n^{-2}$. To this end, observe that if an edge $(u,v)$ is not really-bad,
then we have that $d_{G^{*}}(u,v)\leq 2$ as $N_{G^{*}}(u)\cap
N_{G^{*}}(v)\neq\emptyset$; specifically, there is a path $u\to w\to v$
connecting $u$ and $v$ through some $w\in N_{G^{*}}(u)\cap N_{G^{*}}(v)$.

In what follows, assume both events $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$
happen – as discussed above, this assumption holds with high probability due
to Lemmas 3.5 and 3.6.

Now consider two points $u,v\in V$. First, suppose that $u,v$ are connected in
${\tilde{G}_{\tau}}$. Let $\pi=\langle u_{0}=u,u_{1},\ldots,u_{s}=v\rangle$ be
a shortest path between them in ${\tilde{G}_{\tau}}$. Consider each edge
$(u_{i},u_{i+1})$ in the shortest path $\pi$ in ${\tilde{G}_{\tau}}$. Either
$(u_{i},u_{i+1})\in E({G^{*}})$, in which case we set
$\hat{\pi}(u_{i},u_{i+1})=(u_{i},u_{i+1})$. Otherwise if
$(u_{i},u_{i+1})\notin E({G^{*}})$, then $(u_{i},u_{i+1})$ is not really-bad
due to event $\mathcal{E}_{2}$, meaning that $d_{G^{*}}(u_{i},u_{i+1})\leq 2$.
Hence we can find a path $\hat{\pi}(u_{i},u_{i+1})\subset{G^{*}}$ of length at
most two to connect $u_{i}$ and $u_{i+1}$ in ${G^{*}}$. Putting these two
together, we can construct a path
$\hat{\pi}=\hat{\pi}(u_{0},u_{1})\circ\hat{\pi}(u_{1},u_{2})\circ\cdots\circ\hat{\pi}(u_{s-1},u_{s})$
connecting $u=u_{0}$ to $v=u_{s}$ in ${G^{*}}$. Clearly, this path has length
at most $2s$. Hence, for any $u,v\in V$, we have that $d_{G^{*}}(u,v)\leq
2d_{\tilde{G}_{\tau}}(u,v)$ if $(u,v)$ is connected in ${\tilde{G}_{\tau}}$.

If $u$ and $v$ are not connected in ${\tilde{G}_{\tau}}$, then they are not
connected in ${G^{*}}$ either; because if there is a path connecting them in
${G^{*}}$, then the same path is present in ${\tilde{G}_{\tau}}$ as event
$\mathcal{E}_{1}$ holds. Putting everything together, we then have that with
high probability, for any $u,v\in V$, $d_{G^{*}}(u,v)\leq
2d_{\tilde{G}_{\tau}}(u,v)$; that is
$d_{\tilde{G}_{\tau}}\geq\frac{1}{2}d_{G^{*}}$. The theorem then follows. ∎

##  4 Combined case

The arguments used in Sections 3.1 and 3.2 can be modified to prove our main
result when the observed graph ${\widehat{G}}=G(r,p,q)$ is generated via the
network model described in Definition 2.3 that includes both edge deletion and
insertion. Specifically, we now discuss the case where the perturbed graph
${\widehat{G}}=G(r,p,q)$ is generated via Definition 2.3. That is, it is an
Erdös-Rényi-type perturbed version of ${G^{*}}$ where with probability $p$ an
edge from ${G^{*}}$ is not present in the observed graph, while with
probability $q$ an edge connecting points $u,v$ with $d_{X}(u,v)>r$ will be
inserted into the observed graph. We still use ${\tilde{G}}_{\tau}$ to denote
the graph after Jaccard-filtering with threshold $\tau$.

First, given two graphs $G_{1}=(V,E_{1})$ and $G_{2}=(V,E_{2})$ spanning on
the same set of vertices, we use $G_{1}\cap G_{2}$ to denote the graph
$(V,E_{1}\cap E_{2})$.

###### Lemma 4.1

Let $V$ be a set of $n$ points sampled i.i.d. from an $L$-doubling probability
measure $\mu$ supported on a compact metric space $\mathcal{X}=(X,d_{X})$. Let
${G^{*}}$ be the $r$-neighborhood graph spanned by $V$, and ${\widehat{G}}$
the observed graph as defined in Definition 2.3. If Assumption-R holds and
$p<\frac{1}{2}e^{-\frac{9\ln n}{s(n-1)}}$, then with probability at least
$1-n^{-\Omega(1)}$, we have that the shortest path metric
$d_{{\widehat{G}}\cap{G^{*}}}$ in the graph ${\widehat{G}}\cap{G^{*}}$ is
bounded from above by $2d_{G^{*}}$, implying $d_{\widehat{G}}\leq
d_{{\widehat{G}}\cap{G^{*}}}\leq 2d_{G^{*}}$.

###### Proof.

Since ${\widehat{G}}\cap{G^{*}}$ is a subgraph of ${\widehat{G}}$, we thus
have $d_{\widehat{G}}\leq d_{{\widehat{G}}\cap{G^{*}}}$. Now by an almost
identical argument as the one used in the proof of Theorem 3.4, we can prove
that $d_{{\widehat{G}}\cap{G^{*}}}\leq 2d_{G^{*}}$ with high probability.
Indeed, compared to the ${\widehat{G}}$ used in Theorem 3.4, our
${\widehat{G}}\cap{G^{*}}$ also contain some randomly inserted edges, which
can only further decrease the shortest path distances. The claim then follows.
∎

###### Lemma 4.2

Let $V$ be a set of $n$ points sampled i.i.d. from an $L$-doubling probability
measure $\mu$ supported on a compact metric space $\mathcal{X}=(X,d_{X})$. If
Assumption-R holds, $p\leq\frac{1}{4}$ and
$q\leq\min\\{\frac{1}{8},c{\mathrm{s}}\\}$, then for
$\forall{\tau}\leq\frac{(1-p)^{2}}{(10+\frac{5}{3\ln{n}}+20c)L^{2}}$, we have
with probability at least $1-n^{-0.16}$, that
$\rho_{u,v}({\widehat{G}})\geq{\tau}$ for _all_ pairs of nodes $u,v\in V$ with
$d_{X}(u,v)\leq r$.

###### Proof.

Consider a fixed pair of nodes $u,v\in V$, and let $F=F(u,v)$ be the event
that $d_{X}(u,v)\leq r$. Set ${\alpha}_{*}=|(N_{{G^{*}}}(u)\cap
N_{{G^{*}}}(v))\cap(N_{{\widehat{G}}}(u)\cap N_{{\widehat{G}}}(v))|$, that is,
the number of common neighbors of $u$ and $v$ in both ${G^{*}}$ and
${\widehat{G}}$; Let ${\beta}=|N_{{\widehat{G}}}(u)\cup N_{{\widehat{G}}}(v)|$
denote the total number of neighbors of $u$ and $v$ in the perturb graph
${\widehat{G}}$. It is easy to see that
$\rho_{u,v}({\widehat{G}})=\frac{|N_{\widehat{G}}(u)\cap
N_{\widehat{G}}(v)|}{|N_{\widehat{G}}(u)\cup
N_{\widehat{G}}(v)|}\geq\frac{{\alpha}_{*}}{{\beta}}$. In what follows, we
will aim to prove that $\frac{{\alpha}_{*}}{{\beta}}\geq{\tau}I_{F}$ with high
probability.

We claim that, conditional on the locations of $u$ and $v$, the distribution
of ${\alpha}_{*}$ is $Bin(n-2,\hat{p}_{{\alpha}_{*}})$ with
$\hat{p}_{{\alpha}_{*}}=p_{{\alpha}_{*}}\cdot(1-p)^{2}$, where
$p_{{\alpha}_{*}}=\mu(\mathrm{B}(u,r)\cap\mathrm{B}(v,r))$. Notice that,
conditional on $u$ and $v$, the distribution of the number of common neighbors
of $u$ and $v$ in ${G^{*}}$ is $Bin(n-2,p_{{\alpha}_{*}})$ and the probability
for each node to be still a common neighbor for both $u$ and $v$ in
${\widehat{G}}$ is $(1-p)^{2}$. Thus, by a similar (but more complicated)
argument as in Lemma 3.5, the conditional expectation of ${\alpha}_{*}$ is

$\delta_{{\alpha}_{*}}=(n-2)\hat{p}_{{\alpha}_{*}}=(n-2)\cdot
p_{{\alpha}_{*}}\cdot(1-p)^{2}.$

and we also claim that, conditional on $u$ and $v$, the distribution of
${\beta}-2$ is $Bin(n-2,p_{{\beta}})$ with
$p_{\beta}=p_{{\alpha}_{*}}(1-p^{2})+(p_{{\beta}_{*}}-p_{{\alpha}_{*}})(1-p+pq)+(1-p_{{\beta}_{*}})(1-(1-q)^{2})$,
where $p_{{\beta}_{*}}=\mu(\mathrm{B}(u,r)\cup\mathrm{B}(v,r))$.

It is easy to see that $p_{{\beta}_{*}}\geq p_{{\alpha}_{*}}$. And by the
assumption on $p$ and $q$, we know $1-p-q>0$. Therefore, the conditional
expectation of ${\beta}$ given $u$ and $v$, denoted by $\delta_{\beta}$,
satisfies:

$\displaystyle(n-2)\cdot[(1-p-q)(1-q)]p_{{\beta}_{*}}\leq\delta_{{\beta}}$
$\displaystyle=(n-2)p_{\beta}+2$
$\displaystyle\leq(n-2)\cdot[(1-q)^{2}-p^{2}]p_{{\beta}_{*}}+(n-2)(2q-q^{2})+2$
$\displaystyle<(n-2)\cdot p_{{\beta}_{*}}+(n-2)2q+2.$ (15)

Let us for now assume that
$\frac{c_{1}\delta_{{\alpha}_{*}}}{c_{2}\delta_{{\beta}}}\geq{\tau}I_{F}$ for
constants $c_{1}=1-\sigma_{1}$ and $c_{2}=1+\sigma_{2}$ with $0<\sigma_{1}<1$
and $\sigma_{2}>0$ to be set later. If $d_{X}(u,v)\leq r$, the region
$B(u,r)\cap B(v,r)$ contains at least one metric ball of radius $r/2$ (recall
Figure [1(a)]). Therefore, the conditional expectation of ${\alpha}_{*}$ given
$u$, $v$ and $F$, denoted by $\delta_{{\alpha}_{*}}$, satisfies:

$\delta_{{\alpha}_{*}}\geq(n-2)\cdot\mu(\mathrm{B}(z,r/2))\cdot(1-p)^{2}\geq
12\frac{(n-2)\ln n}{n-2}\cdot(1-p)^{2}=12\ln{n}\cdot(1-p)^{2}.$

Similarly, using (4), the conditional expectation of ${\beta}$ given $u$ and
$v$, denoted by $\delta_{{\beta}_{*}}$, satisfies
$\delta_{{\beta}_{*}}\geq(n-2)(1-p-q)(1-q)p_{{\beta}_{*}}\geq 12\ln
n[(1-p-q)(1-q)]$. We now set $\sigma_{1}=4/5$ and $\sigma_{2}=1$. From the
conditions stated in Lemma 4.2, we have $p\leq 1/4$ and $q\leq 1/8$. It then
follows from Chernoff bounds that

$\displaystyle\mathrm{P}[{\alpha}_{*}<c_{1}\delta_{{\alpha}_{*}}\mid
u,v,F]+\mathrm{P}[{\beta}>c_{2}\delta_{{\beta}}\mid u,v]\leq
e^{-\frac{\sigma_{1}^{2}}{2}\delta_{{\alpha}_{*}}}+e^{-\frac{\sigma_{2}}{3}\delta_{{\beta}}}\leq
2n^{-2.16}.$

Taking expectation of the above with respect to $u$ and $v$ gives

$\displaystyle\mathrm{P}[{\alpha}_{*}<c_{1}\delta_{{\alpha}_{*}}\mid
F]+\mathrm{P}[{\beta}>c_{2}\delta_{{\beta}}]\leq 2n^{-2.16}.$ (16)

By a similar argument as used in the proof of Lemma 3.5, we can derive:

$\mathrm{P}[\rho_{u,v}({\widehat{G}})<{\tau}I_{F}]\leq\mathrm{P}[\frac{{\alpha}_{*}}{{\beta}}<{\tau}I_{F}]\leq
2n^{-2.16}.$

By the union bound, the probability that $\rho_{u,v}({\widehat{G}})\geq{\tau}$
for all pairs of nodes $u,v\in V$ such that $d_{X}(u,v)\leq r$ is thus at
least $1-\frac{1}{2}n^{2}(2n^{-2.16})=1-n^{-0.16}$.

What remains is to verify that
$\frac{c_{1}\delta_{{\alpha}_{*}}}{c_{2}\delta_{{\beta}}}=\frac{\delta_{{\alpha}_{*}}}{10\delta_{\beta}}\geq{\tau}I_{F}$
holds for a.e. $u$ and $v$. This holds automatically if $d_{X}(u,v)>r$, so
assume $d_{X}(u,v)\leq r$. Recall that $\delta_{\beta}\leq(n-2)\cdot
p_{{\beta}_{*}}+(n-2)\cdot 2q+2$. Since $q\leq c{\mathrm{s}}$, we have
$(n-2)2q\leq 2(n-2)c{\mathrm{s}}$. On the other hand, by Assumption-R,
$p_{{\beta}_{*}}\geq\mu(\mathrm{B}(u,r))\geq{\mathrm{s}}$, hence $(n-2)2q\leq
2(n-2)c\cdot p_{{\beta}_{*}}$. Combining with $(n-2)p_{{\beta}_{*}}\geq
s(n-2)\geq 12\ln n$, (which also implies that
$2\leq\frac{(n-2)p_{{\beta}_{*}}}{6\ln n}$), it then follows that

$\displaystyle\frac{\delta_{{\alpha}_{*}}}{10\delta_{\beta}}\geq\frac{\delta_{{\alpha}_{*}}}{10[(n-2)(1+\frac{1}{6\ln
n})p_{{\beta}_{*}}+2(n-2)cp_{{\beta}_{*}}]}=\frac{p_{{\alpha}_{*}}}{p_{{\beta}_{*}}}\cdot\frac{(1-p)^{2}}{10+\frac{5}{3\ln
n}+20c}.$ (17)

Now let $z$ be the midpoint of the shortest path connecting $u$ and $v$ in
$X$. Observe that $p_{{\alpha}_{*}}\geq\mu(\mathrm{B}(z,r/2))$,
$p_{{\beta}_{*}}\leq\mu(\mathrm{B}(z,2r))$ and since $\mu$ is $L$-doubling, it
follows:

$\displaystyle p_{{\beta}_{*}}\leq\mu(\mathrm{B}(z,2r))\leq
L\mu(\mathrm{B}(z,r))\leq L^{2}\mu(\mathrm{B}(z,r/2))\leq
L^{2}p_{{\alpha}_{*}}.$ (18)

Combing equations (17) and (18), we have that as long as
${\tau}\leq\frac{(1-p)^{2}}{(10+\frac{5}{3\ln n}+20c)L^{2}}$, we have that
$\frac{\delta_{{\alpha}_{*}}}{10\delta_{\beta}}\geq{\tau}$ is satisfied. The
lemma then follows. ∎

Recall that we define an edge $(u,v)\in E({\widehat{G}})\setminus E({G^{*}})$
in the observed graph ${\widehat{G}}$ to be _really-bad_ if
$N_{{G^{*}}}(u)\cap N_{{G^{*}}}(v)=\emptyset$.

###### Lemma 4.3

Let $V$ be a set of $n$ points sampled i.i.d. from an $L$-doubling probability
measure $\mu$ supported on a compact metric space $\mathcal{X}=(X,d_{X})$. Let
${G^{*}}$ and ${\widehat{G}}$ be the true graph and observed graph as
described in Definition 2.3, respectively. If Assumption-R holds and
$p\leq\frac{1}{4}$ and $q\leq c{\mathrm{s}}$, then for
$\forall{\tau}\geq\frac{(c+2)q}{1-p}+\frac{2(c+2)}{1-p}\sqrt{\frac{\ln{n}}{{\mathrm{s}}(n-2)}}$,
we have with probability at least $1-n^{-1/4}$, that
$\rho_{u,v}({\widehat{G}})<{\tau}$ for _all_ pairs of nodes $u,v\in V$ such
that $(u,v)$ is really-bad.

###### Proof.

Consider a fixed pair of nodes $(u,v)\in V$, and let $F=F(u,v)$ be the event
that $N_{{G^{*}}}(u)\cap N_{{G^{*}}}(v)=\emptyset$ and $d_{X}(u,v)>r$. Let
${\alpha}=|N_{\widehat{G}}(u)\cap N_{\widehat{G}}(v)|$,

$\displaystyle{\alpha}_{I}$ $\displaystyle=\big{|}(N_{G^{*}}(u)\cup
N_{G^{*}}(v))\cap(N_{\widehat{G}}(u)\cap
N_{\widehat{G}}(v))\big{|},~{}\text{and}$ $\displaystyle{\alpha}_{o}$
$\displaystyle=\big{|}\\{x\not\in N_{G^{*}}(u)\cup N_{G^{*}}(v)|x~{}\text{is
connected to
both}~{}u~{}\text{and}~{}v~{}\text{in}~{}{\widehat{G}}\\}\big{|}.$

Obviously, ${\alpha}={\alpha}_{I}+{\alpha}_{o}$. Further set
${\beta}_{*}=\big{|}(N_{G^{*}}(u)\cup N_{G^{*}}(v))\cap(N_{\widehat{G}}(u)\cup
N_{\widehat{G}}(v))\big{|}$, then $|N_{\widehat{G}}(u)\cup
N_{\widehat{G}}(v)|\geq{\beta}_{*}+{\alpha}_{o}$. Setting
${\beta}:={\beta}_{*}+{\alpha}_{o}-2$, we then have that
$\rho_{u,v}({\widehat{G}})=\frac{{\alpha}}{|N_{\widehat{G}}(u)\cup
N_{\widehat{G}}(v)|}\leq\frac{{\alpha}}{{\beta}_{*}+{\alpha}_{o}-2}=\frac{{\alpha}}{{\beta}}$.
We aim to show that with very high probability
$\frac{{\alpha}}{{\beta}}I_{F}<\tau$, which implies that
$\rho_{u,v}({\widehat{G}})I_{F}<\tau$.

By applying the same technique as in Lemma 3.6, we claim that, conditional on
the locations of $u$ and $v$ and the event $F$, the distribution of ${\alpha}$
is $Bin(n-2,p_{\alpha})$ with
$p_{\alpha}=\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}(1-p)q+\frac{1-p_{{\beta}_{*}}}{1-p^{\prime}}q^{2}$,
where $p_{{\beta}_{*}}=\mu(B(u,r)\cup B(v,r))$ and $p^{\prime}=\mu(B(u,r)\cap
B(v,r))$. We also claim that the conditional distribution of ${\beta}$ given
$u$, $v$ and $F$ is $Bin(n-2,p_{\beta})$ with
$p_{{\beta}}=\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}\cdot(1-p(1-q))+\frac{1-p_{{\beta}_{*}}}{1-p^{\prime}}q^{2}$
by a similar argument.

If $d_{X}(u,v)>r$, we have $p_{{\beta}_{*}}-p^{\prime}\geq
2\mu(B(\frac{r}{2}))\geq 2s$ (recall Figure [1(b)]). Therefore, the
conditional expectation of ${\alpha}$ given $u$, $v$ and $F$, denoted by
$\delta_{\alpha}(=(n-2)p_{\alpha})$, satisfies:

$\displaystyle(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}(1-p)q\leq\delta_{{\alpha}}$
$\displaystyle\leq(n-2)[\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q+\frac{1}{1-p^{\prime}}q^{2}]$
$\displaystyle\leq(c/2+1)\cdot(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}\cdot
q$ (19)

where the last inequality follows from $q\leq c{\mathrm{s}}$. The conditional
expectation of ${\beta}$ given $u$, $v$ and $F$, denoted by
$\delta_{\beta}(=(n-2)p_{\beta})$, satisfies:

$\displaystyle(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}(1-p)\leq\delta_{{\beta}}\leq(n-2)[\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}+\frac{1}{1-p^{\prime}}q^{2}]+2$
(20)

Let us for now assume that
$\frac{c_{1}\delta_{{\alpha}}}{c_{2}\delta_{{\beta}}}I_{F}\leq\tau$ a.s. for
$c_{1}=1+\epsilon$ and some constant $c_{2}=1-\sigma$ with
$\epsilon=\frac{2}{q}\sqrt{\frac{\ln{n}}{s(n-2)}}$ and $0<\sigma<1$ to be set
later.

If $q\leq 2\sqrt{\frac{\ln{n}}{s(n-2)}}$, then we have $\epsilon\geq 1$. In
this case, combining Chernoff bounds with (4) and that
$p_{{\beta}_{*}}-p^{\prime}\geq 2{\mathrm{s}}$ and $p\leq\frac{1}{4}$, we
have:

$\displaystyle\mathrm{P}[{\alpha}\geq(1+\epsilon)\delta_{{\alpha}}]\leq
e^{-\frac{\epsilon}{3}\delta_{{\alpha}}}=e^{-\frac{2}{3}\sqrt{\frac{\ln{n}}{sn}}\frac{1}{q}\delta_{{\alpha}}}\leq
e^{-\frac{2}{3}\sqrt{\frac{\ln{n}}{s(n-2)}}\frac{1}{q}(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}(1-p)q}$
$\displaystyle\leq e^{-\frac{4}{3}\sqrt{(n-2)(\ln{n})s}\frac{3}{4}}\leq
e^{-\sqrt{(n-2)(\ln{n})\frac{12\ln{n}}{(n-2)}}}=n^{-2\sqrt{3}}$ (21)

Otherwise, if $q>2\sqrt{\frac{\ln{n}}{s(n-2)}}$, then $0<\epsilon<1$. In this
case, by Chernoff bounds

$\displaystyle\mathrm{P}[{\alpha}\geq(1+\epsilon)\delta_{{\alpha}}]\leq
e^{-\frac{1}{2}\epsilon^{2}\delta_{{\alpha}}}$ $\displaystyle\leq
e^{-2\frac{\ln{n}}{{\mathrm{s}}(n-2)}\frac{1}{q^{2}}(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}(1-p)q}$
$\displaystyle=e^{-2\frac{(\ln{n})(p_{{\beta}_{*}}-p^{\prime})}{{\mathrm{s}}q}\frac{3}{4}}\leq
e^{-\frac{3}{2}(\ln{n})\frac{2{\mathrm{s}}}{{\mathrm{s}}q}}\leq n^{-3}$ (22)

On the other hand, by Chernoff bounds, we have $\mathrm{P}[{\beta}\leq
c_{2}\delta_{{\beta}}\mid u,v,F]\leq
e^{-\frac{\sigma^{2}}{2}\delta_{{\beta}}}$. Note that
$\delta_{{\beta}}\geq(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}\cdot(1-p)\geq(n-2)\cdot\mu(B(u,r)\cup
B(v,r))\cdot\frac{3}{4}\geq 18\ln{n}$. We now set $\sigma=1/2$. By taking
expectation with respect to $u$ and $v$, we have

$\displaystyle\mathrm{P}[{\alpha}\geq c_{1}\delta_{{\alpha}}\mid
F]+\mathrm{P}[{\beta}\leq c_{2}\delta_{{\beta}}\mid F]\leq 2n^{-9/4}$ (23)

By the same argument as used in the proof of Lemma 3.6, we have
$\mathrm{P}[\rho_{u,v}({\widehat{G}})I_{F}\geq{\tau}]\leq\mathrm{P}[\frac{{\alpha}}{{\beta}}I_{F}\geq{\tau}]\leq
2n^{-9/4}.$ By union bound, the probability that
$\rho_{u,v}({\widehat{G}})<{\tau}$ for all pairs of nodes $u$, $v\in V$
satisfying the required conditions is thus at least
$1-\frac{1}{2}n^{2}(2n^{-9/4})=1-n^{-1/4}$.

Finally, note that for the above argument to hold, we need to verify that

$\frac{c_{1}\delta_{{\alpha}}}{c_{2}\delta_{{\beta}}}I_{F}=\frac{2((1+\frac{2}{q}\sqrt{\frac{\ln{n}}{s(n-2)}})\delta_{{\alpha}})}{\delta_{\beta}}I_{F}\leq{\tau}$

holds for a.e. $u$ and $v$. This holds automatically if $F$ doesn’t happen, so
assume $F$ happens. Recall that
$\delta_{{\alpha}}\leq(c/2+1)\cdot(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q$
by (4) and
$\delta_{{\beta}}\geq(n-2)\cdot\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}\cdot(1-p)$
by (20). This implies that

$\displaystyle\frac{2((1+\frac{2}{q}\sqrt{\frac{\ln{n}}{{\mathrm{s}}n}})\delta_{{\alpha}})}{\delta_{\beta}}$
$\displaystyle\leq\frac{2((c/2+1)(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}q+(c+2)\sqrt{\frac{\ln{n}}{{\mathrm{s}}(n-2)}}(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}})}{(n-2)\frac{p_{{\beta}_{*}}-p^{\prime}}{1-p^{\prime}}(1-p)}$
$\displaystyle=\frac{c+2}{1-p}q+2\frac{c+2}{1-p}\sqrt{\frac{\ln{n}}{{\mathrm{s}}(n-2)}}.$
(24)

We have that as long as
${\tau}\geq\frac{(c+2)q}{1-p}+\frac{2(c+2)}{1-p}\sqrt{\frac{\ln{n}}{{\mathrm{s}}(n-2)}}$,
then $\frac{c_{1}\delta_{{\alpha}}}{c_{2}\delta_{{\beta}}}I_{F}\leq{\tau}$ is
satisfied. The lemma then follows. ∎

###### Theorem 4.4

Let $V$ be a set of $n$ points sampled i.i.d. from an $L$-doubling measure
$\mu:X\to{\rm I\\!R}^{+}$ supported on a compact metric space $(X,d_{X})$. Let
${G^{*}}$ be the resulting $r$-neighborhood graph for $V$; and ${\widehat{G}}$
a graph obtained by the network model $G(r,p,q)$ described in Definition 2.3.
Let ${\tilde{G}_{\tau}}$ be the graph after $\tau$-Jaccard filtering of
${\widehat{G}}$. Then, if Assumption-R holds, $p\leq\frac{1}{4}$,
$q\leq\min\\{\frac{1}{8},c{\mathrm{s}}\\}$ and ${\mathrm{s}}n=\omega(\ln{n})$,
then for any $\tau$ such that
$\frac{(1-p)^{2}}{(10+\frac{5}{3\ln{n}}+20c)L^{2}}>{\tau}>\frac{(c+2)q}{1-p}+o(1)$,
with high probability the shortest path distance metric
$d_{{\tilde{G}}_{\tau}}$ is a 2-approximation of the shortest path metric
$d_{G^{*}}$ of the true graph ${G^{*}}$.

###### Proof.

Let $\mathcal{E}_{1}$ denote the event where $d_{{\widehat{G}}\cap{G^{*}}}\leq
2d_{G^{*}}$. By Lemma 4.1, event $\mathcal{E}_{1}$ happens with probability at
least $1-n^{-\Omega(1)}$.

Let $\mathcal{E}_{2}$ denote the event where all edges
${\widehat{G}}\cap{G^{*}}$ are also contained in the edge set of the filtered
graph ${\tilde{G}_{\tau}}$; that is,
${\widehat{G}}\cap{G^{*}}\subseteq{\tilde{G}_{\tau}}$. By Lemma 4.2, event
$\mathcal{E}_{2}$ happens with probability at least $1-n^{-0.16}$. It then
follows that:

$\displaystyle\text{If both events
}\mathcal{E}_{1}\text{~{}and~{}}\mathcal{E}_{2}\text{~{}happen,
then~{}}d_{\tilde{G}_{\tau}}\leq d_{{\widehat{G}}\cap{G^{*}}}\leq 2d_{G^{*}}.$

What remains is to show $d_{G^{*}}\leq 2d_{\tilde{G}_{\tau}}$. To this end, we
define $\mathcal{E}_{3}$ to be the event where for all really-bad edges
$(u,v)$ in ${\widehat{G}}$, we have $\rho_{u,v}({\widehat{G}})<\tau$. If
$\mathcal{E}_{3}$ happens, then it implies that for an arbitrary edge
$(u,v)\in E({\tilde{G}_{\tau}})$, either $(u,v)\in E({G^{*}})$ or
$d_{G^{*}}(u,v)=2$ (since $N_{G^{*}}(u)\cap N_{G^{*}}(v)\neq\emptyset$). By
Lemma 4.3, event $\mathcal{E}_{3}$ happens with probability at least
$1-n^{-1/4}$.

By union bound, we know that $\mathcal{E}_{1}$, $\mathcal{E}_{2}$ and
$\mathcal{E}_{3}$ happen simultaneously with high probability.

Using the same argument as in the proof of Theorem 3.7, it then follows that
given any $u,v\in V$ connected in ${\tilde{G}_{\tau}}$, we can find a path in
${G^{*}}$ of at most $2d_{\tilde{G}_{\tau}}(u,v)$ number of edges to connect
$u$ and $v$. Furthermore, event $\mathcal{E}_{1}$ implies that if $u$ and $v$
are not connected in ${\tilde{G}_{\tau}}$, then they cannot be connected in
${G^{*}}$ either. Putting everything together, we thus obtain
$d_{\tilde{G}_{\tau}}\geq\frac{1}{2}d_{G^{*}}$. Theorem 4.4 then follows. ∎

Extension to local doubling measure.  We can relax the $L$-doubling condition
of the measure $\mu$ where points are sampled from to a _local doubling_
condition, where the $L$-doubling property is only required to hold for metric
balls of small radius. Specifically,

######  Definition 4.5 ($(R_{0},L_{R_{0}})$-doubling measure)

Given a metric space $\mathcal{X}=(X,d_{X})$, a measure $\mu$ on $\mathcal{X}$
is said to be _$(R_{0},L_{R_{0}})$ -doubling_ if balls have finite and
positive measure and there is a constant $L_{R_{0}}$ s.t. for all $x\in X$ and
any $0<R\leq R_{0}$, we have $\mu(\mathrm{B}(x,2R))\leq
L_{R_{0}}\cdot\mu(\mathrm{B}(x,R))$.

All our results hold for $(R_{0},L_{R_{0}})$-doubling measure, as long as the
parameter $r$ generating the true graph ${G^{*}}_{r}$ satisfies $r<R_{0}$. The
proofs follow the same argument as those for $L$-doubling measure almost
verbatim, and thus are omitted.

##  5 Some empirical results

We provide some proof-of-principle experimental results to show the
effectiveness of the Jaccard filtering process. We report on two sets of
experiments — one controlled experiment on synthetic datasets and the other on
real-world network datasets.

|
---|---
(a) |  (b)

(c)

Figure 2: (a) $2.5K$ points sampled from a hyperboloid surface and $24K$
points sampled from mother-child model. (b) Comparison of 2-approximation rate
$R_{2approx}$ as insertion probability (x-axis) increases. Top curve is after
Jaccard-filtering, while bottom one is for perturbed graph without filtering.
(c) Normalized $L_{2}$-average error with top curve being the one without
filtering, and the bottom one (with significantly lower error) for after
Jaccard-filtering.

Synthetic datasets with ground truth.  In this experiment we seek to
demonstrate that the Jaccard filtering approach works in a robust manner as
predicted by our theoretical results. In particular, we start with the
following two measures: $\mu_{1}$ is the “quasi-uniform” measure on the
hyperboloid $S_{1}$ specified by $x^{2}+y^{2}-z^{2}=1$ [2]; $\mu_{2}$ is a
non-uniform measure on the mother-and-child geometric model $S_{2}$ (see
Figure 2), where the measure is proportional to the local feature size at each
point. For each $\mu_{i}$, we sample $n$ points $V$ i.i.d and build an
$r$-neighborhood graph (we will specify choice of $r$ later). See Figure 2 (a)
for illustration of input samples. This gives rise to a ground-truth
neighborhood graph $G^{*}_{r}$. We next generate a set of observed graph
$G_{p,q}$, varying the deletion probability ($p$) and insertion probability
($q$). Using a fixed parameter $\tau$, we perform $\tau$-Jaccard filtering for
each $G_{p,q}$ to obtain a filtered graph $\widehat{G}^{\tau}_{p,q}$.

To measure the difference between two metrics (represented as matrices) $D$
and $D^{\prime}$, we use two types of error to be introduced shortly. But
first, note that since we delete edges, the connectivity of the graph may
change. Assume that $D_{i,j}=\infty$ if the two corresponding points $p_{i}$
and $p_{j}$ are not connected in the graph. Note that if $D_{i,j}=\infty$ and
$D^{\prime}_{i,j}=\infty$, the relation $\frac{1}{2}D_{i,j}\leq
D^{\prime}_{i,j}\leq 2D_{i,j}$ still holds.

  * •

$2$-approximation rate $R_{2approx}$ is defined by

$R_{2approx}(D,D^{\prime})=\frac{|\\{(i,j),1\leq i<j\leq
n\mid\frac{1}{2}D_{i,j}\leq D^{\prime}_{i,j}\leq 2D_{i,j}\\}|}{n(n-1)/2}.$

In other words, $R_{2approx}$ is the ratio of “good” pairwise distances from
$D^{\prime}$ that $2$-approximate those in $D$.

To analyze $L_{2}$-type error, we need to avoid the cases that $D_{i,j}$ is
not comparable with $D^{\prime}_{i,j}$. Thus, we collect the following _good-
index set_
$I_{good}(D,D^{\prime})=\\{(i,j),1\leq i<j\leq n\mid$ either
$(D_{i,j}<\infty)\wedge(D^{\prime}_{i,j}<\infty)$; or
$(D_{i,j}=\infty)\wedge(D^{\prime}_{i,j}=\infty)\\}$.

  * •

Normalized $L_{2}$-average error $\delta_{N}(D,D^{\prime})$. First, we define
root-mean-squared (RMS) error by

$\delta(D,D^{\prime})=\sqrt{\frac{\sum_{(i,j)\in
I_{good}}(D_{i,j}-D^{\prime}_{i,j})^{2}}{|I_{good}|}}$

where note that if $D_{i,j}=\infty$ and $D^{\prime}_{i,j}=\infty$, then
$D_{i,j}-D^{\prime}_{i,j}=0$. We then normalize it by the normalized $L_{2}$
norm of $D$; that is,

$\delta_{N}(D,D^{\prime})=\frac{\delta(D,D^{\prime})}{\sqrt{\frac{1}{|\\{i<j,D_{i,j}<\infty\\}|}\sum_{i<j,D_{i,j}<\infty}D^{2}_{i,j}}}.$

Let $D_{G}$ denote the shortest path metric induced by a graph $G$. We compare
the $2$-approximation rate $R_{2approx}(D_{G^{*}},D_{G_{q}})$ for the sequence
of observed graphs $G_{q}$ for increasing insertion probability $q$ ($x$-axis
in all the plots) with $R_{2approx}(D_{G^{*}},D_{\widehat{G}^{\tau}_{q}})$s
for the sequence of filtered graph $\widehat{G}_{q}^{\tau}$; while we also
compare the normalized $L_{2}$ error $\delta_{N}(D_{G^{*}},D_{G_{q}})$ versus
$\delta_{N}(D_{G^{*}},D_{\widehat{G}^{\tau}_{q}})$s for increasing $q$s.

In the following experiments, we choose $r$ (to build the $r$-neighborhood
graph) to be (a) (“sparse”) twice or (b) (“dense”) five times of the average
distance from a point to its 10-th nearest neighbor in $P$.

|
---|---
(a) |  (b)
Figure 3: (a) “dense” hyperboloid $R_{2approx}$. (b) “dense” hyperboloid
Normalized $L_{2}$-average error.

Figure 2 (b)(c) is the result when we apply Jaccard filtering to the “sparse”
hyperboloid data ($\\#$nodes: 2581, $\\#$edges: 38321). As we can see,
randomly inserting edges distorts the shortest path metrics (with low
$2$-approximation rate and high normalized $L_{2}$ error for $G_{q}$s).
However, our Jaccard-index filtering process restores the metric not only
w.r.t $2$-approximation rate (which is predicted by our theoretical results),
but also w.r.t normalized $L_{2}$ error. The plots for the “dense” hyperboloid
data ($\\#$nodes: 2581, $\\#$edges: 208290) are shown in Figure 3, where we
observe similar improvements in error rates. Note that the curve for
$R_{2approx}$ of the perturbed (but un-filtered) graphs $G_{q}$ decreases
faster with increasing $q$ for the sparse case compared to the dense case;
while the curve for the normalized $L_{2}$ error increases also faster for the
sparse case. This fits the intuition that sparse graphs are more sensitive to
Erdös-Rényi-type perturbation w.r.t shortest path distance.

|
---|---
(a) |  (b)
|
(c) |  (d)
Figure 4: (a) “sparse” mother-child model $R_{2approx}$. (b) “sparse” mother-
child model Normalized $L_{2}$-average error. (c) “dense” mother-child model
$R_{2approx}$. (d) “dense” mother-child model Normalized $L_{2}$-average
error.

We perform the same experiments to the mother-child model. Figure 4 (a) and
(b) shows the results for the “sparse” mother-child model ($\\#$nodes: 23390,
$\\#$edges: 553797); while the results for the “dense” mother-child data
($\\#$nodes: 23390, $\\#$edges: 3428141) are in (c) and (d). Similar behaviors
are observed.

|
---|---
(a) (co-authorship network) $R_{2approx}$. |  (b) (co-authorship network) Normalized $L_{2}$
|
(c) (PPI network) $R_{2approx}$. |  (d) (PPI network) Normalized $L_{2}$
Figure 5: (a)(c) 2-approximation rate $R_{2approx}$ as $q$ (x-axis) increases,
with top curve (better rate) for graphs $G^{\tau}_{q}$ after $\tau$-Jaccard
filtering (DF=directly filtered vs. FAP=filtered after perturbed), and bottom
one for $G_{q}$ after only $q$-insertion (O=observed vs. P=perturbed). (b)(d)
Normalized $L_{2}$ error (O vs. P is normalized by O and DF vs. FAP is
normalized by DF), with being the one without filtering, and the bottom curve
(lower error) for graphs after Jaccard filtering.

Real networks without ground truth.  For a given real network $G$, we can
consider this as an observed graph. However, we do not know how this network
is generated and there is no ground truth graph ${G^{*}}$. Nevertheless, we
carry out the following experiments to indirectly infer the effectiveness of
Jaccard-filtering. Specifically, given $G$, we gradually add random
$(p=0,q)$-perturbation to it, and compare the shortest path metric $D_{G_{q}}$
of the perturbed graph $G_{q}$ with the metric $D_{G}$ of input network $G$;
$q$ is for the insertion probability. Next, we perform $\tau$-Jaccard
filtering for all these graphs $G$ and $G_{q}$s to obtain $G^{\tau}$ and
$G^{\tau}_{q}$ respectively, and then compare the shortest path metric
$D_{G^{\tau}_{q}}$ for filtered graphs $G^{\tau}_{q}$ with $D_{G^{\tau}}$ of
$G^{\tau}$.

See Figure 5 (a)(b), where the input network is a network representing co-
authorship extracted from papers published at 28 major computer science
conferences [18] ($\\#$nodes: 53442, $\\#$edges: 127969). Note that the
normalized $L_{2}$ error is also reduced by Jaccard filtering. The results for
a protein-protein interaction network [14] ($\\#$nodes: 6327, $\\#$edges:
147547) are also given in Figure 5 (c)(d).

##  6 Concluding remarks

In this paper we study how to recover the shortest path metric of a true graph
$G^{*}$ from an observed graph $G$, when $G^{*}$ is assumed to be some
proximity graph of a hidden domain $X$, while $G$ is generated from $G^{*}$
with random Erdös-Rényi-type perturbations.

Our paper represents one step towards unraveling the structure of the space
where data are sampled from. There are many interesting problems along this
direction, including how to generalize our network model to better model real
networks. We describe one direction here: Our current work recovers the
shortest path metric of the hidden graph $G$. However, there are other common
metrics induced from $G$, such as the diffusion distance metric. In fact, for
dense random graphs, say graphs generated from a graphon [10] (including
stochastic block models), the spectral structure of such random graphs are
stable. This may imply that diffusion distances could also be stable against
random perturbations even without any filtering process. Note that such graphs
have $\Theta(n^{2})$ number edges asymptotically. However, for sparse graphs
(which our model could generate), empirically we observe that diffusion
distances are not stable under random perturbations. It would be interesting
to see whether the Jaccard filtering process (or other filtering procedure)
could recover diffusion distances with theoretical guarantees. (Interestingly,
we have observed that empirically, Jaccard filtering can recover diffusion
distance as well in our experiments.)

Finally, it would be interesting to explore whether the analysis and ideas for
network models from our paper could be used to create a practical wormhole
detector in wireless networks, akin to Ban et al’s local connectivity tests
based on [$\alpha,\beta$]-rings [3].

#### Acknowledgement.

The authors thank Samory Kpotufe for the pointer to the local version of
$L$-doubling measure. This work is in part supported by National Science
Foundation under grants IIS-1550757 and CCF-1618247. SP and DS would like to
acknowledge NSF grant #DMS: 1418265 for partially supporting this work. Any
opinions, findings, and conclusions or recommendations expressed in this
material are those of the author(s) and do not necessarily reflect the views
of the National Science Foundation.

## References

  * [1] M. Alamgir and U. V. Luxburg.  Shortest path distance in random k-nearest neighbor graphs.  In 29th Intl. Conf. Machine Learning (ICML), pages 1031–1038, 2012\.
  * [2] D. Asta and C. Shalizi.  Geometric network comparisons.  In 31st Annu. Conf. Uncertainty in AI (UAI), 2015.
  * [3] X. Ban, R. Sarkar, and J. Gao.  Local connectivity tests to identify wormholes in wireless networks.  In Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc ’11, pages 13:1–13:11, New York, NY, USA, 2011. ACM.
  * [4] H. Bhadauria and M. Dewal.  Efficient denoising technique for ct images to enhance brain hemorrhage segmentation.  Journal of digital imaging, 25(6):782–791, 2012.
  * [5] B. Bollobás and F. R. K. Chung.  The diameter of a cycle plus a random matching.  SIAM Journal on discrete mathematics, 1(3):328–333, 1988.
  * [6] B. Bollobás and O. M. Riordan.  Mathematical results on scale-free random graphs.  Handbook of graphs and networks: from the genome to the internet, pages 1–34, 2003.
  * [7] M. R. Bridson and A. Haefliger.  Metric spaces of non-positive curvature, volume 319.  Springer Science & Business Media, 2011.
  * [8] F. Chazal, L. J. Guibas, S. Y. Oudot, and P. Skraba.  Persistence-based clustering in riemannian manifolds.  Journal of the ACM (JACM), 60(6):41, 2013.
  * [9] R. Durrett.  Random Graph Dynamics, volume 20.  Cambridge University Press, 2006.
  * [10] J. Eldridge, M. Belkin, and Y. Wang.  Graphons, mergeons, and so on!  In Advances in Neural Information Processing Systems, pages 2307–2315, 2016.
  * [11] M. Faloutsos, P. Faloutsos, and C. Faloutsos.  On power-law relationships of the internet topology.  In ACM SIGCOMM Computer Comm. Review, volume 29, pages 251–262, 1999.
  * [12] D. S. Goldberg and F. P. Roth.  Assessing experimentally derived interactions in a small world.  Proceedings of the National Academy of Sciences, 100(8):4372–4376, 2003.
  * [13] J. Heinonen.  Lectures on analysis on metric spaces.  Springer Science & Business Media, 2012.
  * [14] G. Joshi-Tope, M. Gillespie, I. Vastrik, P. D’Eustachio, E. Schmidt, B. de Bono, B. Jassal, G. Gopinath, G. Wu, L. Matthews, et al.  Reactome: a knowledgebase of biological pathways.  Nucleic acids research, 33(suppl 1):D428–D432, 2005.
  * [15] J. Kleinberg.  The small-world phenomenon: An algorithmic perspective.  In Proc. 32nd. ACM Symp. Theory Computing, pages 163–170. ACM, 2000\.
  * [16] J. Kleinberg.  Small-world phenomena and the dynamics of information.  In Advances in Neural Information Processing Systems (NIPS), pages 431–438. 2002.
  * [17] E. A. Leicht, P. Holme, and M. E. Newman.  Vertex similarity in networks.  Physical Review E, 73(2):026120, 2006.
  * [18] T. Lou and J. Tang.  Mining structural hole spanners through information diffusion in social networks.  In WWW’13, 2013.
  * [19] M. Penrose.  Random geometric graphs.  Number 5. Oxford University Press, 2003.
  * [20] V. Satuluri, S. Parthasarathy, and Y. Ruan.  Local graph sparsification for scalable clustering.  In ACM SIGMOD Intl. Conf. Management Data, pages 721–732, 2011\.
  * [21] A. Singer and H.-T. Wu.  Two-dimensional tomography from noisy projections taken at unknown random directions.  SIAM journal on imaging sciences, 6(1):136–175, 2013.
  * [22] H. F. Song and X.-J. Wang.  Simple, distance-dependent formulation of the Watts-Strogatz model for directed and undirected small-world networks.  Phys. Rev. E, 90:062801, 2014.
  * [23] X. F. Wang and G. Chen.  Complex networks: small-world, scale-free and beyond.  Circuits and Systems Magazine, IEEE, 3(1):6–20, 2003.
  * [24] D. J. Watts, P. S. Dodds, and M. E. J. Newman.  Identity and search in social networks.  Science, 296(5571):1302–1305, 2002.
  * [25] D. J. Watts and S. H. Strogatz.  Collective dynamics of ‘small-world’networks.  nature, 393(6684):440–442, 1998.

##  Appendix A Relation between metric structures for ${G_{r}^{*}}$ and for
$\mathcal{X}$

We now prove Theorem 2.5 here.

First, we will argue that $V_{n}$ forms a dense sampling of the compact space
$\mathcal{X}=(X,d_{X})$. We will then show that under the dense sampling
condition, the shortest paths between points in $V_{n}$ with respect to the
input metric $d_{X}$ is approximated by $d_{G^{*}}$ scaled by $r$ as claimed.

We will start with introducing the concept of ${\varepsilon}$-sampling.

###### Definition A.1

A finite set of points $P\subset X$ is an ${\varepsilon}$-sample of
$(X,d_{X})$ if for any $x\in X$, $d(x,P)\leq{\varepsilon}$ where
$d(x,P)=\min_{p\in P}d_{X}(x,p)$. That is, for any $x\in X$ there is a sample
point from $P$ within ${\varepsilon}$ geodesic distance away from $x$.

Now let $\mathcal{N}_{\varepsilon}$ denote the _${\varepsilon}$ -covering
number of $X$_, which is the minimum number of closed geodesic balls centered
in $X$ of radius ${\varepsilon}$ needed to cover $X$; denote by
$\mathcal{B}_{\varepsilon}$ such a collection of geodesic balls with
cardinality $\mathcal{N}_{\varepsilon}$. Set
$\mathcal{V}_{\varepsilon}:=\min_{B\in\mathcal{B}_{\varepsilon}}\mu(B)$, which
is strictly positive and finite since $\mu$ is a doubling measure and
$\mathcal{X}$ is compact. We claim the following, the proof of which is
similar to that of Theorem 5.2 of [8]:

###### Claim A.2

Let $V_{n}$ be a set of $n$ points sampled from $(X,d_{X})$ w.r.t. $\mu$ in
i.i.d. fashion. Then $V_{n}$ forms an ${\varepsilon}$-sample of $X$ with
probability at least $1-\mathcal{N}_{{\varepsilon}/2}\cdot
e^{-n\mathcal{V}_{{\varepsilon}/2}}$.

###### Proof.

Consider a covering set of geodesic balls
$\mathcal{B}_{{\varepsilon}/2}=\\{B_{1},\ldots,B_{m}\\}$ with smallest
cardinality $m=\mathcal{N}_{{\varepsilon}/2}$. For each $i\in[1,m]$, let
$E_{i}$ denote the event that $V_{n}\cap B_{i}=\emptyset$. Since points in
$V_{n}$ are sampled i.i.d. from $\mu$, we have that

$\mathrm{P}[E_{i}]=(1-\mu(B_{i}))^{n}\leq(1-\mathcal{V}_{{\varepsilon}/2})^{n}\leq
e^{-n\cdot\mathcal{V}_{{\varepsilon}/2}},$

where the last inequality follows from $1-x\leq e^{-x}$. On the other hand, it
is easy to see that if $V_{n}\cap B_{i}\neq\emptyset$ for all $i\in[1,m]$,
then $V_{n}$ must be an ${\varepsilon}$-sample of $X$. It follows from this
and the union bound that

$\mathrm{P}[V_{n}\text{ is not an }{\varepsilon}\text{-sample of
}X]\leq\sum_{i\in[1,m]}\mathrm{P}[E_{i}]\leq\mathcal{N}_{{\varepsilon}/2}\cdot
e^{-n\mathcal{V}_{{\varepsilon}/2}}.$

The claim then follows. ∎

###### Claim A.3

Suppose that $V_{n}$ is an ${\varepsilon}$-sample of $(X,d_{X})$ with
${\varepsilon}<r/2$. Then for any $u,v\in V_{n}$,

$d_{X}(u,v)\leq r\cdot
d_{G^{*}}(u,v)\leq\frac{r}{r-2{\varepsilon}}d_{X}(u,v)+r.$ (25)

###### Proof.

Let $\pi\subset X$ be a shortest path (geodesic) from $u$ to $v$ in $X$ with
length being ${\mathrm{Len}}(\pi)=d_{X}(u,v)$. Let
$v_{0}=u,v_{1},\ldots,v_{k}=v$ be the set of vertices in a shortest path
$\hat{\pi}$ from $u$ to $v$ in the $r$-neighborhood graph ${G^{*}}$, so
$k=d_{G^{*}}(u,v)$. Now based on $\hat{\pi}$, we construct the path
$\pi^{\prime}\subset X$ consisting of $k$ pieces, where the $i$th piece is
simply the shortest path connecting $v_{i-1}$ to $v_{i}$ in $X$. Since
$(v_{i-1},v_{i})$ is an edge in ${G^{*}}$, the geodesic distance between them
is at most $r$, so we have ${\mathrm{Len}}(\pi^{\prime})\leq rk=r\cdot
d_{G^{*}}(u,v)$, which implies that

$r\cdot
d_{G^{*}}(u,v)\geq{\mathrm{Len}}(\pi^{\prime})\geq{\mathrm{Len}}(\pi)=d_{X}(u,v).$

Hence the left inequality of (25) holds.

What remains is to bound $r\cdot d_{G^{*}}(u,v)$ from above, showing that it
cannot be too large compared to $d_{X}(u,v)$ as well.

To this end, consider breaking the shortest path $\pi$ (connecting $u$ to $v$
in $X$) at a set of points $p_{0}=u,p_{1},\ldots,p_{s}=v\subset\pi$ so that
for each $i\in[0,s-2]$, ${\mathrm{Len}}(\pi(p_{i},p_{i+1}))=r-2{\varepsilon}$
while ${\mathrm{Len}}(\pi(p_{s-1},p_{s}))=d_{X}(p_{s-1},p_{s})\leq
r-2{\varepsilon}$. (Note that it is possible that $s=1$.) We then have that

$d_{X}(u,p_{s-1})=(s-1)\cdot(r-2{\varepsilon}),~{}\text{implying
that}~{}s-1\leq\frac{d_{X}(u,v)}{r-2{\varepsilon}}.$ (26)

Since $V_{n}$ is an ${\varepsilon}$-sample of $X$, for each $p_{i}$,
$i\in[1,s-1]$, there exists a point $u_{i}\in V_{n}$ within ${\varepsilon}$
geodesic distance to $p_{i}$. Set $u_{0}=p_{0}=u$ and $u_{s}=p_{s}=v$. It then
follows from the triangle inequality that

$d_{X}(u_{i},u_{i+1})\leq
d_{X}(u_{i},p_{i})+d_{X}(p_{i},p_{i+1})+d_{X}(p_{i+1},u_{i+1})\leq
r,~{}~{}\text{for any}~{}i\in[0,s-1].$

Hence for each $i\in[0,s-1]$, either $u_{i}=u_{i+1}$ or $(u_{i},u_{i+1})$ is
an edge in ${G^{*}}$. Thus $d_{G^{*}}(u,v)\leq s$, and combining with (26),
the second inequality of (25) follows. This proves Claim A.3. ∎

We now put everything together to prove the theorem. By Claim A.2, for each
${\varepsilon}$, there exists a sufficiently large integer $n_{\varepsilon}$
such that for $n\geq n_{\varepsilon}$, with probability at least
$1-e^{-\Omega(n)}$, $V_{n}$ is an ${\varepsilon}$-sample of $X$. Let $\Delta$
denote the diameter of $(X,d_{X})$. By Claim A.3, if ${\varepsilon}>0$ is
sufficiently small and $n\geq n_{\varepsilon}$, then with probability at least
$1-e^{-\Omega(n)}$, for all $u,v\in V_{n}$,

$\displaystyle|r\cdot d_{G^{*}}(u,v)-d_{X}(u,v)|\leq
r+\frac{2{\varepsilon}}{r-2{\varepsilon}}d_{X}(u,v)\leq
r+\frac{3{\varepsilon}\Delta}{r},$

so $\|r\cdot d_{G^{*}}-d_{X}|_{V_{n}}\|_{\infty}\leq
r+\frac{3{\varepsilon}\Delta}{r}$. The second term
$\frac{3{\varepsilon}\Delta}{r}$ tends to zero as ${\varepsilon}$ tends to
$0$. Since the exceptional probabilities, $e^{-\Omega(n)}$, are summable in
$n$ (for fixed ${\varepsilon}$), the Borel–Cantelli lemma implies that
$\limsup_{n\to\infty}\|r\cdot d_{G^{*}}-d_{X}|_{V_{n}}\|_{\infty}\leq
r+\frac{3{\varepsilon}\Delta}{r}$ almost surely. Sending ${\varepsilon}\to 0$
along a countable sequence, we have $\limsup_{n\to\infty}\|r\cdot
d_{G^{*}}-d_{X}|_{V_{n}}\|_{\infty}\leq r$ almost surely. Theorem 2.5 then
follows.

#### Remark.

Note that Theorem 2.5 only provides an upper bound on the metric difference.
This is in some sense necessary, as the graph ${G^{*}}$ is an unweighted
graph. Hence we cannot differentiate distances from $X$ smaller than $r$.