# Persistent homology with k-nearest-neighbor filtrations reveals topological
convergence of PageRank

<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Graph-based representations of point-cloud data are widely used in data
science and machine learning, including $\epsilon$-graphs that contain edges
between pairs of data points that are nearer than $\epsilon$ and kNN-graphs
that connect each point to its $k$ nearest neighbors. Recently, topological
data analysis has emerged as a family of mathematical and computational
techniques to investigate topological features of data using simplicial
complexes. These are a higher-order generalization of graphs and many
techniques such as Vietoris-Rips (VR) filtrations are also parameterized by a
distance $\epsilon$. Here, we develop kNN complexes as a generalization of kNN
graphs, leading to kNN-based persistent homology techniques for which we
develop stability and convergence results. We apply this technique to
characterize the convergence properties PageRank, highlighting how the
perspective of discrete topology complements traditional geometrical-based
analyses of convergence. Specifically, we show that convergence of relative
positions (i.e., ranks) is captured by kNN persistent homology, whereas
persistent homology with VR filtrations coincides with vector-norm
convergence. Beyond PageRank, kNN-based persistent homology is expected to be
useful to other data-science applications in which the relative positioning of
data points is more important than their precise locations.

###### Key words and phrases:

Bottleneck distance, stability theorem, kNN filtration, kNN-preserving
transformation.

###### 1991 Mathematics Subject Classification:

Primary: 58F15, 58F17; Secondary: 53C35.

The first author is supported by NSF grant xx-xxxx

Minh Quang Le∗ and Dane Taylor∗

Department of Mathematics

University at Buffalo, State University of New York

USA

(Communicated by the associate editor name)

##  1\. Introduction

Topological data analysis (TDA) is a rapidly growing field of applied
mathematics in which techniques from computational and applied topology are
applied to extract structural information about the “shape” of data. TDA has
been applied to numerous contexts ranging from visualization and
dimensionality reduction [6, 23] and time series analyses [32] to applications
in cosmology [37, 40], physical processes over networks [25, 38, 22, 21],
neuroscience [33, 13, 8, 30], and systems biology [35, 26, 19, 18]. One of the
main tools is the study of persistent homology, which can effectively reveal
multiscale topological properties of data. This approach relies on examining
how the homology of a topological space evolves as one applies a filtration,
which is one of the basic notions in topology. There are many types of
filtrations [1, 34, 17, 7, 12], however we will focus on the widely used
Vietoris-Rips (VR) filtration [10]. In general, different filtrations reveal
complementary insights, and it is important to develop additional filtrations
that cater to different applications.

Figure 1.  Visualizations of simplicial complexes and graphs resulting from
(A) a Vietoris-Rips (VR) filtration and (B) our proposed k-nearest-neighbor
(kNN) filtration. As shown in the second column, VR filtrations are
parameterized by the radius $\epsilon$ of $\epsilon$-balls that are centered
at the points, whereas kNN filtrations are parameterized by the number $k$ of
nearest neighbors. (Dotted lines depict the nearest-neighbor orderings for
node $i=4$.) The third column depicts simplicial complexes that are obtained
at some $\epsilon$ and $k$. The fourth columns shows their 1-skeletons, which
are graphs in which $k$-simplices of $k>1$ are discarded.

In the prototypical setting, one aims to construct and study empirical
topological features for a set of data points, or _point cloud_. The approach
involves using points to construct a filtered topological space, which is
often represented by a simplicial complex in which the data points are
0-simplices, and higher-dimensional $k$-simplices are constructed via some set
of rules. Often, $k$-simplices are added according to the pairwise distances
between 0-simplices. As an example, in Fig. 1(A), we visualize one of the most
commonly studied point-cloud filtrations, the Vietoris-Rips (VR) filtration.
As shown, VR filtrations are constructed by considering simplicial complexes
in which k-simplices are added between 0-simplices that are less that
$\epsilon>0$ distance apart.

In Fig. 1(B), we illustrate a different filtration that we develop in this
paper: _kNN filtrations_ , whereby $k$-simplices are created according to
$k$-nearest-neighbor sets. We note that while $\epsilon$ and kNN graphs are
both very prevalent in the data-science and machine-learning literatures, TDA
methods largely focus on $\epsilon$-based simplicial complexes and
filtrations, thereby limiting their potential utility to new applications. We
develop kNN-based simplicial complexes as a generalization of kNN graphs,
allowing us to develop kNN-based TDA methods including kNN persistent
homology. We formulate and study persistent homology under kNN filtrations,
constructing persistence diagrams and studying their robustness properties. We
also define and study several local version of kNN complexes, filtrations, and
persistent homology. By constructing filtrations using discrete sets, our
approach relies on discrete topology, thereby contrasting approaches that are
tied to continuous topological spaces [20]. In addition, we further analyze
and explore homological features for converging sequences of point sets,
exploring how the convergence of persistent diagrams for kNN filtrations
contrasts that for VR filtrations.

We apply kNN persistent homology to study the ranking of nodes in graphs, and
in particular, we study the convergence of rankings given by approximate
PageRank values that are obtained by the power iteration method. Our work
establishes a new connection between TDA and PageRank, and provides a
topological approach for determining how many iterations are required for the
node rankings to convergence. We visualize this application and motivation in
Fig. 2. In this application, approximate PageRank values $x_{i}(t)\to\pi_{i}$
asymptotically converge to their final values and the normed error $||{\bf
x}(t)-\bm{\pi}||$ exponentially decays. However, as highlighted in Table 1,
the orderings (i.e., node ranks) according to ${x}_{i}(t)$ values converge
after only $t=9$ iterations, even though $||{\bf x}(t)-\bm{\pi}||>0$ for all
$t$. We apply kNN-based persistent homology to study of convergence for these
relative orderings, which is a property that is crucial to PageRank and which
is not revealed through VR filtrations. Although we focus here on PageRank, we
expect kNN-based TDA to be widely useful to other applications in which the
relative positioning of points—as opposed to the precise locations—is a
property of main interest.

Figure 2.  (left) An example graph. (right) Convergence of approximate PageRank values $x_{i}(t)\to\pi_{i}$ with $t$ iterations.  Nodes | $R_{i}(0)$ | $R_{i}(1)$ | $R_{i}(2)$ | $R_{i}(3)$ | $R_{i}(4)$ | $R_{i}(5)$ | $R_{i}(6)$ | $R_{i}(7)$ | $R_{i}(8)$ | $R_{i}(9)$ | ${R}_{i}(\infty)$
---|---|---|---|---|---|---|---|---|---|---|---
$i=0$ | 5 | 1 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4
$i=1$ | 4 | 4 | 1 | 3 | 3 | 2 | 2 | 3 | 3 | 2 | 2
$i=2$ | 3 | 3 | 3 | 1 | 2 | 3 | 3 | 2 | 2 | 3 | 3
$i=3$ | 2 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5
$i=4$ | 1 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1
Table 1. The relative orderings (i.e., node ranks $R_{i}(t)$) converge at
$t\geq 9$. For each $t$, we indicate the top-ranked node by $R_{i}(t)=1$.

This paper is organized as follows. We provide background information in Sec.
2 and our main findings in Sec. 3. In Sec. 4, we apply this approach to study
convergence for the PageRank algorithm. We provide a discussion in Sec. 5.

##  2\. Background information

In Sec. 2.1, we discuss simplicial complexes that are derived from point
clouds. In Sec. 2.2, we define homology and persistent homology for simplicial
complexes. In Sec. 2.3, we discuss the notions of stability and convergence
for persistence diagrams.

###  2.1. Simplicial complexes derived from point clouds

####  2.1.1. Simplicial complexes

We will define simplicial complexes in a geometric way by considering a set of
points, or “point cloud” [36]. Consider a finite set
$\mathcal{Y}=\\{y_{i}\\}\in\mathbb{R}^{p}$ of $N$ points (which we enumerate
$i\in\mathcal{V}=\\{1,\dots,N\\}$) in a $p$-dimensional space that we equip
with the Euclidean metric.

######  Definition 2.1 (Euclidean Metric Space).

Let $\mathbb{R}^{p}$ be the set of all ordered $p$-tuples, or vectors, over
the real numbers and $d:\mathbb{R}^{p}\times\mathbb{R}^{p}$ be the Euclidean
metric

$d(x,y)=||x-y||_{2}=\sqrt{\sum_{i=1}^{p}(x_{i}-y_{i})^{2}},$

where $x=(x_{1},..,x_{p}),y=(y_{1},..,y_{p})\in\mathbb{R}^{p}$. Then the
Euclidean metric space is given by $(\mathbb{R}^{p},d)$.

To facilitate later discussion, it is also helpful to define the following
distance-related concepts.

######  Definition 2.2 (Euclidean Ball, or $\epsilon$-ball).

A $p$-dimensional Euclidean ball $\mathcal{B}_{\epsilon}(x)$ centered at $x$
with radius $\epsilon$ is defined by

$\mathcal{B}_{\epsilon}(x)=\\{y\in\mathbb{R}^{p}:d(x,y)\leq\epsilon\\}$

######  Definition 2.3 (Pairwise-Distance Map).

Let $\mathcal{Y}=\\{y_{i}\\}_{i\in\mathcal{V}}\subset\mathbb{R}^{p}$ be a
finite set of $N$ points in a Euclidean metric space $(\mathbb{R}^{p},d)$.
Then we define the “pairwise-distance map”
$f:\mathcal{Y}\to\mathbb{R}_{+}^{N\times N}$ to encode the distances between
all pairs of points so that $f_{ij}(\mathcal{Y})=d(y_{i},y_{j})$. We similarly
define a map $f_{i}:\mathcal{Y}\to\mathbb{R}_{+}^{N}$ for each row $i$ of
matrix $[f_{ij}]$ by $f_{i}:\mathcal{Y}\to\mathbb{R}_{+}^{N}$ so that
$[f_{i}(\mathcal{Y})]_{j}=f_{ij}(\mathcal{Y})$.

Given a point-cloud, we define a simplicial complex as a collection of
$k$-simplices involving a set $\mathcal{V}=\\{1,\dots,N\\}$ of vertices with
locations $\mathcal{Y}=\\{y_{i}\\}$. A $k$-dimensional simplex—or simply
k-simplex—$\mathcal{S}^{k}$ is defined by a subset of $\mathcal{V}$ having
cardinality $k+1$. For example, each 0-simplex is a vertex, each 1-simplex is
an edge, 2-simplices are informally “triangles” that must be defined using
$k+1=3$ vertices. Because the vertices are spatially embedded in
$\mathbb{R}^{p}$, each $k$-simplex is a $k$-dimensional geometrical object. It
is then natural to consider their $(k-1)$-dimensional faces, which can be
defined as follows. A face of a $k$-simplex $S^{k}$ is a subset of $S^{k}$
with cardinality $k$, i.e , with one of the elements of $S^{k}$ omitted. If
$S^{k-1}_{f}$ is a face of simplex $S^{k}$, then $S^{k}$ is called coface of
$S^{k-1}_{f}$. For example, the 0-simplices at the start and end of a
1-simplex are its faces, and the set of 1-simplices that are adjacent to a
0-simplex are its cofaces.

A simplicial complex $X$ is a collection of $k$-simplices with the property
that if $S^{k}\in X$, then all the faces of $S^{k}$ are also members of $X$.
The notions of face and coface can also be extended to abstract simplicial
complexes that lack spatial coordinates, and one can also define connections
between $k$-simplices of the same dimension by considering if their faces and
cofaces overlap. Two $k$-simplices $S^{k}_{i}$ and $S^{k}_{j}$ are said to be
lower adjacent if they have a common face, and they are upper adjacent if they
are both faces of a common $(k+1)$-simplex. For any $S^{k}\subset X$ we define
its degree, denote by $deg(S^{k})$, to be the number of cofaces of $S^{k}$. We
use $X^{k}$ to denote the subset of $k$-simplices in $X$.

