Suppose that $\overline{N}$ is a coproduct of $N$ with itself, with associated
maps $N\xrightarrow[]{\pi_{i}}\overline{N}$, $i=1,2$ for the left and right
factors. Applying the universal property to the diagram
$N\xrightarrow[]{\mathbbm{1}_{N}}N\xleftarrow[]{\mathbbm{1}_{N}}N$, together
with Lemma 23, implies that $\pi_{1}=\pi_{2}$. One then derives a
contradiction by applying the universal property to the diagram
$N\xrightarrow[]{\mathbbm{1}_{N}}N\xleftarrow[]{\mu\otimes\mu}N$.

To see that $\mathcal{N}_{\mathrm{c}}$ does not have pullbacks, let $N$ be a
measure network whose underlying set has at least 2 points, and suppose that
its network function $\omega$ is bounded above by $R\geq 0$. Let $N_{R}$ be
the one-point measure network defined earlier in the proof. Then there is a
unique expansive morphism $N\xrightarrow[]{\pi}N_{R}$. A pullback for the
diagram $N\xrightarrow[]{\pi}N_{R}\xleftarrow[]{\pi}N$ would be a product of
$N$ with itself, and we showed above that no such object exists. A similar
argument illustrates the lack of pushouts.

In summary, the similarity in structure between $\mathcal{N}_{\mathrm{m}}$ and
the category of sets $\mathcal{S}$ means that it enjoys many basic limit
constructions. However, the ambivalence of expansive maps to topological and
measure structure may be seen as undesirable; for example, this causes the
issue with functoriality for the $q$-clique expansion and $q$-line graph maps
when $q<\infty$, and this category is unable to capture the notion of strong
isomorphism. On the other hand, the additional measure-theoretic structure of
$\mathcal{N}_{\mathrm{c}}$ leads to obstructions to many limit constructions.
An interesting future direction of research will be to explore explore
alternative category structures on measure networks which balance structure
preservation and richness.

##  5 Computational Examples

In this section, we demonstrate our computational framework on various
analysis tasks involving hypergraph matching, comparison, and simplification.

###  5.1 Implementation Details

To compute the distance between two hypergraphs, we use the Python3
implementation of CO-Optimal Transport (COOT) due to Redko et al. Redko et al.
(2020) 222https://github.com/PythonOT/COOT. They give an efficient algorithm
for efficiently approximating the solution to the optimization problem (4) in
the finite case, when $p=2$. Computation of $d_{\mathcal{H},2}$ is a nonconvex
bilinear programming problem Gallo and Ülkücü (1977), and is NP-Hard to solve
exactly. According to Redko et al. (2020), the overall computational
complexity of their algorithm is $O(\min((n+n^{\prime})dd^{\prime}+n^{\prime
2}n,(d+d^{\prime})nn^{\prime}+d^{\prime 2}d))$, where $n=\lvert X\rvert$,
$n^{\prime}=\lvert X^{\prime}\rvert$, $d=\lvert Y\rvert$ and
$d^{\prime}=\lvert Y^{\prime}\rvert$. The dependencies of the COOT
implementation include _Numpy_ , _Matplotlib_ , and _Python Optimal Transport
(POT)_ Flamary et al. (2021) 333https://pythonot.github.io/. Our main
computational contributions are new processing algorithms for modeling
hypergraphs as measure hypernetworks amenable to the COOT algorithm.

###  5.2 Soft Matching Between Hypergraphs

We first expand on Example 1 and give a refined method for generating a
measure hypernetwork from a combinatorial hypergraph.

Before we begin, we recall various choices available when modeling a
hypergraph as a hypernetwork. Here we suppose that we are given a hypergraph
$(X,Y)$ and are tasked with obtaining a hypernetwork $(X,\mu,Y,\nu,\omega)$.

First we consider $\mu$. Let $x\in X$. Two simple choices for $\mu(x)$ are as
follows:

  * •

Uniform: $\mu(x):={1}/{\lvert X\rvert}.$

  * •

Normalized node degree: $\mu(x):={\mathrm{deg}(x)}/{\sum_{x^{\prime}\in
X}\mathrm{deg}(x^{\prime})}.$

Next we consider $\nu$. Let $y\in Y$. Two simple choices for $\nu(y)$ are as
follows:

  * •

Uniform: $\nu(y):={1}/{\lvert Y\rvert}.$

  * •

Normalized sum of node degree:
$\nu(y):={\widehat{\nu}(y)}/{\sum_{y^{\prime}\in
Y}\widehat{\nu}(y^{\prime})}$, where $\widehat{\nu}(y):=\sum_{x\in
y}\mathrm{deg}(x).$

The simplest choice for $\omega$ is to use the incidence function
$\omega(x,y)=1$ if $x\in y$ and $0$ otherwise. Describing more interesting
choices for $\omega$ requires some setup. Recall the line graph construction
in Section 3.1: a line graph $\mathsf{L}(H)$ (in this section, $\mathsf{L}(H)$
will be used generically as a stand in for several specific line graph
constructions) is constructed from a combinatorial hypergraph $H=(X,Y)$ by
taking the node set of $\mathsf{L}(H)$ to be $Y$, and adding an edge
$\\{y,y^{\prime}\\}$ whenever $y\cap y^{\prime}\neq\emptyset$—this coincides
with the $\mathsf{L}_{\infty}$ line graph map defined in Section 3.6.
Moreover, $\mathsf{L}(H)$ may be weighted—our line graph maps $\mathsf{L}_{q}$
for $q\in[1,\infty)$ define weighted variants of the line graph.

In the hypergraph modeling task discussed here, the line graph map is only an
intermediate step and we have found empirically that different weighting
schemes are more useful. To assign a hypernetwork function to $H$, we will use
a metric structure on the line graph, where it is more useful to intuitively
think of edge weights as conductances rather than impedances—that is,
hyperedges that share more nodes are considered as more similar and should
thus receive a smaller edge weight. With this in mind, we use edge weights
corresponding to _intersection size_ ${1}/{\lvert y\cap y^{\prime}\rvert}$ (if
$y\cap y^{\prime}\neq\emptyset$) or _reciprocal Jaccard index_ ${\lvert y\cup
y^{\prime}\rvert}/{\lvert y\cap y^{\prime}\rvert}$. Then, we may define the
hypernetwork function as
$\omega(x,y):=\min\\{d_{\mathsf{L}(H)}(y^{\prime},y):x\in y^{\prime}\\}$,
where $d_{\mathsf{L}(H)}$ denotes the shortest path metric with respect to the
chosen edge weights. In summary, we consider three choices for $\omega$:

  * •

Intersection size: $\omega$ is the shortest path distance based on the
intersection size-weighted line graph.

  * •

Jaccard index: $\omega$ is the shortest path distance based on the reciprocal
Jaccard index-weighted line graph.

  * •

Incidence: $\omega(x,y)=1$ if $x\in y$ and $0$ otherwise.

######  Example 7 (Hypergraph Matching Toy Examples).

Figure 4 shows two toy examples of matching between nodes and hyperedges of
hypergraphs, computed simultaneously via the co-optimal transport distance
$d_{\mathcal{H},2}$. Hypergraphs are visualized using the hybrid convex
hull/incidence graph method of Figure 1. Both examples utilize node degree-
based probability measures and Jaccard shortest path hypernetwork functions.

Figure 4: Two toy examples of hypergraph matching.

The coupling matrices after running the co-optimal transport optimization on
the first pair of hypergraphs $H$ and $H^{\prime}$ are shown below. The 1st
example in (a)-(b) has optimal coupling matrices $\xi$ for hyperedge coupling
(rows indexed by hyperedges of $H$ and columns indexed by hyperedges of
$H^{\prime}$) and $\pi$ for node coupling (rows indexed by nodes of $H$ and
columns indexed by nodes of $H^{\prime}$).

$\xi=\begin{bmatrix}0.158&0&0\\\ 0&0.211&0\\\ 0.115&0&0.254\\\
0&0.062&0.201\end{bmatrix}\;\pi=\begin{bmatrix}0.111&0&0&0&0\\\
0&0.111&0&0&0\\\ 0&0&0.143&0&0.079\\\ 0&0.032&0&0.286&0.016\\\
0.032&0&0&0&0.190\end{bmatrix}.$

In Figure 4(a), we illustrate the hypergraph matching $H\to H^{\prime}$, where
the visual encodings capture information from the hyperedge coupling matrix
$\xi$. Colored nodes (with white rim) and colored convex hulls in the hybrid
visualization for $H$ represent the four hyperedges of $H$. The co-optimal
transport results in a color transfer such that colored nodes in $H^{\prime}$
capture information from the hyperedge coupling matrix $\xi$ via pie charts.
For instance, the 3rd column of $\xi$ shows that hyperedges $c$ (red) and $d$
(purple) in $H$ are both matched to the hyperedge $c$ in $H^{\prime}$ with
non-zero probabilities. Therefore node $c$ in $H^{\prime}$ is visualized by a
pie chart in both red and purple. The convex hull associated with hyperedge
$c\in H^{\prime}$, on the other hand, carries the color of the hyperedge $c\in
H$ with the highest coupling probability. Similarly in Figure 4(b), node
coupling between $H$ and $H^{\prime}$ is visualized via a color transfer and
pie charts. For example, both node 2 and node 4 in $H$ are matched with node 2
in $H^{\prime}$ with non-zero probability, most likely due to the symmetry of
these hypergraphs. Figure 4(c)-(d) show another visualization of a hypergraph
matching.

