# Smart Vectorizations for Single and Multiparameter Persistence

Baris Coskunuzer<EMAIL_ADDRESS>
Mathematical Sciences, University of Texas at Dallas, USA Cuneyt Gurcan Akcora
<EMAIL_ADDRESS>
Computer Science, University of Manitoba, Canada Zhiwei Zhen
<EMAIL_ADDRESS>
Mathematical Sciences, University of Texas at Dallas, USA Ignacio Segovia
Dominguez<EMAIL_ADDRESS>
Mathematical Sciences, University of Texas at Dallas, USA Murat Kantarcioglu
<EMAIL_ADDRESS>
Computer Science, University of Texas at Dallas, USA Yulia R. Gel
<EMAIL_ADDRESS>
Mathematical Sciences, University of Texas at Dallas, USA

###### Abstract

The machinery of topological data analysis becomes increasingly popular in a
broad range of machine learning tasks, ranging from anomaly detection and
manifold learning to graph classification. Persistent homology is one of the
key approaches here, allowing us to systematically assess the evolution of
various hidden patterns in the data as we vary a scale parameter. The
extracted patterns, or homological features, along with information on how
long such features persist throughout the considered filtration of a scale
parameter, convey a critical insight into salient data characteristics and
data organization.

In this work, we introduce two new and easily interpretable topological
summaries for single and multi-parameter persistence, namely, saw functions
and multi-persistence grid functions, respectively. Compared to the existing
topological summaries which tend to assess the numbers of topological features
and/or their lifespans at a given filtration step, our proposed saw and multi-
persistence grid functions allow us to explicitly account for essential
complementary information such as the numbers of births and deaths at each
filtration step.

These new topological summaries can be regarded as the complexity measures of
the evolving subspaces determined by the filtration and are of particular
utility for applications of persistent homology on graphs. We derive
theoretical guarantees on the stability of the new saw and multi-persistence
grid functions and illustrate their applicability for graph classification
tasks.

##  1 Introduction

Topological data analysis (TDA) has been recently applied to many different
domains ranging from cryptocurrency transaction analysis to anomaly detection.
Persistent homology-based approaches emerged as one of the key TDA techniques
that allow systematical assessment of the evolution of various hidden patterns
in the data as a function of a scale parameter. The extracted patterns, or
homological features, along with information on how long such features persist
throughout the considered filtration of a scale parameter, convey a critical
insight into underlying data properties. In the past, such homological
features have been successfully used as an input to various machine learning
tasks to enable efficient and accurate models that are robust to noise in the
data sets.

In this work, we provide new and easily interpretable topological summaries
for single and multi-parameter persistence, namely, saw functions and multi-
persistence grid functions (MPGFs). Compared to the existing topological
summaries which tend to assess the numbers of topological features and/or
their lifespans at a given filtration step, our proposed saw functions allow
us to extract additional information that captures the numbers of births and
deaths at each filtration step. On the other hand, MPGFs are one of the first
topological summaries in the Multi-Persistence case which needs no slicing. In
our empirical evaluations, we show that these summaries are useful in building
efficient and accurate graph classification models.

One important contribution of our work is to leverage these interpretable
features to build accurate graph classification models even with limited
training data. This is important because existing work on graph convolutional
networks (GCNs) for graph classification require large amounts of data and
expensive training process without providing any insights into why certain
classification result is provided. Compared to GCN-based approaches, the
proposed single and multi-parameter persistence features provide insights into
changes in the underlying sets or graphs as the scale parameter varies and
enables the building of an efficient machine learning model using these
extracted features. Especially for the application domain where the size of
the data set is limited, building machine learning models such as random
forests using the topological summaries for single and multi-parameter
persistence result in prediction accuracy close to best GCN models while
providing insights into why certain features are useful.

Contributions of our paper can be summarized as follows:

  * •

We introduce two new topological summaries for single- and multi-persistence:
Saw functions and Multi-persistence Grid Functions (MPGFs). The new summaries
are interpretable as complexity measure of the space and, contrary to the
existing descriptors, contain such salient complementary information on the
underlying data structure as the numbers of births and deaths of topological
features at each filtration step.

  * •

We prove theoretical stability of the new topological summaries. Our MPGF is
one of the first successful and provably stable vectorizations of multi-
parameter persistence without slicing. The theory of multi-parameter
persistence suffers from many technical difficulties to define persistence
diagrams in general settings. Our MPGFs bypass these problems by going
directly to the subspaces defined, and deliver 2D descriptors.

  * •

The proposed new topological summaries are computationally simple and
tractable. Our MPGF takes a few minutes for most datasets, but on average
provides results that differ as little as 3.53% from popular graph neural
network solutions.

  * •

To the best of our knowledge, this is the first paper bringing the machinery
of multi-persistence to graph learning. We discuss the utility and limitations
of multi-persistence for graph studies.

##  2 Related Work

Topological Summaries: While constructing the right filtration for a given
space $X$ is quite important, the vectorization and topological summaries of
the information produced in persistent homology are crucial to obtain the
desired results. This is because the summary should be suitable for ML tools
to be used in the problem so that the produced topological information can
address the question effectively. However, the produced persistent diagrams
(PDs) are a multi-set that does not live in a Hilbert space and, hence, cannot
be directly inputted into an ML model. In that respect, there are several
approaches to solve this issue where they can be considered in two categories.
The first one is called vectorization (Di Fabio and Ferri, 2015; Bubenik,
2015; Adams et al., 2017) which embeds PDs into $\mathbb{R}^{d}$, and the
second one is called kernelization (Kusano et al., 2016; Le and Yamada, 2018;
Zieliński et al., 2019; Zhao and Wang, 2019) which is to induce kernel Hilbert
spaces by using PDs. Both approaches enjoy certain stability guarantees and
some of their key parameters are learnable. However, the resulting performance
of such topological summaries as classifiers is often highly sensitive to the
choice of the fine-tuned kernel and transformation parameters. In this paper,
we find a middle way where our topological summaries both keep most of the
information produced in PDs and do not need fine calibration.

In (Chung and Lawson, 2019), the authors bring together the class of
vectorizations which are single variable functions in the domain of thresholds
in a nice way and call them Persistence curves. Here, the infrastructure is
very general, and most of the current vectorization can be interpreted under
this umbrella. In particular, Betti functions, life span, persistence
landspaces, Betti entropy, and several other summaries can be interpreted in
this class. Another similar infrastructure to describe the topological
summaries of persistent homology especially in graph case is PersLay (Carrière
et al., 2020). In this work, the authors define a general framework for
vectorizations of persistent diagrams, which can be used as a neural network
layer. The vectorizations in this class are very general and suitable to
include kernels in construction.

TDA for graph classification: Recently, TDA methods have been successfully
applied to the graph classification tasks often in combination with DL and
learnable kernelization of PDs (Hofer et al., 2017; Togninalli et al., 2019;
Rieck et al., 2019; Le and Yamada, 2018; Zhao and Wang, 2019; Hofer et al.,
2019; Kyriakis et al., 2021). Furthermore, as mentioned above, Carrière et al.
(2020) unified several current approaches to PD representations to obtain the
most suitable topological summary with a learnable set of parameters, under an
umbrella infrastructure. Finally, most recently, Cai and Wang (2020) obtained
successful results by combining filtrations with different vectorization
methods.

##  3 Background

In this section, we provide a brief introduction to persistent homology.
Homology $H_{k}(X)$ is an essential invariant in algebraic topology, which
captures the information of the $k$-dimensional holes (connected components,
loops, cavities) in the topological space $X$. Persistent homology is a way to
use this important invariant to keep track of the changes in a controlled
topological space sequence induced by the original space $X$. For basic
background on persistence homology, see (Edelsbrunner and Harer, 2010;
Zomorodian and Carlsson, 2005).

###  3.1 Persistent Homology

For a given metric space $X$, consider a continuous function
$f:X\to\mathbf{R}$. Define $X_{\alpha}=\\{x\in X\mid f(x)\leq\alpha\\}$ as the
$\alpha$-sublevel set of $X$. Choose $\\{\alpha_{i}\\}$ as an increasing
sequence of numbers with $\alpha_{0}=\min f$ to $\alpha_{N}=\max f$. Then,
$\\{X_{\alpha_{i}}\\}$ gives an exhaustion of the space $X$, i.e.
$X_{\alpha_{0}}\subset X_{\alpha_{1}}\subset...\subset X_{\alpha_{N}}=X$. By
using $X_{\alpha_{i}}$ itself, or inducing natural topological spaces
$\widehat{X}_{\alpha_{i}}$ (e.g. VR-complexes), one obtains a sequence of
topological spaces
$\widehat{X}_{\alpha_{0}}\subset\widehat{X}_{\alpha_{1}}\subset\ldots\widehat{X}_{\alpha_{i}}$
which is called a filtration induced by $f$. For each $i$, one can compute the
$k^{th}$ homology group $H_{k}(\widehat{X}_{\alpha_{i}})$ which describes the
$k^{th}$ dimensional holes in $\widehat{X}_{\alpha_{i}}$. The rank of the
homology group $H_{k}(\widehat{X}_{\alpha_{i}})$ is called the Betti number
$\mathcal{B}_{k}(\alpha_{i})$ which is basically number of $k$-dimensional
holes in the space $\widehat{X}_{\alpha_{i}}$.

By using persistent homology, we keep track of the topological changes in the
sequence $\\{\widehat{X}_{\alpha_{i}}\\}$ as follows. When a topological
feature $\sigma$ (connected component, loop, cavities) appears in
$H_{k}(\widehat{X}_{\alpha_{i}})$, we mark $b_{\sigma}=\alpha_{i}$ as its
birth time. The rank of $H_{k}(\widehat{X}_{\alpha_{i}})$ is called Betti
number. The feature $\sigma$ can disappear at a later time
$H_{k}(\widehat{X}_{\alpha_{j}})$ by merging with another feature or by being
filled in. Then, we mark $d_{\sigma}=\alpha_{j}$ as its death time. We say
$\sigma$ persists along $[b_{\sigma},d_{\sigma})$. The longer the length
($d_{\sigma}-b_{\sigma}$) of the interval, the more persistent the feature
$\sigma$ is (Adams and Coskunuzer, 2021). A multi-set
$PD_{k}(X,f)=\\{(b_{\sigma},d_{\sigma})\mid\sigma\in
H_{k}(\widehat{X}_{\alpha_{i}})\\}$ is called persistence diagram of $(X,f)$
which is the collection of $2$-tuples marking birth and death times of
$k$-dimensional holes $\\{\sigma\\}$ in $\widehat{X}_{\alpha_{i}}$. Similarly,
we call the collection of the intervals $\\{[b_{\sigma},d_{\sigma})\\}$ the
barcodes of $(X,f)$, which store the same information with the persistence
diagrams.

Even though the constructions are very similar, depending on the initial space
$X$, and the filter function $f$, the interpretation and the meaning of the
topological changes recorded by the persistent homology for $(X,f)$ might be
different. For example, when the initial space $X$ is a point cloud, and
$f(p)=d(p,X)$ is the distance function in the ambient space, this sublevel
construction coarsely captures the shape of the point cloud as follows: The
sublevel sets $f(p)=d(p,X)\leq\epsilon$ gives a union of $\epsilon$-balls
$\bigcup_{x\in X}N_{\epsilon}(x)$, and it naturally induces relevant complexes
(Vietoris-Rips, Cech, Clique) to capture the coarse geometry of the set. In
this case, by the celebrated Nerve Theorem, we observe that persistence
homology and our filtration captures the shape of the underlying manifold
structure of the point cloud (Edelsbrunner and Harer, 2010).