Note that a graph, while typically defined via two sets (vertices, edges), can
also be interpreted as a 1-dimensional abstract simplicial complex, since it
contains $k$-simplices of dimension $k\leq 1$. Moreover, for any simplicial
complex, one can obtain an associated graph that is its 1-skeleton, whereby
one discards any $k$-simplices of dimension $k>1$. More generally, a
$\kappa$-skeleton of a simplicial complex $X$ can be obtained by discarding
all $k$-simplices of dimension $k>\kappa$. Thus, a simplicial complex can be
understood as a generalization of a graph that allows for higher-order
relationships between vertices. To emphasize this connection, we will make no
distinction between 1-simplices in a simplical complex $X$ and the edges of a
graph, and we will refer to them interchangeably.

####  2.1.2. Two simplicial complexes based on $\epsilon$

There are many ways in which one can construct a set of simplices involving
the vertices $\mathcal{V}$ associated with a given a set of points
$\mathcal{Y}=\\{y_{i}\\}\in\mathbb{R}^{p}$. Most approaches stem from
considering $\epsilon$-balls centered at the points $\mathcal{Y}$. Here, we
present two closely related simplicial complexes that are parameterized by a
distance threshold $\epsilon$ and are often motivated by the assumption that
the point cloud lies on a low-dimensional manifold.

######  Definition 2.4 (Čech Complex [4]).

Given a collection of points
$\mathcal{Y}=\\{y_{i}\\}_{i=1}^{N}\in\mathbb{R}^{p}$, the Čech complex,
$\mathcal{C}_{\epsilon}$, is the abstract simplicial complex whose
$k$-simplices are determined by the unordered $(k+1)$-tuples of points
$\\{y_{i}\\}_{i=1}^{k+1}$ whose closed $(\epsilon/2)$-ball neighborhoods have
a point of common intersection.

The Vietoris-Rips (VR) complex is closely related and is defined as follows.

######  Definition 2.5 (Vietoris-Rips Complex [2]).

Given a collection of points
$\mathcal{Y}=\\{y_{i}\\}_{i=1}^{N}\in\mathbb{R}^{p}$, the Rips complex,
$\mathcal{R}_{\epsilon}$, is the abstract simplicial complex whose
$k$-simplices correspond to unordered $(k+1)$-tuples of points
$C=\\{y_{i}\\}^{k+1}_{i=1}\in\mathcal{R}_{\epsilon}$ whose pairwise distance
satisfy $||y_{i}-y_{j}||_{2}\leq\epsilon$ for any $y_{i},y_{j}\in C$.

Notably, Čech complexes are sometimes preferred over VR complexes because of
their relation to the a continuous topological space that is associated with
unions of $\epsilon$-balls, as established in the following Theorem.

######  Theorem 2.6 (Čech theorem [20]).

The Čech theorem (or, equivalently, the “Nerve theorem”) states that a Čech
complex $\mathcal{C}_{\epsilon}$ has the homotopy type of the union of closed
$(\epsilon/2)$-balls about the point set $\mathcal{Y}=\\{y_{i}\\}$.

This result is somewhat surprising since a Čech complex
$\mathcal{C}_{\epsilon}$ is an abstract simplicial complex, which is a
discrete topological space of potentially high dimension. In contrast, the
union of closed $(\epsilon/2)$-balls is a continuous topological space (i.e.,
subset of $\mathbb{R}^{p}$), and so it is interesting that these two spaces
have the same homotopy type. While an identical relation has not been
identified for VR complexes, it has been shown that they are very closely
related Čech complexes through the following interleaving result.

######  Lemma 2.7 (Relation between Čech complex and Vietoris-Rips complex
[20] ).

For any $\epsilon>0$, there is a chain of inclusion maps for Čech complexes
and VR complexes

$\mathcal{R}_{\epsilon}\subseteq\mathcal{C}_{\epsilon\sqrt{2}}\subseteq\mathcal{R}_{\epsilon\sqrt{2}}.$

From a practical perspective, applications involving TDA often focus on VR
complexes because they are more computationally efficient to compute than Čech
complexes. That is, it is easier to compute whether the distance between two
points is less than $\epsilon$ versus check whether the intersection of
$\epsilon$-balls is nonempty. As such, TDA methods based on VR complexes are
very popular in applied settings, and we will later conduct numerical
experiments that use them as a baseline for comparison. Given the relations
between VR and Čech complexes and the unions of $\epsilon$-balls, these all
may approximate the structure of a manifold, assuming all data points lie on
the manifold. Such an assumption, however, is not appropriate for every data
set.

Before continuing, we note that simplicial complexes can be constructed in
ways that do not require a set of points. For example, one can construct
abstract simplicial complexes based on a given graph.

######  Definition 2.8 (Clique Complex [42]).

The clique complex $Cl(G)$ of an undirected graph
$G=(\mathcal{V},\mathcal{E})$ is a simplicial complex where $\mathcal{V}$ are
vertices of $G$ and each $k$-clique (i.e. a complete subgraph with $k$
vertices) in $G$ corresponds to a $(k-1)$-simplex in $Cl(G)$. More precisely,
it is the simplicial complex

$Cl(G)=\mathcal{V}\cup\mathcal{E}\cup\left\\{\sigma|\binom{\sigma}{2}\subseteq\mathcal{E}\right\\},$

where $\sigma\subset\mathcal{V}$ denotes a simplex and
$\binom{\sigma}{2}\in\mathcal{V}\times\mathcal{V}$ denotes the set of pairs
that can be obtained by selecting two 0-simplices from $\sigma$ (which must be
an edge in the graph).

It is worth noting that the _1-skeleton_ (i.e., 0-simplices and 1-simplices)
of any clique complex recovers its associated graph
$G=(\mathcal{V},\mathcal{E})$. That is, the construction of a graph’s clique
complex is an invertible transformation.

###  2.2. Homology and persistent homology

After representing a data set by a simplicial complex, one can study its
topological structure via its homology. To obtain multiscale insights, it is
also useful to study how that homology changes and persists as one varies a
parameter, such as a distance threshold $\epsilon$.

####  2.2.1. Homology

We formulate homology by considering functions defined over $k$-simplices
within a simplicial complex. A chain complex over a field $\mathbf{F}$ is a
tuple $(\mathcal{C};\partial)$ where $\mathcal{C}$ is a collection
$\\{\mathcal{C}_{k}\\}_{k\in\mathbf{N}}$ of vector spaces together with a
collection $\partial$ of F-linear maps $\\{\partial_{k}:C_{k}\longrightarrow
C_{k-1}\\}_{k\in\mathbf{N}}$ such that $\partial_{k-1}\circ\partial_{k}=0$ for
all integers $k$. The maps $\partial_{k}$ are called boundary maps. The
$k$-cycles of the complex are the elements that are sent to zero by the map
$\partial_{k}$; the $k$-boundaries are the elements in the image of
$\partial_{k+1}$. A map of chain complexes
$f:(C;\partial)\longrightarrow(C^{\prime};\partial^{\prime})$ is a collection
$\\{f_{k}:C_{k}\longrightarrow C_{k^{\prime}}\\}_{k\in\mathbf{N}}$ of
$\mathbf{F}$-linear map such that
$f_{k-1}\circ\partial_{k}=\partial_{k}^{\prime}\circ f_{k}$ for all natural
numbers $k$ .

The $k$-cycles form a vector space, and so do the $k$-boundaries; we denote
these vector spaces by $Z_{k}$ and $B_{k}$, respectively. The $k$th homology
of a chain complex $(C,\partial)$ over a field $\mathbf{F}$ is the quotient
vector space

$H_{k}((C,\partial))=Z_{k}/B_{k}.$

The number

$\beta_{k}(C)\equiv\textsf{dim}(H_{k}(C,\partial))=\textsf{dim}Z_{k}-\textsf{dim}B_{k}$

is called the $k$-th Betti number. For a geometric intuition, the dimension of
$H_{k}(X)$ can be thought of as the number of ‘$k$-dimensional holes’ of X:

  * •

The 0th Betti number $\beta_{0}$ is the number of connected components.

  * •

The 1st Betti number $\beta_{1}$ counts the number of loops, or 1-cycles.

  * •

The 2nd Betti number $\beta_{2}$ counts the number of voids, or 2-cycles.

The dimension of a simplicial complex is the maximum over the dimensions of
its simplices. If $X$ is a simplicial complex of dimension $d$ then
$H_{k}(X)=0$ for all $k\geq d.$

Any map of chain complexes
$\Xi:(C,\partial)\longrightarrow(C^{\prime};\partial^{\prime})$ induces a
linear map on homology:

$H(\Xi):H_{k}((C,\partial))\longrightarrow
H_{k}((C^{\prime},\partial^{\prime}))$

To simplify notation, we later use $\Xi$ in place of $H(\Xi)$.

####  2.2.2. Filtrations

To discuss how homology changes and persists, it is necessary to define a
filtration for simplicial complexes. Given a simplicial complex $X$, a
filtration is a totally ordered set of subcomplexes $X_{i}$ of $X$, indexed by
the nonnegative integers, such that if $i\leq j$ then $X_{i}\subset X_{j}$
[39] (or equivalently a sequence of simplicial complexes $X_{1},...,X_{l}$
such that $X_{1}\subseteq\dots\subseteq X_{l}=X$). The totally ordering itself
is called a filter. We call a simplicial complex together with a filtration a
filtered simplicial complex.

There are different ways to define a filtration [1], and we will focus herein
on the popular Vietoris-Rips filtration.

######  Definition 2.9 (Vietoris-Rips Filtration [1]).

Let $G=({V},{E})$ be an undirected graph in which each vertex
$i\in\mathcal{V}$ has a position $x_{i}\in\mathcal{R}^{p}$ in a metric space
with metric $d$. Consider a weight function
$W:\mathcal{V}\times\mathcal{V}\longrightarrow\mathbb{R}$ defined on the edges
$\mathcal{E}$ so that $W(i,j)=d(x_{i},x_{j})$ encodes the distance between
$x_{i}$ and $x_{j}$. Let $Cl(G)$ be the associated clique complex for
$G(\mathcal{V},\mathcal{E})$. For any $\delta\in\mathbb{R}$, the 1-skeleton
$G_{\delta}=(V,E_{\delta})$ is defined as the subgraph of $G$ where
$E_{\delta}\subseteq E$ includes only the edges such that
$d(x_{i},x_{j})\leq\delta$. Then, for any $\delta\in\mathbb{R}$, we define the
Vietoris-Rips filtration by

$\\{Cl(G_{\delta})\longrightarrow
Cl(G_{\delta^{\prime}})\\}_{0\leq\delta\leq\delta^{\prime}}.$

In this work, we will only consider when the distance function is the
Euclidean metric, although one can in principle use other metrics. That said,
we note in passing that one can also construct filtrations in a variety of
ways including functional metric filtrations [1], vertex-based clique
filtrations [34], $k$-clique filtrations [34], weighted simplex filtrations
[17], vertex function based filtrations [1], Dowker sink and source filtration
[7], and the intrinsic Čech filtrations [12].

####  2.2.3. Persistent homology

Persistent homology involves studying how homology changes (or more precisely,
identifies when it does not change) during a filtration. Consider a simplicial
complex, for all $i\leq j$ the inclusion maps $X_{i}\hookrightarrow{X_{j}}$
induce $\mathbf{F}$-linear maps $\Xi_{i,j}:H_{k}(X_{i})\longrightarrow
H_{k}(X_{j})$ on simplicial homology. For a generator $x\in H_{k}(X_{i})$ with
$x\neq 0$, we say that $x$ dies in $H_{k}(X_{j})$ if $j>i$ is the smallest
index for which $\Xi_{i,j}(x)=0$. We similarly say that $x\in H_{k}(X_{i})$ is
born in $H_{k}(X_{i})$ if $\Xi^{-1}_{t,i}(x)=0$ for all $t<i$. We can
represent the lifetime of $x$ by the half open interval $[i,j)$. If
$\Xi_{i,j}(x)\neq 0$ for all $i<j\leq l$, then we say that $x$ lives forever
and we represent its lifetime by the interval $[i;\infty)$.