Figure 5: Multiscale reduction via iterated nerve graphs.

###  5.3 Multiscale Graph Matching

In this section, we give a use case of hypergraph matching for multiscale
graph matching. Multiscale structure has implicitly been shown to be
instrumental in providing efficient proxies for Gromov-Wasserstein matching
through low-rank approximations Scetbon et al. (2022), quantization Chowdhury
et al. (2021), and iterated clustering approaches Xu et al. (2019a); Blumberg
et al. (2020). While these aforementioned works have focused on demonstrating
performance benchmarks against a well-defined problem of matching point clouds
or graphs, we focus on demonstrating a new use case toward _summarized_ graph
matching.

Our method proceeds by first constructing multiple levels of simplification
for two graphs, and then performing graph matching within each level of
simplification _while maintaining compatibility across levels of
simplification_. Note that unless explicitly enforced, compatibility may be
broken by the symmetries of the problem (e.g. a left limb being matched to a
left limb at one scale and to a right limb at another scale). Hypergraph
matching is specifically used to maintain the compatibility condition.
Informally, we are summarizing our graph matching at multiple levels of
granularity while maintaining consistency across summaries.

The first stage of our method is inspired by a construction known as the
_multiscale mapper_ Dey et al. (2016). We begin by recalling some concepts
related to the _mapper_ Singh et al. (2007) construction. Given a topological
space $X$ and a finite open cover $\mathcal{U}=\\{U_{i}\\}_{i\in I}$ of $X$,
that is $X\subseteq\bigcup_{i\in I}U_{i}$, the _nerve_ of $\mathcal{U}$ is the
simplicial complex $\mathsf{N}(\mathcal{U})$ with vertices given by the index
set $I$ and subsets $\\{i_{0},\ldots,i_{k}\\}\subseteq I$ forming
$k$-simplices whenever $U_{i_{0}}\cap\ldots\cap U_{i_{k}}\neq\emptyset$, for
any $k\geq 1$. The _nerve graph_ is simply the 1-skeleton of this simplicial
complex, and it is easier to compute in practice than the nerve complex
because it involves checking only pairwise intersections. Next, given
topological spaces $X$ and $Y$, a finite open cover $\mathcal{V}$ of $Y$, and
a continuous map $f:X\to Y$, consider a pullback cover of $X$, defined as
$f^{-1}(\mathcal{V})$. The mapper construction is simply the nerve of such a
pullback cover, denoted as $\mathsf{N}(f^{-1}(\mathcal{V}))$. In practice, one
often considers only the nerve graph, and refers to the simplified
construction as a _mapper graph_.

The mapper graph provides a representation of data at a _single_ scale
controlled by the scale of the cover $\mathcal{V}$. The multiscale mapper was
devised as a method for relating mapper graphs constructed at different
scales. In this setup, the key idea is that of a map of covers. Let
$\mathcal{U}=\\{U_{i}\\}_{i\in I},\mathcal{V}=\\{V_{j}\\}_{j\in J}$ be two
covers of a topological space $Z$. Then a set map $\xi:I\to J$ is a _map of
covers_ if $U_{i}\subseteq V_{\xi(i)}$ for all $i\in I$. The multiscale mapper
construction utilizes the observation Dey et al. (2016) that a map of covers
induces a map of pullback covers, and thus induces a map between mapper graphs
at different scales.

#### Step 1: multiscale reduction

With the mapper context in place, we now present the first stage of our
multiscale graph matching method. Given a graph $G=(V,E)$, we first use a
data-driven method (described below) to compute an overlapping cover
$\mathcal{U}=\\{U_{i}\\}_{i\in I}$ of $V$ and its nerve graph $G_{1}$. We then
repeat the process on the new nerve graph $G_{1}$, obtaining a reduced graph
at each step of the iteration, $G_{1},G_{2},\dots$, etc. We terminate the
reduction process after the number of nodes in the graph falls below a
threshold $n_{\alpha}$. For a multiscale graph matching problem, we compute
these reductions for each graph and pass the collections of nerve graphs into
the second stage of the method.

To compute a data-driven cover, we use a procedure involving the graph heat
kernel. The heat kernel and related spectral constructions are well-known for
capturing shape signatures Reuter et al. (2006); Mémoli (2011b), and thus help
produce semantically meaningful cover elements. Moreover, heat kernels have
been shown to produce superior performance in GW graph matching applications
Chowdhury and Needham (2021), and thus we are able to recycle computational
elements across both stages of our multiscale graph matching method. Our exact
procedure is described next.

Fix a graph $G$ with node set $V$. Initialize a set of visited nodes
$U=\emptyset$ as well as a cover $Y=\emptyset$. Also fix a node $x\in
V\setminus U$. Let $L$ denote the normalized graph Laplacian of $G$. We first
compute its eigendecomposition $\Phi\Lambda\Phi^{T}$. Computing a full
eigendecomposition is an $O(n^{3})$ operation, so for large graphs we limit
runtime by using Lanczos iterations to obtain extremal eigenpairs and using
these to construct a low-rank factorization of $L$. In our experiments, we
have found the top 300 largest eigenvalues and their eigenvectors to provide
good results while keeping runtimes low (e.g. below 1 minute for a graph
having over 15K nodes). Next, note that for a given $t>0$, we may compute the
graph heat kernel $K^{t}:=\operatorname{exp}(-tL)$ as
$K^{t}=\Phi\operatorname{exp}(-t\Lambda)\Phi^{T}$. Given a Dirac delta vector
$\delta_{x}$, the matrix-vector product $v:=K^{t}\delta_{x}$ can be
interpreted as the diffusion of a unit mass of heat out from $x$ within time
$t$, and essentially has the form of a Gaussian centered at $x$. Following the
idea of full width at half maximum (FWHM), we mark the set
$\\{v\geq\max(v)/2\\}$ as visited, and set $U\leftarrow
U\cup\\{v\geq\max(v)/2\\}$. Additionally we set $Y\leftarrow
Y\cup\\{\\{v\geq\max(v)/4\\}\\}.$ We then select another $x\in V\setminus U$
and iterate the procedure until $U=V$. Note that the use of $U$ prevents us
from sampling graph nodes too densely, and the extra $1/2$ multiplicative
factor in $Y$ allows us to enforce overlaps between cover elements. Also note
that the choice of $t$ is difficult to prescribe _a priori_. In our
experiments, we found $t:=\log_{10}(|V|)$ to produce good results. Note from
this choice that we utilize different values of $t$ at each reduction step.

In summary, the multiscale reduction step iterates a particular technique of
reducing a graph that factors through a process of computing covers and taking
nerves, as illustrated in Figure 5. The reduced graphs and the cover relations
are then passed to the hypergraph matching step.

Algorithm 1 Cyclic Block Coordinate Descent for Multiscale Matching

Initialize $\pi_{i},\xi_{i}$ for all $0\leq i\leq k$, $maxIter\in\mathbb{N}$,
$n\leftarrow 0$

while $n<maxIter$ do

// Left-to-right sweep

for $i=0,1,\ldots,k$ do

// Matrix formulation of co-optimal transport cost

// $\odot$ denotes elementwise square

// $\mathbf{1}_{*},\mathbf{1}_{\star}$ have dimensions needed to match third
matrix

$M\leftarrow(\omega_{i}^{\odot
2})^{T}\mu_{i}\mathbf{1}_{*}^{T}+\mathbf{1}_{\star}(\mu^{\prime}_{i})^{T}(\omega^{\prime}_{i})^{\odot
2}-2\omega^{T}\pi_{i}\omega^{\prime}$

$\xi_{i}\leftarrow OT(\nu_{i},\nu_{i}^{\prime},M)$

if $i<k$ then

$\pi_{i+1}\leftarrow\xi_{i}$

end if

end for

// Right-to-left sweep

for $i=k,k-1,\ldots,0$ do

// $\mathbf{1}_{*},\mathbf{1}_{\star}$ have new dimensions as needed to match
third matrix

$M\leftarrow\omega_{i}^{\odot
2}\nu_{i}\mathbf{1}_{*}^{T}+\mathbf{1}_{\star}(\nu^{\prime}_{i})^{T}((\omega^{\prime}_{i})^{\odot
2})^{T}-2\omega\xi_{i}(\omega^{\prime})^{T}$

$\pi_{i}\leftarrow OT(\mu_{i},\mu_{i}^{\prime},M)$

if $i>0$ then

$\xi_{i-1}\leftarrow\pi_{i}$

end if

end for

$n\leftarrow n+1$

end while

return $\pi_{i}$ (and optionally $\xi_{i}$) for all $0\leq i\leq k$

#### Step 2: Hypergraph matching

We now describe the graph matching stage of our method. A cover
$\mathcal{U}=\\{U_{i}\\}_{i\in I}$ of a topological space $X$ defines a
hypergraph with nodes given by $X$ and hyperedges given by $\mathcal{U}$. Thus
each cover used in the construction above defines a hypergraph. Consequently,
the iterated nerve construction described above provides a sequence of
hypergraphs where the hyperedges of one hypergraph comprise the nodes of the
next. We will first describe our method for graph matching that utilizes these
hypergraphs, and then provide some comparison to alternative methods.