On the other hand, when we use a graph $G$ as our initial space $X$, and $f$
as a suitable filter function on $G$ (e.g. degree), the sublevel filtration
gives a sequence of subgraphs (or complexes induced by them). In particular,
the filter function $f$ positions the nodes in a suitable direction and
determines the direction for the evolution of these subgraphs. In this sense,
the filter function is highly dominant to govern the behavior of the
filtration, and outcome persistent homology. Hence, one can express that these
outputs not only describe the topological space $X$’s features (or shape) but
also the behavior of the filter function $f$ on $X$. While in the point cloud
case, the persistent homology can be said that it captures the shape of the
point cloud coarsely, in the graph case, the meaning of the outputs of the
persistent homology is highly different. In the following section, we discuss
the interpretation of the persistent homology induced by these different
filter functions as measuring the topological complexity of these subspaces.

While the persistence homology originated with a single filter function, one
can generalize the filtration idea to several functions. In particular, single
parameter filtration can be viewed as chopping off the manifold into slices
and bringing these slices together in an ordered fashion. For topologists,
this is the Morse Theoretic point of view to analyze a given space $X$ by
using a filter function (Morse function) $f$ (Mischaikow and Nanda, 2013).
This approach can naturally be adapted to several filter functions. By slicing
up space with more than one filter function at the same time, we can get a
much finer look at the topological changes in the space in different filtering
directions. This is called Multiparameter Persistence. By construction,
multiparameter persistence gives more refined information on the topological
space, and the theory has been growing rapidly in the past few years (Carrière
and Blumberg, 2020; Vipond, 2020; Harrington et al., 2019).

As a simple example for the construction of multiparameter persistence,
consider two filter functions $f,g:X\to\mathbf{R}$ on the space $X$. Let
$\mathcal{I}=(\alpha_{i},\beta_{j})$ be the partially ordered index set where
$(\alpha_{i},\beta_{j})\leq(\alpha_{i^{\prime}},\beta_{j^{\prime}})$ if
$\alpha_{i}\leq\alpha_{i^{\prime}}$ and $\beta_{j}\leq\beta_{j^{\prime}}$.
Then, define $X_{ij}=\\{x\in X\mid f(x)\leq\alpha_{i}\mbox{ and
}g(x)\leq\beta_{j}\\}$. Similarly, for each fixed $i_{o}$, we get a single
parameter filtration
$\widehat{X}_{i_{o}1}\subset\widehat{X}_{i_{o}2}\subset...\subset\widehat{X}_{i_{o}m_{2}}$
where $\widehat{X}_{ij}$ is the complex induced by $X_{ij}$. Multiparameter
persistence enables one to look at the space from more than one direction, and
to detect topological changes with respect to more than one filter function at
the same time. The advantage of multiparameter persistence over doing single
parameter persistence multiple times is that it gives a finer filtration to
understand the space, and one can further detect the interrelation between the
filtering functions.

###  3.2 Interpretation of Persistent Homology as Complexity Measure

In the previous section, we discussed that the interpretation of persistent
homology output highly depends on the filter function $f:X\to\mathbf{R}$. When
$f(p)=d(p,X)$ is the distance function to space $X$, persistent homology
captures the coarse shape of the point cloud given in ambient space. This
point cloud mostly comes from a dataset embedded in a feature space. Then
persistent homology gives information on patterns, topological features of the
manifold structure where the dataset lies. Therefore, this output gives
crucial information on the data and enables one to see the hidden patterns in
it.

Even though in the origins of the persistent homology, the filtration
constructed was induced by the distance function described above, the
technique to construct persistent homology allows using a different type of
filter functions. When we choose a different filter function on the space, we
get a completely different filtration, and naturally, the persistent homology
output completely changes. Over the years, the technique of persistent
homology highly developed, and generalized in many different settings.
Depending on the question at hand, one applies suitable filter functions to
space and gets a filtration to find the features and patterns detected by the
topological tools.

For example, when the filter function $f:X\to\mathbf{R}$ is coming from a
qualitative property of the set $X$, we can interpret the persistent homology
output as the records of “complexity changes” in the space with respect to
this filter function. This is because, in this setting, the persistent
homology keeps track of the topological changes in the sequence of subspaces
$\\{\widehat{X}_{\alpha}\\}$ determined by the filter function. As $\alpha$
evolves, the topological complexity of $X_{\alpha}$ changes. One can describe
topological complexity as the number of components, loops, cavities at a given
threshold level $\alpha$. In this setting, birth and death times of
topological features are not determined by the position of the points in $X$
with respect to each other, but they are determined by the filter function.
This new persistent homology output does not solely depend on the space $X$,
but mostly depends on the filter function $f$. Hence, one can also interpret
the persistent homology as valuable information on the behavior of the filter
function $f$ on $X$.

For instance, when $X$ is a graph $G$, and $f$ is the degree function on the
vertices of $G$, then the persistent homology first describes the topological
changes in the subgraphs generated by low degree nodes, and then evolves
toward subgraphs with high degree places. The persistent homology output is
the information on how the complexity changes in the filtration while the
degree function increases.

With the motivation of this interpretation of persistent homology, we present
two novel topological summaries capturing the “complexity changes” notion
described above very well as easily interpretable single variable and multi-
variable functions.

##  4 Novel Topological Summaries: Saw Functions

In the following, we interpret persistent homology as a tool to keep track of
the topological complexity changes in $X$ with respect to filter
$f:X\to\mathbf{R}$, and propose two new topological summaries. We define our
first topological summary, the Saw Function, for the single parameter case.

###  4.1 Saw Functions

Saw Function counts the existing live topological features in the intervals
$(\alpha_{i},\alpha_{i+1}]$ similar to the Betti functions (Edelsbrunner and
Harer, 2010). The advantage of Saw Functions is that they remedy the loss of
several essential information when vectorizing persistent diagrams.

When passing from persistent diagrams to Betti functions, one loses most of
the information on birth and death times as it only counts the number of live
features at time $\alpha_{i}$. The death/birth information for the whole
interval $(\alpha_{i},\alpha_{i+1})$ is lost during this transition. With Saw
Functions, we capture this information by keeping the number of deaths and
births in the interval $(\alpha_{i},\alpha_{i+1})$ in a natural way.

Throughout the construction, we use sublevel filtration as above, but the same
construction can be easily adapted to superlevel, or similar filtrations.
Given $(X,f)$ and $\mathcal{I}=\\{\alpha_{i}\\}$, let
$\\{\widehat{X}_{\alpha_{i}}\\}$ be the sublevel filtration as described in
Section 3.1, i.e.
$\widehat{X}_{\alpha_{0}}\subset\widehat{X}_{\alpha_{1}}\subset..\subset\widehat{X}_{\alpha_{N}}$.

Now, let $\mathcal{B}_{k}(\alpha_{i})$ be the $k^{th}$ Betti number of
$\widehat{X}_{\alpha_{i}}$. This defines a function
$\mathcal{B}_{k}:[\alpha_{0},\infty)\to\mathbf{N}$ called $k^{th}$ Betti
function of the filtration $(X,f,\mathcal{I})$ as follows:
$\mathcal{B}_{k}(t)=\mathcal{B}_{k}(\alpha_{j})$ where $\alpha_{j}$ is the
largest number in $\mathcal{I}$ with $\alpha_{j}\leq t$. By definition,
$\mathcal{B}_{k}$ is a piecewise constant function which only changes values
at $\mathcal{I}$. See black function in Figure 1.

Let $PD_{k}(X)$ be the persistence diagram of $(X,f)$ at $k^{th}$ level. Here,
we give the construction of Saw Function $\mathcal{S}_{0}(t)$ for $k=0$.
Higher levels will be similar.

Let $PD_{0}(X)=\\{(b_{j},d_{j})\\}$ where $b_{j},d_{j}$ represent the birth
and death of $j^{th}$ component in the filtration. Notice that
$b_{j},d_{j}\in\mathcal{I}=\\{\alpha_{i}\\}$ for any $j$. Let
$\mathbf{b}(\alpha_{i})=\sharp\\{b_{j}=\alpha_{i}\\}$ and
$\mathbf{d}(\alpha_{i})=\sharp\\{d_{j}=\alpha_{i}\\}$, i.e.
$\mathbf{b}(\alpha_{i})$ is the number of births at
$t\in(\alpha_{i-1},\alpha_{i}]$, and $\mathbf{d}(\alpha_{i})$ is the number of
deaths at $t\in(\alpha_{i-1},\alpha_{i}]$. The regular Betti functions only
capture the information
$\mathbf{b}(\alpha_{i})-\mathbf{d}(\alpha_{i})=\mathcal{B}_{k}(\alpha_{i})-\mathcal{B}_{k}(\alpha_{i-1})$.
With Saw Functions, we keep the number of births and deaths in the intervals
$(\alpha_{i-1},\alpha_{i}]$, and embed it naturally in the function as
follows.

When defining Saw Functions, we define a simple generator function for each
point $(b_{j},d_{j})\in PD_{0}(X)$. Let $\chi_{j}=\chi(I_{j})$ be the
characteristic function for half closed interval $I_{j}=[b_{j},d_{j})$, i.e.
$\chi_{j}(t)=1$ for $t\in I_{j}$, and $\chi_{j}(t)=0$ otherwise. Notice that
$\mathcal{B}_{0}(t)=\sum_{j}\chi_{j}$ by construction.

To include the counting of birth and death times information in the function,
we modify $\chi_{j}$. In general, for a given filtration $(X,f,\mathcal{I})$,
we choose a suitable lag parameter as follows:

Assuming the thresholds $\\{\alpha_{i}\\}$ are somewhat evenly distributed as
in generic case, we let
$\lambda\sim\frac{1}{4}\mbox{average}(\\{|\alpha_{i+1}-\alpha_{i}|\\})$. The
reason for the coefficient $1/4$, and how to choose $\lambda$ in general case
is explained in Remark 4.1. For simplicity, we assume our thresholds are
integer valued with $\alpha_{i+1}-\alpha_{i}=1$. One can think of $X$ is a
graph $G$, and $f$ is the degree, or eccentricity functions on the vertices of
$G$. For this case, set $\lambda=1/4$. Then, modify $\chi_{j}$ as follows.