The $k$-th persistent homology vector spaces of a filtered simplicial complex
$X$ are defined as $H_{k}^{i,j}=\mathbf{img}(\Xi_{i,j})$, and the total $k$th
persistent homology of $X$ is defined as $\oplus_{i=1}^{l}H_{k}(X_{i})$. By
the Correspondence Theorem of Persistent Homology [43], for each $k$ we can
assign to the total $k$-th persistent homology vector space a finite well-
defined collection of half open intervals, i.e., its so called _barcode_. An
alternative way to represent persistent homology graphically is given by
persistence diagrams, in which case each open interval $[i,j)$ is represented
by the point $(i,j)$ in $\mathbb{R}^{2}$. See Fig. 3 for an example
persistence diagram, which we will more formally define in the next section.

###  2.3. Stability and convergence of persistence diagrams

Persistence diagrams and barcodes are widely used as a concise representation
for the multiscale homological features of a point-cloud data set. As such, it
is important to understand their robustness to perturbations, which can
represent data error or noise [9]. One can also study for a converging
sequence of point clouds whether their associated persistence diagrams also
converge. In this section, we present basic results related to stability and
convergence.

Figure 3. Example of stability for persistence diagrams resulting from
Vietoris-Rips filtrations. (left) Two point-cloud sets $\mathcal{Y}$ and
$\mathcal{Z}$ are close with respect to the $\mathsf{L}_{\infty}$ norm. The
center and right panels depict their associated persistence diagrams
$D_{\mathcal{Y}}$ and $D_{\mathcal{Z}}$, which are also close with respect to
the bottleneck distance.

####  2.3.1. Stability

We first discuss stability in a general setting, which requires several
definitions. Let $X$ be a simplicial complex and
$g:X\longrightarrow\mathbb{R}$ be a tame function.

######  Definition 2.10 (Tame [9]).

A function $g:X\longrightarrow\mathbb{R}$ is tame if it has a finite number of
homological critical values and the homology groups $H_{k}(g^{-1}(-\infty,a))$
are finite-dimensional for all $k\in\mathbb{Z}$ and $a\in\mathbb{R}$.

In particular, Morse functions on compact manifolds are tame, as well as
piece-wise linear functions on finite simplicial complexes and, more
generally, Morse functions on compact Whitney-stratified spaces [15]. Assuming
a fixed integer $k$, we define $G_{x}=H_{k}(g^{-1}(-\infty,x])$, and for any
$x<y$, we let $g_{x}^{y}:G_{x}\longrightarrow G_{y}$ be the map induced by
inclusion of the sub-level set of x in that of y.

######  Lemma 2.11 (Critical Value Lemma [9]).

If some closed interval $[x,y]$ contains no homological critical value of $g$,
then $g^{y}_{x}$ is an isomorphism for every integer $k$.

We now formally define a $\textbf{persistence diagram}.$ Using the same
notation as above, we write $G_{x}^{y}={\bf img}(g_{x}^{y})$ for the image of
$G_{x}$ in $G_{y}$. By convention, we set $G_{x}^{y}=\\{0\\}$ whenever $x$ or
$y$ is infinite. The group $G_{x}^{y}$ is called the persistent homology
group.

Let $g:X\longrightarrow\mathbb{R}$ be a tame function and denote
$(a_{i})_{i=1,...,n}$ as its homological critical values, and let
$(b_{i})_{i=0..n}$ be an interleaved sequence in which $b_{i-1}<a_{i}<b_{i}$
for all $i$. We set $b_{-1}=a_{0}=-\infty$ and $b_{n+1}=a_{n+1}=+\infty$. For
two integers $0\leq i<j\leq n+1$, we define the multiplicity of the pair
$(a_{i},a_{j})$ by:

$\mu_{i}^{j}=\beta_{b_{i-1}}^{b_{j}}-\beta_{b_{i}}^{b_{j}}+\beta_{b_{i}}^{b_{j-1}}-\beta_{b_{i-1}}^{b_{j-1}}$

where $\beta_{x}^{y}={\bf{dim}}(F_{x}^{y})$ denotes the persistent Betti
numbers for all $-\infty\leq x\leq y\leq+\infty$.

######  Definition 2.12 (Persistence Diagram [9]).

The persistence diagram $D(\mathcal{A})\subset\overline{\mathbb{R}}^{2}$ of a
filtered topological space $\mathcal{A}$ is the set of points $(a_{i},a_{j})$,
which are counted with multiplicity $\mu_{i}^{j}$ for $0\leq i<j\leq n+1$,
along with all points on the diagonal, which are counted with infinite
multiplicity.

Given two persistence diagrams, we can quantify their dissimilarity using
various metrics. In particular, we will consider the following metric.

######  Definition 2.13 (Bottleneck Distance [9]).

The bottleneck distance between two point sets $\mathcal{Y}$ and $\mathcal{Z}$
is given by

$\displaystyle d_{B}(\mathcal{Y},\mathcal{Z})$
$\displaystyle=\inf_{\gamma}\sup_{y}\left\lVert{y-\gamma(y)}\right\rVert_{\infty}~{},$
(1)

where $y\in\mathcal{Y}$ and $z\in\mathcal{Z}$ range over all points and
$\gamma$ ranges over all bijections from $\mathcal{Y}$ to $\mathcal{Z}$. Here,
we interpret each point with multiplicity $k$ as $k$ individual points and the
bijection is between the resulting sets.

Next, we present triangulable spaces. As in [11], an underlying space of a
simplicial complex $K$ is defined as $\bigcup K=\bigcup_{\sigma\in K}\sigma$.
If there exists a simplicial complex $K$ such that $\bigcup K$ is homeomorphic
to $X$, then $X$ is triangulable.

In Fig. 3, we show that it two point clouds are similar, then their associated
persistence diagrams are similar. That is, persistence diagrams are ‘stable’
with respect to small changes, which can be quantified through the bottleneck
distance.

######  Theorem 2.14 (Stability Theorem [5] ).

Let $X$ be a triangulable space with continuous tame functions
$g,h:X\longrightarrow\mathbb{R}$, and let $D_{g}$ and $D_{h}$ denote their
associated persistence diagrams obtained using a height filtration. Then the
bottleneck distance between these persistence diagrams satisfies a global
uniform bound

$d_{B}(D_{g},D_{h})\leq\left\lVert{g-h}\right\rVert_{\infty}.$

While Thm. 2.14 describes the stability of persistence diagrams with respect
to changes to the functions to which filtrations are applied, one can also use
it to equivalently prove the stability of persistence diagrams for when the
function changes due to perturbations of points. We present the following
example.

######  Corollary 1 (Stability of VR Persistence Diagrams to Point
Perturbations).

Let $\mathcal{Y}=\\{y_{i}\\}_{i\in\mathcal{V}}\in\mathbb{R}^{d}$ with
$\mathcal{V}=\\{1,...,N\\}$ denote a set of $N$ points, and let
$\mathcal{Y^{\prime}}=\\{y_{i}^{\prime}\\}_{i\in\mathcal{V}}\in\mathbb{R}^{d}$
be a set of perturbed points such that
$||y_{i}-y_{i}^{\prime}||_{2}\leq\epsilon$ for all $i$. If
$g:\mathcal{Y}\longrightarrow\mathbb{R}^{n\times n}_{+}$ denotes the pairwise
distance function in which $g_{ij}(\mathcal{Y})=||y_{i}-y_{j}||_{2}$ and
$h:\mathcal{Y^{\prime}}\longrightarrow\mathbb{R}^{n\times n}_{+}$ with
$h_{ij}(\mathcal{Y^{\prime}})=||y^{\prime}_{i}-y^{\prime}_{j}||_{2}$. It then
follows that $d_{B}(D_{g},D_{h})\leq 2\epsilon$.

###### Proof.

$\displaystyle d_{B}(D_{g},D_{h})\leq||g-h||_{\infty}$
$\displaystyle=\max_{i,j\in\mathcal{V}}|g(y_{i},y_{j})-h(y^{\prime}_{i},y^{\prime}_{j})|$
$\displaystyle=\max_{i,j\in\mathcal{V}}\left|||y_{i}-y_{j}||_{2}-||y^{\prime}_{i}-y^{\prime}_{j}||_{2}\right|.$

However, if we define $y^{\prime}_{i}=y_{i}+e_{i}$, then
$||e_{i}||_{2}\leq\epsilon$ for any $i\in\mathcal{V}$ and

$\displaystyle||y^{\prime}_{i}-y^{\prime}_{j}||_{2}=||(y_{i}-y_{j})+(e_{i}-e_{j})||_{2}\leq||(y_{i}-y_{j})||_{2}+||(e_{i}-e_{j})||_{2}.$

It follows that

$\displaystyle\left|||y_{i}-y_{j}||_{2}-||y^{\prime}_{i}-y^{\prime}_{j}||_{2}\right|\leq||(e_{i}-e_{j})||_{2}\leq
2\epsilon,$

which subsequently also bounds $d_{B}(D_{g},D_{h})$.

∎

####  2.3.2. Convergence

The stability of persistence diagrams also has important consequences for the
convergence of a sequence of persistence diagrams that is associated with
convergent sequence of point clouds. Focusing on VR filtrations, consider a
sequence of point clouds $\mathcal{Y}^{m}=\\{y^{m}_{i}\\}_{i=1}^{N}$ of fixed
size $N=|\mathcal{Y}^{m}|$ for each $m\in\mathbb{N}_{+}$ with
$y_{i}^{m}\in\mathbb{R}^{p}$. Assume for each point $i$ that the sequence
converges $y_{i}^{m}\to y_{i}$ such that
$\lVert{y^{m}_{i}-y_{i}}\rVert_{2}\leq 1/m$. Note that such a convergence
criterion can be ensured by considering a subsequence in which each subsequent
element is chosen so that the bound is true for all $i\in\\{1,\dots,N\\}$. Let
$D_{f_{m}}$ and $D_{f}$ be the persistent diagrams for VR filtrations using
the pairwise distance functions $f_{m}$ and $f$, which are respectively
defined using the respective point clouds $\mathcal{Y}^{m}$ and $\mathcal{Y}$.
The Stability Theorem and Corollary 1 imply convergence of the associated
persistence diagrams since

$d_{B}(D_{f_{m}},D_{f})\leq\left\lVert{f_{m}-f}\right\rVert_{\infty}\leq
2\lVert{y^{m}_{i}-y_{i}}\rVert_{2}\leq\frac{2}{m},$

which converges to $0$ as $m\to\infty$.

##  3\. Topological data analysis using kNN orderings

We now present our main findings: an approach for persistent homology that is
based on the relative positioning of points according to their $k$-nearest-
neighbor (kNN) sets. Our approach introduces kNN complexes and filtrations
using a filtration parameter $k\in\mathbb{N}_{+}$, thereby contrasting VR and
other filtrations that use a distance threshold $\epsilon$ as the filtration
parameter. We will show that kNN-based persistent homology has certain
advantages that can benefit applications for which the relative positioning of
data points is important, i.e., as opposed to their precise locations.

This section is organized as follows. In Sec. 3.1, we define kNN orderings of
points. In Sec. 3.2, we develop kNN filtrations, use them to study kNN
persistent homology, and compare them to the study of VR filtrations. In Sec.
3.3, we analyze the stability and convergence of persistence diagrams
resulting from kNN filtrations.