Fix a method for converting a hypergraph to a hypernetwork. Let $G,G^{\prime}$
be two graphs. We first apply the iterated nerve construction described above
for obtaining sequences of hypergraphs, and then the method for passing from
hypergraphs to hypernetworks. Let $H_{0},H_{1},\ldots H_{k}$ denote the
sequence of hypernetworks arising from $G$ (by letting $H_{0}:=G$), where each
$H_{i}$ represents a tuple $(X_{i},\mu_{i},Y_{i},\nu_{i},\omega_{i})$. The
hyperedges of $H_{i}$ form the nodes of $H_{i+1}$ for each $0\leq i<k$. Next,
let $H^{\prime}_{0},H^{\prime}_{1},\ldots,H^{\prime}_{k}$ denote the sequence
of hypernetworks arising from $G^{\prime}$. We then solve a variant of a co-
optimal transport problem that: (1) simultaneously returns couplings $\pi_{i}$
between $\mu_{i},\mu^{\prime}_{i}$ and $\xi_{i}$ between
$\nu_{i},\nu^{\prime}_{i}$ for all $i$, and (2) enforces the constraint
$\pi_{i+1}=\xi_{i}$ for all $0\leq i<k$. The $\pi_{i}$ yield correspondences
between graph nodes at multiple scales, and the $\pi_{i+1}=\xi_{i}$ condition
enforces consistency between correspondences at different scales. Whereas
standard co-optimal transport Redko et al. (2020) employs a block coordinate
descent scheme to alternate between two variables, we employ cyclic block
coordinate descent to sweep through $2k$ variables to achieve the described
solution. We present our pseudocode in Algorithm 1.

We now describe some design considerations that went into our method. An
alternative form of multiscale graph matching could be carried out by: (1)
iteratively applying any black-box graph simplification method, and (2)
applying any black-box graph matching method along each level of
simplification. The second step of such a method benefits from being
embarrassingly parallel, as the graph matchings across different levels of
simplification are independent. As a consequence of this independence,
however, such a method is unable to enforce consistency of correspondences
across different levels of simplification. In contrast, our method utilizes a
careful choice of a graph simplification method that immediately suggests an
application of hypergraph matching. While hypergraph matching across different
levels of simplification could be solved in a parallel, independent manner, we
choose to create dependence by enforcing the $\pi_{i+1}=\xi_{i}$ condition.
Thus we trade off performance (via parallelization) for consistency of
matching across scales.

Figure 6: Color transfer via multiscale matching, as described by Algorithm 1.
Each graph in the top row is displayed with user-defined node colors. For each
of these graphs, the colors are transferred to the graph below using the
transport matrices returned by Algorithm 1. Note that despite a few mistakes
(appearing as discontinuities in the color gradient), the transport matrices
perform reasonably well in matching semantically related parts.

######  Example 8 (multiscale matching on TOSCA graphs).

We demonstrate the methods described in this section on a pair of Centaur
meshes from the TOSCA dataset Bronstein et al. (2008). We discard the mesh
faces and retain only the underlying graph structures, which comprise over 15K
nodes. In Figure 5 we display these graphs as well as the output of the
multiscale reduction via iterated nerve graphs. We then perform multiscale
matching on these graphs using Algorithm 1. We demonstrate the quality of the
matching in Figure 6. Note that the smaller graphs provide summaries of the
overall matching at multiple levels of granularity.

Parameter analysis. We use our multiscale matching framework to explore how
the choices of parameters ($\mu$, $\nu$, and $\omega$) affect the matching
results. In order to have a ground truth to compare to, we permute the labels
of nodes in a Centaur graph (from the TOSCA dataset), and perform the
hypergraph matching between the original hypergraph and the permuted
hypergraph, where the hypergraph structure is obtained via the method
described in this subsection. If $(\pi,\xi)$ is a true pair of optimal
couplings, then $\pi$ should be induced by the node label permutation; that
is, the optimal coupling should match each node in the graph to itself. The
node-level matching results with different parameter settings are shown in
Figure 7. For each parameter setting, we compute a putatively optimal node
coupling $\pi$ and use it to infer a hard matching from the source to the
target by declaring a node $x$ in the source to be matched to a node $y$ in
the target if $y=\mathrm{argmax}_{y^{\prime}}\pi(x,y^{\prime})$. We then
compute the average graph distance between the nodes in the original graph and
their matched nodes in the permuted graph—theoretically, this should be zero,
but this test measures the effectiveness of gradient descent at finding the
true optimal matching under our various parameter regimes. We repeat the
permutation 100 times. Figure 8 shows the box plot of the average graph
distances for each parameter setting. Our results show that defining $\omega$
via Jaccard index or intersection size (c, d, f, and g) performs better than
taking $\omega$ to be the incidence matrix (b and e). When $\omega$ is Jaccard
index or intersection size, the results are fairly comparable, when $\mu$ and
$\nu$ are either uniform or proportional to degrees. We repeated the above
experiments across a few more meshes and obtained similar observations. The
experimental results in Section 5.4 are generated for $\mu$ and $\nu$ being
proportional to degrees, and $\omega$ being the Jaccard index.

Figure 7: The hypergraph matching between the Centaur graph (a) and a
permutation of the Centaur graph with different parameter settings: (b-d)
$\mu$ and $\nu$ being uniform, and $\omega$ being incidence, Jaccard index,
and intersection size, respectively; (e-g) $\mu$ being normalized node degree,
$\nu$ being normalized sum of node degrees, and $\omega$ being incidence,
Jaccard index, and intersection size, respectively. Figure 8: The distribution
of average graph distances across 100 permutations for each parameter setting:
(b-d) $\mu$ and $\nu$ being uniform, and $\omega$ being incidence, Jaccard
index, and intersection size, respectively; (e-g) $\mu$ being normalized node
degree, $\nu$ being normalized sum of node degrees, and $\omega$ being
incidence, Jaccard index, and intersection size, respectively.

###  5.4 Measure-Preserving Hypergraph Simplification

In this section, we give examples that capture changes in hypernetwork
distances as we apply multiscale hypergraph simplification based on the
framework of Zhou et al. Zhou et al. (2022). Visualizing large hypergraphs is
a challenging task. To reduce visual clutter, we may apply _node collapse_ and
_edge collapse_ to reduce the size of the hypergraph, see Example 4. Zhou et
al. Zhou et al. (2022) relaxed these notions by allowing nodes to be combined
into a _super-node_ if they belong to _almost the same_ set of hyperedges, and
hyperedges to be merged into a _super-hyperedge_ if they share _almost the
same_ set of nodes; these operations are referred to as _node simplification_
and _hyperedge simplification_ , respectively. We follow similar setup from
Zhou et al. (2022) and focus on _measure-preserving_ hyperedge simplification
for our experiments.

To enable hyperedge simplification, we first convert a hypergraph $H$ into a
weighted line graph $\mathsf{L}(H)$, as described above in Section 5.2. Each
edge in $\mathsf{L}(H)$ is weighted by the multiplicative inverse of the
Jaccard index of its end points. We compute a minimum spanning tree of
$\mathsf{L}(H)$, denoted as $T_{\mathsf{L}(H)}$. We then perform a topological
simplification of $H$ based on $T_{\mathsf{L}(H)}$. In particular, we sort
edges in $T_{\mathsf{L}(H)}$ monotonically by increasing weights,
$\\{e_{1},\cdots,e_{k}\\}$. We then simplify the hypergraph $H$ across
multiple scales by merging hyperedges connected by edge $e_{i}\in
T_{\mathsf{L}(H)}$ for each $i$, as $i$ increases from $1$ to $k$. To enable
node simplification, we convert a hypergraph $H$ into a weighted line graph of
its dual (i.e., a _clique expansion_) and apply a similar procedure. We use
the same visual encodings from Example 4, where super-nodes are visualized by
concentric ring glyphs and super-hyperedge are visualized by pie-chart glyphs.

We utilize the co-optimal transport metric $d_{\mathcal{H},2}$ as a heuristic
to determine simplification levels of interest—in prior work, simplification
levels were tuned in a more ad hoc manner. The basic idea is to measure the
distance at each simplification step to the original hypergraph, in order to
find “elbows” at simplification levels of interest. We now explain details of
the co-optimal transport heuristic in the context of a real-world dataset.

######  Example 9 (ActiveDNS Hyperedge Simplification).

Our first example arises from Domain Name System (DNS), a naming database in
which internet domain names are located and translated into IP addresses. In
domain aliasing, multiple domains may map to the same IP address. A single
domain can be assigned to multiple servers for web hosting services, which
correspond to multiple IP addresses. We study a subset of DNS records, from
April 26, 2018, as part of the ActiveDNS dataset Kountouras et al. (2016). We
explore the relationship between domains and IP addresses via an ActiveDNS
hypergraph $H_{0}$, where nodes are IP addresses and hyperedges are domains.

Figure 9: Multiscale simplification of an ActiveDNS hypergraph via hyperedge
simplification, together with changes in hypernetwork distances.