$\widehat{\chi}_{j}(t)=\left\\{\begin{array}[]{cc}4(t-b_{j})&t\in[b_{j},b_{j}+\frac{1}{4}]\\\
4(t-d_{j})&t\in[d_{j}-\frac{1}{4},d_{j}]\\\
\chi_{j}(t)&\mbox{otherwise}\par\end{array}\right.$

Now, define the Saw Function by adding up each generator $\widehat{\chi}_{j}$
for each $(b_{j},d_{j})\in PD_{0}(X)$ as follows:
$\mathcal{S}_{0}(t)=\sum_{j}\widehat{\chi}_{j}(t)$. For general $k$, we have

$\mathcal{S}_{k}(t)=\sum_{(b^{k}_{j},d^{k}_{j})\in
PD_{k}(X)}\widehat{\chi}^{k}_{j}(t),$

where $PD_{k}(X)$ is the $k^{th}$ persistent diagram of $X$.

Figure 1:  $\mathcal{B}_{0}(t)$ is a step function with
$\mathcal{B}_{0}(1)=30$, $\mathcal{B}_{0}(2)=25$, $\mathcal{B}_{0}(3)=15$, and
$\mathcal{B}_{0}(4)=20$. We get $\mathcal{S}_{0}(t)$ by modifying
$\mathcal{B}_{0}(t)$ with birth and death times $\mathbf{b}(n),\mathbf{d}(n)$.
Here, $\mathbf{b}(0)=30$, $\mathbf{b}(1)=15$, $\mathbf{b}(2)=10$,
$\mathbf{b}(3)=5$, $\mathbf{d}(1)=20$, $\mathbf{d}(2)=20$, $\mathbf{d}(3)=0$
and $\mathbf{d}(4)=10$.

Notice that with this definition, we have a piecewise linear function
$\mathcal{S}_{k}(t)$ with the following properties. For
$n\in\mathcal{I}\subset\mathbf{N}$,

  * •

$\mathcal{S}_{k}(t)=\mathcal{B}_{k}(t)$ for
$t\in[n+\frac{1}{4},n+\frac{3}{4}]$

  * •

$\mathcal{B}_{k}(n)-\mathcal{S}_{k}(n)=\mathbf{b}_{k}(n)$ where
$\mathbf{b}_{k}(n)$ the number of births of $k$-cycles at time $t\in(n-1,n]$.

  * •

$\mathcal{B}_{k}(n-1)-\mathcal{S}_{k}(n)=\mathbf{d}_{k}(n)$ where
$\mathbf{d}_{k}(n)$ the number of deaths of $k$-cycles at time $t\in(n-1,n]$.

Now, when the filtration function is integer valued with $\lambda={1}/{4}$,
the explicit description of Saw Function $\mathcal{S}_{k}(t)$ is as follows.
For any $n\in\mathcal{I}$ and $t\geq\alpha_{0}$, we have

$\mathcal{S}_{k}(t)=\left\\{\begin{array}[]{ll}\mathcal{B}_{k}(t)-4\mathbf{d}_{k}(n)(t\mbox{-}n)+1&t\in[n-\frac{1}{4},n)\\\
\mathcal{B}_{k}(t)-\mathbf{b}_{k}(n)+4\mathbf{b}_{k}(n)(t\mbox{-}n)&t\in[n,n+\frac{1}{4}]\\\
\mathcal{B}_{k}(t)&\mbox{ otherwise}\\\ \end{array}\right.$

The novelty of Saw Functions is that it transforms most of the information
produced by persistence diagrams in a simple way to interpretable functions.
As described earlier, if one considers persistent homology as machinery which
keeps track of the complexity changes with respect to the filter function, Saw
Functions immediately summarizes the output in an interpretable way where one
immediately reads the live topological features at the given times as well as
the number of births and deaths at a given instance.

######  Remark 4.1 (Choice of the Lag Parameter $\lambda$).

In our sample construction, we chose
$\lambda\sim\frac{1}{4}\mbox{average}(\\{|\alpha_{i+1}-\alpha_{i}|\\})$ with
the assumption of the thresholds $\\{\alpha_{i}\\}$ are evenly distributed.
The reason for the coefficient $1/4$ should be clear from the Figure 1. Lag
parameter $\lambda>0$ marks two points in the interval
$(\alpha_{i},\alpha_{i+1})$, e.g.
$\alpha_{i}<\alpha_{i}+\lambda<\alpha_{i+1}-\lambda<\alpha_{i+1}$. Notice that
on the interval $[\alpha_{i}+\lambda,\alpha_{i+1}-\lambda]$, our Saw functions
coincides with the Betti functions. We chose $\lambda=1/4$ in our setting to
make it the length ($\alpha_{i+1}-\alpha_{i}-2\lambda$) of the interval
$[\alpha_{i}+\lambda,\alpha_{i+1}-\lambda]$ is the same with the length
($2\lambda$) of the interval where Betti function and the Saw function differs
$(\alpha_{i}-\lambda,\alpha_{i}+\lambda)$, i.e.
$\alpha_{i}+\lambda,\alpha_{i+1}-\lambda=2\lambda$. Depending on the
thresholds set $\\{\alpha_{i}\\}$, and the problem at hand, one can choose
varying lag parameters $\\{\lambda_{i}\\}$, too, i.e.
$(\alpha_{i}-\lambda_{i},\alpha_{i}+\lambda_{i})$.

###  4.2 Comparison with Similar Summaries:

In the applications, since we also embed birth and death information into the
function, when comparing persistent homologies of different spaces, Saw
Functions as their vectorization will give us a finer understanding of their
differences, and produce finer descriptors. In particular, if we compare the
Saw Functions with Betti functions or Persistence Curves, and similar
summaries (Umeda, 2017; Chen et al., 2020) the main differences are two-fold:
In non-technical terms, the summaries above are piecewise-constant and do not
store the information on the birth/death times in the threshold intervals
$(\alpha_{i},\alpha_{i+1})$. However, embedding this information to Saw
Functions give more thorough information around the topological changes near
the threshold instances. If the number of births and deaths are high numbers
at a threshold instance, Betti functions and similar summaries see only their
differences. However, in Saw Functions, such high numbers around a threshold
instance can be interpreted as an anomaly (or high activity) in the slice
$f^{-1}((\alpha_{i},\alpha_{i+1}))$ and the deep zigzag pieces exactly
quantifies this anomaly.

In technical terms, we can describe this difference as follows: Let
$(X^{+},f^{+},\mathcal{I}^{+})$ and $(X^{-},f^{-},\mathcal{I}^{-})$ describe
two filtrations. For simplicity, assume
$\mathcal{I}^{+}=\mathcal{I}^{-}=\mathcal{I}$. Assume that they both induce
the same Betti functions $\mathcal{B}_{k}^{+}(t)=\mathcal{B}_{k}^{-}(t)$ for
$t\in[\alpha_{0},\infty)$ in the $k^{th}$-level. Notice that this implies that
$\mathbf{b}^{+}_{k}(\alpha_{i})-\mathbf{d}^{+}_{k}(\alpha_{i})=\mathbf{b}^{-}_{k}(\alpha_{i})-\mathbf{d}^{-}_{k}(\alpha_{i})$
for any $i$ by definition. On the other hand, as Saw Functions store the
number of birth and death information, we see that $\mathcal{S}^{+}_{k}(t)$
may be highly different from $\mathcal{S}^{-}_{k}(t)$ as follows.

To see the difference in $L^{1}$-metric, let
$d_{1}(f,g)=\int_{\alpha_{0}}^{\infty}|f(t)-g(t)|\,dt$ represent
$L^{1}$-distance between $f$ and $g$. Then, we have
$d_{1}(\mathcal{S}^{+}_{k},\mathcal{S}^{-}_{k})=\sum_{i=1}^{N}\lambda\cdot|\mathbf{b}^{+}_{k}(\alpha_{i})-\mathbf{b}^{-}_{k}(\alpha_{i})|=\sum_{i=1}^{N}\lambda\cdot|\mathbf{d}^{+}_{k}(\alpha_{i})-\mathbf{d}^{-}_{k}(\alpha_{i})|$.
Here, the second equality comes from the fact that
$\mathbf{b}^{+}_{k}(\alpha_{i})-\mathbf{d}^{+}_{k}(\alpha_{i})=\mathbf{b}^{-}_{k}(\alpha_{i})-\mathbf{d}^{-}_{k}(\alpha_{i})$
by assumption. In other words, while the same filtration induces exactly same
Betti functions $\mathcal{B}^{+}_{k}(t)=\mathcal{B}^{-}_{k}(t)$, the induced
Saw Functions can be very far away from each other in the space of functions,
and this shows that they induce much finer descriptors.

Similarly, from $L^{2}$-metric perspective, Saw Functions produce much finer
information than the similar summaries in the literature because of the slope
information in the zigzags. In particular, Let
$d_{2}(f,g)=\int_{\alpha_{0}}^{\infty}|f(t)-g(t)|+|f^{\prime}(t)-g^{\prime}(t)|\,dt$
be the $L^{2}$-distance. If we use the notation above,
$(X^{\pm},f^{\pm},\mathcal{I})$ induces exactly same Betti functions
$\mathcal{B}^{+}_{k}(t)=\mathcal{B}^{-}_{k}(t)$, while
$d_{2}(\mathcal{S}^{+}_{k},\mathcal{S}^{-}_{k})=\sum_{i=1}^{N}(\lambda+1)\cdot|\mathbf{b}^{+}_{k}(\alpha_{i})-\mathbf{b}^{-}_{k}(\alpha_{i})|$.
Notice that the distance is much higher in $L^{2}$-metric, as the lag
parameter $\lambda$ can be a small number. In practice, if number of births
and deaths near a threshold, $\mathbf{b}_{k}(\alpha_{i})$ and
$\mathbf{d}_{k}(\alpha_{i})$, are both very close large numbers, Betti
functions and similar summaries does not see this phenomena as they only
detect their difference,
$\mathbf{b}_{k}(\alpha_{i})-\mathbf{d}_{k}(\alpha_{i})$. However, in Saw
Functions, we observe a steep slope, and deep zigzag near the threshold
$\alpha_{i}$ which can be interpreted as ”high activity”, or ”anomaly” near
the slice $f^{-1}((\alpha_{i-1},\alpha_{i}))$, which can be an effective tool
for classification purposes.

Tension at a threshold: Motivated by the idea above, we define $k$-tension of
$\alpha_{i}$ as
$\tau_{k}(\alpha_{i})=\mathbf{b}_{k}(\alpha_{i})+\mathbf{d}_{k}(\alpha_{i})$
which represents the amount of the activity (total number of births and
deaths) in the interval $(\alpha_{i-1},\alpha_{i}]$. As discussed above, while
betti functions only detect the difference
$\mathbf{b}_{k}(\alpha_{i})-\mathbf{d}_{k}(\alpha_{i})$, Saw Functions detect
also their sum
$\tau_{k}(\alpha_{i})=\mathbf{b}_{k}(\alpha_{i})+\mathbf{d}_{k}(\alpha_{i})$
at a given threshold. In particular, the tension $\tau_{k}(\alpha_{i})$ is the
stepness of the zigzag at $\alpha_{i}$ as it is the sum of the slopes of the
Saw Function at that point.

Here, we only discuss the comparison of Saw Functions with Betti functions,
but similar arguments can also be used to compare other persistence curves or
similar vectorizations.

Another advantage of Saw Functions over other common summaries is that one
does not need to choose suitable parameters or kernels in the process. In
other summaries, one needs to make suitable fine assumptions on the
parameters, or kernel functions which can highly distort the output if not
done properly.

Saw Functions as Persistence Curves:

If we consider Saw Functions in the Persistence Curves Framework (Chung and
Lawson, 2019), our Saw Functions can be interpreted as a new Persistence Curve
with the following inputs. With their notation, our Saw Function
$\mathcal{S}_{k}(t)$ corresponds to the persistence curve with generating
function $\psi(b,d,t)=\widehat{\chi}_{(b,d)}(t)$ (defined in the proof above)
and summary statistics $T=\sum$ (summation), i.e.
$\mathcal{S}_{k}(t)=\sum_{(b,d)\in PD}\widehat{\chi}_{(b,d)}(t)$. Note that
with this notation the Betti function $\mathcal{B}_{k}(t)=\sum_{(b,d)\in
PD}\chi_{(b,d)}(t)$ where $\chi_{(b,d)}(t)$ is the usual characteristic
function for interval $[b,d)$, i.e. $\chi_{(b,d)}(t)=1$ when $t\in[b,d)$ and
$\chi_{(b,d)}(t)=0$ otherwise.

###  4.3 Stability of Saw Functions

In this part, we discuss the stability of Saw Functions as vectorizations of
persistence diagrams. In other words, we compare the change in persistence
diagrams with the change they cause in Saw Functions.

Let $(X^{+},f^{+},\mathcal{I}^{+})$ and $(X^{-},f^{-},\mathcal{I}^{-})$ define
two filtrations. Let $PD_{k}(X^{\pm})$ be the corresponding persistence
diagrams in $k^{th}$ level. Define $p^{th}$ Wasserstein distance
$\mathcal{W}_{p}$ between persistence diagrams as follows. We use
$\mathcal{W}_{p}(X^{+},X^{-})$ notation instead of
$\mathcal{W}_{p}(PD_{k}(X^{+}),PD_{k}(X^{-}))$ for short. Let
$PD_{k}(X^{+})=\\{q_{j}^{+}\\}\cup\Delta^{+}$ and
$PD_{k}(X^{-})=\\{q_{l}^{-}\\}\cup\Delta^{-}$ where $\Delta^{\pm}$ represents
the diagonal with infinite multiplicity. Here,
$q_{j}^{+}=(b^{+}_{j},d_{j}^{+})\in PD_{k}(X^{+})$ represents the birth and
death times of a $k$-dimensional cycle $\sigma_{j}$. Let
$\phi:PD_{k}(X^{+})\to PD_{k}(X^{-})$ represent a bijection (matching). With
the existence of the diagonal $\Delta^{\pm}$ in both sides, we make sure the
existence of these bijections even if the cardinalities $|\\{q_{j}^{+}\\}|$
and $|\\{q_{l}^{-}\\}|$ are different. Then,

$\mathcal{W}_{p}(X^{+},X^{-})=\min_{\phi}(\sum_{j}\|q_{j}^{+}-\phi(q_{j}^{+})\|_{\infty}^{p})^{\frac{1}{p}},\quad
p\in\mathbb{Z}^{+}.$

In turn, the bottleneck distance is
$\mathcal{W}_{\infty}(X^{+},X^{-})=\max_{j}\|q_{j}^{+}-\phi(q_{j}^{+})\|_{\infty}$.

We compare the Wasserstein distance between persistence diagrams with the
distance between the corresponding Saw Functions. Let
$\mathcal{S}_{k}^{\pm}(t)$ be the $k^{th}$ Saw Functions as defined above.
Assuming $\mathcal{S}^{\pm}=0$ outside their domains $I^{\pm}$, the
$L^{p}$-distance between these two functions defined as

$d_{p}(\mathcal{S}^{+},\mathcal{S}^{-})=\biggl{(}\int_{I^{+}\cup
I^{-}}|\mathcal{S}^{+}(t)-\mathcal{S}^{-}(t)|^{p}\ dt\biggr{)}^{\frac{1}{p}}.$

Now, we state our stability result:

######  Theorem 4.1.

Let $(X^{\pm},f^{\pm},\mathcal{I}^{\pm})$ be as defined in previous paragraph.
Then, Saw Functions are stable for $p=1$, and unstable for $p=\infty$. i.e.

$d_{1}(\mathcal{S}^{+}(t),\mathcal{S}^{-}(t))\leq
C\cdot\mathcal{W}_{1}(X^{+},X^{-}).$

Proof: For simplicity, we first prove the result for Betti functions, and
modify it for Saw Functions. Notice that $\mathcal{B}_{k}(t)=\sum_{i}\chi_{i}$
and $\mathcal{S}_{k}(t)=\sum_{i}\widehat{\chi}_{i}$, where the index $i$
represents the points in $PD_{k}(G)=\\{q_{i}\\}$ where $q_{i}=(b_{i},d_{i})$.
That is, $\chi_{i}$ is the characteristic function for the interval
$[b_{i},d_{i})$. Then,

$|\mathcal{B}_{k}^{+}(t)-\mathcal{B}_{k}^{-}(t)|\leq|\sum_{i}\chi^{+}_{i}-\sum_{j}\chi_{j}^{-}|\leq\sum_{i}|\chi^{+}_{i}-\chi^{-}_{\phi(i)}|$
(1)

Notice that given $q^{+}=(b^{+},d^{+})$ and $q^{-}=(b^{-},d^{-})$, assuming
$d^{-}\leq d^{+}$, there are two cases for $\chi^{+}-\chi^{-}$. In case 1,
$d^{-}\leq b^{+}$, which gives
$\int_{\alpha_{0}}^{\infty}|\chi^{+}-\chi^{-}|=|d^{+}-b^{+}|+|d^{-}-b^{-}|\leq|d^{+}-d^{-}|+|b^{+}-b^{-}|$.
In case 2, $d^{-}>b^{+}$ and we get
$\int_{\alpha_{0}}^{\infty}|\chi^{+}-\chi^{-}|=|d^{+}-d^{-}|+|b^{+}-b^{-}|$.
Hence,

$\displaystyle\int_{\alpha_{0}}^{\infty}|\chi^{+}_{i}(t)$ $\displaystyle-$
$\displaystyle\chi^{-}_{\phi(i)}(t)|dt\leq|b_{i}^{+}-b_{\phi(i)}^{-}|+|d_{i}^{+}-d_{\phi(i)}^{-}|\
$ (2) $\displaystyle\leq$ $\displaystyle
2\max\bigl{\\{}|b_{i}^{+}-b_{\phi(i)}^{-}|,|d_{i}^{+}-d_{\phi(i)}^{-}|\bigr{\\}}$
$\displaystyle=$ $\displaystyle 2\|q^{+}_{i}-q^{-}_{\phi(i)}\|_{\infty}.$

Now, in view of (1), we obtain

$\displaystyle d_{p}(\mathcal{B}_{k}^{+}(t),\mathcal{B}_{k}^{-}(t))$
$\displaystyle=$
$\displaystyle\biggl{(}\int_{\alpha_{0}}^{\infty}|\mathcal{B}_{k}^{+}(t)-\mathcal{B}_{k}^{-}(t)|^{p}\
dt\biggr{)}^{\frac{1}{p}}$ $\displaystyle\leq$
$\displaystyle\biggl{(}\int_{\alpha_{0}}^{\infty}\bigl{[}\
\sum_{i}|\chi^{+}_{i}(t)-\chi^{-}_{\phi(i)}(t)|\ \bigr{]}^{p}\
dt\biggr{)}^{\frac{1}{p}}$

By (2), the stability result for $p=1$ follows from

$\displaystyle d_{1}(\mathcal{B}_{k}^{+}(t),\mathcal{B}_{k}^{-}(t))$
$\displaystyle=$
$\displaystyle\int_{\alpha_{0}}^{\infty}\sum_{i}|\chi^{+}_{i}(t)-\chi^{-}_{\phi(i)}(t)|dt$
$\displaystyle\leq$
$\displaystyle\sum_{i}2\|q^{+}_{i}-q^{-}_{\phi(i)}\|_{\infty}$
$\displaystyle=$ $\displaystyle 2\mathcal{W}_{1}(X^{+},X^{-}).$

This finishes the proof for Betti functions. Notice that Equation 2 is still
true when we replace $\chi^{\pm}_{i}$ with $\widehat{\chi}_{i}^{\pm}$. Then,
when we replace Betti functions $\mathcal{B}^{\pm}_{k}(t)$ with
$\mathcal{S}^{\pm}_{k}(t)$ and $\chi^{\pm}_{i}$ with
$\widehat{\chi}_{i}^{\pm}$ in the inequalities above, we get the same result
for Saw Functions, i.e.
$d_{1}(\mathcal{S}_{k}^{+}(t),\mathcal{S}_{k}^{-}(t))\leq
2\mathcal{W}_{1}(X^{+},X^{-})$. The proof follows. $\Box$

Note that when $p>1$, Equation 4.3 above may no longer be true. So, the
stability for $1<p<\infty$ is not known. For $p=\infty$, we have the following
counterexample.

Counterexample for $p=\infty$ Case:

Here, we describe a counterexample showing that similar statement for
$p=\infty$ cannot be true, i.e.
$d_{\infty}(\mathcal{S}^{+}(t),\mathcal{S}^{-}(t))\leq
C\cdot\mathcal{W}_{\infty}(X^{+},X^{-})$. We define two persistence diagrams,
where one has $n$ off-diagonal elements, and the other has no off-diagonal
element. Let $PD_{k}(X^{+})=\\{(1,2)^{n}\\}\cup\Delta$, i.e. $(1,2)$ has
multiplicity $n$. Let $PD_{k}(X^{-})=\Delta$, i.e. only diagonal elements.
Note that it is straightforward to get such a $X^{\pm}$ for any $k$ and $n$.
Then, as $d_{\infty}((1,2),\Delta)=\sqrt{2}/2$, we have
$\mathcal{W}_{\infty}(X^{+},X^{-})=\sqrt{2}/2$. On the other hand, each copy
of the point $(1,2)$ contributes $1$ to betti function in the interval
$[1,2)$. This means $\mathcal{B}^{+}_{k}(t)=n$ for $t\in[1,2)$ while
$\mathcal{B}^{-}_{k}(t)=0$ for any $t$. This gives
$d_{\infty}(\mathcal{S}_{k}^{+},\mathcal{S}_{k}^{-})=\sup_{t}|\mathcal{S}_{k}^{+}(t)-\mathcal{S}_{k}^{-}(t)|=n$
while $\mathcal{W}_{\infty}(X^{+},X^{-})=\sqrt{2}/2$. This shows that there is
no $C>0$ with $d_{\infty}(\mathcal{S}_{k}^{+}(t),\mathcal{S}_{k}^{-}(t))\leq
C\cdot\mathcal{W}_{\infty}(X^{+},X^{-})$ in general.

##  5 Multi-Persistence Grid Functions (MPGF)

In this part, we introduce our second topological summary: Multi-Persistence
Grid Functions (MPGF). Like in Saw Functions, we aim to use persistent
homology as a complexity measure of evolving subspaces determined by
filtration. In this case, instead of one filter function, we use multiple
filter functions. One can consider this approach as a vectorization of
multiparameter persistent homology.

First, to keep the setup simple, we construct MPGFs in $2$-parameter setting.
Then, we give the natural generalization in any number of parameters. Here, we
only consider sublevel filtrations for more than one function at the same
time.

###  5.1 MPGFs for 2-parameter

A Short Outline: Before starting the formal construction, we start by giving
an outline of the setup. Given two filter functions $f,g:X\to\mathbf{R}$ with
their threshold sets $\\{\alpha_{i}\\}$ and $\\{\beta_{j}\\}$ respectively,
one can chop off $X$ into finer pieces $X^{ij}=\\{x\in X\mid
f(x)\leq\alpha_{i},\ g(x)\leq\beta_{j}\\}$. The subspaces $\\{X^{ij}\\}$
induce a natural filtration, however partially ordered nature of the threshold
set $\\{(\alpha_{i},\beta_{j})\\}$, getting persistence homology in the
multiparameter setting is highly technical (Lesnick, 2019b). We bypass this
technicalities, by directly going to the subspaces $\\{X^{ij}\\}$, and
considering their Betti numbers $\mathcal{B}_{k}(X^{ij})$ as the subspaces’
topological complexity measure. Then, by using the grid
$\\{(\alpha_{i},\beta_{j})\\}$ in the threshold domain $R$, we assign these
Betti numbers to the corresponding boxes $\Delta_{ij}$ as in Figure 2. This
construction defines a $2$-parameter function $\mathcal{G}_{k}(x,y)$ which we
call MPGF.

Next is the formal construction of MPGFs. Let $X$ be a metric space, and
$f,g:X\to\mathbf{R}$ be two filter functions. Define $F:X\to\mathbf{R}^{2}$ as
$F(x)=(f(x),g(x))$. Let $\mathcal{I}_{1}=\\{\alpha_{1},...\alpha_{m_{1}}\\}$
be the set of thresholds for the first filtration $f$, where $\alpha_{1}=\min
f(x)<\alpha_{2}...<\alpha_{m_{1}}=\max f(x)$. Similarly,
$\mathcal{I}_{2}=\\{\beta_{1},...,\beta_{m_{2}}\\}$ is defined for $g$. Let
$\delta_{1}={(\alpha_{m_{1}}-\alpha_{1})}/{(m_{1}-1)}$,
$\delta_{2}={(\beta_{m_{2}}-\beta_{1})}/{(m_{2}-1)}$,
$\alpha_{0}=\alpha_{1}-\delta_{1}$, and $\beta_{0}=\beta_{1}-\delta_{2}$. We
define our MPGFs on the rectangle
$\mathcal{R}=(\alpha_{0},\alpha_{m_{1}}]\times(\beta_{0},\beta_{m_{2}}]$.
Notice that the points $\\{(\alpha_{i},\beta_{j})\\}$ gives a grid in our
rectangle $R$.

Let $\Delta_{ij}=(\alpha_{i-1},\alpha_{i}]\times(\beta_{j-1},\beta_{j}]$ for
$1\leq i\leq m_{1}$ and $1\leq j\leq m_{2}$. Then,
$\mathcal{R}=\bigcup_{i,j}\Delta_{ij}$. Let
$\Omega_{ij}=(\alpha_{0},\alpha_{i}]\times(\beta_{0},\beta_{j}]$ (see Figure
2).

Figure 2: Filtration. The rectangle $R$ is the domain of $\mathcal{G}_{k}$
which consists of $m_{1}\times m_{2}$ small rectangles $\\{\Delta_{ij}\\}$.
$\mathcal{G}_{k}$ is constant for each $\Delta_{ij}$ which is the $k$th Betti
number of the complex coming from $F^{-1}(\Omega_{ij})$.

Define $X^{ij}=\\{x\in X\mid f(x)\leq\alpha_{i}\mbox{ and
}g(x)\leq\beta_{j}\\}$, i.e. $X^{ij}=F^{-1}(\Omega_{ij})$. Then, let
$\widehat{X}^{ij}$ be the complex generated by $X^{ij}$. $\widehat{X}^{ij}$
can be the set $X^{ij}$ itself, or VR, or similar complex induced by $X^{ij}$.
Then, for each fixed $i_{0}$,
$\widehat{X}^{i_{0}1}\subset\widehat{X}^{i_{0}2}\subset...\subset\widehat{X}^{i_{0}m_{2}}$
gives a single parameter filtration for $(X^{i_{0}},g)$ where
$X^{i_{0}}=f^{-1}((-\infty,\alpha_{i_{0}}])$.

######  Definition 5.1.

Let $\mathcal{B}_{k}(\widehat{X}^{ij})$ be the $k^{th}$-Betti number of
$\widehat{X}^{ij}$. Define $k^{th}$ MPGF of the filtration for the filter
function $F:X\to\mathbf{R}^{2}$ as

$\mathcal{G}_{k}(x)=\mathcal{B}_{k}(\widehat{X}^{ij})$

for any $x\in\Delta_{ij}$.

That is, we assign every rectangle $\Delta_{ij}$ of the threshold domain, we
assign the Betti number of the space $\widehat{X}^{ij}$ corresponding to these
thresholds. Notice that $\mathcal{G}_{k}:\mathcal{R}\to\mathbf{N}$ has
constant value at any small rectangle $\Delta_{ij}\subset\mathcal{R}$. The
algorithm is outlined in Alg. 1.

Complexity: Algorithm 1 requires computation of Betti functions at each of the
$m_{1}\times m_{2}$ grid cell. Betti computations require finding the rank of
the homology group, which has a complexity of $\tilde{O}(|A|+r^{\omega})$
where $|A|$ is the number of non-zero entries in the group, r is the true rank
of the group and $\omega<2.38$ is the multiplication exponent (Cheung et al.,
2013).

Example: In Figure 3, we described a simple example to show how MPGF works. In
the example, $X$ is graph $G$, and $f,g:V\to\mathbf{N}$ integer valued
functions on vertices. Here, $\widehat{X}^{ij}$ is the subgraph $G^{ij}$
generated by $V^{ij}=\\{v\in V\mid f(v)\leq i,\ g(v)\leq j\\}$. In the grid,
we count the number of topological feature exist in $X^{ij}$, and record this
number to the box
$\Delta_{ij}=(\alpha_{i-1},\alpha_{i}]\times(\beta_{j-1},\beta_{j}]$. In the
example, we see MPGF $\mathcal{G}_{0}$ for $0$-cycles (connected components).

Why MPGFs are useful? Multiparameter filtration slices up space $X$ in a much
finer and controlled way than single parameter filtration so that we can see
the topological changes with respect to both functions at the same time. Then,
by using MPGFs for the corresponding multiparameter persistence, we can
analyze, and interpret both functions’ behavior on the space $X$, and
interrelation between these two functions. In many cases, we have more than
one important descriptors that are not directly connected, but both give very
valuable information on the dataset. In that case, when both functions are
used for multiparameter persistence, then together both functions will provide
much finer information on the dataset, and the functions’ undisclosed
relationship with each other could be observed. One very popular case is the
time-series datasets. One function is the time, and the other is another
important qualitative descriptor of the dataset.

Figure 3: Grid. In the graph $G$, black numbers are node degrees whereas red
numbers are node eccentricities (i.e., max distance to any node in the graph).
In the right, $G^{i}$ represents the subgraph corresponding to sublevel set
$f(v)\leq i$ where $f$ is the degree function. The subgraph $G^{ij}$ of
$G^{i}$ is defined by $g(v)\leq j$ where $g$ is the eccentricity function.
MPGF $\mathcal{G}_{0}(\Delta_{ij})=\mathcal{B}_{0}(G^{ij})$. Algorithm 1
Multi-Persistence Graph Classification

Input: graph $G$, functions $f,g$, grid sizes $m_{1},m_{2}$.

Output: A matrix of betti 0 and 1 values defined for a grid filtration.

Compute $f$ values for $\forall v\in G$

Fix $\alpha_{i}$ for $1\leq i\leq m_{1}$.

Initialize matrix $grid$

for $1\leq i\leq m_{1}$ do

Define $G^{i}=\\{v\in\mathcal{G}\mid f(v)\leq\alpha_{i}\\}$.

Set $G^{i}$ as the original input space for the filtration function
$g:X^{i}\to\mathbf{R}$

for $1\leq j\leq m_{2}$ do

Set subgraph $G^{ij}=\\{v\in G^{i}\mid f(v)\leq\beta_{j}\\}$.

$grid[i,j,0]=\mathcal{B}_{0}(G^{ij})$

$grid[i,j,1]=\mathcal{B}_{1}(G^{ij})$

end for

end for

RETURN $grid$

###  5.2 MPGFs for any number of parameters

We generalize the idea above in any number of parameters as follows: Let
$F:X\to\mathbf{R}^{d}$ be our filter function. In particular, let
$F=(f_{1},f_{2},..,f_{d})$. Let $\mathcal{I}_{i}=\\{\alpha_{ij}\mid 1\leq
j\leq m_{i}\\}$ be the thresholds of the filter function $f_{i}$. In
particular, $\\{\alpha_{i_{0}j}\\}$ is the thresholds of $f_{i_{0}}$ where
$\alpha_{i_{0}1}=\min_{V}f_{i_{0}}(v)<\alpha_{i_{02}}<..<\alpha_{i_{0}m_{i_{0}}}=\max_{V}f_{i_{0}}(v)$.

Again, let $\delta_{i}={(\alpha_{im_{i}}-\alpha_{i1})}/{(m_{i}-1)}$, and let
$\alpha_{i0}=\alpha_{i1}-\delta_{i}$. Define $d$-dimensional rectangular box

$\mathcal{R}=(\alpha_{10},\alpha_{1m_{1}}]\times(\alpha_{20},\alpha_{1m_{2}}]\times...\times(\alpha_{d0},\alpha_{dm_{d}}].$

Notice that the $d$-tuples
$\\{(\alpha_{1j_{1}},\alpha_{2j_{2}},...\alpha_{dj_{d}})\\}$ deliver a
$d$-dimensional grid in $R$ where $1\leq j_{i}\leq m_{i}$. Similarly, define
small $d$-dimensional boxes

$\displaystyle\Delta_{j_{1}j_{2}..j_{d}}$ $\displaystyle=$
$\displaystyle(\alpha_{1(j_{1}-1)},\alpha_{1j_{1}}]$ $\displaystyle\times$
$\displaystyle(\alpha_{2(j_{2}-1)},\alpha_{2j_{2}}]\times\ldots\times(\alpha_{d(j_{d}-1)},\alpha_{dj_{d}}].$

Then, again we have
$\mathcal{R}=\bigcup_{j_{1},..j_{d}}\Delta_{j_{1}j_{2}..j_{d}}$. In other
words, $\mathcal{R}$ is the union of $N=m_{1}\cdot m_{2}\cdot...\cdot m_{d}$
small boxes.

Similarly, define the subspace $X^{j_{1}j_{2}..j_{d}}=\\{x\in X\mid
f_{i}(x)\leq\alpha_{ij_{i}}\mbox{ for }1\leq i\leq d\\}$ of $X$ induced by the
thresholds $j_{1},j_{2},...,$ and $j_{d}$. Let
$\widehat{X}^{j_{1}j_{2}..j_{d}}$ be the complex induced by
$X^{j_{1}j_{2}..j_{d}}$. Here, $\widehat{X}^{j_{1}j_{2}..j_{d}}$ can be the
subspace $X^{j_{1}j_{2}..j_{d}}$ itself, or the VR (or similar) complex
induced by $X^{j_{1}j_{2}..j_{d}}$.

Let $\mathcal{B}_{k}(\widehat{X}^{j_{1}j_{2}..j_{d}})$ $k^{th}$ Betti number
of the space $\widehat{X}^{j_{1}j_{2}..j_{d}}$. Define $k^{th}$ MPGF of the
filtration $F:X\to\mathbf{R}^{d}$ as

$\mathcal{G}_{k}(x)=\mathcal{B}_{k}(\widehat{X}^{j_{1}j_{2}..j_{d}})$

for any $x\in\Delta_{j_{1}j_{2}..j_{d}}$. Notice that
$\mathcal{G}_{k}:\mathcal{R}\to\mathbf{N}$ has constant value at any small box
$\Delta_{j_{1}j_{2}..j_{d}}\subset\mathcal{R}$.

Algorithm for MPGFs in any number of parameters:  We fix $j_{1},...,j_{d-1}$
for $1\leq j_{i}\leq m_{i}$. Define $X^{j_{1}j_{2}..j_{d-1}}=\\{x\in X\mid
f_{i}(v)\leq\alpha_{ij_{i}}\mbox{ for }1\leq i\leq d-1\\}$. Then, set
$X^{j_{1}j_{2}..j_{d-1}}$ as the original input space for the filtration
function $f_{d}:X^{j_{1}j_{2}..j_{d-1}}\to\mathbf{R}$. Compute the persistence
diagrams, and corresponding Betti functions for this filtration. Then, in
particular $\widehat{X}^{j_{1}j_{2}..j_{d-1}\widehat{j}}$ is the
$\widehat{j}^{th}$ complex in this filtration.
$\mathcal{G}_{k}(\Delta_{j_{1}j_{2}..j_{d-1}\widehat{j}})=\mathcal{B}_{k}(\widehat{X}^{j_{1}j_{2}..j_{d-1}\widehat{j}})$,
$k^{th}$-Betti number of $\widehat{X}^{j_{1}j_{2}..j_{d-1}\widehat{j}}$. In
other words, if one can obtain $\widehat{X}^{j_{1}..j_{d}}$, and compute its
$k^{th}$-Betti number directly, then
$\mathcal{G}_{k}(\Delta_{j_{1}...j_{d})}=\mathcal{B}_{k}(\widehat{X}^{j_{1}...j_{d}})$.

###  5.3 Comparison with other Multiparameter Persistence Summaries

The crucial advantage of our MPGFs over the existing topological summaries of
the multiparameter persistence is its simplicity and generality. Except for
some special cases, Multiparameter Persistence theory suffers from the problem
of the nonexistence of barcode decomposition because of the partially ordered
structure of the index set $\\{(\alpha_{i},\beta_{j})\\}$ (Thomas, 2019;
Lesnick, 2019a). The existing approaches remedy this issue by slicing
technique by studying one-dimensional fibers of the multiparameter domain. In
particular, in the threshold domain
$\Omega=[\alpha_{0},\alpha_{N}]\times[\beta_{0},\beta_{M}]$ in the $xy$-plane,
one needs to find a good slice (line segment) $ax+by=c$ in $\Omega$, where the
multipersistence restricted to such slice can be read as a single parameter
persistence. This makes the summaries vulnerable to the choice of ”good
slicing” (choice of $a,b,c$) and combining back the multiple single parameter
information into a multi-parameter setting. For example, in (Carrière and
Blumberg, 2020), the authors define a similar grid object called
”Multiparameter Persistence Image” where they slice the domain $\mathcal{R}$,
and consider restricted single parameter persistence diagrams in the slices.
Then, they successfully remedy the nonexistence of the barcode decomposition
problem by matching the nearby barcodes to the same family, which they call
vineyard decomposition. Then, by using this, for each grid point, they take a
weighted sum of each barcode family to see the “topological importance” of
that grid point in this decomposition. They use 3 types of fibering (vineyard
family) for the domain $\Omega$, which are expected to give good results for a
generic case. However, their construction heavily depends on these slicing
choices, and when filtration functions do not interact well, different slicing
might give different images.

In our MPGFs, we take a more direct approach to construct our summaries. We
bypass the serious technical issues in defining multiparameter persistence
diagrams and directly go to the topological behavior of the subspaces induced
by each grid. This gives a simple and general method that can be applied to
any topological space with more than one filtration function. The topological
summary is much simpler, and interpretable as one can easily read the changes
in the graph. It also enables one to read the interrelation between the
filtration functions, and their behavior on the space. Furthermore, as it does
not use any slicing, it directly captures the multidimensional information
produced by filtration functions.

Life Span Information: Notice that in both Saw Functions and Multi-Persistence
Grid functions, when vectorizing persistence diagrams, we consider persistence
homology as complexity measurement during the evolution of filter function.
While these functions give the count of live topological features, they seem
to miss important information from persistence diagrams, i.e. life spans. Life
span $d_{\sigma}-b_{\sigma}$ of a topological feature $\sigma$ is crucial
information to show how persistent the feature is. In particular, if
$d_{\sigma}-b_{\sigma}$ is large, it is an essential/persistent feature, while
if short, it can be considered nonessential/noise. In that sense, our
topological summaries do not carry the individual life span information
directly, but indirectly. In particular, any persistent feature $\sigma$
contributes to Saw or MPGF functions as many numbers of intervals (boxes) they
survive.

###  5.4 Stability of MPGFs

In this part, we discuss the stability of MPGFs. Even though the
multiparameter persistence theory is developing very fast in the past few
years, there are still technical issues to overcome to use this technique in
general. As mentioned before, because of the partially ordered nature of the
threshold domain in the multiparameter case, the single parameter persistent
homology theory does not generalize immediately to the multiparameter case.
Similarly, distance definitions have related problems in this setting. There
are several distance functions (interleaving, matching) suggested in the
literature for multiparameter persistence (Thomas, 2019). The theory is very
active, and there are several promising results in recent years (Lesnick,
2015; Carrière and Blumberg, 2020). Here, we conjecture that our MPGFs are
stable with respect to matching distance, and we sketch proof of the
conjecture in a special case.

Let $(X^{+},F^{+},\mathcal{I}^{+})$ and $(X^{-},F^{-},\mathcal{I}^{-})$ define
two filtrations where $F^{\pm}=(f^{\pm},g^{\pm})$, and
$\mathcal{I}^{\pm}=\\{(\alpha_{i}^{\pm},\beta_{j}^{\pm})\\}$. Let
$\mathfrak{D}_{M}(X^{+},X^{-})$ represent the matching distance of
multiparameter persistence modules induced by $(X^{+},F^{+},\mathcal{I}^{+})$
and $(X^{-},F^{-},\mathcal{I}^{-})$ (Thomas, 2019).

Next, by assuming $\mathcal{G}^{\pm}=0$ outside of their domains
$\mathcal{R}^{\pm}$, define the $L^{1}$-distance between induced MPGFs as

$\mathbf{d}(\mathcal{G}^{+},\mathcal{G}^{-})=\int\int_{\mathcal{R}^{+}\cup\mathcal{R}^{-}}|\mathcal{G}^{+}(x,y)-\mathcal{G}^{-}(x,y)|\,dxdy$

Now, we have the following conjecture for the stability of MPGFs.

######  Conjecture 5.1.

Let $(X^{\pm},F^{\pm},\mathcal{I}^{\pm})$ be as defined above. Then, MPGFs are
stable i.e.

$\mathbf{d}(\mathcal{G}^{+},\mathcal{G}^{-})\leq
C\cdot\mathfrak{D}_{M}(X^{+},X^{-}).$

Here, the main motivation for this conjecture is that it naturally holds in
the technically simplest case. Again, the partially ordered nature of the
thresholds in multiparameter setting prevents having good barcode
decomposition for the generators like in the single parameter persistent
homology (Lesnick, 2019b). However, there are simple cases where good barcode
decomposition exists (Lesnick, 2019b). In such a $2$-parameter setting, a
barcode $\mathcal{B}^{\pm}_{i}$ is not one rectangle, but unions of rectangles
(with vertices at thresholds) where the union is connected. Let
$\\{\mathcal{B}^{\pm}_{i}\\}$ be the set of barcodes in our multiparameter
persistent homology for $(X^{\pm},F^{\pm},\mathcal{I}^{\pm})$. Then, the
induced MPGFs $\mathcal{G}^{\pm}$ can be defined just like single parameter
persistent homology as follows. In particular, let
$\chi_{\mathcal{B}^{\pm}_{i}}(x,y)$ be the characteristic function for the
barcode $\mathcal{B}^{\pm}_{i}$, then we have

$\mathcal{G}^{\pm}(x,y)=\sum_{i}\chi_{\mathcal{B}^{\pm}_{i}}(x,y).$

In that case, our proof for Theorem 4.1 goes through similar way by replacing
generator functions $\widehat{\chi}^{\pm}_{j}(t)$ in the proof with the
characteristic functions $\chi_{\mathcal{B}^{\pm}_{i}}(x,y)$ of barcodes of
multiparameter persistence. Since having a good barcode is a very special
case, we leave this as a conjecture for general setting.

###  5.5 An alternative definition for MPGFs

Even though MPGFs are giving the Betti numbers of corresponding subspaces
$\\{X^{ij}\\}$, when restricted to single parameter, MPGFs are different than
regular Betti functions. While single parameter Betti functions defined as
$\mathcal{B}_{k}([\alpha_{i},\alpha_{i+1}))=\mathcal{B}_{k}(\alpha_{i})$, when
MPGFs restricted to single parameter, we slide the interval one unit back so
that $\mathcal{G}_{k}((\alpha_{i-1},\alpha_{i}])=\mathcal{G}_{k}(\alpha_{i})$.
Here, both $\mathcal{G}_{k}(\alpha_{i})=\mathcal{B}_{k}(\alpha_{i})$
represents the $k^{th}$ Betti number of the space $X^{i}=\\{x\in X\mid
f(x)\leq\alpha_{i}\\}$. We chose this presentation for MPGFs since it is more
natural and easy to read for multiparameter case as it can be seen in Figure 2
in the main text. In particular, if one wants to define MPGFs consistent with
the single parameter Betti functions, one needs to replace the half open
intervals $(\alpha_{i},\alpha_{i+1}]\times(\beta_{j},\beta_{j+1}]$ in the
original definition with the
$[\alpha_{i},\alpha_{i+1})\times[\beta_{j},\beta_{j+1})$ starting from
$\alpha_{0}=\min f$, and $\beta_{0}=\min g$, then the similar construction
will give the definition for MPGFs consistent with the single parameter Betti
functions. In this definition, the extra column goes to the right not to the
left. Compare the Figure 4 with the Figure 2 in the main text. This
alternative definition has exactly the same information with our MPGFs, but as
mentioned above, our definition is more user friendly in multiparameter case.

Figure 4: The rectangle $R$ is the domain of $\mathcal{B}_{k}$ consists of
$m_{1}.m_{2}$ small rectangles $\\{\Delta_{ij}\\}$. $\mathcal{B}_{k}$ is
constant for each $\Delta_{ij}$ which is the $k$ Betti number of the complex
coming from $F^{-1}(\Omega_{ij})$.

Betti Function Notation: When restricted to single parameter, our MPGFs above
is slightly different than regular Betti functions. While single parameter
Betti functions defined as
$\mathcal{B}_{k}([\alpha_{i},\alpha_{i+1}))=\mathcal{B}_{k}(\alpha_{i})$, in
our notation, we slide the interval back so that
$\mathcal{B}_{k}((\alpha_{i-1},\alpha_{i+1}])=\mathcal{B}_{k}(\alpha_{i})$.
This is because this presentation is more natural and easy to read for
multiparameter case as it can be seen in Figure 2. Recall that
$\mathcal{G}_{k}(\Delta_{ij})=\mathcal{B}_{k}(X_{ij})$ where
$X_{ij}=F^{-1}(\Omega_{ij})$. With our notation, we choose $\Delta_{ij}$
inside $\Omega_{ij}$ which is more natural in multiparameter case. However, if
we want to define MPGF $\mathcal{G}_{k}$ as direct generalization of Betti
function $\mathcal{B}_{k}$, then we need to use this alternative definition
described above. Then, with this definition, $\Delta_{ij}$ will be outside of
$\Omega_{ij}$ as in Figure 4.

Superlevel filtrations for MPGFs:

If the goal is to use superlevel filtration in original MPGFs, we apply the
following reverse approach:

Let $X$ be a metric space, and $f,g:X\to\mathbf{R}$ be two filtration
functions. Let $F:X\to\mathbf{R}^{2}$ defined as $F(x)=(f(x),g(x))$. Let
$\mathcal{I}_{1}=\\{\alpha_{1},\ldots,\alpha_{m_{1}}\\}$ be the set of
thresholds for the first filtration $f$, where $\alpha_{1}=\min
f(x)<\alpha_{2}\ldots<\alpha_{m_{1}}=\max f(x)$. Let
$\mathcal{I}_{2}=\\{\beta_{1},\ldots,\beta_{m_{2}}\\}$ defined similarly for
$g$. Now, let $\delta_{1}={(\alpha_{m_{1}}-\alpha_{1})}/{(m_{1}-1)}$ and
$\delta_{2}={(\beta_{m_{2}}-\beta_{1})}/{(m_{2}-1)}$. Let
$\alpha_{m_{1}+1}=\alpha_{m_{1}}+\delta_{1}$, and
$\beta_{m_{2}+1}=\beta_{m_{2}}+\delta_{2}$.

Let $\Delta_{ij}=[\alpha_{i},\alpha_{i+1})\times[\beta_{j},\beta_{j+1})$ for
$1\leq i\leq m_{1}$ and $1\leq j\leq m_{2}$. Then,
$\mathcal{R}=\bigcup_{i,j}\Delta_{ij}$. Let
$\Omega_{ij}=[\alpha_{i},\alpha_{m+1})\times[\beta_{j},\beta_{m_{2}+1})$. That
is, in the sublevel filtration, we take lower left part of $\mathcal{R}$ as
$\Omega_{ij}$, while in superlevel filtration, we consider the upper right
corner of $\mathcal{R}$ as $\Omega_{ij}$.

If $X^{ij}=\\{x\in X\mid f(v)\geq\alpha_{i}\mbox{ and }g(v)\geq\beta_{j}\\}$,
i.e. $X^{ij}=F^{-1}(\Omega_{ij})$, then $\widehat{X}^{ij}$ is defined as the
complex generated by $X^{ij}$. Now, let $\mathcal{B}_{k}(\widehat{X}^{ij})$ be
the $k^{th}$-Betti number of $\widehat{X}^{ij}$. The $k^{th}$ MPGF of the
filtration $F:X\to\mathbf{R}^{2}$ is then given by
$\mathcal{G}_{k}(x)=\mathcal{B}_{k}(\widehat{X}^{ij})$ for any
$x\in\Delta_{ij}$.

A recursive algorithm to compute $\mathcal{G}_{k}$ can be described as
follows. One can proceed by slicing $\mathcal{R}$ inductively. Let
$X^{d}_{j_{d}}=\\{x\in X\mid f_{d}(x)\leq\alpha_{dj_{d}}\\}$. Let
$\widehat{X}^{d}_{j_{d}}$ be the complex induced by $X^{d}_{j_{d}}$. This
defines a $(d-1)$-dimensional slice in $\mathbf{R}$. Then, one can do
$(d-1)$-parameter filtration on $\widehat{X}^{d}_{j_{d}}$ with the filtration
functions $\\{f_{1},..,f_{d-1}\\}$. We now start the process with
$X^{d}_{j_{d}}$ as original input space for $d-1$-parameter filtration, finish
the process inductively, and complete the function $\mathcal{B}_{k}$. Both
methods computationally demonstrate same efficiency, but coding inductively in
the second case could be easier.

##  6 Application to Graph Classification

In the following, as a case study, we will apply our topological summaries to
the graph classification problem. Our task is to classify graph instances of a
dataset. In particular, let $G$ be a graph with vertex set $V=\\{v_{i}\\}$ and
edge set $E=\\{e_{ij}\\}$, i.e. $e_{ij}\in E$ if there is an edge between the
vertex $v_{i}$ and $v_{j}$ in $G$. Let $f:V\to\mathbf{R}$ be a function
defined on the vertices of $G$. $\mathcal{I}=\\{\alpha_{i}\\}$ be the
threshold set which is an increasing sequence with $\alpha_{1}=\min f$ to
$\alpha_{N}=\max f$. Let $V^{i}=\\{v\in V\mid f(v)\leq\alpha_{i}\\}$. Let
$G^{i}$ be the subgraph generated by $V^{i}$, i.e. $e_{ij}\in G^{i}$ if
$v_{i},v_{j}\in G^{i}$. Then, $G^{1}\subset G^{2}\subset...\subset G^{N}$
defines the sublevel filtration for $(G,f)$. Similarly, one can define
$\widehat{G}^{i}$ as the clique complex of $G^{i}$. Then,
$\widehat{G}^{1}\subset\widehat{G}^{2}\subset...\subset\widehat{G}^{N}$
defines another natural filtration defined by $(G,f)$. We call this clique
sublevel filtration.

###  6.1 Datasets

In experiments, we used COX2 (Kersting et al., 2016), DHFR (Kersting et al.,
2016), BZR (Kersting et al., 2016), PROTEINS (Borgwardt et al., 2005), NIC1
(Wale et al., 2008) and DHFR (Schomburg et al., 2004) for binary and multi-
class classification of chemical compounds, whereas IMDB-BINARY, IMDB-MULTI,
REDDIT-BINARY and REDDIT-5K (Yanardag and Vishwanathan, 2015) are social
datasets. Table 1 shows characteristics of the graphs.

Dataset | NumGraphs | NumClasses | AvgNumNodes | AvgNumEdges
---|---|---|---|---
BZR | 405 | 2 | 35.75 | 38.36
COX2 | 467 | 2 | 41.22 | 43.45
DHFR | 467 | 2 | 42.43 | 44.54
FRANKENSTEIN | 4337 | 2 | 16.90 | 17.88
IMDB-BINARY | 1000 | 2 | 19.77 | 96.53
IMDB-MULTI | 1500 | 3 | 13.00 | 65.94
NCI1 | 4110 | 2 | 29.87 | 32.30
PROTEINS | 1113 | 2 | 39.06 | 72.82
REDDIT-BINARY | 2000 | 2 | 429.63 | 497.75
REDDIT-MULTI-5K | 4999 | 5 | 508.82 | 594.87
Table 1: Characteristics of the datasets used in experiments.

Reddit5K has five and ImdbMulti has three label classes. All other datasets
have binary labels.

We adopt the following traditional node functions (Hage and Harary, 1995) in
graph classification: 0) degree, 1) betweenness and 2) closeness centrality,
3) hub/authority score, 4) eccentricity, 5) Ollivier-Ricci and 6) Forman-Ricci
curvatures. Ollivier and Forman functions are implemented in Python by Ni et
al. (Ni et al., 2019). We compute functions 0-4 by using the iGraph library in
R.