###  3.1. kNN orderings, neighborhoods, and symmetrization

We begin with a definition for kNN orderings. One complication is that the
ordering of nearest neighbors is not necessarily symmetric, and so we will
also describe additional transformations that we will use to symmetrize
orderings prior to constructing filtrations.

######  Definition 3.1 ($k$-Nearest-Neighbor Orderings).

Let $\mathcal{V}=\\{1,\dots,N\\}$ enumerate a set of points
$\mathcal{Y}=\\{y_{i}\\}_{i\in\mathcal{V}}\in\mathbb{R}^{p}$ in a normed
metric space and $\\{f_{ij}=||y_{i}-y_{j}||_{2}\\}$ be their pairwise
distances resulting from the pairwise distance map given in Definition 2.3.
For each $i$, let $k_{ij}$ denote the nearest-neighbor order of $y_{j}$ with
respect to $y_{i}$ so that $y_{j}$ is the ($k_{ij}$)-th nearest neighbor of
$y_{i}$ ($k_{ii}\equiv 0$). The ordering is formally defined for each fixed
$i$ by $\\{k_{ij}\\}_{j=1}^{N}=\phi(\\{f_{ij}\\}_{j=1}^{N})$, where
$\phi:\mathbb{R}^{N}\longrightarrow\mathbb{N}^{N}$ is the “argsort function”.

In the above, we assume that the orderings are well-defined in that for a
given $i\in\mathcal{V}$, the entries in the set $\\{f_{ij}\\}_{j=1}^{N}$ are
unique. In practice, if two distances $f_{ij}$ and $f_{ij^{\prime}}$ are the
same and they correspond or order $k$, then we assign an ordering at random so
that either $k_{ij}=k$ and $k_{ij^{\prime}}=k+1$, or vice versa. If even more
distances are the same, then we similarly assign them a relative ordering
uniformly at random. In principle, the argsort function $\phi$ can be defined
in a variety ways to handle the ordering of repeated entries. Given the above
definition of kNN orderings, we now introduce an associated map between a set
of points and an associated matrix with entries $k_{ij}$.

######  Definition 3.2 (kNN Ordering Function).

Let $\mathcal{Y}=\\{y_{i}\\}_{i\in\mathcal{V}}$ denote a set of $N\geq 2$
points with $\mathcal{V}=\\{1,2,...,N\\}$ in a Euclidean metric space and
recall the row-defined pairwise distance function
$f_{i}:\mathcal{Y}\longrightarrow\mathbb{R}^{N}_{+}$ given in Definition 2.3.
Letting $\phi$ be the argsort function, we define the map k-nearest-neighbor
(kNN) ordering function $F:\mathcal{Y}\longrightarrow\mathbb{N}^{N\times
N}_{+}$ as the matrix-valued function $F=[F_{1},\dots,F_{N}]^{T}$ in which
each row $F_{i}$ is defined by $F_{i}=\phi\circ
f_{i}:\mathcal{Y}\longrightarrow\mathbb{N}^{N}_{+}$.

We will use kNN orderings of points to define local neighborhoods
$\mathcal{N}_{ik}$ for each point $i\in\mathcal{V}$, noting that any nested
sequence of neighborhoods defines a local filtration of the vertices
$\mathcal{V}$.

######  Definition 3.3 (kNN Neighborhoods).

Given a set of kNN orderings $\\{k_{ij}\\}$ for $i,j\in\mathcal{V}$, we define
the kNN neighborhoods as the sets $\mathcal{N}_{ik}=\\{j|k_{ij}\leq k\\}$ for
each $i\in\mathcal{V}$ and $k\in\\{0\\}\cup\mathcal{V}\setminus\\{N\\}$.

Importantly, the kNN orderings and kNN neighborhoods are not symmetric—that
is, $j\in\mathcal{N}_{ik}$ does not imply $i\in\mathcal{N}_{jk}$. Because we
would like to use the kNN neighborhood sets to construct filtrations of
simplicial complexes that contain undirected simplices, we will now describe
how to construct symmetric kNN neighborhoods.

######  Definition 3.4 (Symmetrized kNN Orderings and Neighborhoods).

We define three types of symmetrized kNN
neighborhoods—${\mathcal{N}}_{ik}^{min}$, ${\mathcal{N}}_{ik}^{trans}$ and
${\mathcal{N}}_{ik}^{max}$—that use, respectively, the following three
symmetrizations of kNN orderings $\\{k_{ij}\\}$:

$\displaystyle\tilde{k}_{ij}$ $\displaystyle=\min\\{k_{ij},k_{ji}\\}$
$\displaystyle\overline{k}_{ij}$ $\displaystyle=(k_{ij}+k_{ji})/2$
$\displaystyle\hat{k}_{ij}$ $\displaystyle=\max\\{k_{ij},k_{ji}\\}.$ (2)

Notably, these kNN neighborhoods satisfy the following nestedness relation.

######  Lemma 3.5 (Nestedness of Symmetrized kNN Neighborhoods).

Consider fixed $k$ and $i$. Then the neighborhood sets
$\mathcal{N}_{ik}^{min},\mathcal{N}_{ik}^{trans},\mathcal{N}_{ik}^{max}$
satisfy the following nestedness relationships:

$\mathcal{N}^{max}_{ik}\subseteq\mathcal{N}^{trans}_{ik}\subseteq\mathcal{N}^{min}_{ik}.$

###### Proof.

For any $k_{ij},k_{ji}\in\mathbb{R}$, one has
$\tilde{k}_{ij}\leq\overline{k}_{ij}\leq\hat{k}_{ij}$ by definition of the min
and max functions. If $j\in\mathcal{N}^{max}_{ik}$, then $\hat{k}_{ij}\leq k$.
This implies $\tilde{k}_{ij}\leq\overline{k}_{ij}\leq\hat{k}_{ij}\leq k$, and
so
$j\in\mathcal{N}^{min}_{ik}\subseteq\mathcal{N}^{trans}_{ik}\subseteq\mathcal{N}^{max}_{ik}$.
∎

We now define graphs and clique complexes using symmetrized kNN orderings and
neighborhoods.

######  Definition 3.6 (Symmetrized kNN Graph).

Given a set of points enumerated by $\mathcal{V}$, let
$\mathcal{E}_{k}=\\{(i,j)|i\in\mathcal{V},j\in\mathcal{N}_{ik}\\}$ be a set of
undirected edges connecting pairs of nearest neighbors, which are
symmetrically defined by choosing
$\mathcal{N}_{ik}\in\\{\mathcal{N}_{ik}^{min},\mathcal{N}_{ik}^{trans},\mathcal{N}_{ik}^{max}\\}$.
We denote the respective graphs
$\mathcal{G}_{k}(\mathcal{V},\mathcal{E}_{k})$, depending on symmetrization
method, by $\mathcal{G}_{k}^{min}$, $\mathcal{G}_{k}^{trans}$, and
$\mathcal{G}_{k}^{max}$.

######  Definition 3.7 (Symmetrized kNN Clique Complex).

Given a symmetrized kNN graph
$\mathcal{G}_{k}\in\\{\mathcal{G}_{k}^{min},\mathcal{G}_{k}^{trans},\mathcal{G}_{k}^{max}\\}$
with vertices $\mathcal{V}$ and edges $\mathcal{E}_{k}$, we construct its
associated clique complex $X_{k}=Cl(\mathcal{G}_{k})$, and we similarly use a
superscript to denote the method of symmetrization, i.e., $X_{k}^{min}$,
$X_{k}^{trans}$, and $X_{k}^{max}$.

######  Corollary 2 (Nestedness of Symmetrized kNN Graphs and kNN Complexes).

Symmetrized kNN graphs and kNN complexes satisfy the following nestedness
relations

$\displaystyle\mathcal{G}^{max}_{k}$
$\displaystyle\hookrightarrow\mathcal{G}^{trans}_{k}\hookrightarrow\mathcal{G}^{min}_{k}$
$\displaystyle X^{max}_{k}$ $\displaystyle\hookrightarrow
X^{trans}_{k}\hookrightarrow X^{min}_{k}.$ (3)

###### Proof.

The results follow immediately from Lemma 3.5, which proved the nestedness of
kNN neighborhoods. ∎

Corollary 2 implies that $\mathcal{G}^{max}_{k}$ is a subgraph of
$\mathcal{G}^{trans}_{k}$, which is a subgraph of $\mathcal{G}^{min}_{k}$.
Similarly, $X^{max}_{k}$ is a subcomplex of $X^{trans}_{k}$, which is a
subcomplex of $X^{min}_{k}$.

###  3.2. Filtrations and persistent homology using kNN complexes

We now formulate filtrations and persistent homology using symmetrized kNN
complexes. Varying $k$ gives rise to a sequence of nested sets called a
filtration, and we will define several types based on the different
symmetrization methods. We will also define local and global versions of
filtrations.

Figure 4. Visualization of kNN-filtered simplicial complexes for a point cloud
using the three types of symmetrization given by Definition 3.4. Comparing
across the columns, observe the nestedness property given by Corollary 2.

######  Definition 3.8 (Global kNN Filtration).

Let $X_{k},X_{k^{\prime}}\in\\{X_{k}^{min},X_{k}^{trans},X_{k}^{max}\\}$ be
kNN complexes with the same symmetrization method. Then we define a kNN-
filtered simplicial complex

$\\{X_{k}\longrightarrow X_{k^{\prime}}\\}_{0\leq k\leq k^{\prime}\leq N-1}.$

In Fig. 4, we illustrate global kNN filtrations with the three different
symmetrization methods given by Definition 3.4. For simplicity, we only
visualize 0-simplices and 1-simplices. By comparing the kNN complexes across a
given column, one can observe the nestedness relations defined by Corollary 2.

We formulate persistent homology for kNN filtrations of a simplicial complex
anaologous to that defined for a VR filtrations (recall Sec. 2.2), and in Fig.
5, we visualize persistence diagrams for both (left) a kNN filtration and
(right) a VR filtration for an example point cloud. The red and blue
persistence barcodes indicate 0-dimensional and 1-dimensional cycles,
respectively. Observe that the kNN filtration reveals a 1-cycle, whereas the
VR filtration does not. Hence, filtrations of simplicial complexes
(specifically clique complexes) according to pairwise distances and kNN
provide complementary homological information.

Figure 5. Comparison of persistent homology for an example point cloud using
two different filtrations: (left) our proposed kNN filtration; and (right) a
VR filtration. The red and blue persistence barcodes indicate 0-dimensional
and 1-dimensional cycles, respectively. Observe that the kNN filtration
reveals a 1-cycle, whereas the VR filtration does not.

In the next sections, we will further compare persistence diagrams resulting
from kNN and VR filtrations; however, it’s worth highlighting several
differences here. First, one benefit of using kNN sets versus a distance
threshold $\epsilon$ is that filtrations are standardized. That is, the
filtration parameter range $k\in[0,N]$ for kNN filtrations is always the same
for a set of $N$ points. In contrast, different point clouds have different
lengths scales, and so the range of a distance-based filtration parameter is
in general not standardized. One could seek to standardize the ranges of VR
filtration parameters by standardizing distances; however, there are many ways
to normalize a point cloud, such as dividing by the mean distance or by the
distances’ standard deviation. Given that one could implement a variety of
normalization approaches, comparing VR filtrations across different point
clouds that have different length scales or different dimensions is not
straightforward. In contrast, kNN filtrations are standardized by definition.

Second, the filtration parameter $\epsilon\in\mathbb{R}_{+}$ for VR
filtrations can in principle take on any positive number. In contrast,
$k\in\\{0,\dots,N-1\\}$ can only take on integer values (or in the case of the
symmetrization method of $trans$, half integers as well). Potentially, this
reduced space of possible filtration parameters could benefit the
computationally efficiency of implementing kNN filtrations, although we don’t
explore that pursuit herein. That said, our experiments generally find kNN
filtrations to have higher computational complexity, since they require both
computing pairwise distances as well as their orderings.