This dataset has been explored as a hypergraph in Zhou et al. (2022), where we
apply a multiscale hyperedge simplification and obtain a sequence of
simplified hypergraphs $H_{1},\dots,H_{29}$ using the procedure described
above, some of which are shown in Figure 9. We now model each $H_{i}$ ($0\leq
i\leq 29$) as a hypernetwork—specifically, we set $\mu$ to be normalized node
degree, $\nu$ to be normalized sum of node degree and $\omega$ to be the
incidence function (see Section 5.2). We compute the hypernetwork distances
$d_{\mathcal{H},2}(H_{0},H_{i})$ between $H_{0}$ and $H_{i}$, shown in Figure
9. To escape from (undesirable) local minima while optimizing the distance, we
use random initialization for the coupling matrices $\pi$ and $\xi$. For each
simplification step, we compute the distance multiple times and plot its
distribution using a box plot. We connect the minimum distance values across
simplification steps with a line plot. In the multiscale hypergraph
simplification framework, edges in $T_{\mathsf{L}(H)}$ with the same weight
value will be merged together simultaneously; thus we only plot the box plot
at unique weight values.

As expected, $d_{\mathcal{H},2}(H_{0},H_{i})$ is shown in the line plot to
increase as we simplify the hypergraph across multiple scales. To determine
the appropriate simplification threshold, we use the “elbow method”, meaning
that we are interested in the simplification step where there is a sharp
increase in distance. The elbow of the $d_{\mathcal{H},2}(H_{0},H_{i})$ curve
is at $H_{24}$. A closer inspection reveals that $H_{24}$ is well-aligned with
a simplified hypergraph manually tuned by an expert from Zhou et al. (2022).
In particular, $H_{24}$ shows a clear separation into two hyperedges $a$ and
$b$ (shown with pie chart glyphs), each of which is the result of merging
domains registered by the same organization. In particular, hyperedge $a$
arises from merging $14$ domains that are variants of “World’s Leading Cruise
Lines” registered to Carnival Corporation. Hyperedge $b$ is the result of
merging, for the most part, $7$ domains registered to Radio Free Europe. $a$
and $b$ then merge into hyperedge $c$ in $H_{26}$. This example provides
initial evidence that the hypergraph distance $d_{\mathcal{H},2}$ may be used
to quantify information loss during hypergraph simplification, thus supporting
parameter tuning.

######  Example 10 (Coauthor Network Hyperedge Simplification).

In the second example, we study a co-authorship dataset from ArnetMiner Tang
et al. (2008) from authors in the field of information-retrieval. We model the
dataset as a hypergraph where each hyperedge represents an author, and nodes
in a hyperedge are researchers who have coauthored at least one paper with the
corresponding author. Figure 10 shows the original hypergraph $H_{0}$ and the
multiscale simplification results. We identify step 217 as the elbow point.
The simplified hypergraph $H_{217}$ shows that David A. Grossman and Ophir
Frieder are in two different super-hyperedges, who are the authors of the book
“Information Retrieval: Algorithms and Heuristics”, an important introductory
textbook in the field. In a subsequent simplified hypergraph ($H_{298}$), the
two super-hyperedges merge into one.

Figure 10: multiscale simplification of a coauthor network hypergraph via
hyperedge simplification, together with changes in hypernetwork distances.

######  Example 11 (Les Misérables Node Simplification).

In the final example, we consider Victor Hugo’s novel Les Misérables from the
Stanford Graph Base Knuth (1994). A set of characters are found within each
volume, book, chapter, and scene of the story. Following the work in Zhou et
al. (2022), we form our hypergraph by considering each character to be a node
and each (volume, book)-pair to be a hyperedge that contains characters that
appear within. We apply multiscale node simplification of this dataset and
identify the hypergraph at step $62$ ($H_{62}$) as the elbow point in the
$d_{\mathcal{H},2}$ curve, see Figure 11. $H_{62}$ is also the one identified
in Zhou et al. (2022) as the manually tuned result, where three super-vertices
are identified: $v_{1}$ contains many peripheral characters in the first
volume who interact with Jean Valjean and Fantine; $v_{2}$ contains all of the
“Friends of the ABC” revolutionary student group, and $v_{3}$ contains Jean
Valjean, Cosette, Javert, Marius, and all of Marius’ family.

Figure 11: Multiscale simplification of a Les Misérables hypergraph via node
simplification, together with changes in hypernetwork distances.

An analysis of the runtime for these experiments is provided in the Appendix
A.3.

##  6 Conclusion

We view this work to be the first in a landscape of new research directions in
hypergraph data analysis. In analogy with the measure network setting, we
expect that future work could further develop the geometry of hypergraph
space, and utilize this study to obtain methods for carrying out geometric
statistics (e.g. Fréchet means) on this space. From the applied perspective,
we expect that future work could focus on applications to machine learning
problems as well as scalability and deployment into deep learning pipelines.
Integrating GW distance computation as part of the hypergraph visual analytic
tool Zhou et al. (2022) would be of interest as well. Finally, the study of
morphisms between network and hypernetwork categories initiated in this work
suggests new questions about obtaining families of Lipschitz maps and further
understanding existing graphification methods from a categorical perspective.
For example, a long term project would be to classify all Lipschitz,
functorial graphifications satisfying reasonable axioms—Proposition 15 gives a
first step in this direction. It will also be interesting to consider metric
and categorical aspects of maps from networks to hypernetworks, or multiscale
versions thereof, building on the already substantial literature on the
category theory of data partitioning.

Acknowledgments This work was partially supported by NSF DMS 2107808, NSF IIS
1910733, NSF IIS 214549 and DOE DE-SC0021015.