We implement our methods on an Intel(R) Core i7 CPU @1.90GHz and 16Gb of RAM
without parallelization. Our R code is available at
https://github.com/cakcora/PeaceCorps.

###  6.2 Models

In graph classification, we will compare our results to five well-known graph
representation learning methods benchmarked in a recent in-depth study by
Errica et al. (Errica et al., 2020). These are GIN (Xu et al., 2018), DGCNN
(Zhang et al., 2018), DiffPool (Ying et al., 2018), ECC (Simonovsky and
Komodakis, 2017) and GraphSage (Hamilton et al., 2017).

For our results, we employ Random Forest (Breiman, 2001), SVM (Noble, 2006),
XGBoost (Chen et al., 2015) and KNN with Dynamic Time warping (Müller, 2007)
to classify graphs. Best models were chosen by 10-fold cross-validation on the
training set, and all accuracy results are computed by using the best models
on out-of-bag test sets.

Random Forest consistently gave the best accuracy results for both Single and
Multi-Persistence experiments. SVM with Radial Kernel yielded the next best
results. In the rest of this paper, we will demonstrate the Random Forest
results. In Random Forest, we experimented with the number of predictors
sampled for splitting at each node (mtry) from $\sqrt{n}-3,\ldots,\sqrt{n}+3$
where n is the number of dataset features. Our models use $ntree=500$ trees.