###  3.3. Stability and convergence of kNN homology

Here, we will study two key properties for the space of persistence diagrams
that follow from kNN filtrations: stability and convergence.

####  3.3.1. kNN-preserving transformations

We observe that if points undergo perturbations that are sufficiently small,
then it is possible to move points without changing any of the neighbor
orderings. To make this more precise, we define a family of point-cloud
transformations that have this property.

######  Definition 3.9 (Local and Global kNN-Preserving Transformations).

Let $\mathcal{Y}=\\{y_{i}\\}_{i\in\mathcal{V}}$ with $y_{i}\in\mathbb{R}^{p}$
be a set of points that are enumerated $\mathcal{V}=\\{1,...,N\\}$,
$f:\mathcal{Y}\longrightarrow\mathbb{R}^{N\times N}_{+}$ be the pairwise
distance function given by Def. 2.3, and
$F:\mathcal{Y}\longrightarrow\mathbb{N}^{N\times N}_{+}$ be the neighbor-
ordering function given by Def. 3.2. We define a transformation
$h:\mathcal{Y}\longrightarrow\mathcal{Y^{\prime}}$ with
$h(x)=(h_{1}(y_{1}),...,h_{n}(y_{n}))=(y^{\prime}_{1},...,y^{\prime}_{n})$ and
define two types of preservation properties:

  * •

$h$ is local kNN-preserving for some $i\in\mathcal{V}$ if and only if $(F\circ
h)_{ij}(\mathcal{Y})=F_{ij}(\mathcal{Y})$ for fixed $i$ and $j\in\mathcal{V}$.

  * •

$h$ is global kNN-preserving if and only if it is local kNN-preserving for all
$i\in\mathcal{V}$.

Note that local kNN-preservation implies that the neighbor orderings are
preserved for a particular point $x_{i}$, while global-kNN preservation
implies that all neighbor orderings are preserved for all points. We also note
that local and global kNN-preserving transformations can also be similarly
defined for the three symmetrized versions of kNN orderings. We also define a
slight variation in which the preservation of orderings is only required for
the nearest neighbor orderings up to a finite size $k\leq K$, which we refer
to as “$K$-bounded” local and global kNN-preserving transformations.

As one example, consider a set of three points
$x_{i}\in\\{0,2,3\\}\subset\mathbb{R}$ and the transformation
$h(\\{0,2,3\\})=\\{0,2.1,3\\}$. It is both local and global kNN-preserving,
since the perturbation $2\to 2.1$ is sufficiently small such that none of the
neighbor orderings change. In fact, all isometric transformations including
(i.e., translation, rotation, reflection and glide reflection) are global kNN-
preserving transformations because they leave the pairwise distances
unchanged.

Figure 6. Example with 3 points $\mathcal{Y}=\\{x_{a},x_{b},x_{c}\\}$ with
$x_{a}=-1$, $x_{c}=1$ and either (A) $x_{b}=-\epsilon$ or (B) $b=\epsilon$.
Note that the perturbation can be made arbitrarily small for any $\epsilon>0$,
and the nearest-neighbor orderings are different. (See Tables 3 and 3.)

However, there are many transformations that are not kNN preserving. In Fig.
6, we illustrate an example where a small perturbation to one point can change
the neighbor ordering in a discontinuous way. Consider a set of points
$\mathcal{V}=\\{a,b,c\\}$ with locations
$\mathcal{Y}=\\{x_{a},x_{b},x_{c}\\}\subset\mathbb{R}$ where $x_{a}=-1$,
$x_{c}=1$ and $x_{b}=-\epsilon$ (for some small value $0<\epsilon\ll 1$). Then
the neighbor ordering matrix is given in Table 3. Now consider the
transformation $h_{1}(x_{a})=x_{a}$, $h_{2}(x_{b})=x_{b}+2\epsilon$, and
$h_{3}(x_{c})=x_{c}$, then the neighbor ordering matrix changes, as shown in
Table 3.

| point a | point b | point c
---|---|---|---
point a | 0 | 1 | 2
point b | 1 | 0 | 2
point c | 2 | 1 | 0
Table 2. kNN orderings before transformation $h$.

| point a | point b | point c
---|---|---|---
point a | 0 | 1 | 2
point b | 2 | 0 | 1
point c | 2 | 1 | 0
Table 3. kNN orderings after transformation $h$.

Given the definitions of local and global kNN-preserving transformations, we
can also define equivalence classes for any finite set of points
$\mathcal{Y}=\\{y_{i}\\}\subset\mathbb{R}^{p}$.

######  Definition 3.10 (kNN Equivalence of Point Sets).

Let $F$ denote the neighbor-ordering function given by Def. 3.2. Any two point
clouds $\mathcal{Y}=\\{y_{i}\\}_{i\in\mathcal{V}}$ and
$\mathcal{Y^{\prime}}=\\{y_{i}^{\prime}\\}_{i\in\mathcal{V}}$ with
$y_{i},y^{\prime}_{i}\in\mathbb{R}^{p}$ are said to be kNN-equivalent if
$F(\mathcal{Y})=F(\mathcal{Y^{\prime}})$. We denote the equivalence by
$\mathcal{Y}\sim\mathcal{Y^{\prime}}$. Furthermore, we have
$[\mathcal{Y}]=\\{\mathcal{Y^{\prime}}|\mathcal{Y^{\prime}}\sim\mathcal{Y}\\}$
as the kNN-equivalence class of $\mathcal{Y}$.

Indeed, one can show

  * •

Reflexivity: $\mathcal{Y}\sim\mathcal{Y}^{\prime}$.
It is trivial. Take $h(t)=\mathbf{id}$ as the kNN-preserving transformation.

  * •

Symmetry: if $\mathcal{Y}\sim\mathcal{Y^{\prime}}$ then
$\mathcal{Y^{\prime}}\sim\mathcal{Y}$ .
Let $h:\mathcal{Y}\longrightarrow\mathcal{Y^{\prime}}$ be a global kNN-
preserving transformation. Then $(F\circ
h)_{ij}(\mathcal{Y})=(F_{ij})(\mathcal{Y})$ and $h$ is a one-to-one function.
Let $h^{-1}$ be the inverse function of $h$. So, we have: $(F\circ
h^{-1})_{ij}(\mathcal{Y^{\prime}})=(F_{ij})(\mathcal{Y^{\prime}})$, thus
$h^{-1}$ is the global kNN-preserving transformation from
$\mathcal{Y^{\prime}}$ to $\mathcal{Y}$.

  * •

Transitivity: if $\mathcal{Y}\sim\mathcal{Y^{\prime}}$ and
$\mathcal{Y^{\prime}}\sim\mathcal{Y^{\prime\prime}}$ then
$\mathcal{Y}\sim\mathcal{Y^{\prime\prime}}$.
Let $h(t)$ be kNN-preserving transformation between $\mathcal{Y}$ and
$\mathcal{Y^{\prime}}$, $g(t)$ be kNN-preserving transformation between
$\mathcal{Y^{\prime}}$ and $\mathcal{Y^{\prime\prime}}$, then $g\circ h$ be
kNN-preserving transformation between $\mathcal{Y}$ and
$\mathcal{Y^{\prime\prime}}$.

The equivalence of kNN orderings implies that kNN filtrations and kNN-based
persistent homology are identical for any two point clouds within a given
equivalence class. Thus, persistence diagrams for kNN persistent homology are
robust to (and in fact, unaffected by) any kNN-preserving transformation. That
said, such persistence diagrams can also be unstable to other types of
perturbations, as we explore below.

####  3.3.2. Stability of kNN persistence diagrams

In analogy to the stability theorem for the space $\mathcal{H}_{VR}$ of
persistence diagrams obtained using VR filtrations, we consider whether the
space $\mathcal{H}_{kNN}$ of persistence diagrams using kNN filtrations is
also stable with respect to perturbations of the associated point cloud. We
fist show that persistence diagrams resulting from kNN filtrations are do not
satisfy the same stability condition as that for VR filtrations.

######  Theorem 3.11 (kNN Persistence Diagrams are not Uniformly Globally
Stable to Point Changes).

Let $\mathcal{Y}=\\{y_{i}\\}_{i\in\mathcal{V}}$ with
$\mathcal{V}=\\{1,...,N\\}$ be a point cloud with a neighbor-ordering function
$F=\phi\circ f$, where $f:\mathcal{Y}\longrightarrow\mathbb{R}^{N\times
N}_{+}$ is the pairwise distance function and $\phi:\mathbb{R}^{N\times
N}_{+}\longrightarrow\mathbb{N}^{N\times N}_{+}$ is the ‘argsort’ function.
Further let $\mathcal{Y^{\prime}}=\\{y^{\prime}_{i}\\}_{i\in\mathcal{V}}$ be a
second point cloud with the neighbor-ordering function $G=\phi\circ g$.
Further let $D_{F}$ and $D_{G}$ denote the persistence diagrams of kNN
filtrations applied to $\mathcal{Y}$ and $\mathcal{Y^{\prime}}$. Further,
define the metric for two enumerated point clouds
$\left\lVert{\mathcal{Y}-\mathcal{Y^{\prime}}}\right\rVert_{\infty}=\max_{i\in\mathcal{V}}||y_{i}-y_{i}^{\prime}||_{2}$.
Then there does not exist a uniform global bound on the bottleneck distance
between persistence diagrams of the form:

$d_{B}(D_{F},D_{G})\leq\lVert{F-G}\rVert_{\infty}=\left\lVert{\phi\circ
f-\phi\circ g}\right\rVert_{\infty}\not\leq
L\left\lVert{\mathcal{Y}-\mathcal{Y^{\prime}}}\right\rVert_{\infty}.$

###### Proof.

The first inequality is satisfied by applying the original statement of the
stability theorem: persistence diagrams are uniformly bound by the maximal
difference between the functions that are filtered. By definition, the
neighbor-ordering function yields a matrix of k nearest neighbors,
$[k_{ij}]=F(\mathcal{Y})$ and $[k^{\prime}_{ij}]=G(\mathcal{Y^{\prime}})$,
implying

$\lVert{F-G}\rVert_{\infty}\equiv\max_{ij}|k_{ij}-k^{\prime}_{ij}|.$

That is, the difference in persistence diagrams is bound by the maximum
difference in neighbor orderings. However, the stability of persistent
homology with respect to neighbor-ordering changes does not imply stability
with respect to point-location changes.

To disprove the last inequality, we provide a counter example. Recall the sets
of $N=3$ points in Fig. 6 with $\mathcal{V}=\mathcal{V}^{\prime}=\\{a,b,c\\}$
and locations $\mathcal{Y}=\\{1,-\epsilon,1\\}\in\mathbb{R}$ and
$\mathcal{Y}^{\prime}=\\{1,\epsilon,1\\}\in\mathbb{R}$. By construction,
$||F-G||_{\infty}=1$ for any small $\epsilon$, but
$\left\lVert{\mathcal{Y}-\mathcal{Y^{\prime}}}\right\rVert_{\infty}=2\epsilon$.
Suppose there did exist a uniform bound with Lipschitz constant $L>1$, then
the points $\mathcal{Y}$ and $\mathcal{Y^{\prime}}$ with any $\epsilon<1/2L$
yields a contradiction since $||F-G||_{\infty}=1$ and
$||\mathcal{Y}-\mathcal{Y^{\prime}}||_{\infty}<1$.

∎

####  3.3.3. Topological convergence of kNN orderings

In this section, we will use the neighbor-ordering function to define a
discrete-topological notion of convergence for a sequence of point sets using
kNN persistent homology.