## References

  *   * Agarwal et al. (2005) Agarwal, S., Lim, J., Zelnik-Manor, L., Perona, P., Kriegman, D., Belongie, S.: Beyond pairwise clustering. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), vol. 2, pp. 838–845 (2005)
  * Ambrosio et al. (2005) Ambrosio, L., Gigli, N., Savaré, G.: Gradient Flows: in Metric Spaces and in the Space of Probability Measures. Birkhäuser Verlag, Basel, Switzerland (2005)
  * Banerjee et al. (2017) Banerjee, A., Char, A., Mondal, B.: Spectra of general hypergraphs. Linear Algebra and its Applications 1, 14–30 (2017)
  * Bermond et al. (1977) Bermond, J.-C., Heydemann, M.-C., Sotteau, D.: Line graphs of hypergraphs I. Discrete Mathematics 18(3), 235–241 (1977)
  * Blumberg et al. (2020) Blumberg, A.J., Carriere, M., Mandell, M.A., Rabadan, R., Villar, S.: MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data. arXiv preprint arXiv:2001.01666 (2020)
  * Bochner (2020) Bochner, S.: Harmonic Analysis and the Theory of Probability. University of California Press, Berkeley, CA, USA (2020)
  * Borceux (1994) Borceux, F.: Handbook of Categorical Algebra: Basic Category Theory vol. 1. Cambridge University Press, Cambridge, England (1994)
  * Bretto (2013) Bretto, A.: Hypergraph Theory: An Introduction. Springer, New York, NY, USA (2013)
  * Bronstein et al. (2008) Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Numerical Geometry of Non-rigid Shapes. Springer, New York, NY, USA (2008)
  * Carlsson and Mémoli (2008) Carlsson, G., Mémoli, F.: Persistent clustering and a theorem of j. kleinberg. arXiv preprint arXiv:0808.2241 (2008)
  * Carlsson and Mémoli (2010) Carlsson, G., Mémoli, F.: Characterization, stability and convergence of hierarchical clustering methods. Journal of Machine Learning Research 11, 1425–1470 (2010)
  * Carlsson and Mémoli (2013) Carlsson, G., Mémoli, F.: Classifying clustering schemes. Foundations of Computational Mathematics 13(2), 221–252 (2013)
  * Carlsson et al. (2021) Carlsson, G., Mémoli, F., Segarra, S.: Robust hierarchical clustering for directed networks: An axiomatic approach. SIAM Journal on Applied Algebra and Geometry 5(4), 675–700 (2021)
  * Carlsson et al. (2013) Carlsson, G., Mémoli, F., Ribeiro, A., Segarra, S.: Axiomatic construction of hierarchical clustering in asymmetric networks. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5219–5223 (2013)
  * Carlsson et al. (2018) Carlsson, G., Mémoli, F., Ribeiro, A., Segarra, S.: Hierarchical clustering of asymmetric networks. Advances in Data Analysis and Classification 12(1), 65–105 (2018)
  * Cencetti et al. (2021) Cencetti, G., Battiston, F., Lepri, B., Karsai, M.: Temporal properties of higher-order interactions in social networks. Scientific Reports 11(7028) (2021)
  * Chertok and Keller (2010) Chertok, M., Keller, Y.: Efficient high order matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 32(12), 2205–2215 (2010)
  * Chowdhury and Mémoli (2018) Chowdhury, S., Mémoli, F.: Explicit geodesics in Gromov-Hausdorff space. Electronic Research Announcements in Mathematical Sciences 25, 48 (2018)
  * Chowdhury and Mémoli (2019) Chowdhury, S., Mémoli, F.: The Gromov–Wasserstein distance between networks and stable network invariants. Information and Inference: A Journal of the IMA 8(4), 757–787 (2019)
  * Chowdhury and Needham (2020) Chowdhury, S., Needham, T.: Gromov-Wasserstein averaging in a Riemannian framework. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 842–843 (2020)
  * Chowdhury and Needham (2021) Chowdhury, S., Needham, T.: Generalized spectral clustering via Gromov-Wasserstein learning. In: International Conference on Artificial Intelligence and Statistics, pp. 712–720 (2021)
  * Chowdhury et al. (2021) Chowdhury, S., Miller, D., Needham, T.: Quantized Gromov-Wasserstein. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 811–827 (2021)
  * Culbertson et al. (2018) Culbertson, J., Guralnik, D.P., Stiller, P.F.: Functorial hierarchical clustering with overlaps. Discrete Applied Mathematics 236, 108–123 (2018)
  * Culbertson et al. (2016) Culbertson, J., Guralnik, D.P., Hansen, J., Stiller, P.F.: Consistency constraints for overlapping data clustering. arXiv preprint arXiv:1608.04331 (2016)
  * Dey et al. (2016) Dey, T.K., Mémoli, F., Wang, Y.: Multiscale mapper: Topological summarization via codomain covers. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 997–1013 (2016)
  * Dörfler and Waller (1980) Dörfler, W., Waller, D.: A category-theoretical approach to hypergraphs. Archiv der Mathematik 34(1), 185–192 (1980)
  * Duchenne et al. (2011) Duchenne, O., Bach, F., Kweon, I.-S., Ponce, J.: A tensor-based algorithm for high-order graph matching. IEEE transactions on pattern analysis and machine intelligence 33(12), 2383–2395 (2011)
  * Flamary and Courty (2017) Flamary, R., Courty, N.: POT: Python Optimal Transport library (2017)
  * Flamary et al. (2021) Flamary, R., Courty, N., Gramfort, A., Alaya, M.Z., Boisbunon, A., Chambon, S., Chapel, L., Corenflos, A., Fatras, K., Fournier, N., Gautheron, L., Gayraud, N.T.H., Janati, H., Rakotomamonjy, A., Redko, I., Rolet, A., Schutz, A., Seguy, V., Sutherland, D.J., Tavenard, R., Tong, A., Vayer, T.: Pot: Python optimal transport. Journal of Machine Learning Research 22(78), 1–8 (2021)
  * Folland (1999) Folland, G.B.: Real Analysis: Modern Techniques and Their Applications. John Wiley & Sons, Hoboken, NJ, USA (1999)
  * Gallo and Ülkücü (1977) Gallo, G., Ülkücü, A.: Bilinear programming: an exact algorithm. Mathematical Programming 12(1), 173–194 (1977)
  * Gold and Rangarajan (1996) Gold, S., Rangarajan, A.: A graduated assignment algorithm for graph matching. IEEE Transactions on pattern analysis and machine intelligence 18(4), 377–388 (1996)
  * Hell and Nesetril (2004) Hell, P., Nesetril, J.: Graphs and Homomorphisms vol. 28. OUP, Oxford, England (2004)
  * Hendrikson (2016) Hendrikson, R.: Using Gromov-Wasserstein distance to explore sets of networks. Master’s thesis, University of Tartu (2016)
  * Isbell (1964) Isbell, J.R.: Six theorems about injective metric spaces. Commentarii Mathematici Helvetici 39(1), 65–76 (1964)
  * Karoński and Palka (1977) Karoński, M., Palka, Z.: On Marczewski–Steinhaus type distance between hypergraphs. Applicationes Mathematicae 16(1), 47–57 (1977)
  * Klamt et al. (2009) Klamt, S., Haus, U.-U., Theis, F.: Hypergraphs and cellular networks. PLoS Computational Biology 5(e1000385) (2009)
  * Knuth (1994) Knuth, D.E.: The Stanford GraphBase: a Platform for Combinatorial Computing. ACM Press and Addison-Wesley Publishing Company, New York, NY, USA (1994)
  * Konstantinova and Skorobogatov (2001) Konstantinova, E.V., Skorobogatov, V.A.: Application of hypergraph theory in chemistry. Discrete Mathematics 235(1-3), 365–383 (2001)
  * Kountouras et al. (2016) Kountouras, A., Kintis, P., Lever, C., Chen, Y., Nadji, Y., Dagon, D., Antonakakis, M., Joffe, R.: Enabling network security through active DNS datasets. In: International Symposium on Research in Attacks, Intrusions, and Defenses, pp. 188–208 (2016)
  * Lawvere (1962) Lawvere, F.W.: The category of probabilistic mappings. preprint (1962)
  * Lee et al. (2011) Lee, J., Cho, M., Lee, K.M.: Hyper-graph matching via reweighted random walks. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2011)
  * Li et al. (2021) Li, M., Palande, S., Yan, L., Wang, B.: Sketching merge trees for scientific data visualization. arXiv preprint arXiv:2101.03196 (2021)
  * Lin (1994) Lin, C.-L.: Hardness of approximating graph transformation problem. In: Algorithms and Computation: 5th International Symposium, pp. 74–82 (1994)
  * Lotito et al. (2022) Lotito, Q.F., Musciotto, F., Montresor, A., Battiston, F.: Higher-order motif analysis in hypergraphs. Communications Physics 5(79) (2022)
  * Mémoli (2007) Mémoli, F.: On the use of Gromov-Hausdorff distances for shape comparison. Eurographics Symposium on Point-Based Graphics, 81–90 (2007)
  * Mémoli (2011a) Mémoli, F.: Gromov–Wasserstein distances and the metric approach to object matching. Foundations of Computational Mathematics 11(4), 417–487 (2011a)
  * Mémoli (2011b) Mémoli, F.: A spectral notion of Gromov–Wasserstein distance and related methods. Applied and Computational Harmonic Analysis 30(3), 363–401 (2011b)
  * Mutlu and Gürdal (2016) Mutlu, A., Gürdal, U.: Bipolar metric spaces and some fixed point theorems. J. Nonlinear Sci. Appl 9(9), 5362–5373 (2016)
  * Patania et al. (2017) Patania, A., Petri, G., Vaccarino, F.: The shape of collaborations. PJ Data Science 6(18) (2017)
  * Perrone (2021) Perrone, P.: Lifting couplings in wasserstein spaces. arXiv preprint arXiv: 2110.06591 (2021)
  * Peyré et al. (2019) Peyré, G., Cuturi, M., et al.: Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning 11(5-6), 355–607 (2019)
  * Peyré et al. (2016) Peyré, G., Cuturi, M., Solomon, J.: Gromov-Wasserstein averaging of kernel and distance matrices. In: International Conference on Machine Learning, pp. 2664–2672 (2016)
  * Pu and Faltings (2012) Pu, L., Faltings, B.: Hypergraph learning with hyperedge expansion. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 410–425 (2012)
  * Redko et al. (2020) Redko, I., Vayer, T., Flamary, R., Courty, N.: Co-optimal transport. In: Advances in Neural Information Processing Systems, vol. 33, pp. 17559–17570 (2020)
  * Reuter et al. (2006) Reuter, M., Wolter, F.-E., Peinecke, N.: Laplace–Beltrami spectra as ‘Shape-DNA’of surfaces and solids. Computer-Aided Design 38(4), 342–366 (2006)
  * Rodri´ guez (2002) Rodri´ guez, J.A.: On the laplacian eigenvalues and metric parameters of hypergraphs. Linear and Multilinear Algebra 50(1), 1–14 (2002)
  * Scetbon et al. (2022) Scetbon, M., Peyré, G., Cuturi, M.: Linear-time gromov wasserstein distances using low rank couplings and costs. In: International Conference on Machine Learning, pp. 19347–19365 (2022)
  * Schmidt and Ströhlein (2012) Schmidt, G., Ströhlein, T.: Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer, Berlin, Heidelberg (2012)
  * Singh et al. (2007) Singh, G., Mémoli, F., Carlsson, G.E.: Topological methods for the analysis of high dimensional data sets and 3d object recognition. In: The IEEE Eurographics Symposium on Point-Based Graphics (PBG), vol. 2, pp. 091–100 (2007)
  * Smaniotto and Pelillo (2021) Smaniotto, S., Pelillo, M.: Two metrics for attributed hypergraphs. Pattern Recognition Letters 149, 143–149 (2021)
  * Solomon (2018) Solomon, J.: Optimal transport on discrete domains. AMS Short Course on Discrete Differential Geometry (2018)
  * Solomon et al. (2016) Solomon, J., Peyré, G., Kim, V.G., Sra, S.: Entropic metric alignment for correspondence problems. ACM Transactions on Graphics (TOG) 35(4), 1–13 (2016)
  * Sturm (2006) Sturm, K.-T.: On the geometry of metric measure spaces. Acta mathematica 196(1), 65–131 (2006)
  * Sturm (2012) Sturm, K.-T.: The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. arXiv preprint arXiv:1208.0434 (2012)
  * Sun et al. (2008) Sun, L., Ji, S., Ye, J.: Hypergraph spectral learning for multi-label classification. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 668–676 (2008)
  * Surana et al. (2021) Surana, A., Chen, C., Rajapakse, I.: Hypergraph dissimilarity measures. arXiv preprint arXiv:2106.08206 (2021)
  * Tang et al. (2008) Tang, J., Zhang, J., Yao, L., Li, J., Zhang, L., Su, Z.: ArnetMiner: Extraction and miningof academic social networks. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 990–998 (2008)
  * Ulam (1972) Ulam, S.M.: Some ideas and prospects in biomathematics. Annual Review of Biophysics and Bioengineering 1, 227–292 (1972)
  * Umeyama (1988) Umeyama, S.: An eigendecomposition approach to weighted graph matching problems. IEEE transactions on pattern analysis and machine intelligence 10(5), 695–703 (1988)
  * Vayer et al. (2019) Vayer, T., Courty, N., Tavenard, R., Flamary, R.: Optimal transport for structured data with application on graphs. In: International Conference on Machine Learning, pp. 6275–6284 (2019)
  * Villani (2003) Villani, C.: Topics in Optimal Transportation vol. 58. American Mathematical Soc., Providence, Rhode Island (2003)
  * Xia et al. (2021) Xia, X., Yin, H., Yu, J., Wang, Q., Cui, L., Zhang, X.: Self-supervised hypergraph convolutional networks for session-based recommendation. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 4503–4511 (2021)
  * Xu (2020) Xu, H.: Gromov-Wasserstein factorization models for graph clustering. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 6478–6485 (2020)
  * Xu et al. (2019a) Xu, H., Luo, D., Carin, L.: Scalable Gromov-Wasserstein learning for graph partitioning and matching. In: Advances in Neural Information Processing Systems, pp. 3046–3056 (2019a)
  * Xu et al. (2019b) Xu, H., Luo, D., Zha, H., Carin, L.: Gromov-Wasserstein learning for graph matching and node embedding. In: International Conference on Machine Learning, pp. 6932–6941 (2019b)
  * Zeng et al. (2009) Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment 2(1), 25–36 (2009)
  * Zhou et al. (2022) Zhou, Y., Rathore, A., Purvine, E., Wang, B.: Topological simplifications of hypergraphs. IEEE Transactions on Visualization and Computer Graphics (2022)
  * Zien et al. (1999) Zien, J., Schlag, M., Chan, P.K.: Multi-level spectral hypergraph partitioning with arbitrary vertex sizes. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 18, 1389–1399 (1999)