All results are averaged over 30 runs. In Single Persistence, we use Saw
Signatures of length 100. In Multi-Persistence, 10x10 grids yielded the best
results.

We compute classification results on ten datasets, but only six of those have
been used in the five benchmarked methods. As such, we report multi-
persistence results for the five datasets in Table 4, and rest of the datasets
in 5.

###  6.3 Results

####  6.3.1 Single Persistence

Single Persistence results are shown in Table 2. Each row corresponds to a
model that uses Saw Signatures from the associated Betti functions only. We
report the best-performing filtration function for each dataset for Bettis 0
and 1. Betweenness and Closeness filtrations yield the most accurate
classification results in four and five cases, respectively. Curvature methods
Ollivier and Forman are computationally costly, and generally yield
considerably lower accuracy values. Although curvature methods yield the best
results for Protein, the closeness filter reaches similar (i.e., $0.698$ and
$0.695$) accuracy values for the dataset. We advise against using curvature
methods due to their computational costs.

Table 2: Single-persistence classification results for best performing (in
accuracy) filtrations. The  N(%) column of the table reports the percentage of
graph instances that can be classified by using the associated model. Some
Betti 1 models cannot classify all graph instances, because these graphs do
not form Betti 1 values (i.e., 1-dimensional holes do not exist).
dataset | filt | betti | acc | N(%)
---|---|---|---|---
IMDBBinary | betw | 0 |  64.8 $\pm$ 3.5 | 100
IMDBBinary | betw | 1 |  65.6 $\pm$ 2.7 | 100
IMDBMulti | clos | 0 |  41.1 $\pm$ 3.4 | 100
IMDBMulti | clos | 1 |  44.2 $\pm$ 3.8 | 98
NCI1 | clos | 0 |  69.8 $\pm$ 1.3 | 100
NCI1 | clos | 1 |  59.9 $\pm$ 1.8 | 82.7
Protein | ollivier | 0 |  70.9 $\pm$ 3.2 | 100
Protein | forman | 1 |  72.2 $\pm$ 3.1 | 100
Reddit5k | betw | 0 |  47.8 $\pm$ 1.1 | 100
Reddit5k | clos | 1 |  41.7 $\pm$ 1.8 | 91.8
RedditBinary | deg | 0 |  86.0 $\pm$ 1.5 | 100
RedditBinary | betw | 1 |  69.4 $\pm$ 2.0 | 86.0
Table 3: Single-persistence classification results for best performing
filtrations (in accuracy) for additional datasets.
dataset | filt | betti | acc | N (%)
---|---|---|---|---
BZR | deg | 0 |  84.3$\pm$3.5 | 100
BZR | deg | 1 |  85.4$\pm$5.2 | 60.4
COX2 | betw | 0 |  77.4$\pm$3.3 | 100
COX2 | ricci | 1 |  82.3$\pm$4.6 | 76.1
DHFR | clos | 0 |  79.8$\pm$2.0 | 100
DHFR | clos | 1 |  70.7$\pm$3.4 | 95.6
FRANKENSTEIN | betw | 0 |  67.0$\pm$1.3 | 100
FRANKENSTEIN | deg | 1 |  72.1$\pm$7.2 | 4.4
Figure 5: Timings. Single filtration costs of the three functions in
experiments. Most dataset filtrations take a few minutes to complete. At most,
2000 RedditBinary and 4999 RedditMulti graphs take 4709 (betw) and 920 (clos)
seconds, respectively.