######  Definition 3.12.

Consider a sequence of point sets
$\mathcal{Y}^{(t)}=\\{y^{(t)}_{i}|i\in\mathcal{V}\\}$ with $t\in\mathbb{N}$
and $\mathcal{V}=\\{1,...,N\\}$ and $y^{(t)}_{i}\in\mathbb{R}^{p}$. We say
that the sequence $\\{\mathcal{Y}^{(t)}\\}$ has global convergence in kNN
topology to the limit $\mathcal{Y}$ iff
$\lim_{t\to\infty}F(\mathcal{Y}^{(t)})=F(\mathcal{Y})$, where $F$ is the
neighbor-ordering function. More precisely, for any $\epsilon$, there exists a
$t^{*}$ such that
$\max_{ij}|F_{ij}(\mathcal{Y})-F_{ij}(\mathcal{Y}^{(t)})|<\epsilon$ for all
$t>t^{*}$.

######  Definition 3.13.

Consider a sequence of point sets
$\mathcal{Y}^{(t)}=\\{y^{(t)}_{i}|i\in\mathcal{V}\\}$ with $t\in\mathbb{N}$
and $\mathcal{V}=\\{1,...,N\\}$ and $y^{(t)}_{i}\in\mathbb{R}^{p}$. We say
that the sequence $\\{\mathcal{Y}^{(t)}\\}$ has $\kappa$-bounded convergence
in kNN topology to a limit $\mathcal{Y}$ iff
$\lim_{t\to\infty}F_{ij}(\mathcal{Y}^{(t)})=F_{ij}(\mathcal{Y})$ for all
$i\in\mathcal{V}$ and $j\in\mathcal{N}_{ik}$, where $k\leq\kappa$ and
$\mathcal{N}_{k}\in\\{\mathcal{N}_{ik}^{min},\mathcal{N}_{ik}^{trans},\mathcal{N}_{ik}^{max}\\}$
are symmetrized neighborhoods that are defined in Def. 3.3. More precisely,
for any $\epsilon$, there exists a $t^{*}$ such that
$\max_{i\in\mathcal{V},j\in\mathcal{N}_{ik}}|F_{ij}(\mathcal{Y})-F_{ij}(\mathcal{Y}^{(t)})|<\epsilon$
for all $t>t^{*}$.

######  Remark 1.

Note that $\kappa$-bounded convergence is inclusive so that convergence for a
given $\kappa$ also implies convergence for any $\kappa^{\prime}\leq\kappa$.
In particular, global convergence in kNN topology implies $\kappa$-bounded
convergence for any $\kappa$.

We now define local variants of kNN topological convergence.

######  Definition 3.14.

Consider a sequence of point sets
$\mathcal{Y}^{(t)}=\\{y^{(t)}_{i}|i\in\mathcal{V}\\}$ with $t\in\mathbb{N}$
and $\mathcal{V}=\\{1,...,N\\}$ and $y^{(t)}_{i}\in\mathbb{R}^{p}$. We say
that the sequence $\\{\mathcal{Y}^{(t)}\\}$ has $\mathcal{U}$-local
convergence in kNN topology to a limit $\mathcal{Y}$ iff
$\lim_{t\to\infty}F_{ij}(\mathcal{Y}^{(t)})=F_{ij}(\mathcal{Y})$ for all
$i,j\in\mathcal{U}\subseteq\mathcal{V}$ . More precisely, for any $\epsilon$,
there exists a $t^{*}$ such that
$\max_{i,j\in\mathcal{U}}|F_{ij}(\mathcal{Y})-F_{ij}(\mathcal{Y}^{(t)})|<\epsilon$
for all $t>t^{*}$.

######  Definition 3.15.

Consider a sequence of point sets
$\mathcal{Y}^{(t)}=\\{y^{(t)}_{i}|i\in\mathcal{V}\\}$ with $t\in\mathbb{N}$
and $\mathcal{V}=\\{1,...,N\\}$ and $y^{(t)}_{i}\in\mathbb{R}^{p}$. We say
that the sequence $\\{\mathcal{Y}^{(t)}\\}$ has $\kappa$-bounded
$\mathcal{U}$-local convergence in kNN topology to a limit $\mathcal{Y}$ iff
$\lim_{t\to\infty}F_{ij}(\mathcal{Y}^{(t)})=F_{ij}(\mathcal{Y})$ for all
$i\in\mathcal{U}\subseteq\mathcal{V}$ and $j\in\mathcal{N}_{ik}$, where the
symmetrized neighborhoods
$\mathcal{N}_{k}\in\\{\mathcal{N}_{ik}^{min},\mathcal{N}_{ik}^{trans},\mathcal{N}_{ik}^{max}\\}$
are given in Def. 3.3 and $k\leq\kappa$. More precisely, for any $\epsilon$,
there exists a $t^{*}$ such that
$\max_{i\in\mathcal{U},j\in\mathcal{V}}|F_{ij}(\mathcal{Y})-F_{ij}(\mathcal{Y}^{(t)})|<\epsilon$
for all $t>t^{*}$.

Note for any point set that convergences in global kNN topology (or k-bounded
convergence in kNN topology), that there exists a $t^{*}$ such that
$F_{ij}(\mathcal{Y})=F_{ij}(\mathcal{Y}^{(t)})$ for all $t>t^{*}$ and
$i,j\in\mathcal{V}$ (or $i\in\mathcal{V}$ and $j\in N_{ik}$). Specifically, we
can choose $\epsilon\in(0,1)$. Since $F_{ij}(\mathcal{Y})\in\mathbb{N}$ for
any point set $\mathcal{Y}$, the condition
$|F_{ij}(\mathcal{Y})-F_{ij}(\mathcal{Y}^{(t)})|<\epsilon$ implies
$F_{ij}(\mathcal{Y})-F_{ij}(\mathcal{Y}^{(t)})=0$ for all $t>t^{*}$. That is,
kNN convergence is a discrete property that is exactly obtained for
sufficiently large $t>t^{*}$. This significantly contrasts the notion of
convergence in norm, which is often asymptotically approached rather than
exactly obtained. The next theorem more precisely establishes a relation
between convergence in a normed metric space and convergence in kNN topology.

######  Theorem 3.16 (Convergence in Norm Implies Convergence in kNN
Topology).

Let $\mathcal{Y}^{(t)}=\\{y^{(t)}_{i}|i\in\mathcal{V}\\}\subset\mathbb{R}^{p}$
be an element of a sequence of point clouds in which each point converges in
norm to some limit, $\lim_{t\to\infty}||y_{i}^{(t)}-y_{i}||=0$ for each
$i\in\mathcal{V}$. Define
$\mathcal{Y}=\\{y_{i}|i\in\mathcal{V}\\}\subset\mathbb{R}^{p}$ as that limit.
Then $\mathcal{Y}^{(t)}\to\mathcal{Y}$ in kNN topology, and there exists a
$t^{*}$ such that $F(\mathcal{Y}^{(t)})=F(\mathcal{Y})$ for any $t>t^{*}$,
where $F$ is the neighbor-ordering given by Def. 3.2.

###### Proof.

To prove this theorem, we use a contradiction. If $\mathcal{Y}^{(t)}$ does not
converge to $\mathcal{Y}$ in kNN-topology, then for any $t$, there exists at
least one neighbor ordering that differs, i.e., $F_{ij}(\mathcal{Y}^{(t)})\neq
F_{ij}(\mathcal{Y})$ for some $i,j\in\mathcal{V}$. Letting
$d_{ij}^{(t)}=||y_{i}^{(t)}-y_{j}^{(t)}||_{2}$ and
$d_{ij}^{(\infty)}=||y_{i}-y_{j}||_{2}$, this implies
$d_{ij}^{(\infty)}-d_{ik}^{(\infty)}>0$ but $d_{ij}^{(t)}-d_{ik}^{(t)}\leq 0$
for some $i,j,k\in\mathcal{V}$. (This must be true of the distances if the
neighbor orderings differ.) Let
$\delta^{*}=\max_{i,j,k}|d_{ij}^{(\infty)}-d_{ik}^{(\infty)}|$. However,
because $\lim_{t\to\infty}||y_{i}^{(t)}-y_{i}||$ for each $i$, there exists a
$t^{*}$ such that $||y_{i}^{(t)}-y_{i}||_{\infty}<\epsilon/4$ for all $i$ when
$t>t^{*}$. It then follows that $|d_{ij}^{(t)}-d_{ij}^{(\infty)}|<\epsilon/2$
and $|d_{ik}^{(t)}-d_{ik}^{(\infty)}|<\epsilon/2$. Now suppose
$d_{ij}^{(\infty)}-d_{ik}^{(\infty)}>0$. Then

$\displaystyle d_{ij}^{(t)}-d_{ik}^{(t)}$
$\displaystyle>d_{ij}^{(t)}-(d_{ik}^{(\infty)}+\epsilon/2)$
$\displaystyle>(d_{ij}^{(\infty)}-\epsilon/2)-(d_{ik}^{(\infty)}+\epsilon/2)$
$\displaystyle=d_{ij}^{(\infty)}-d_{ik}^{(\infty)}-\epsilon$
$\displaystyle=\delta^{*}-\epsilon.$ (4)

This is true for any $\epsilon$, so we may choose $\epsilon<\delta^{*}$, which
implies $d_{ij}^{(t)}-d_{ik}^{(t)}>0$, contradicting the above statement.

∎

Finally, we prove that the reverse property does not necessarily hold.

######  Theorem 3.17 (Convergence in kNN Topology Does Not Imply Convergence
in Norm).

Let $\mathcal{Y}^{(t)}=\\{y^{(t)}_{i}|i\in\mathcal{V}\\}\subset\mathbb{R}^{p}$
be an element of a sequence of point sets that converges in kNN topology. Then
each $y_{i}^{(t)}$ may or may not converge to some limit $y_{i}$ as
$t\to\infty$.

###### Proof.

See the proof to Thm. 3.11 for a counter example in which points converge as
$\epsilon\to 0$, but not for kNN topology, which remains bounded below by 1.

∎

##  4\. kNN persistent homology reveals topological convergence of pageRank
algorithm

In this section, we study the convergence of an iterative method for
approximating Google’s PageRank an use kNN persistent homology to develop a
perspective from discrete topology—that is, as opposed to the typical
geometric perspective of convergence under a vector norm. In Sec. 4.1, we
present the PageRank algorithm. In Sec. 4.2, we present numerical experiments
for an empirical network: a dolphin social network. In Sec. 4.3, we study
PageRank for the same network using local versions of kNN topological
convergence.

###  4.1. PageRank

Google developed _PageRank_ to solve the problem of web search and ranking for
the World Wide Web [3]. Their aim was to create an importance measure for each
webpage distinguish highly recognizable, relevant pages from those that are
less known. There are many derivations of PageRank [24, 16], all of which stem
from modeling ‘websurfing’ (i.e., how people navigate the web) as a Markov
chain. In this analogy, the fraction of random websurfers at a particular web
page is given by the stationary distribution of a Markov chain.

A main challenge for this formulation is that in practice, a network
connecting webpages via their hyperlinks does not usually consist of a single
connected component. Instead, there are isolated webpages that cannot be
navigated to, or navigated from. To address this issue, the Google founders
introduced ‘teleportation’ so that with probability $\alpha$, websurfers click
a hyperlink to move between webpages, and with probability $1-\alpha$,
websurfers randomly jump to webpage $i$ with probability $v_{i}$. Parameter
$\alpha$ is called as _teleportation parameter_ or _damping factor_. In the
original formulation, a walker would jump uniformly at random to another
webpage so that the transition probability to each webpage is the same:
$v_{i}=v_{j}=1/N$, where $N$ is the number of webpages. It is also beneficial
to allow the $v_{i}$ values to be heterogeneous to bias the random websurfing
to remain near a particular set of webpages. Such dynamics is called
‘personalized’ PageRank, and ${\bf v}$ is called the _personalization vector_.