##  Appendix A Appendix

###  A.1 Proofs from Section 2.3

To prove Theorem 1, we begin with a technical result.

######  Lemma 24.

The infimum in the definition of $d_{\mathcal{H},p}$ is realized.

Proof: For a Polish space $X$, let $\mathrm{Prob}(X)$ denote the set of Borel
probability measures over $X$, endowed with the weak topology.

Let
$H=(X,\mu,Y,\nu,\omega),H^{\prime}=(X^{\prime},\mu^{\prime},Y^{\prime},\nu^{\prime},\omega^{\prime})\in\mathcal{H}$.
As $X$ and $X^{\prime}$ are Polish spaces and $\mu$ and $\mu^{\prime}$ are
Borel probability measures, we have that $\mathcal{C}(\mu,\mu^{\prime})$ is
compact in $\mathrm{Prob}(X\times X^{\prime})$, by (Chowdhury and Mémoli,
2019, Lemma 10). It follows that
$\mathcal{C}(\mu,\mu^{\prime})\times\mathcal{C}(\nu,\nu^{\prime})$ is compact
in $\mathrm{Prob}(X\times X^{\prime})\times\mathrm{Prob}(Y\times Y^{\prime})$.

Now we will show that the distortion functional
$\mathrm{dis}_{p}^{\mathcal{H}}=\mathrm{dis}_{H,H^{\prime},p}^{\mathcal{H}}$
is continuous on
$\mathcal{C}(\mu,\mu^{\prime})\times\mathcal{C}(\nu,\nu^{\prime})$, beginning
with the $1\leq p<\infty$ case. Since we are working in Polish spaces with
finite measures, we have that bounded continuous functions are dense. So for
every $n\in\mathbb{N}$, we can choose continuous bounded functions
$\omega_{n}\in L^{p}(\mu\otimes\nu)$ and $\omega^{\prime}_{n}\in
L^{p}(\mu^{\prime}\otimes\nu^{\prime})$ such that the following holds for all
$x\in X,y\in Y,x^{\prime}\in X^{\prime},$ and $y^{\prime}\in Y^{\prime}$:

$\|\omega(x,y)-\omega_{n}(x,y)\|_{L^{p}(\mu\otimes\nu)}\leq\frac{1}{n}\quad\mbox{and}\quad\|\omega^{\prime}(x^{\prime},y^{\prime})-\omega^{\prime}_{n}(x^{\prime},y^{\prime})\|_{L^{p}(\mu^{\prime}\otimes\nu^{\prime})}\leq\frac{1}{n}.$

Then for each $n\in\mathbb{N}$ we define a $n$-distortion functional
$\mathrm{dis}_{p}^{n}:\mathcal{C}(\mu,\mu^{\prime})\times\mathcal{C}(\nu,\nu^{\prime})\longrightarrow\mathbb{R}_{+}$
as
$\mathrm{dis}_{p}^{n}(\pi,\xi):=\|\omega_{n}(x,y)-\omega^{\prime}_{n}(x^{\prime},y^{\prime})\|_{L^{p}(\pi\otimes\xi)}$

Now let us show that the $n$-distortion functional is continuous. Let
$(\pi,\xi)\in\mathcal{C}(\mu,\mu^{\prime})\times\mathcal{C}(\nu,\nu^{\prime})$
and let $(\pi_{m})_{m\in\mathbb{N}}$ and $(\xi_{m})_{m\in\mathbb{N}}$ be
sequences in $\mathcal{C}(\mu,\mu^{\prime})$ and
$\mathcal{C}(\nu,\nu^{\prime})$ that converge to $\pi$ and $\xi$ with respect
to the weak topology. Then

$\displaystyle\lim_{m\rightarrow\infty}\text{dis}_{p}^{n}(\pi_{m},\xi_{m})$
(29) $\displaystyle=\lim_{m\rightarrow\infty}\left(\int_{Y\times
Y^{\prime}}\int_{X\times
X^{\prime}}\lvert\omega_{n}(x,y)-\omega^{\prime}_{n}(x^{\prime},y^{\prime})\rvert^{p}\pi_{m}(dx\times
dx^{\prime})\xi_{m}(dy\times dy^{\prime})\right)^{\frac{1}{p}}$ (30)
$\displaystyle=\left(\int_{Y\times Y^{\prime}}\int_{X\times
X^{\prime}}\lvert\omega_{n}(x,y)-\omega^{\prime}_{n}(x^{\prime},y^{\prime})\rvert^{p}\pi(dx\times
dx^{\prime})\xi(dy\times
dy^{\prime})\right)^{\frac{1}{p}}=\text{dis}_{p}^{n}(\pi,\xi).$ (31)

So we have that $\text{dis}_{p}^{n}$ is sequentially continuous. As
$\mathcal{C}(\mu,\mu^{\prime})\times\mathcal{C}(\nu,\nu^{\prime})\subseteq$
Prob$(X\times X^{\prime}\times Y\times Y^{\prime})$, it is a metrizable space
(Ambrosio et al., 2005, Remark 5.1.1). Therefore, as $\text{dis}_{p}^{n}$ is
sequentially continuous in a metrizable space, it is also continuous.

Now let us see that $\text{dis}_{p}^{n}$ converges to
$\text{dis}^{\mathcal{H}}_{p}$ uniformly. Let
$(\pi,\xi)\in\mathcal{C}(\mu,\mu^{\prime})\times\mathcal{C}(\nu,\nu^{\prime})$
and observe

$\displaystyle\lvert\text{dis}_{p}^{\mathcal{H}}(\pi,\xi)-\text{dis}_{p}^{n}(\pi,\xi)\rvert$
$\displaystyle=\lvert\|\omega(x,y)-\omega^{\prime}(x^{\prime},y^{\prime})\|_{L^{p}(\pi\otimes\xi)}-\|\omega_{n}(x,y)-\omega^{\prime}_{n}(x^{\prime},y^{\prime})\|_{L^{p}(\pi\otimes\xi)}\rvert$
$\displaystyle\leq\|\omega(x,y)-\omega^{\prime}(x^{\prime},y^{\prime})-\omega_{n}(x,y)+\omega^{\prime}_{n}(x^{\prime},y^{\prime})\|_{L^{p}(\pi\otimes\xi)}$
$\displaystyle\leq\|\omega(x,y)-\omega_{n}(x,y)\|_{L^{p}(\mu\otimes\nu)}+\|\omega^{\prime}(x^{\prime},y^{\prime})-\omega^{\prime}_{n}(x^{\prime},y^{\prime})\|_{L^{p}(\mu^{\prime}\otimes\nu^{\prime})}\leq\frac{2}{n}.$

Since $\mathrm{dis}_{p}^{\mathcal{H}}$ is the uniform limit of continuous
functions, it is also continuous. It follows that the infimum in (4) is
realized with a minimal coupling.

For the case in which $p=\infty$, let $(\pi,\xi)$ be couplings in
$\mathcal{C}(\mu,\mu^{\prime})\times\mathcal{C}(\nu,\nu^{\prime})$. As the
domain of $\mathrm{dis}_{p}$,
$\mathcal{C}(\mu,\mu^{\prime})\times\mathcal{C}(\nu,\nu^{\prime})$, is a
subset of Prob$(X\times X^{\prime}\times Y\times Y^{\prime})$, Jensen’s
Inequality shows that if $1\leq p\leq q\leq\infty$, then we have that
$\mathrm{dis}_{p}^{\mathcal{H}}\leq\mathrm{dis}_{q}^{\mathcal{H}}$. Also note
that
$\lim_{p\rightarrow\infty}\mathrm{dis}_{p}^{\mathcal{H}}(\pi,\xi)=\mathrm{dis}_{\infty}^{\mathcal{H}}(\pi,\xi)$.
Then as for $p\in[1,\infty),\mathrm{dis}_{p}^{\mathcal{H}}$ is continuous, and
$\mathrm{dis}_{\infty}^{\mathcal{H}}=\sup\\{\mathrm{dis}_{p}^{\mathcal{H}}\>|\>p\in[1,\infty)\\}$
we have that $\mathrm{dis}_{\infty}^{\mathcal{H}}$ is lower semicontinuous. As
$\mathrm{dis}_{p}^{\mathcal{H}}$ is at least lower semicontinuous over a
compact domain, we have that the infimum in (4) is realized with a minimal
coupling for any $p\in[1,\infty]$.