Figure 6: Running time comparison results for two datasets. (a)Proteins (b)
NCI1. For our method, the cost is for a complete end-to-end run. For other
methods, the costs are for 10 epochs only. Note that in practice, these
methods are run for 1000 epochs or more (Errica et al., 2020). Hence our end-
to-end run times are considerably shorter than those of the five methods.

####  6.3.2 Multi Persistence

Multi-Persistence results are shown in Table 4 for best filtration grids. We
achieved the best results over betweenness, closeness, and degree filtration
pairs across all datasets. On average our method provides accuracy that
differs as little as 3.53% from the five popular graph neural network
solutions. Especially for the large Reddit graphs, our method ranks 3rd among
the methods.

Table 4: Multi-persistence classification accuracy results for best performing filtrations.  MPGFs | DGCNN | GIN | DiffPool | ECC | GraphSage
---|---|---|---|---|---
ImdbB | deg | betw |  67.8 $\pm$ 2.7 | 70.0 | 71.23 | 68.4 | 67.67 | 68.80
ImdbM | betw | clos |  44.3 $\pm$ 3.4 | 47.8 | 48.53 | 45.64 | 43.49 | 47.56
Nci1 | deg | betw |  74.0 $\pm$ 1.6 | 74.4 | 80.04 | 76.93 | 76.18 | 76.02
Protein | betw | clos |  73.8 $\pm$ 2.8 | 75.5 | 73.25 | 73.73 | 72.30 | 73.01
Reddit5K | clos | betw |  51.6 $\pm$ 1.2 | 49.20 | 56.09 | 53.78 | OOR | 50.02
RedditB | deg | clos |  89.0 $\pm$ 0.9 | 87.7 | 89.93 | 89.08 | OOR | 84.32
dataset | Filt1 | Filt2 | Acc
---|---|---|---
BZR | deg | clos | 84.3$\pm$3.5
COX2 | deg | betw | 79.0$\pm$4.0
DHFR | clos | betw | 79.5$\pm$2.3
FRANKENSTEIN | deg | betw | 69.4$\pm$1.3
Table 5: Additional results for multi-persistence classification for most
accurate filtrations. These datasets are not studied by our competitors.