Both PageRank and personalized PageRank can be formulated as a discrete-time
Markov chain in which the transition matrix is given by the Google matrix:

$\displaystyle{\bf G}=\alpha{\bf P}+(1-\alpha){\bf e}{\bf v}^{T},$ (5)

where ${\bf e}$ is a vector of ones and each entry $P_{ij}$ gives the
probability of transitioning from webpage $i$ to webpage $j$ following a
hyperlink. The matrices $P$, ${\bf e}{\bf v}^{T}$ and $G$ are all row-
stochastic transition matrices. The stationary distribution of the Markov
chain with transition matrix ${\bf G}$ is called the PageRank vector
$\pi\in\mathbb{R}^{N}$, which is the limit of the iterative equation

$\displaystyle{\bf x}(t+1)^{T}={\bf x}(t)^{T}{\bf G},$ (6)

for which the fixed point is the solution to the eigenvalue problem ${\bf
G}^{T}\bm{\pi}=\bm{\pi}$.

The PageRank algorithm has contributed toward Google’s rise as a leading
technology company, but it’s worth noting that it has also been applied in a
wide variety of domains beyond web search [14]. In any context, the practical
usage of PageRank comes with various challenges. For example, what $\alpha$
value should be used? The PageRank vector can be integrated with a machine
learning framework for web search [29], used to help fit functions over
directed graphs [41], and can be used to predict missing genes and protein
functions [18, 28]. In these various cases, $\alpha$ must be separately chosen
as appropriate. As in [31], the author suggests choosing $\alpha=0.15$ for
correlated discovery in a multimedia database. Google historically set
$\alpha=0.85$, which often remains as the default choice in the literature.

Figure 7. (A) A social network of interactions among $N=62$ dolphins in New
Zealand. (B) Node colors indicate the nodes’ respective PageRank values. In
both panels, nodes with larger/smaller size have more/fewer connecting edges.

In our paper, we explore a different challenge that arises when considering
how many times to iterate Eq. (6). The iterated values ${\bf x}(t)\to\bm{\pi}$
converge as $t\to\infty$, but a more practical questions involves studying how
many iterations are required for the associated ranks to converge. That is, if
one ranks webpages from top to bottom based on their $\pi_{i}$ values, then
one only needs to iterate Eq. (6) until those ranks converge. Understanding
the asymptotic convergence rate and asymptotic error is not immediately
relevant when considering this practical question, and we propose kNN
persistent homology as a mathematically principled technique to study the
convergence of rankings (and relative orderings more generally).

###  4.2. Ranking nodes in a dolphin social network

In this section, we consider the convergence of the iterative method for
computing PageRank. We will study the convergence of persistence diagrams
associated with converging approximate PageRank values ${\bf
x}(t)\to\bm{\pi}$, comparing the result for kNN filtrations to those of VR
filtrations. We will show that the convergence of persistence diagrams for VR
filtrations closely relates to the convergence in vector norm (i.e., due to
the stability theorem). In contrast, we the convergence of persistence
diagrams for kNN filtrations more closely resembles the convergence of rank
orderings. In other words, convergence of kNN persistent homology can be used
to predict how many iterations are required for ${\bf x}(t)$ to be
sufficiently close to $\bm{\pi}$ such that the ranking of nodes—i.e., from 1
to N—has converged.

Figure 8. Visualization of the approximate PageRank values
$x_{i}(t)\approx\pi_{i}$ for the iterative method with different
$t\in\\{3,6,9,12\\}$. Node colors indicate the $x_{i}(t)$ values. The black
circles around nodes indicate the ranks $R_{i}({\bf x}(t))$ that have already
converged to their limiting rank $R_{i}(\bm{\pi})$. For each node $i$, we
define $t^{*}_{i}$ to be the time step for which $R_{i}({\bf
x}(t))={R}_{i}(\bm{\pi})$ for $t\geq t^{*}$. Observe that most ranks converge
after 12 time steps, even though $||{\bf x}-\bm{\pi}||>0$.

We present our results for an empirical network in which undirected,
unweighted edges encode social interactions among $N=62$ bottlenose dolphins
living near Doubtful Sound in New Zealand [27]. We apply the iterative
PageRank algorithm with teleportation parameter $\alpha=0.85$ to the network
with an initial condition given by $x_{i}(0)=i/(\sum_{j=1}^{N}j)$. In the
Figure 7, we illustrate the dolphin network and indicate the nodes’ converged
PageRank values by node color.

We formally define the converged rank order according to PageRank by

$[R_{i}(\bm{\pi)}]=\phi(-\bm{\pi}),$