Proof: [Proof of Theorem 1.]

In the following, let $H=(X,\mu,Y,\nu,\omega)$,
$H^{\prime}=(X^{\prime},\mu^{\prime},Y^{\prime},\nu^{\prime},\omega^{\prime})$
and
$H^{\prime\prime}=(X^{\prime\prime},\mu^{\prime\prime},Y^{\prime\prime},\nu^{\prime\prime},\omega^{\prime\prime})$
be measure hypernetworks.

Pseudometric. Symmetry is obvious. For the triangle inequality, let
$(\pi_{12},\xi_{12})$ and $(\pi_{23},\xi_{23})$ be couplings realizing
$d_{\mathcal{H},p}(H,H^{\prime})$ and
$d_{\mathcal{H},p}(H^{\prime},H^{\prime\prime})$, respectively (see Lemma 24).
Then, using the gluing lemma (see, e.g., (Sturm, 2012, Lemma 1.4)), we
construct a probability measure $\pi$ on $X\times X^{\prime}\times
X^{\prime\prime}$ such that the $X\times X^{\prime}$ marginal of $\pi$ is
$\pi_{12}$, the $X^{\prime}\times X^{\prime\prime}$ marginal is $\pi_{23}$ and
the $X\times X^{\prime\prime}$ marginal is a coupling of $\mu$ and
$\mu^{\prime\prime}$, which we denote $\pi_{13}$. Likewise, we construct a
probability measure $\xi$ on $Y\times Y^{\prime}\times Y^{\prime\prime}$ with
analogous properties—in particular, the $Y\times Y^{\prime\prime}$ marginal is
denoted $\xi_{13}$. Then, using the various marginal conditions, we have

$\displaystyle d_{\mathcal{H},p}(H,H^{\prime\prime})$
$\displaystyle\leq\mathrm{dis}_{p}^{\mathcal{H}}(\pi_{13},\xi_{13})$
$\displaystyle=\|\omega-\omega^{\prime\prime}\|_{L^{p}(\pi\otimes\xi)}$
$\displaystyle\leq\|\omega-\omega^{\prime}\|_{L^{p}(\pi\otimes\xi)}+\|\omega^{\prime}-\omega^{\prime\prime}\|_{L^{p}(\pi\otimes\xi)}$
$\displaystyle=\|\omega-\omega^{\prime}\|_{L^{p}(\pi_{12}\otimes\xi_{12})}+\|\omega^{\prime}-\omega^{\prime\prime}\|_{L^{p}(\pi_{23}\otimes\xi_{23})}=d_{\mathcal{H},p}(H,H^{\prime})+d_{\mathcal{H},p}(H^{\prime},H^{\prime\prime}).$

Complete. We prove completeness by adapting the proof of (Sturm, 2012, Theorem
5.8). Let $H_{n}=(X_{n},\mu_{n},Y_{n},\nu_{n},\omega_{n})$ be a Cauchy
sequence of measure hypernetworks. Then we can choose couplings
$\pi_{n}\in\mathcal{C}(\mu_{n},\mu_{n+1})$ and
$\xi_{n}\in\mathcal{C}(\nu_{n},\nu_{n+1})$ such that
$\mathrm{dis}_{p}^{\mathcal{H}}(\pi_{n},\xi_{n})\to 0$. We then apply the
generalized Gluing Lemma (Sturm, 2012, Lemma 1.4) to
$\pi_{1},\ldots,\pi_{N-1}$ (respectively, to $\xi_{1},\ldots,\xi_{N-1}$) to
construct a measure $\Pi_{N}$ on $\prod_{n=1}^{N}X_{n}$ (respectively,
$\Xi_{N}$ on $\prod_{n=1}^{N}Y_{N}$). We now define $\overline{\mu}$ to be the
projective limit $\varprojlim\Pi_{N}$, a well-defined probability measure on
$\prod_{n=1}^{\infty}X_{n}$ (e.g., Bochner (2020)). Set
$\overline{X}:=\mathrm{supp}(\overline{\mu})$; then $\overline{X}$ is a closed
subspace of a countable product of Polish spaces and is therefore Polish.
Similarly, define $\overline{\nu}:=\varprojlim\Xi_{N}$ and
$\overline{Y}:=\mathrm{supp}(\overline{\nu})$. Next we define
$\Omega_{N}:\overline{X}\times\overline{Y}\to{\mathbb{R}}$ by

$\Omega_{N}((x_{i})_{i=1}^{\infty},(y_{i})_{i=1}^{\infty})=\omega_{N}(x_{N},y_{N}).$

The sequence $(\Omega_{N})_{N=1}^{\infty}$ is a Cauchy sequence in the Banach
space
$L^{p}(\overline{X}\times\overline{Y},\overline{\mu}\otimes\overline{\nu})$,
since

$\|\Omega_{N}-\Omega_{N+1}\|_{L^{p}(\overline{\mu}\otimes\overline{\nu})}=\mathrm{dis}_{p}^{\mathcal{H}}(\pi_{N},\xi_{N})\to
0,$

and we define $\overline{\omega}$ to be its limit. Each $\omega_{N}$ is
essentially bounded, so it follows that $\overline{\omega}$ is as well.
Setting
$\overline{H}:=(\overline{X},\overline{\mu},\overline{Y},\overline{\nu},\overline{\omega})$,
we have $\overline{H}\in\mathcal{H}$ and

$d_{\mathcal{H},p}(H_{n},\overline{H})\leq\|\omega_{n}-\overline{\omega}\|_{L^{p}(\overline{\mu}\otimes\overline{\nu})}\to
0.$

Geodesic. Finally, we show that the metric on $\mathcal{H}$ modulo weak
isomorphism is geodesic. For $H\in\mathcal{H}$, let $[H]$ denote its weak
isomorphism class. We will construct an explicit geodesic between any two weak
isomorphism classes of hypernetworks $[H]$ and $[H^{\prime}]$, following the
main idea of the proof of (Sturm, 2012, Theorem 3.1). Let
$\pi\in\mathcal{C}(\mu,\mu^{\prime})$ and
$\xi\in\mathcal{C}(\nu,\nu^{\prime})$ be optimal couplings (which exist, by
Lemma 24). Consider the path $\gamma:[0,1]\to\mathcal{H}$ defined by

$\gamma(t)=\left(\mathrm{supp}(\pi),\pi,\mathrm{supp}(\xi),\xi,\omega_{t}\right),$
(32)

where

$\omega_{t}((x,x^{\prime}),(y,y^{\prime}))=(1-t)\omega(x,y)+t\omega^{\prime}(x^{\prime},y^{\prime}).$

Observe that $\gamma(0)\in[H]$ and $\gamma(1)\in[H^{\prime}]$; indeed,
coordinate projection maps $\phi:X\times X^{\prime}\to X$ and $\psi:Y\times
Y^{\prime}\to Y$ define a basic weak isomorphism $\gamma(0)\to H$ and a
similar construction works for $\gamma(1)\to H^{\prime}$. To show that
$\gamma$ defines a geodesic in $[\mathcal{H}]$, it suffices to show that for
all $0\leq s\leq t\leq 1$,

$d_{\mathcal{H},p}(\gamma(s),\gamma(t))\leq(t-s)d_{\mathcal{H},p}(H,H^{\prime})$
(33)

(see, e.g., (Chowdhury and Mémoli, 2018, Lemma 1.3)). One can show by an
elementary computation that

$\mathrm{dis}_{\gamma(s),\gamma(t),p}^{\mathcal{H}}(\pi,\xi)^{p}\leq(t-s)^{p}\mathrm{dis}_{H,H^{\prime},p}^{\mathcal{H}}(\pi,\xi)^{p}$

for any pair of couplings $(\pi,\xi)$—indeed, this holds because linear
interpolations are geodesics in $L^{p}$ spaces—and (33) follows.

######  Remark 12.

The proof of the triangle inequality above uses the notion of gluing, which
appears in our category theoretic framework in Section 3. The coupling
$\pi_{13}$ constructed above is written as $\pi_{13}=\pi_{23}\bullet\pi_{13}$
in the notation from Section 3. A byproduct of our proof is the following
useful fact: for measure networks $N,N^{\prime},N^{\prime\prime}$ and
couplings $\pi\in\mathcal{C}(\mu,\mu^{\prime})$ and
$\pi^{\prime}\in\mathcal{C}(\mu^{\prime},\mu^{\prime\prime})$, we have

$\mathrm{dis}_{p}^{\mathcal{N}}(\pi^{\prime}\bullet\pi)\leq\mathrm{dis}_{p}^{\mathcal{N}}(\pi^{\prime})+\mathrm{dis}_{p}^{\mathcal{N}}(\pi).$