A major advantage of our method is its low computational costs, compared to
those of the five neural network solutions, which can take days. For example,
as Table 4 shows, some methods run out of resources and cannot even complete
the task. In comparison, as Figure 5 shows our method takes a few minutes to
compute filtrations for all but two large Reddit networks. In Multi-
Persistence, filtrations can be further parallelized for each row or column of
the grid to reduce Multi-Persistence time costs.

Comparison: On average, our MPGF takes a few minutes for most datasets, but on
average provides results that differ as little as 3.53% from popular graph
neural network solutions with the caveat that Single Persistence with Betti 1
may not classify all graph instances. We demonstrate the additional results in
Table 3 for Single Persistence and Table 5 for Multi Persistence for the BZR,
COX2, DHFR and FRANKENSTEIN datasets. Except for the DHFR dataset, Betti 1
results are more accurate than Betti 0 results.

##  7 Lessons Learned

Efficiency: Single persistence yields lower (i.e., 1%–6%) accuracy values than
Graph Neural Network solutions, but it is considerably faster to compute. In
general, single persistence can be preferred when the classified graphs are
too large to be handled with Graph Neural networks.

Multi-Filtration: In filtrations, we aimed to capture local (degree,
eccentricity) and global (closeness and betweenness) graph structure around
each node. We hypothesized that multi-persistence would benefit from looking
at a graph from both local and global connections. This intuition proved
correct, but we also observed that in some cases filtrations with global
functions (e.g., betw and clos) reached the highest accuracy values (Table 4).
Especially in datasets with $\geq 3$ classes, global connections may play a
more important role.