where $\phi:\mathbb{R}\to\\{1,\dots,N\\}$ is the ‘argsort’ function. Recall
that the function $\phi$ was previously defined to sort the pairwise distances
in ascending order. By multiplying $\bm{\pi}$ by negative one, we now sort the
$\pi_{i}$ values in descending order so that $R_{i}(\bm{\pi})=1$ for the top-
ranked node $i=\text{argmax}_{j}\pi_{j}$, which is considered to be the most
important dolphin in the social network. Similarly, $R_{i}(\bm{\pi})=N$ for
the lowest-ranked node $i=\text{argmin}_{j}\pi_{j}$, which is the least
important dolphin. ( For each time $t$, we similarly define the approximate
rank orderings

$[R_{i}({\bf x}(t))]=\phi(-{\bf x}(t)).$

We note that the rank orderings satisfy $R_{i}({\bf
x}(t)),{R}_{i}(\bm{\pi})\in\\{1,\dots,N\\}$. Because ${\bf x}(t)\to\bm{\pi}$,
the approximate rank orderings $R_{i}({\bf x}(t))$ converge to their final
rank orderings ${R}_{i}(\bm{\pi})$. Moreover, for each node $i$, the rank
$R_{i}({\bf x}(t))$ can converge to $R_{i}(\bm{\pi})$ at a different time step
$t$. Therefore, we define $t^{*}_{i}$ to be the iteration of rank convergence,
which is the value of $t$ at which $R_{i}({\bf x}(t))={R}_{i}(\bm{\pi})$ for
all $t\geq t^{*}_{i}$.

In Fig. 8, we illustrate the convergence for the approximate PageRank values
$x_{i}(t)\approx\pi_{i}$ for different time steps. That is, for the time steps
$t\in\\{3,6,9,12\\}$, we use node color to indicate the values $x_{i}(t)$.
Moreover, we use black circles to indicate which nodes have already obtained
their limiting rank, i.e., $R_{i}({\bf x}(t))={R(\bm{\pi})}_{i}$ for $t\geq
t^{*}_{i}$. Most ranks converge after 12 time steps.

Figure 9. (left) Convergence of nodes’ rank orderings $R_{i}({\bf
x}(t))\to{R}_{i}(\bm{\pi})$ versus time step $t$. (right) Scatter plot
comparing $t^{*}_{i}$ and $\pi_{i}$ across the nodes $i$.

In Fig. 9, we further study the convergence of the rank orderings $R_{i}({\bf
x}(t))\to{R}_{i}(\bm{\pi})$ for the dolphin network. In Fig. 9(left), observe
that the $R_{i}({\bf x}(t))$ values change up until a time step $t^{*}_{i}$,
which is potentially different for each node $i$. In Fig. 9(left), we depict a
scatter plot comparing $t^{*}_{i}$ and $\pi_{i}$, noting that we do not see
any strong correlation. From a practical perspective, one is often most
interested in the top-ranked nodes, and so one is primarily interested in how
many iterations are required for the top-ranks to converge. However, there is
no guarantee that the top-rank nodes converge before the lower-ranked ones do,
or vice versa.

We now study the convergence of persistence diagrams for the converging
$x_{i}(t)\to\pi_{i}$ values, comparing persistence diagrams resulting from kNN
filtrations to those of VR filtrations. More precisely, we define $D_{VR}({\bf
x})$ and $D_{kNN}({\bf x})$ to be the persistence diagrams according to VR and
kNN filtrations, respectively. We will also study kNN filtrations with two
types of symmetrization for k-nearest neighbor sets: the minimum and maximum
approaches. Given the persistence diagrams for $\bm{\pi}$ and ${\bf x}(t)$, we
study homological convergence through the bottleneck distance, e.g.,
$d(D_{VR}({\bf x}(t))-D_{VR}(\bm{\pi}))$.

In Fig. 10, we illustrate the convergence of persistence diagrams for (left)
VR filtrations and (right) kNN filtrations. We compare these two converging
topological spaces, respectively, with the normed approximation error, $||{\bf
x}(t)-\bm{\pi}||$, and the total difference in rank orderings,
$\sum_{i}|{R}_{i}(\bm{\pi})-R_{i}({\bf x}(t))|$. Observe in Fig. 10(left) that
VR persistent homology converges similarly to $||{\bf x}(t)-\bm{\pi}||$,
whereas kNN persistent homology converges similarly to
$\sum_{i}|{R}_{i}(\bm{\pi})-R_{i}({\bf x}(t))|$. That is, kNN topological
convergence can be used as a proxy to estimate the number of iterations
required for the rank orderings to converge to exactly their final values.

Figure 10. Homological convergence of an iterative algorithm for PageRank for
the dolphin social network. (left) Convergence of persistent homology for VR
filtrations coincides with a geometrical notion of convergence $||{\bf
x}(t)-\bm{\pi}||\to 0$ due to the stability theorem. Both asymptotically
approach 0 with exponential decay. (right) In contrast, convergence of
persistent homology for kNN filtrations more closely resembles the convergence
of the rank ordering, which exactly converges after $t=14$ time steps in this
case. Observe the kNN persistence diagrams for the max and min methods of
symmetrization for kNN sets converge at around the same number of iterations.

###  4.3. U-local convergence of dolphin social network

Before concluding, we further study the homological convergence of PageRank
for the dolphin network, except we now focus on our notion of
$\mathcal{U}$-local topological convergence, which we presented in Sec. 3.3.3.
In this context, we focus on convergence for a subset
$\mathcal{U}\subset\mathcal{V}$ of the nodes, and we will consider two
subsets: a randomly selected set of nodes—$\mathcal{U}_{1}=\\{$Ripplefluke,
Zig, Feather, Gallatin, SN90, DN16, Wave, DN21, Web, Upbang$\\}$ and
$\mathcal{U}_{2}$ is the set of 10 nodes that have the top PageRank values.
Note that we still compute the iterative approximation to PageRank in the
usual way, except that we only consider the values $\pi_{i}$ and $x_{i}(t)$
for which $i\in\mathcal{U}$.

Figure 11. $\mathcal{U}$-local topological convergence for the following
subset of nodes: $\mathcal{U}_{1}=\\{$Ripplefluke, Zig, Feather, Gallatin,
SN90, DN16, Wave, DN21, Web, Upbang$\\}$ . Similar to Fig. 10, the left and
right panels depict convergence of persistence diagrams for VR and kNN
filtrations, respectively.  Figure 12. Same information as in Fig. 11, except
we consider the subset $\mathcal{U}_{1}$ of nodes that have the largest
PageRank values.

In Fig. 11(left) and (right), we depict convergence of VR and kNN persistence
homology, respectively for the subset of nodes $\mathcal{U}_{1}$. Observer
that convergence for VR persistent homology is similar to that for the full
system. In contrast, observe in Fig. 11(right) that the kNN homology and rank
orderings converge after approximately $t=5$ iterations for this subset.

In Fig. 12, we depict the same information, except that we now consider the
subset $\mathcal{U}_{2}$ of nodes with top PageRank values. In this case, the
VR convergence more closely aligns with $||{\bf x}(t)-\bm{\pi}||$ than when we
considered the full set $\mathcal{V}$ of nodes or the subset
$\mathcal{U}_{1}$. Moreover, the kNN homology and the rank orderings converge
after approximately $t=9$ iterations in this case.

##  5\. Discussion

In this paper, we developed an approach for topological data analysis (TDA)
that utilizes k-nearest neighbor sets to define kNN complexes, kNN
filtrations, and kNN persistent homology. Our approach was developed in the
spirit of discrete topology and by examining the relative ordering of points,
as opposed to the precise distances between points. Although kNN orderings are
related to pairwise distances, we provided theory and many experiments
highlighting important differences between persistent homology that is based
on kNN filtrations versus Vietoris-Rips (VR) filtrations.

To gain theoretical insights into kNN-based TDA, we investigated stability
properties for the resulting persistence diagrams in Sec. 3.3.2 and
convergence properties in Sec. 3.3.3. While persistence diagrams resulting
from kNN filtrations do not satisfy a stability theorem involving a universal
bound on perturbed point sets (see Theorem 3.11), we identified and
characterized different notions of stability and convergence by identifying
equivalence classes as well as bounds on the bottleneck distance between
persistence diagrams for kNN homology that are based on the maximum difference
for a kNN ordering. Our formulation of convergence also led to several types
including global convergence, $\kappa$-bounded convergence and
$\mathcal{U}$-local convergence. Moreover, we identified some relations among
these types as in Theorem 3.16 and Theorem 3.17.

As a concrete application, we applied persistent homology to study the
topological convergence of an iterative method for solving PageRank. We showed
that the convergence of persistence diagrams for VR filtrations closely
relates to the convergence in vector norm (i.e., due to the stability
theorem). In contrast, the convergence of persistence diagrams for kNN
filtrations more closely resembles the convergence of rank ordering. In other
words, convergence of kNN persistent homology can be used to predict how many
iterations are required for ${\bf x}(t)$ to be sufficiently close to
$\bm{\pi}$ such that the ranking of nodes—i.e., from 1 to N—has converged.
Although we have focused on the PageRank algorithm, iterative algorithms for
solving systems (e.g., root finding) are some of the most widely used
numerical algorithms. We have shown that the existing TDA approach of VR
filtrations coincides with geometrical (i.e., normed) convergence and thereby
provides one perspective for the convergence of numerical algorithms. In
contrast, kNN filtrations provide complementary insights from the perspective
of a discrete topological space that is associated with the relative
positioning of points. As such, we expect kNN complexes, filtrations, and
persistent homology to have many applications for converging numerical
algorithms beyond PageRank.

## Acknowledgments

M.Q.L. and D.T. were supported in part by the Simons Foundation (Grant No.
578333). D.T also acknowledges the National Science Foundation (Grants No.
DMS-2052720 and No. EDT-1551069).

## References

  * [1] Mehmet E Aktas, Esra Akbas, and Ahmed El Fatmaoui.  Persistence homology of networks: methods and applications.  Applied Network Science, 4(1):61, 2019.
  * [2] Dominique Attali, André Lieutier, and David Salinas.  Vietoris–rips complexes also provide topologically correct reconstructions of sampled shapes.  Computational Geometry, 46(4):448–465, 2013.
  * [3] Sergey Brin and Lawrence Page.  The anatomy of a large-scale hypertextual web search engine.  Computer networks and ISDN systems, 30(1-7):107–117, 1998.
  * [4] Peter Bubenik.  Statistical topological data analysis using persistence landscapes.  The Journal of Machine Learning Research, 16(1):77–102, 2015.
  * [5] Anuraag Bukkuri, Noemi Andor, and Isabel K Darcy.  Applications of topological data analysis in oncology.  Frontiers in Artificial Intelligence, 4:38, 2021.
  * [6] Gunnar Carlsson.  Topology and data.  Bulletin of the American Mathematical Society, 46(2):255–308, 2009\.
  * [7] Samir Chowdhury and Facundo Mémoli.  A functorial dowker theorem and persistent homology of asymmetric networks.  Journal of Applied and Computational Topology, 2(1):115–175, 2018\.
  * [8] Moo K Chung, Peter Bubenik, and Peter T Kim.  Persistence diagrams of cortical surface data.  In International Conference on Information Processing in Medical Imaging, pages 386–397. Springer, 2009.
  * [9] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer.  Stability of persistence diagrams.  Discrete & Computational Geometry, 37(1):103–120, 2007.
  * [10] Herbert Edelsbrunner and John Harer.  Persistent homology-a survey.  Contemporary mathematics, 453:257–282, 2008.
  * [11] Herbert Edelsbrunner and Nimish R Shah.  Triangulating topological spaces.  International Journal of Computational Geometry & Applications, 7(04):365–378, 1997.
  * [12] Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier.  The relationship between the intrinsic cech and persistence distortion distances for metric graphs.  arXiv preprint arXiv:1812.05282, 2018.
  * [13] Chad Giusti, Eva Pastalkova, Carina Curto, and Vladimir Itskov.  Clique topology reveals intrinsic geometric structure in neural correlations.  Proceedings of the National Academy of Sciences, 112(44):13455–13460, 2015.
  * [14] David F Gleich.  Pagerank beyond the web.  siam REVIEW, 57(3):321–363, 2015.
  * [15] Mark Goresky and Robert MacPherson.  Stratified morse theory.  In Stratified Morse Theory, pages 3–22. Springer, 1988.
  * [16] Desmond J Higham.  Google pagerank as mean playing time for pinball on the reverse web.  Applied Mathematics Letters, 18(12):1359–1362, 2005.
  * [17] Weiyu Huang and Alejandro Ribeiro.  Persistent homology lower bounds on high-order network distances.  IEEE Transactions on Signal Processing, 65(2):319–334, 2016.
  * [18] Takashi Ichinomiya, Ippei Obayashi, and Yasuaki Hiraoka.  Protein-folding analysis using features obtained by persistent homology.  Biophysical Journal, 118(12):2926–2937, 2020.
  * [19] Peter M Kasson, Afra Zomorodian, Sanghyun Park, Nina Singhal, Leonidas J Guibas, and Vijay S Pande.  Persistent voids: a new structural metric for membrane fusion.  Bioinformatics, 23(14):1753–1759, 2007.
  * [20] Jisu Kim, Jaehyeok Shin, Frédéric Chazal, Alessandro Rinaldo, and Larry Wasserman.  Homotopy reconstruction via the cech complex and the vietoris-rips complex.  arXiv preprint arXiv:1903.06955, 2019.
  * [21] L Kondic, A Goullet, CS O’Hern, M Kramar, Konstantin Mischaikow, and RP Behringer.  Topology of force networks in compressed granular media.  EPL (Europhysics Letters), 97(5):54001, 2012.
  * [22] M Kramar, Arnaud Goullet, Lou Kondic, and Konstantin Mischaikow.  Persistence of force networks in compressed granular media.  Physical Review E, 87(4):042207, 2013.
  * [23] Genki Kusano, Yasuaki Hiraoka, and Kenji Fukumizu.  Persistence weighted gaussian kernel for topological data analysis.  In International Conference on Machine Learning, pages 2004–2013. PMLR, 2016.
  * [24] Amy N Langville and Carl D Meyer.  Updating markov chains with an eye on google’s pagerank.  SIAM journal on matrix analysis and applications, 27(4):968–987, 2006.
  * [25] Minh Quang Le and Dane Taylor.  Persistent homology of convection cycles in network flows.  Physical Review E, 105:044311, 2021.
  * [26] Jie Liang, Herbert Edelsbrunner, Ping Fu, Pamidighantam V Sudhakar, and Shankar Subramaniam.  Analytical shape computation of macromolecules: I. molecular area and volume through alpha shape.  Proteins: Structure, Function, and Bioinformatics, 33(1):1–17, 1998\.
  * [27] David Lusseau, Karsten Schneider, Oliver J Boisseau, Patti Haase, Elisabeth Slooten, and Steve M Dawson.  The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations.  Behavioral Ecology and Sociobiology, 54(4):396–405, 2003.
  * [28] Julie L Morrison, Rainer Breitling, Desmond J Higham, and David R Gilbert.  Generank: using search engine technology for the analysis of microarray experiments.  BMC bioinformatics, 6(1):1–14, 2005.
  * [29] Marc A Najork, Hugo Zaragoza, and Michael J Taylor.  Hits on the web: How does it compare?  In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 471–478, 2007.
  * [30] Jessica L Nielson, Shelly R Cooper, John K Yue, Marco D Sorani, Tomoo Inoue, Esther L Yuh, Pratik Mukherjee, Tanya C Petrossian, Jesse Paquette, Pek Y Lum, et al.  Uncovering precision phenotype-biomarker associations in traumatic brain injury using topological data analysis.  PloS one, 12(3):e0169490, 2017.
  * [31] Jia-Yu Pan, Hyung-Jeong Yang, Christos Faloutsos, and Pinar Duygulu.  Automatic multimedia cross-modal correlation discovery.  In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 653–658, 2004.
  * [32] Jose A Perea and John Harer.  Sliding windows and persistence: An application of topological methods to signal analysis.  Foundations of Computational Mathematics, 15(3):799–838, 2015.
  * [33] Giovanni Petri, Paul Expert, Federico Turkheimer, Robin Carhart-Harris, David Nutt, Peter J Hellyer, and Francesco Vaccarino.  Homological scaffolds of brain functional networks.  Journal of The Royal Society Interface, 11(101):20140873, 2014.
  * [34] Bastian Rieck, Ulderico Fugacci, Jonas Lukasczyk, and Heike Leitte.  Clique community persistence: A topological visual analysis approach for complex networks.  IEEE transactions on visualization and computer graphics, 24(1):822–831, 2017.
  * [35] Matteo Rucco, Lorenzo Falsetti, Damir Herman, Tanya Petrossian, Emanuela Merelli, Cinzia Nitti, and Aldo Salvi.  Using topological data analysis for diagnosis pulmonary embolism.  arXiv preprint arXiv:1409.5020, 2014.
  * [36] Michael T Schaub, Austin R Benson, Paul Horn, Gabor Lippner, and Ali Jadbabaie.  Random walks on simplicial complexes and the normalized hodge laplacian.  arXiv preprint arXiv:1807.05044, 2018.
  * [37] Thierry Sousbie.  The persistent cosmic web and its filamentary structure–i. theory and implementation.  Monthly Notices of the Royal Astronomical Society, 414(1):350–383, 2011.
  * [38] Dane Taylor, Florian Klimm, Heather A Harrington, Miroslav Kramár, Konstantin Mischaikow, Mason A Porter, and Peter J Mucha.  Topological data analysis of contagion maps for examining spreading processes on networks.  Nature communications, 6:7723, 2015.
  * [39] KAIRUI GLEN Wang.  The basic theory of persistent homology, 2012.
  * [40] Rien van de Weygaert, Gert Vegter, Herbert Edelsbrunner, Bernard JT Jones, Pratyush Pranav, Changbom Park, Wojciech A Hellwing, Bob Eldering, Nico Kruithof, EGP Bos, et al.  Alpha, betti and the megaparsec universe: on the topology of the cosmic web.  In Transactions on computational science XIV, pages 60–101. Springer, 2011.
  * [41] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf.  Learning from labeled and unlabeled data on a directed graph.  In Proceedings of the 22nd international conference on Machine learning, pages 1036–1043, 2005.
  * [42] Afra Zomorodian.  Fast construction of the vietoris-rips complex.  Computers & Graphics, 34(3):263–271, 2010.
  * [43] Afra Zomorodian and Gunnar Carlsson.  Computing persistent homology.  Discrete & Computational Geometry, 33(2):249–274, 2005.

Received xxxx 20xx; revised xxxx 20xx; early access xxxx 20xx.