A similar statement holds in the measure hypernetwork setting.

###  A.2 Proofs of Technical Lemmas from Section 3.6

Proof: [Proof of Lemma 12] We will prove the statement for hypernetworks, as
the network case is similar. Let $\pi$ and $\xi$ be couplings realizing
$d_{\mathcal{H},p}(H,H^{\prime})$ (such couplings always exist, see Lemma 24
in the appendix). Define

$\overline{X}=\mathrm{supp}(\pi)\subset X\times
X^{\prime},\quad\overline{\mu}=\pi\mid_{\overline{X}},\quad\overline{Y}=\mathrm{supp}(\xi)\subset
Y\times Y^{\prime},\quad\overline{\nu}=\xi\mid_{\overline{Y}}$

and define hypernetwork functions
$\overline{\omega},\overline{\omega}^{\prime}:\overline{X}\times\overline{Y}\to{\mathbb{R}}$
as follows. Let $p_{Z}:X\times X^{\prime}\to Z$ be coordinate projection for
$Z\in\\{X,X^{\prime}\\}$ and let $p_{Z}:Y\times Y^{\prime}\to Z$ be coordinate
projection for $Z\in\\{Y,Y^{\prime}\\}$. The hypernetwork functions are then
given by

$\overline{\omega}=\omega\circ(p_{X}\times
p_{Y})\qquad\mbox{and}\qquad\overline{\omega}^{\prime}=\omega^{\prime}\circ(p_{X^{\prime}}\times
p_{Y^{\prime}}).$

The coordinate projections are measure-preserving, due to the marginal
constraints of $\pi$ and $\xi$, and the pair $(p_{X},p_{Y})$ (respectively,
$(p_{X^{\prime}},p_{Y^{\prime}})$) therefore defines a basic weak isomorphism
(Definition 6) from $\overline{H}$ to $H$ (respectively,
$\overline{H^{\prime}}$ to $H^{\prime}$).

To see (12), observe first that
$d_{\mathcal{H},p}(H,H^{\prime})=d_{\mathcal{H},p}(\overline{H},\overline{H^{\prime}})$
follows by weak isomorphism. To see the other equality for $p\in[1,\infty)$,
we have

$\displaystyle d_{\mathcal{H},p}(H,H^{\prime})^{p}$
$\displaystyle=\int_{Y\times Y^{\prime}}\int_{X\times
X^{\prime}}\lvert\omega(x,y)-\omega^{\prime}(x^{\prime},y^{\prime})\rvert^{p}\;\pi(dx\times
dx^{\prime})\xi(dy\times dy^{\prime})$
$\displaystyle=\int_{\overline{Y}}\int_{\overline{X}}\lvert\omega(x,y)-\omega^{\prime}(x^{\prime},y^{\prime})\rvert^{p}\;\overline{\mu}(dx\times
dx^{\prime})\overline{\nu}(dy\times dy^{\prime}),$

since the value of the integral isn’t changed by replacing the full spaces
with supports of the measures. Using the change of variables
$\overline{x}=(x,x^{\prime})\in\overline{X}$ and
$\overline{y}=(y,y^{\prime})\in\overline{Y}$, the above is equal to

$\int_{\overline{Y}}\int_{\overline{X}}\lvert\overline{\omega}(\overline{x},\overline{y})-\overline{\omega}^{\prime}(\overline{x},\overline{y})\rvert^{p}\;\overline{\mu}(d\overline{x})\overline{\nu}(d\overline{y})=\|\overline{\omega}-\overline{\omega}^{\prime}\|_{L^{p}(\overline{\mu}\otimes\overline{\nu})}^{p}.$

For the $p=\infty$ case, a similar change of variables gives

$\displaystyle d_{\mathcal{H},\infty}(H,H^{\prime})$
$\displaystyle=\inf\\{c\mid\lvert\omega(x,y)-\omega^{\prime}(x^{\prime},y^{\prime})\rvert\leq
c\mbox{ for $\pi\otimes\xi$-almost every $(x,y,x^{\prime},y^{\prime})$}\\}$
$\displaystyle=\inf\\{c\mid\lvert\overline{\omega}(\overline{x},\overline{y})-\overline{\omega}^{\prime}(\overline{x},\overline{y})\rvert\leq
c\mbox{ for $\overline{\mu}\otimes\overline{\xi}$-almost every
$(\overline{x},\overline{y})$}\\}$
$\displaystyle=\|\overline{\omega}-\overline{\omega}^{\prime}\|_{L^{\infty}(\overline{\mu}\times\overline{\nu})}.$

Proof: [Proof of Lemma 13] By Proposition 2, it suffices to show that if there
is a basic weak isomorphism $(\phi,\psi)$ from $H$ to $H^{\prime}$, then
$\phi$ defines a basic weak isomorphism of
$N:=\mathsf{Q}_{q}(H)=(X,\mu,\omega_{\mathsf{Q}_{q}})$ and
$N^{\prime}:=\mathsf{Q}_{q}(H^{\prime})=(X^{\prime},\mu^{\prime},\omega_{\mathsf{Q}_{q}}^{\prime})$.
By an argument similar to the one used to prove functoriality in Theorem 11,
the assumption that $(\phi,\psi)$ is a basic weak isomorphism implies that for
$\mu\otimes\mu\otimes\nu$-almost every $(x_{1},x_{2},y)\in X\times X\times Y$,
$\min_{j}\omega(x_{j},y)=\min_{j}\omega^{\prime}(\phi(x_{j}),\psi(y))$. In the
$q<\infty$ case, we deduce that for $\mu\otimes\mu$ almost every
$(x_{1},x_{2})$,

$\displaystyle\omega_{\mathsf{Q}_{q}}^{\prime}(\phi(x_{1}),\phi(x_{2}))^{p}$
$\displaystyle=\int_{Y^{\prime}}\min_{j}\omega^{\prime}(\phi(x_{j}),y^{\prime})^{p}\;\nu^{\prime}(dy^{\prime})$
$\displaystyle=\int_{Y}\min_{j}\omega^{\prime}(\phi(x_{j}),\psi(y))^{p}\;\nu(dy)$
(34) $\displaystyle=\int_{Y}\min_{j}\omega(x_{j},y)^{p}\;\nu(dy)$
$\displaystyle=\omega_{\mathsf{Q}_{q}}(x_{1},x_{2})^{p},$

where (34) follows by the change-of-variables formula (using that $\psi$ is
measure-preserving). The $q=\infty$ case follows by a limiting argument.

Proof: [Proof of Lemma 14] This is (Mémoli, 2011a, Theorem 5.1 (d)), in the
metric measure space setting. The proof goes through in the measure network
setting.

###  A.3 Runtime Analysis for Hypergraph Simplification

We ran the experiments using the following computing infrastructures:

  * •

CPU models: 32 Intel Xeon Silver 4108 CPU 1.80GHz cores (HT)

  * •

Amount of memory: 132GB of RAM

  * •

Operating system: OpenSUSE Leap 15.3 (x86_64)

Table 1 summarizes the size of each dataset, including the number of
hyperedges and the number of vertices contained in each hypergraph, the
runtime of computing the barcode, the runtime of performing the simplification
(simp.) at the first step, and the maximum runtime among all simplification
steps for each dataset. Figure 12 demonstrates the distribution and the
minimum runtime of computing the hypernetwork distances
$d_{\mathcal{H},2}(H_{0},H_{i})$ at each step $i$. Table 2 summarizes the
minimum runtime at the first step as well as the minimum, maximum, mean, and
median values of the minimum runtime of computing the distances across all
simplification steps for each dataset.

The largest dataset is the Coauthor Network dataset, which contains 506 nodes
and 491 hyperedges. Therefore, this dataset gives rise to the largest runtime
of computing the barcode, simplified hypergraphs, and hypernetwork distances.
The maximum runtime among all steps is around 5 seconds for the Coauthor
Network dataset.

Data | #v | #e | Barcode | Simp. (first step) | Simp. (maximum)
---|---|---|---|---|---
DNS | 57 | 30 | 0.0014 | 0.1130 | 0.1130
CN | 506 | 491 | 0.1317 | 4.0484 | 4.1506
LM | 80 | 45 | 0.0041 | 0.2025 | 0.2438
Table 1: The number of vertices (#v), the number of hyperedges (#e), the runtime (in seconds) of computing the barcode, the runtime (in seconds) of performing the simplification at the first step, and the maximum runtime (in seconds) among all simplification steps in datasets ActiveDNS (DNS), Coauthor Network (CN), and Les Misérables (LM). Figure 12: Runtime in computing the GW distances for activeDNS (a), Les Misérables (b) and Coauthor Network (c) datasets. The $x$-axes display the simplification steps. The $y$-axes are time recorded in seconds. Data | First step | Minimum | Maximum | Mean | Median
---|---|---|---|---|---
DNS | 0.0299 | 0.0171 | 0.0299 | 0.0236 | 0.0216
CN | 3.5320 | 1.4722 | 4.5847 | 2.9872 | 3.3658
LM | 0.0513 | 0.0249 | 0.0514 | 0.0399 | 0.0406
Table 2: The minimum runtime (in seconds) at the first step as well as the
minimum, maximum, mean, and median values of the minimum runtime (in seconds)
of computing the distances across all simplification steps for each dataset.