Figure 7: Variability. The impact of filter variability on accuracy. Low
variability implies having the same view on the graph from both filters, which
seems to affect performance negatively. The first two data points with 0 and
$0.0007$ variability yield the lowest accuracy in MPGFs.

Variability is good: In Multi-Persistence, filtrations may yield similar
numbers of persistent features across thresholds. This is due to the dominant
impact of edge connectivity in the graph, which causes similar persistent
holes to form even when different filtrations are used. Consider the zero-
dimensional holes created by two filters. We observe that when filters (e.g.,
betw, deg) create different numbers of zero-dimensional holes in all
thresholds, MPFGs tend to learn models that reach higher accuracy. We compute
a variability (variance) of Betti 0 numbers created by two filters to capture
this behavior. Figure 7 shows the relationship between variability and
accuracy. As the variability increases, MPGFs can learn better models.

##  8 Conclusion

In this paper, we have brought a new perspective to persistence homology as a
complexity measure, and with this motivation, we have defined two new
topological summaries in the single and multi-parameter setting. These
summaries turn out to be very interpretable, computationally efficient with a
success rate comparable to the state-of-the-art models. We have only applied
these summaries in a graph classification setting, but multi-persistence has
enough promise to be useful in many complex problems.

## References

  * Adams and Coskunuzer (2021) Henry Adams and Baris Coskunuzer.  Geometric approaches on persistent homology.  _arXiv preprint arXiv:2103.06408_ , 2021.
  * Adams et al. (2017) Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier.  Persistence images: A stable vector representation of persistent homology.  _JMLR_ , 18(1):218–252, 2017.
  * Borgwardt et al. (2005) Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Hans-Peter Kriegel.  Protein function prediction via graph kernels.  _Bioinformatics_ , 21(suppl_1):i47–i56, 2005\.
  * Breiman (2001) Leo Breiman.  Random forests.  _Machine learning_ , 45(1):5–32, 2001.
  * Bubenik (2015) Peter Bubenik.  Statistical topology using persistence landscapes.  _JMLR_ , 16:77–102, 2015.
  * Cai and Wang (2020) Chen Cai and Yusu Wang.  Understanding the power of persistence pairing via permutation test.  _arXiv preprint arXiv:2001.06058_ , 2020.
  * Carrière and Blumberg (2020) Mathieu Carrière and Andrew Blumberg.  Multiparameter persistence image for topological machine learning.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Carrière et al. (2020) Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda.  Perslay: A neural network layer for persistence diagrams and new graph topological signatures.  In _AISTATS_ , pages 2786–2796, 2020.
  * Chen et al. (2015) Tianqi Chen, Tong He, Michael Benesty, Vadim Khotilovich, Yuan Tang, Hyunsu Cho, et al.  Xgboost: extreme gradient boosting.  _R package version 0.4-2_ , 1(4), 2015.
  * Chen et al. (2020) Yen-Chi Chen, Adrian Dobra, et al.  Measuring human activity spaces from gps data with density ranking and summary curves.  _Annals of Applied Statistics_ , 14(1):409–432, 2020.
  * Cheung et al. (2013) Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau.  Fast matrix rank algorithms and applications.  _Journal of the ACM (JACM)_ , 60(5):1–25, 2013\.
  * Chung and Lawson (2019) Yu-Min Chung and Austin Lawson.  Persistence curves: A canonical framework for summarizing persistence diagrams.  _arXiv preprint arXiv:1904.07768_ , 2019.
  * Di Fabio and Ferri (2015) Barbara Di Fabio and Massimo Ferri.  Comparing persistence diagrams through complex vectors.  In _ICIAP_ , pages 294–305, 2015.
  * Edelsbrunner and Harer (2010) Herbert Edelsbrunner and John Harer.  _Computational topology: an introduction_.  American Mathematical Soc., 2010.
  * Errica et al. (2020) Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli.  A fair comparison of graph neural networks for graph classification.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=HygDF6NFPB.
  * Hage and Harary (1995) Per Hage and Frank Harary.  Eccentricity and centrality in networks.  _Social networks_ , 17(1):57–63, 1995.
  * Hamilton et al. (2017) William L Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _arXiv preprint arXiv:1706.02216_ , 2017.
  * Harrington et al. (2019) Heather A Harrington, Nina Otter, Hal Schenck, and Ulrike Tillmann.  Stratifying multiparameter persistent homology.  _SIAM Journal on Applied Algebra and Geometry_ , 3(3):439–471, 2019.
  * Hofer et al. (2017) Christoph Hofer, Roland Kwitt, Marc Niethammer, and Andreas Uhl.  Deep learning with topological signatures.  _arXiv preprint arXiv:1707.04041_ , 2017.
  * Hofer et al. (2019) Christoph D Hofer, Roland Kwitt, and Marc Niethammer.  Learning representations of persistence barcodes.  _JMLR_ , 20(126):1–45, 2019.
  * Kersting et al. (2016) Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann.  Benchmark data sets for graph kernels, 2016.  http://graphkernels.cs.tu-dortmund.de.
  * Kusano et al. (2016) Genki Kusano, Yasuaki Hiraoka, and Kenji Fukumizu.  Persistence weighted gaussian kernel for topological data analysis.  In _ICML_ , pages 2004–2013, 2016.
  * Kyriakis et al. (2021) Panagiotis Kyriakis, Iordanis Fostiropoulos, and Paul Bogdan.  Learning hyperbolic representations of topological features.  In _International Conference on Learning Representations_ , 2021.
  * Le and Yamada (2018) Tam Le and Makoto Yamada.  Persistence fisher kernel: A riemannian manifold kernel for persistence diagrams.  In _NIPS_ , pages 10007–10018, 2018.
  * Lesnick (2019a) M Lesnick.  Multiparameter persistence lecture notes, 2019a.  https://www.albany.edu/~ML644186/AMAT_840_Spring_2019/Math840_Notes.pdf.
  * Lesnick (2015) Michael Lesnick.  The theory of the interleaving distance on multidimensional persistence modules.  _Foundations of Computational Mathematics_ , 15(3):613–650, 2015.
  * Lesnick (2019b) Michael Lesnick.  Multiparameter persistence.  In _Lecture Notes_ , 2019b.
  * Mischaikow and Nanda (2013) Konstantin Mischaikow and Vidit Nanda.  Morse theory for filtrations and efficient computation of persistent homology.  _Discrete & Computational Geometry_, 50(2):330–353, 2013.
  * Müller (2007) Meinard Müller.  Dynamic time warping.  _Information retrieval for music and motion_ , pages 69–84, 2007\.
  * Ni et al. (2019) Chien-Chun Ni, Yu-Yao Lin, Feng Luo, and Jie Gao.  Community detection on networks with ricci flow.  _Scientific reports_ , 9(1):1–12, 2019.
  * Noble (2006) William S Noble.  What is a support vector machine?  _Nature biotechnology_ , 24(12):1565–1567, 2006\.
  * Rieck et al. (2019) Bastian Rieck, Christian Bock, and Karsten Borgwardt.  A persistent weisfeiler-lehman procedure for graph classification.  In _ICML_ , pages 5448–5458, 2019.
  * Schomburg et al. (2004) Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg.  Brenda, the enzyme database: updates and major new developments.  _Nucleic acids research_ , 32(suppl_1):D431–D433, 2004.
  * Simonovsky and Komodakis (2017) Martin Simonovsky and Nikos Komodakis.  Dynamic edge-conditioned filters in convolutional neural networks on graphs.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3693–3702, 2017.
  * Thomas (2019) Ashleigh Linnea Thomas.  _Invariants and Metrics for Multiparameter Persistent Homology_.  PhD thesis, Duke University, 2019.
  * Togninalli et al. (2019) Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt.  Wasserstein weisfeiler-lehman graph kernels.  In _NeurIPS_ , pages 6439–6449, 2019.
  * Umeda (2017) Yuhei Umeda.  Time series classification via topological data analysis.  _Information and Media Technologies_ , 12:228–239, 2017\.
  * Vipond (2020) Oliver Vipond.  Multiparameter persistence landscapes.  _Journal of Machine Learning Research_ , 21(61):1–38, 2020.
  * Wale et al. (2008) Nikil Wale, Ian A Watson, and George Karypis.  Comparison of descriptor spaces for chemical compound retrieval and classification.  _Knowledge and Information Systems_ , 14(3):347–375, 2008.
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Yanardag and Vishwanathan (2015) Pinar Yanardag and SVN Vishwanathan.  Deep graph kernels.  In _Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 1365–1374, 2015.
  * Ying et al. (2018) Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec.  Hierarchical graph representation learning with differentiable pooling.  _arXiv preprint arXiv:1806.08804_ , 2018.
  * Zhang et al. (2018) Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen.  An end-to-end deep learning architecture for graph classification.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Zhao and Wang (2019) Qi Zhao and Yusu Wang.  Learning metrics for persistence-based summaries and applications for graph classification.  In _NeurIPS_ , pages 9859–9870, 2019.
  * Zieliński et al. (2019) Bartosz Zieliński, Michał Lipiński, Mateusz Juda, Matthias Zeppelzauer, and Paweł Dłotko.  Persistence bag-of-words for topological data analysis.  In _IJCAI_ , pages 4489–4495, 2019.
  * Zomorodian and Carlsson (2005) Afra Zomorodian and Gunnar Carlsson.  Computing persistent homology.  _Discrete & Computational Geometry_, 33(2):249–274, 2005.