---
abstract: 'We study the question of reconstructing a weighted, directed network up to isomorphism from its motifs. In order to tackle this question we first relax the usual (strong) notion of graph isomorphism to obtain a relaxation that we call weak isomorphism. Then we identify a definition of distance on the space of all networks that is compatible with weak isomorphism. This global approach comes equipped with notions such as completeness, compactness, curves, and geodesics, which we explore throughout this paper. Furthermore, it admits global-to-local inference in the following sense: we prove that two networks are weakly isomorphic if and only if all their motif sets are identical, thus answering the network reconstruction question. Further exploiting the additional structure imposed by our network distance, we prove that two networks are weakly isomorphic if and only if certain essential associated structures—the skeleta of the respective networks—are strongly isomorphic.'
address: 'Department of Mathematics, The Ohio State University, 100 Math Tower, 231 West 18th Avenue, Columbus, OH 43210. Phone: (302)831-7753, Fax: (302)831-7753 '
author:
- Samir Chowdhury and Facundo Mémoli
bibliography:
- 'biblio.bib'
title: The Metric Space of Networks
---

Introduction
============

One of the prevalent hypotheses used in systems biology and network analysis is that complex networks are assembled from simpler subnetworks called *motifs* @shen2002network [@sporns2004motifs; @alon2007network; @milo2002network; @alon2006introduction]. For example, motifs have been used to characterize transcription regulation networks, protein-protein interactions, and to simulate network datasets that resemble real brain networks across a variety of structural measures @sporns2004motifs [@yeger2004network; @konagurthu2008origin]. These considerations motivate the following theoretical question:

\[q:1\] *Is it possible to reconstruct, up to isomophism, a network from the knowledge of its subnetworks?*

In this paper we provide an answer to the question above. The motivation for our answer to Question (\[q:1\]) is rooted in the metric space literature, specifically a construction called a *curvature class* due to Mikhail Gromov @gromov-book [1.19+]. Given a metric space $(X,d_X)$ and $n\in {\mathbb{N}}$, the $n$th curvature class of $X$, denoted $K_n(X)$, is the collection of $n\times n$ distance matrices that can be realized by $n$-tuples of points in $X$. Gromov proved that two compact metric spaces $(X,d_X)$ and $(Y,d_Y)$ are *isometric* (i.e. related by a distance-preserving bijection) if and only if $K_n(X) = K_n(Y)$ for all $n\in {\mathbb{N}}$ @gromov-book [3.27$\tfrac{1}{2}$]. Thus the knowledge of (the countably many) curvature classes is sufficient to recover the full structure of the metric space (which may be uncountable). Our strategy is to prove an analogous result in the setting of general networks.

In order to be able to reason about and eventually answer Question (\[q:1\]), we first need to clarify several concepts. For example: what is a sufficiently general definition of network, what is a suitable notion of isomorphism between two networks, and how can we relate networks to metric spaces?

Networks may have asymmetric edge relations and data attached to each node, so intuitively, they should be represented as edge-weighted directed graphs with self-loops, where the edge weights are allowed to be arbitrary real numbers. Such a model for a network can alternatively be expressed as a square matrix of real values, i.e. the adjacency matrix of the graph. Thus when dealing with finite networks, a reasonable model for a network is a pair $(X,{\omega}_X)$, where $X$ is a finite set of *nodes* and ${\omega}_X: X \times X {\rightarrow}{\mathbb{R}}$ is a *weight function*, i.e. the edge weights. Real-world networks that arise in computational settings are necessarily finite, but when they are very large, they may be modeled as objects with infinite cardinality. To accommodate this possibility while still maintaining some control over the underlying node set, we choose to model a general network as follows:

\[defn:nets\] A network is a pair $(X,{\omega}_X)$ where $X$ is a first countable topological space and ${\omega}_X:X\times X {\rightarrow}{\mathbb{R}}$ is a continuous function. The collection of all networks is denoted ${\mathcal{N}}$.

We also consider the subcollection of *compact networks*, which satisfy the additional restriction that the underlying set is compact. We denote the collection of all compact networks by ${\mathcal{CN}}$, and the subcollection of finite networks by ${\mathcal{F}\mathcal{N}}$. Notice that such a network model is a generalization of a metric space: for $(X,{\omega}_X)$ to be a metric space, ${\omega}_X$ needs to satisfy additional assumptions such as symmetry and triangle inequality, and the underlying topology is assumed to be the metric topology generated by open balls in $X$.

Recall that a space is first countable if each point in the space has a countable local basis (see @counterexamples [p. 7] for more details). First countability is a technical condition guaranteeing that when the underlying topological space of a network is compact, it is also sequentially compact.

Interestingly, the model that we have just described has already appeared in the applied mathematics literature, at least in the setting of finite networks. In recent years, various authors have used the model of ${\mathcal{F}\mathcal{N}}$ in applying topological data analysis methods such as *hierarchical clustering* and *persistent homology* to network data @carlsson2013axiomatic [@clust-net; @nets-asilo; @dowker-arxiv; @dowker-asilo; @pph]. An additional ingredient in each of these papers was a notion of *network distance* ${d_{\mathcal{N}}}$ between objects in ${\mathcal{F}\mathcal{N}}$. However, until recently the theoretical foundations of this network distance were unknown. In @dn-part1, we generalized the network distance ${d_{\mathcal{N}}}$ to all of ${\mathcal{N}}$, studied its computational aspects, and developed a notion of isomorphism called *weak isomorphism* that turned out to be compatible with ${d_{\mathcal{N}}}$. These notions of ${d_{\mathcal{N}}}$ and weak isomorphism are key players in our search for a motif reconstruction theorem. In this paper, we continue laying down the foundations of ${d_{\mathcal{N}}}$. In particular, we complete our answer to the following question, which we had raised and partially answered in our previous work:

\[q:2\] What is the "continuous limit" of a convergent sequence of finite networks?

Returning to the question about motif reconstruction, recall that one natural notion of isomorphism in the network setting is the standard notion of *graph isomorphism*, which we call *strong isomorphism* in our context. Specifically, two networks $(X,{\omega}_X)$ and $(Y,{\omega}_Y)$ are said to be *strongly isomorphic*, denoted $X \cong^s Y$, if they are related by a weight-preserving bijection, i.e. a map ${\varphi}:X {\rightarrow}Y$ such that ${\omega}_X(x,x') = {\omega}_Y({\varphi}(x),{\varphi}(x'))$ for all $x,x' \in X$. The notion of weak isomorphism is a relaxation of this condition.

\[defn:wisom\] Two networks $(X,{\omega}_X)$ and $(Y,{\omega}_Y)$ are *weakly isomorphic*, denoted $X\cong^w Y$, if there exists a set $V$ and surjections ${\varphi}_X:V {\rightarrow}X,\; {\varphi}_Y:V {\rightarrow}Y$ such that: $${\omega}_X({\varphi}_X(v),{\varphi}_X(v')) = {\omega}_Y({\varphi}_Y(v),{\varphi}_Y(v')) \quad
\text{for all } v,v'\in V.$$

With regards to subnetworks: we organize all the motifs present in a given network $(X,{\omega}_X)$ into *motif sets*. For each $n \in {\mathbb{N}}$, the $n$-motif set is the collection of $n\times n$ weight matrices obtained from $n$-tuples of points in $X$, possibly with repetition. We formalize this next.

\[Motif set\]\[defn:motif\] For each $n\in \mathbb{N}$ and each $(X,{\omega}_X) \in {\mathcal{CN}}$, define $\Psi^n_X: X^n {\rightarrow}{\mathbb{R}}^{n \times n}$ to be the map $(x_1, \cdots, x_n) \mapsto {({\!}({{\omega}_X(x_i,x_j)})\!)}_{i,j=1}^n$, where the ${({\!}({})\!)}$ notation refers to the square matrix associated with the sequence. Note that $\Psi^n_X$ is simply a map that sends each sequence of length $n$ to its corresponding weight matrix. Let ${\mathcal}{C}({\mathbb{R}}^{n\times n})$ denote the closed subsets of ${\mathbb{R}}^{n\times n}$. Then let ${\mathrm{M}}_n:{\mathcal{CN}}{\rightarrow}{\mathcal}{C}({\mathbb{R}}^{n\times n})$ denote the map defined by $$(X,{\omega}_X)\mapsto {\left\{\Psi^n_X(x_1,\ldots, x_n) : x_1,\ldots,x_n\in X\right\}}.$$ We refer to ${\mathrm{M}}_n(X)$ as the $n$-motif set of $X$. Notice that the image of ${\mathrm{M}}_n$ is closed in ${\mathbb{R}}^{n\times n}$ because each coordinate is the continuous image of the compact set $X\times X$ under ${\omega}_X$, hence the image of ${\mathrm{M}}_n$ is compact in ${\mathbb{R}}^{n\times n}$ and hence closed.

It is easy to come up with examples of networks that share the same motif sets, but are not strongly isomorphic. Instead, we hypothesize that if two networks share the same motif sets, then they are weakly isomorphic, i.e. are at ${d_{\mathcal{N}}}$-distance zero. In pursuing this idea, we develop the theory of ${d_{\mathcal{N}}}$ throughout this paper, ultimately answering both Questions (\[q:1\]) and (\[q:2\]). At the same time, we find a surprising answer to the following question relating weak and strong isomorphism:

\[q:3\] Does weak isomorphism between two networks imply that some essential substructures are strongly isomorphic?

Contributions and organization of the paper
-------------------------------------------

In this paper, we develop the theory of the network distance ${d_{\mathcal{N}}}$, which lies at the core of Questions (\[q:1\]-\[q:3\]) posed above. We prove that the metric space of weak isomorphism classes of compact networks endowed with ${d_{\mathcal{N}}}$ is complete (§\[sec:completeness\]). Thus Question (\[q:2\]) can be answered as follows: a convergent sequence of finite networks limits to a compact network, i.e. a compact, first countable topological space equipped with a continuous weight function. We show that the pseudometric space $({\mathcal{CN}},{d_{\mathcal{N}}})$, while not compact, contains many precompact families (§\[sec:completeness\]), and moreover is geodesic (§\[sec:geodesic\]).

We define a construction for any network called a "skeleton". Using properties of skeleta, we show that for two compact networks (with some additional topology assumptions), the following are equivalent: weak isomorphism between the two networks, strong isomorphism between their skeleta, and equality of their motif sets. In other words, such networks can be recovered from their motif sets. This forms our answer to Question (\[q:1\]) (§\[sec:compact\]).

Results used from prior work
----------------------------

We adopt our definition of a network as a first countable topological space $X$ with a continuous weight function ${\omega}_X:X\times X {\rightarrow}{\mathbb{R}}$ from @dn-part1. There we also proved the following result about the pseudometric structure of $({\mathcal{CN}},{d_{\mathcal{N}}})$:

\[Weak isomorphism in compact networks\] \[thm:weak-isom-cpt\] The collection of compact networks ${\mathcal{CN}}$ is a pseudometric space when equipped with ${d_{\mathcal{N}}}$. Moreover, for any $X,Y \in {\mathcal{CN}}$, we have ${d_{\mathcal{N}}}(X,Y) = 0$ if and only if $X$ and $Y$ are weakly isomorphic.

We already exploited motif sets to provide computable lower bounds for ${d_{\mathcal{N}}}$ in @dn-part1. The main result enabling this is the *stability theorem* that we explain next. For each $n \in {\mathbb{N}}$, we write $d_n$ to denote the Hausdorff distance between closed subsets of ${\mathbb{R}}^{n\times n}$ equipped with the $\ell^\infty$ metric.

\[Stability of motif sets\] \[thm:motif-stab\] Let $(X,{\omega}_X),(Y,{\omega}_Y) \in {\mathcal{CN}}$. For any $n \in {\mathbb{N}}$, $$d_n({\mathrm{M}}_n(X),{\mathrm{M}}_n(Y)) \leq 2{d_{\mathcal{N}}}(X,Y).$$

Related literature
------------------

In the graph theory literature, the problem of deciding how much information is encoded in the subgraph structure of a graph has a long history. Boutin and Kemper outline some of these efforts in @boutin2007lossless, and also prove, using combinatorial methods, that a large class of graphs can be fully determined from the distribution of their subtriangles. In our language, this is analogous to saying that ${\mathrm{M}}_3(X)={\mathrm{M}}_3(Y)$ implies $X=Y$, where equality is in the sense of graph isomorphism. We move away from the combinatorial approach, and reformulate the problem to find when ${\mathrm{M}}_3(X)={\mathrm{M}}_3(Y)$ implies ${d_{\mathcal{N}}}(X,Y)=0$, where ${d_{\mathcal{N}}}$ is a certain (pseudo)metric on the space of all networks. This converts the content of Question (\[q:1\]) to a question about finding an appropriate network similarity measure.

The network distance ${d_{\mathcal{N}}}$ at the core of this paper is structurally based on the Gromov-Hausdorff distance @gromov-book [@gromov1981structures] proposed by Mikhail Gromov in the early 1980s. Beyond its origins in metric geometry @burago [@petersen2006riemannian], the Gromov-Hausdorff distance between metric spaces has found applications in the context of shape and data analysis @dgh-sgp [@dghlp-focm; @dgh-props; @clust-um]. The close analogy with ${d_{\textrm{GH}}}$ highlights some of the merits of our definition of ${d_{\mathcal{N}}}$: it yields a very natural completion of the space of weak isomorphism classes of finite networks, and admits geodesics interpolating between any two networks. The analogous results in the setting of compact metric spaces can be found in @petersen2006riemannian [@ivanov2015gromov; @dgh-note].

Notation and basic terminology
------------------------------

We will denote the cardinality of any set $S$ by ${\mathrm{card}}(S)$. For any set $S$ we denote by $F(S)$ the collection of all finite subsets of $S$. For a topological space $X$, we write ${\mathcal}{C}(X)$ to denote the closed subsets of $X$. For a given metric space $(Z,d_Z)$, the Hausdorff distance between two nonempty subsets $A,B \subseteq Z$ is given by: $$d_{{\operatorname{H}}}^Z(A,B) = \max{\left\{\sup_{a\in A}\inf_{b \in B}d_Z(a,b), \sup_{b \in B}\inf_{a \in A}d_Z(a,b)\right\}}.$$ We will denote the non-negative reals by ${\mathbb{R}}_+$. The all-ones matrix of size $n \times n$ will be denoted $\mathbbm{1}_{n \times n}$. Given a function $f:X {\rightarrow}Y$ between two sets $X$ and $Y$, the image of $f$ will be denoted ${\operatorname{im}}(f)$ or $f(X)$. Given a topological space $X$ and a subset $A\subset X$, we will write $\overline{A}$ to denote the closure of $A$.

Networks: Examples and Constructions {#sec:networks}
====================================

Examples of motif sets {#sec:net-first-examples}
----------------------

We begin with some examples of networks and their motif sets. We also provide examples of infinite networks that fall within the framework of ${\mathcal{N}}$ and ${\mathcal{CN}}$.

\[every node/.style=<span>font=</span>\] (1) at (0,0)<span>$p$</span>; (1) edge \[loop above, min distance=10mm,in=0,out=60\] node\[right\]<span>${\alpha}$</span>(1);

\(2) at (3,0)<span>$p$</span>; (3) at (5,0)<span>$q$</span>; (2) edge \[loop left, min distance = 10mm\] node\[above\]<span>${\alpha}$</span>(2); (3) edge \[loop right, min distance = 10mm\] node\[below\]<span>$\beta$</span>(3); (2) edge \[bend left\] node\[above\]<span>${\delta}$</span> (3); (3) edge \[bend left\] node\[below\]<span>${\gamma}$</span> (2);

at (0,-1)<span>$N_1({\alpha})$</span>; at (4,-1)<span>$N_2({\Omega})$</span>;

\[ex:simple-networks\] We first introduce networks with one or two nodes (see Figure \[fig:simplenets\]).

-   A network with one node $p$ can be specified by $\alpha \in {\mathbb{R}}$, and will be denoted by $N_1(\alpha)$. We have $N_1({\alpha})\cong^s N_1({\alpha}')$ if and only if ${\alpha}={\alpha}'$.

-   A network with two nodes will be denoted by $N_2(\Omega)$, where $\Omega = {\left(\begin{smallmatrix}
                {\alpha} & {\delta}\\
                    {\gamma} & {\beta}
                         \end{smallmatrix}\right)}\in {\mathbb{R}}^{2\times 2}$. Given $\Omega,\Omega'\in {\mathbb{R}}^{2\times 2}$, $N_2(\Omega)\cong^s N_2(\Omega')$ if and only if there exists a permutation matrix $P$ of size $2\times 2$ such that $\Omega' = P\,\Omega\, P^T$.

-   Any $k$-by-$k$ matrix $\Sigma\in {\mathbb{R}}^{k\times k}$ induces a network on $k$ nodes, which we refer to as $N_k(\Sigma)$. Notice that $N_k(\Sigma)\cong^s N_\ell(\Sigma')$ if and only if $k=\ell$ and there exists a permutation matrix $P$ of size $k$ such that $\Sigma'=P\,\Sigma\,P^T.$

\[rem:surj\] Already from Figure \[fig:simplenets\], it is evident that if $\Omega = {\left(\begin{smallmatrix}
            {{\alpha}} & {{\alpha}}\\
                {{\alpha}} & {{\alpha}}
                     \end{smallmatrix}\right)}$, then $N_1({\alpha})$ and $N_2({\alpha})$ are weakly isomorphic. This can be generalized as follows. Let $(X,\omega_X),(Y,\omega_Y) \in {\mathcal{CN}}$ and suppose $f:X\rightarrow Y$ is a surjective map such that $\omega_X(x,x')=\omega_Y(f(x'),f(x'))$ for all $x,x'\in X$. Then $X$ and $Y$ are weakly isomorphic, i.e. $X \cong^w Y$. This result follows from Definition \[defn:wisom\] by: (1) choosing $V = X$, (2) letting ${\varphi}_X$ be the identity map, and (3) letting ${\varphi}_Y=f$.

\[ex:conf-sets\] Consider the two networks from Figure \[fig:simplenets\]. Then we have ${\mathrm{M}}_1(N_2(\Omega)) = \{\alpha,\beta\}$ and $${\mathrm{M}}_2(N_2(\Omega))=\big\{{\left(\begin{smallmatrix}
            {\alpha} & {\alpha}\\
                {\alpha} & {\alpha}
                     \end{smallmatrix}\right)},{\left(\begin{smallmatrix}
            {\beta} & {\beta}\\
                {\beta} & {\beta}
                     \end{smallmatrix}\right)},{\left(\begin{smallmatrix}
            {\alpha} & {\delta}\\
                {\gamma} & {\beta}
                     \end{smallmatrix}\right)},{\left(\begin{smallmatrix}
            {\beta} & {\gamma}\\
                {\delta} & {\alpha}
                     \end{smallmatrix}\right)}\big\}, 
\qquad {\mathrm{M}}_2(N_1({\alpha})) = {\left\{{\left(\begin{smallmatrix}
            {{\alpha}} & {{\alpha}}\\
                {{\alpha}} & {{\alpha}}
                     \end{smallmatrix}\right)}\right\}}.$$

In line with our discussion in the introduction, we wish to examine the extent to which motif sets determine the structure of a network. To proceed pedagogically, we begin with the following:

\[strong isomorphism and motif sets\]\[conj-strong\] Let $X, Y \in {\mathcal{CN}}$. Then ${\mathrm{M}}_n(X) = {\mathrm{M}}_n(Y)$ for all $n \in {\mathbb{N}}$ if and only if $X \cong^s Y.$

This approach is not immediately fruitful: by setting $\Omega:= {\left(\begin{smallmatrix}
            {{\alpha}} & {{\alpha}}\\
                {{\alpha}} & {{\alpha}}
                     \end{smallmatrix}\right)}$ in Example \[ex:conf-sets\] (also see Remark \[rem:surj\]), we see that $N_1({\alpha})$ and $N_2(\Omega)$ have the same motif sets, but are clearly not related by a bijection. The strong isomorphism approach does work with some strong additional assumptions (Theorem \[thm:conj-generic\]). More importantly, the strong isomorphism approach works in the setting of compact metric spaces, and making it work in the network setting provides motivation for some of our main results.

The failure of motif sets in characterizing strongly isomorphic networks leads one to hope that weakly isomorphic networks might be an appropriate object of study.

\[Weak isomorphism and motif sets\]\[conj-weak\] Let $X, Y \in {\mathcal{CN}}$. Then ${\mathrm{M}}_n(X) = {\mathrm{M}}_n(Y)$ for all $n  \in {\mathbb{N}}$ if and only if $X \cong^w Y.$

One of our main results is that the preceding statement is in fact true. The approach via weak isomorphism will be the focus of §\[sec:compact\].

We conclude this section by showing that with additional assumptions of *genericity*, the motif sets contain all the information of a finite network up to strong isomorphism. To say that a finite network $(X,\omega_X)$ is *generic* means ${\omega}_X(x_1,x_1') = {\omega}_X(x_2,x_2')$ if and only if $x_1=x_2$ and $x_1' = x_2'$.

\[thm:conj-generic\] Let $X, Y \in {\mathcal{F}\mathcal{N}}$. Suppose $X$ and $Y$ are generic, and ${\mathrm{M}}_n(X) = {\mathrm{M}}_n(Y)$ for each $n \in {\mathbb{N}}$. Then $X \cong^s Y$.

\[Proof of Theorem \[thm:conj-generic\]\] Since $X$ and $Y$ are generic, we have ${\mathrm{card}}(X) = {\mathrm{card}}({\mathrm{M}}_1(X))$ and ${\mathrm{card}}(Y) = {\mathrm{card}}({\mathrm{M}}_1(Y))$. Thus ${\mathrm{card}}(X) = {\mathrm{card}}(Y)$. Let $n = {\mathrm{card}}(X) = {\mathrm{card}}(Y)$. For any $X \in {\mathcal{F}\mathcal{N}}$ with ${\mathrm{card}}(X) = n$, define: $$\begin{aligned}
D(X) &= {\left\{\Psi^n_X[(x_i)_{i=1}^n] : x_i \neq x_k \text{ if } i \neq k\right\}}\\
R(X) &= {\left\{\Psi^n_X[(x'_i)_{i=1}^n] : \exists j \neq k, x'_j = x'_k\right\}}\end{aligned}$$

Then we may write ${\mathrm{M}}_n(X) = D(X) \cup R(X)$, and ${\mathrm{M}}_n(Y) = D(Y) \cup R(Y).$

In particular, ${\mathrm{M}}_n(X) = {\mathrm{M}}_n(Y)$. We claim that $D(X) = D(Y)$, and thus $R(X) = R(Y)$. Let $M \in D(X)$. By genericity, each entry in $M$ is distinct. Also, $M \in {\mathrm{M}}_n(Y)$. So $M = \Psi^n_Y[(y_i)]$ for some sequence in $Y$. Suppose $M \in R(Y)$. Then there exist $j \neq k$ such that $y_j = y_k$. Thus the term ${\omega}_Y(y_j,y_k)$ ($={\omega}_Y(y_k,y_j) = {\omega}_Y(y_k, y_k) = {\omega}_Y(y_j,y_j)$) appears in $M$ with multiplicity greater than 1. This is a contradiction, so $M \in D(Y)$. By a symmetric argument, we conclude $D(X) = D(Y)$. Next, let $(x_i)_{i=1}^n$ be a sequence of distinct elements in $X$. Note that $(x_i)$ includes each element of $X$. Since $D(X) = D(Y)$, there exists $(y_i)_{i=1}^n$ a sequence of distinct elements such that $\Psi^n_X[(x_i)] = \Psi^n_X[(y_i)].$ Now define a bijection ${\varphi}:X {\rightarrow}Y$ by ${\varphi}(x_i) = y_i$. This gives us the required (strong) isomorphism.

Interested readers should look at @boutin2007lossless, where Boutin and Kemper give conditions under which complete, undirected, weighted graphs with self-loops are determined by the distributions of their three-node subgraphs. In our language, the result by Boutin and Kemper would be similar to the implication ${\mathrm{M}}_3(X) = {\mathrm{M}}_3(Y) \implies X \cong^s Y$.

Examples of infinite networks: the directed circles {#sec:dir-s1}
---------------------------------------------------

<span>0.4</span>

\[every node/.style=<span>font=, minimum size=1cm</span>\]

(0,0) circle (1.8); at (0,0)<span>$({\vec{\mathbb{S}}}^1,{{\omega}_{{\vec{\mathbb{S}}}^1}})$</span>;

<span>0.2</span>

The collections ${\mathcal{N}}$, ${\mathcal{CN}}$, and ${\mathcal{F}\mathcal{N}}$ contain the collections of all metric spaces, compact metric spaces, and finite metric spaces, respectively. It is interesting to identify networks in these families that are not just metric spaces. In §\[sec:net-first-examples\], we provided some examples of finite, asymmetric networks. Here we provide examples of infinite, asymmetric networks in both the compact and noncompact cases. These constructions appear in detail in @dn-part1. See Figure \[fig:dir-s1\] for an illustration.

Define ${\vec{\mathbb{S}}}^1:= {\left\{ e^{i\theta}\in {\mathbb{C}}: \theta\in [0,2\pi)\right\}}.$ For any ${\alpha},{\beta}\in [0,2\pi)$, define ${\vec{d}}({\alpha},{\beta}):= {\beta}- {\alpha}\bmod 2\pi$, with the convention ${\vec{d}}({\alpha},{\beta}) \in [0,2\pi)$. Then ${\vec{d}}({\alpha},{\beta})$ is the counterclockwise geodesic distance along the unit circle in ${\mathbb{C}}$ from $e^{i{\alpha}}$ to $e^{i{\beta}}$. Next for each $e^{i{\theta}_1}, e^{i{\theta}_2} \in {\vec{\mathbb{S}}}^1$, define $${\omega}_{{\vec{\mathbb{S}}}^1}(e^{i\theta_1},e^{i\theta_2}):= {\vec{d}}(\theta_1,\theta_2).$$

Now fix $\rho \geq 1$. For each $e^{i{\theta}_1}, e^{i{\theta}_2} \in {\vec{\mathbb{S}}}^1$, define $${{\omega}_{{\vec{\mathbb{S}}}^1 \!\!,\rho}}(e^{i\theta_1},e^{i\theta_2}):= \min{\left(}{\vec{d}}(\theta_1,\theta_2), \rho{\vec{d}}(\theta_2,\theta_1){\right)}.$$

The pair $({\vec{\mathbb{S}}}^1,{{\omega}_{{\vec{\mathbb{S}}}^1}})$ equipped with the discrete topology is a *directed circle network*, and the pair $({\vec{\mathbb{S}}}^1,{{\omega}_{{\vec{\mathbb{S}}}^1 \!\!,\rho}})$ equipped with the standard topology of ${\mathbb{C}}$ is a *directed circle network with reversibility $\rho$.* The difference is that ${{\omega}_{{\vec{\mathbb{S}}}^1}}$ allows for travel only in the counterclockwise direction, whereas ${{\omega}_{{\vec{\mathbb{S}}}^1 \!\!,\rho}}$ allows for travel in the clockwise direction (see Figure \[fig:dir-s1\]). It turns out that $({\vec{\mathbb{S}}}^1,{{\omega}_{{\vec{\mathbb{S}}}^1}})$ equipped with the discrete topology is a noncompact asymmetric network, and $({\vec{\mathbb{S}}}^1,{{\omega}_{{\vec{\mathbb{S}}}^1 \!\!,\rho}})$ equipped with the standard topology on ${\mathbb{C}}$ is a compact asymmetric network @dn-part1.

Skeletons and blow-up networks {#sec:weak-isom}
------------------------------

As we saw in the simple examples discussed above, strong isomorphism implies weak isomorphism, and weak isomorphism does not in general imply strong isomorphism. One may nevertheless wonder whether strong and weak isomorphism may be related in the sense of Question (\[q:3\]) posed above. We show that the answer to this question is positive. The following definitions enable us to formulate the appropriate statement.

\[Automorphisms\]\[defn:automorph\] Let $(X,{\omega}_X) \in {\mathcal{CN}}$. We define the *automorphisms of $X$* to be the collection $${\operatorname{Aut}}(X):={\left\{{\varphi}:X {\rightarrow}X : {\varphi}\text{ a weight preserving bijection}\right\}}.$$

\[Poset of weak isomorphism\] \[defn:poset\] Let $(X,{\omega}_X) \in {\mathcal{CN}}$. Define a set ${\mathfrak}{p}(X)$ as follows: $${\mathfrak}{p}(X):={\left\{(Y,{\omega}_Y)\in {\mathcal{CN}}: \text{ there exists a surjective, weight preserving map } {\varphi}:X {\rightarrow}Y\right\}}.$$ Next we define a partial order $\preceq$ on ${\mathfrak}{p}(X)$ as follows: for any $(Y,{\omega}_Y), (Z,{\omega}_Z) \in {\mathfrak}{p}(X)$, $$(Y,{\omega}_Y) \preceq (Z,{\omega}_Y) \iff \text{ there exists a surjective, weight preserving map } {\varphi}:Z {\rightarrow}Y.$$ Then the set ${\mathfrak}{p}(X)$ equipped with $\preceq$ is called the *poset of weak isomorphism of $X$.*

\[Terminal networks in ${\mathcal{CN}}$\]\[defn:terminal\] Let $(X,{\omega}_X) \in {\mathcal{CN}}$. A compact network $Z \in {\mathfrak}{p}(X)$ is *terminal* if:

1.  For each $Y\in {\mathfrak}{p}(X)$, there exists a weight preserving surjection ${\varphi}: Y {\rightarrow}Z$.

2.  Let $Y\in {\mathfrak}{p}(X)$. If $f: Y {\rightarrow}Z$ and $g:Y {\rightarrow}Z$ are weight preserving surjections, then there exists ${\varphi}\in {\operatorname{Aut}}(Z)$ such that $g={\varphi}\circ f$.

at (0,0) <span> (X) <span>$X$</span>;\
(Z) <span>$Z$</span>;\
</span>; (X) edge \[bend right\] node \[left\] <span>$f$</span>(Z); (X) edge \[bend left\] node \[right\] <span>$g$</span>(Z); (Z) edge \[dashed, loop below, min distance = 10 mm\] node \[right\] <span>${\varphi}$</span>(Z);

\[xshift=2.5in\] \[every node/.style=<span>midway</span>\] at (0,0) <span> (X) <span>$X$</span> ; & (V) <span>$V$</span>; & (Y) <span>$Y$</span>; & (d) <span>$\cdots$</span>;\
() ; & () ; & () ; & (Z) <span>$Z$</span>;\
</span>; (X) edge \[\] node \[\] (V); (V) edge \[\] node \[\] (Y); (Y) edge \[\] node \[\] (d); (d) edge \[\] node \[\] (Z); (Y) edge \[\] node \[\] (Z); (V) edge \[\] node \[\] (Z); (X) edge \[\] node \[\] (Z);

In §\[sec:cpt-skel\] we define a construction called the *skeleton* of a network and show that it is terminal. One of our main results (Theorem \[thm:cpt-sisom\]) shows that two *weakly isomorphic networks* have *strongly isomorphic skeleta*.

A terminal network captures the idea of a minimal substructure of a network. One may ask if anything interesting can be said about superstructures of a network. This motivates the following construction of a "blow-up" network. We provide an illustration in Figure \[fig:blowup\].

Let $(X,\omega_X)$ be any network. Let $\mathbf{k}=(k_x)_{x\in X}$ be a choice of an index set $k_x$ for each node $x\in X$. Consider the network $X[\mathbf{k}]$ with node set $\bigcup_{x\in X} \{(x,i) : i\in {k_x}\}$ and weights $\omega$ given as follows: for $x,x'\in X$ and for $i \in {k_x}$, $i'\in {k_{x'}}$, $$\omega\big((x,i),(x',i')\big):= {\omega}_X(x,x').$$ The topology on $X[\mathbf{k}]$ is given as follows: the open sets are of the form $\bigcup_{x\in U}{\left\{(x,i) : i \in k_x\right\}}$, where $U$ is open in $X$. By construction, $X[\mathbf{k}]$ is first countable with respect to this topology. We will call any such $X[\mathbf{k}]$ a *blow-up network* of $X$.

In a blow-up network of $X$, each node $x\in X$ is replaced by another network, indexed by ${k_x}$. All internal weights of this network are constant and all outgoing weights are preserved from the original network. If $X$ is compact, then so is $X[\mathbf{k}]$.

We also observe that $X$ is weakly isomorphic to any of its blow-ups $Y = X[\mathbf{k}]$. To see this, let $Z = X[\mathbf{k}]$, let $\phi_Y:Z\rightarrow Y$ be the map sending each $(x,i)$ to $(x,i)$, and let $\phi_X:Z\rightarrow X$ be the map sending each $(x,i)$ to $x$. Then $\phi_X, \phi_Y$ are surjective, weight preserving maps from $Z$ onto $X$ and $Y$ respectively. By Remark \[rem:surj\], we obtain $X \cong^w Y$.

The construction of blow-up networks leads to the following theorem, which provides another perspective on Question \[q:3\]:

\[Proposition 18, @dn-part1\] \[thm:blow-isom\] Let $(X,{\omega}_X), (Y,{\omega}_Y) \in {\mathcal{F}\mathcal{N}}$. Then $X \cong^w Y$ if and only if there exist blow-ups $X', Y'$ such that $X' \cong^s   Y'$.

\[every node/.style=<span>font=</span>\]

\(2) at (-3,0)<span>q</span>; (3) at (-1,0)<span>r</span>;

\(2) edge \[loop left, min distance = 10mm\] node<span>$1$</span>(2); (3) edge \[loop right, min distance = 10mm\] node<span>$4$</span>(3); (2) edge \[bend left\] node\[above\]<span>$2$</span> (3); (3) edge \[bend left\] node\[below\]<span>$3$</span> (2);

(dummy1) at (1.5,2.5); (dummy2) at (1.5,-2.5); (dummy3) at (-1,1); (dummy4) at (-1,-1);

(dummy3) edge\[bend left,thick\] node \[above left\] <span>blow-up</span> (dummy1) (dummy2) edge\[bend left, thick\] node \[below left\] <span>skeletonize</span> (dummy4);

\(4) at (4,3)<span>$(q,1)$</span>; (5) at (4,-3)<span>$(q,2)$</span>;

\(6) at (10,3)<span>$(r,1)$</span>; (7) at (10,-3)<span>$(r,2)$</span>;

(f1) at (2.5,4); (f2) at (5,-4);

\[on background layer\] ;

(f3) at (9,4); (f4) at (11.5,-4);

;

\(4) edge \[min distance = 10mm, in = 180,out=120\] node\[above\]<span>$1$</span>(4); (5) edge \[min distance = 10mm,in=240,out=180\] node\[below\]<span>$1$</span>(5); (4) edge \[bend left\] node\[left\]<span>$1$</span> (5); (5) edge \[bend left\] node\[left\]<span>$1$</span> (4);

\(6) edge \[min distance = 10mm, in =0, out=60\] node\[above\]<span>$4$</span>(6); (7) edge \[min distance = 10mm, out=0,in=300\] node\[below\]<span>$4$</span>(7); (6) edge \[bend left\] node\[right\]<span>$4$</span> (7); (7) edge \[bend left\] node\[right\]<span>$4$</span> (6);

\(4) edge \[bend left\] node\[above,pos=0.5\]<span>$2$</span> (6); (5) edge \[bend left\] node\[below,pos=0.5\]<span>$2$</span> (7); (6) edge \[bend left\] node\[above,pos=0.5\]<span>$3$</span> (4); (7) edge \[bend left\] node\[above,pos=0.5\]<span>$3$</span> (5);

\(4) edge \[bend left\] node\[pos=0.5,above\]<span>$2$</span> (7); (5) edge \[bend left\] node\[pos=0.5,above\]<span>$2$</span> (6); (7) edge \[bend left\] node\[pos=0.5,above\]<span>$3$</span> (4); (6) edge \[bend left\] node\[pos=0.5,above\]<span>$3$</span> (5);

at (-2,-6)<span>$N_2({\left(\begin{smallmatrix}
            {1} & {2}\\
                {3} & {4}
                     \end{smallmatrix}\right)})$</span>; at (7,-6)<span>$N_4
\left(\left(\begin{smallmatrix}
1&1&2&2\\
1&1&2&2\\
3&3&4&4\\
3&3&4&4
\end{smallmatrix}\right)\right)$</span>;

The network distance
--------------------

We now present the network distance ${d_{\mathcal{N}}}$ that is the central focus of this paper. We remind the reader that restricted formulations of this network distance have appeared in earlier applications of *hierarchical clustering* @clust-net [@carlsson2013axiomatic] and *persistent homology* @dowker-asilo [@dowker-arxiv; @pph] methods to network data. Furthermore, we presented the current formulation of ${d_{\mathcal{N}}}$ in @dn-part1 and provided a treatment of both its theoretical and computational aspects. We now give an independent presentation of ${d_{\mathcal{N}}}$, and motivate its definition by tracing its roots in the metric space literature.

The network distance ${d_{\mathcal{N}}}$ arises by extending the well-known Gromov-Hausdorff distance ${d_{\textrm{GH}}}$ between compact metric spaces @gromov1981structures [@burago; @petersen2006riemannian]. The best-known formulation of ${d_{\textrm{GH}}}$ arises from the *Hausdorff distance* between closed subsets of a metric space.

\[defn:dgh\] Given metric spaces $(X,d_X)$ and $(Y,d_Y)$, the *Gromov-Hausdorff distance* between them is defined as: $$\begin{aligned}
{d_{\textrm{GH}}}((X,d_X),(Y,d_Y)) :=\inf \big\{d_{{\operatorname{H}}}^Z({\varphi}(X),\psi(Y)) &: \text{$Z$ a metric space,}\\
&{\varphi}:X {\rightarrow}Z,\; \psi:Y{\rightarrow}Z \text{ isometric embeddings} \big\}.\end{aligned}$$

This particular definition does not appear to admit an easy extension to the network setting: an obstruction is that the standard formulation of the Hausdorff distance relies on open metric balls that have no analogue in the network setting. However, it turns out that there is a reformulation of ${d_{\textrm{GH}}}$ that utilizes the language of *correspondences* @kalton1999distances [@burago]. We present this construction next.

\[Correspondence\] Let $X,Y$ be two sets. A *correspondence between $X$ and $Y$* is a relation $R \subseteq X \times Y$ such that $\pi_X(R) = X$ and $\pi_Y(R) = Y$, where $\pi_X$ and $\pi_Y$ are the canonical projections of $X\times Y$ onto $X$ and $Y$, respectively. The collection of all correspondences between $X$ and $Y$ will be denoted ${\mathscr{R}}(X,Y)$, abbreviated to ${\mathscr{R}}$ when the context is clear.

\[1-point correspondence\]\[ex:corresp\] Let $X$ be a set, and let ${\left\{p\right\}}$ be the set with one point. Then there is a unique correspondence $R = {\left\{(x,p) : x \in X\right\}}$ between $X$ and ${\left\{p\right\}}$.

\[Diagonal correspondence\]\[ex:diag-corresp\] Let $X = {\left\{x_1,\ldots, x_n\right\}}$ and $Y={\left\{y_1,\ldots, y_n\right\}}$ be two enumerated sets with the same cardinality. A useful correspondence is the *diagonal correspondence*, defined as $\Delta:={\left\{(x_i,y_i) : 1\leq i \leq n\right\}}.$ When $X$ and $Y$ are infinite sets with the same cardinality, and ${\varphi}:X {\rightarrow}Y$ is a given bijection, then we can write the diagonal correspondence as $\Delta:={\left\{(x,{\varphi}(x)) : x \in X\right\}}.$

\[Distortion of a correspondence\] Let $(X,{\omega}_X),(Y,{\omega}_Y) \in {\mathcal{N}}$ and let $R\in{\mathscr{R}}(X,Y)$. The *distortion* of $R$ is given by: $$\mathrm{dis}(R):=\sup_{(x,y),(x',y')\in R}|{\omega}_X(x,x')-{\omega}_Y(y,y')|.$$

\[Composition of correspondences\]\[rem:chained-corr\] Let $(X,{\omega}_X), \ (Y,{\omega}_Y), \ (Z,{\omega}_Z) \in {\mathcal{N}}$, and let $R \in {\mathscr{R}}(X,Y),\ S \in {\mathscr{R}}(Y,Z)$. Then we define: $$R\circ S := {\left\{(x,z) \in X \times Z \mid \exists y, (x,y) \in R, (y,z) \in S\right\}}.$$ It can be verified that $R\circ S \in {\mathscr{R}}(X,Z)$, and that ${\operatorname{dis}}(R\circ S) \leq {\operatorname{dis}}(R) + {\operatorname{dis}}(S)$. In particular, we verify this fact in the proof of Lemma \[lem:chain-corr\].

\[The network distance ${d_{\mathcal{N}}}$\]\[defn:dno\] Let $(X,{\omega}_X),(Y,{\omega}_Y) \in {\mathcal{N}}$. We define the *network distance* between $X$ and $Y$ as follows: $${d_{\mathcal{N}}}((X,{\omega}_X),(Y,{\omega}_Y)):=\frac{1}{2}\inf_{R\in{\mathscr{R}}}\mathrm{dis}(R).$$

When the context is clear, we will often write ${d_{\mathcal{N}}}(X,Y)$ to denote ${d_{\mathcal{N}}}((X,{\omega}_X),(Y,{\omega}_Y))$. We define the collection of *optimal correspondences* ${\mathscr{R}}^{\operatorname{opt}}$ between $X$ and $Y$ to be the collection ${\left\{R \in {\mathscr{R}}(X,Y) : {\operatorname{dis}}(R) = 2{d_{\mathcal{N}}}(X,Y)\right\}}.$ This set is always nonempty when $X,Y \in {\mathcal{F}\mathcal{N}}$: by finiteness, the $\inf/\sup$ can be replaced by $\min/\max$. More interestingly, optimal correspondences also exist when $X,Y$ are compact metric spaces @dgh-note.

\[rem:dno-finite\] We list some simple but important properties of ${d_{\mathcal{N}}}$.

1.  As stated in Theorem \[thm:weak-isom-cpt\], ${d_{\mathcal{N}}}$ is a metric on ${\mathcal{CN}}$ modulo weak isomorphism.

2.  When restricted to metric spaces, ${d_{\mathcal{N}}}$ agrees with ${d_{\textrm{GH}}}$. This can be seen from the reformulation of ${d_{\textrm{GH}}}$ in terms of correspondences @burago [Theorem 7.3.25]. Whereas ${d_{\textrm{GH}}}$ vanishes only on pairs of isometric compact metric spaces (which are strongly isomorphic as networks), ${d_{\mathcal{N}}}$ vanishes on pairs of weakly isomorphic networks.

3.  ${d_{\mathcal{N}}}(X,Y)$ is always bounded for $X,Y\in{\mathcal{CN}}$. A valid correspondence between $X$ and $Y$ is always given by $X\times Y$. So we have: $${d_{\mathcal{N}}}(X,Y)\leq \frac{1}{2}\mathrm{dis}(X\times Y)
    \leq\frac{1}{2}\left(\sup_{x,x'}\big|\omega_X(x,x')\big|+\sup_{y,y'\in Y}\big|\omega_Y(y,y')\big|\right)<\infty.$$

Throughout this paper, we work to better understand the metric space $({\mathcal{CN}/{\cong^w}},{d_{\mathcal{N}}})$, where ${d_{\mathcal{N}}}:{\mathcal{CN}/{\cong^w}}\times {\mathcal{CN}/{\cong^w}}{\rightarrow}{\mathbb{R}}_+$ is defined (abusing notation) as follows: $${d_{\mathcal{N}}}([X],[Y]) := {d_{\mathcal{N}}}(X,Y),\quad\text{for each }[X],[Y]\in {\mathcal{CN}/{\cong^w}}.$$

To check that ${d_{\mathcal{N}}}$ is well-defined on $[X],[Y] \in {\mathcal{CN}}/\cong^w$, let $X' \in [X], Y' \in [Y]$. Then: $${d_{\mathcal{N}}}([X'],[Y'])={d_{\mathcal{N}}}(X',Y')= {d_{\mathcal{N}}}(X,Y)={d_{\mathcal{N}}}([X],[Y]),$$ where the second-to-last equality follows from the triangle inequality and the observation that ${d_{\mathcal{N}}}(X,X') = {d_{\mathcal{N}}}(Y,Y') = 0$.

Completeness and precompactness {#sec:completeness}
===============================

The completion of ${\mathcal{CN}}/\cong^w$
------------------------------------------

A very natural question regarding ${\mathcal{CN}}/\cong^w$ is if it is complete. This indeed turns out to be the case, and its proof is the content of the current section.

\[lem:chain-corr\] Let $X_1,\ldots, X_n \in {\mathcal{F}\mathcal{N}}$, and for each $i = 1,\ldots, n-1$, let $R_i \in {\mathscr{R}}(X_i,X_{i+1})$. Define $$\begin{aligned}
R&:=R_1\circ R_2 \circ \cdots \circ R_n\\
&={\left\{(x_1,x_n)\in X_1\times X_n \mid \exists (x_i)_{i=2}^{n-1}, (x_i,x_{i+1})\in R_i \text{ for all } i\right\}}.\end{aligned}$$ Then ${\operatorname{dis}}(R) \leq \sum_{i=1}^n{\operatorname{dis}}(R_i).$

We proceed by induction, beginning with the base case $n=2$. For convenience, write $X:= X_1$, $Y:=X_2$, and $Z:= X_3$. Let $(x,z), (x',z') \in R_1 \circ R_2$. Let $y\in Y$ be such that $(x,y) \in R_1$ and $(y,z) \in R_2$. Let $y' \in Y$ be such that $(x',y') \in R_1, (y',z')\in R_2$. Then we have: $$\begin{aligned}
|{\omega}_X(x,x') - {\omega}_Z(z,z')| &= |{\omega}_X(x,x') - {\omega}_Y(y,y') + {\omega}_Y(y,y') - {\omega}_Z(z,z')|\\
&\leq |{\omega}_X(x,x') - {\omega}_Y(y,y')| + |{\omega}_Y(y,y') - {\omega}_Z(z,z')|\\
&\leq {\operatorname{dis}}(R) + {\operatorname{dis}}(S).\end{aligned}$$ This holds for any $(x,z), (x',z') \in R\circ S$, and proves the claim.

Suppose that the result holds for $n=N \in {\mathbb{N}}$. Write $R'=R_1\circ \cdots \circ R_N$ and $R=R' \circ R_{N+1}.$ Since $R'$ is itself a correspondence, applying the base case yields: $$\begin{aligned}
{\operatorname{dis}}(R) &\leq {\operatorname{dis}}(R') + {\operatorname{dis}}(R_{N+1})\\
&\leq \sum_{i=1}^N{\operatorname{dis}}(R_i) + {\operatorname{dis}}(R_{N+1}) \quad \text{by induction}\\
&=\sum_{i=1}^{N+1}{\operatorname{dis}}(R_i).\end{aligned}$$ This proves the lemma.

\[thm:complete\] The completion of $({\mathcal{F}\mathcal{N}}/{\cong^w},{d_{\mathcal{N}}})$ is $({\mathcal{CN}}/{\cong^w},{d_{\mathcal{N}}})$.

Let $([X_i])_{i\in {\mathbb{N}}}$ be a Cauchy sequence in ${\mathcal{F}\mathcal{N}}/{\cong^w}$. First we wish to show this sequence converges in ${\mathcal{CN}}/{\cong^w}$. Note that $(X_i)_{i\in {\mathbb{N}}}$ is a Cauchy sequence in ${\mathcal{F}\mathcal{N}}$, since the distance between two equivalence classes is given by the distance between any representatives. To show $(X_i)_i$ converges, it suffices to show that a subsequence of $(X_i)_i$ converges, so without loss of generality, suppose ${d_{\mathcal{N}}}(X_i,X_{i+1})<2^{-i}$ for each $i$. Then for each $i$, there exists $R_i\in {\mathscr{R}}(X_i,X_{i+1})$ such that ${\operatorname{dis}}(R_i)\leq 2^{-i+1}$. Fix such a sequence $(R_i)_{i\in {\mathbb{N}}}$. For $j> i$, define $$R_{ij}:=R_i\circ R_{i+1}\circ R_{i+2}\circ \cdots \circ R_{j-1}.$$ By Lemma \[lem:chain-corr\], ${\operatorname{dis}}(R_{ij})\leq {\operatorname{dis}}(R_i) + {\operatorname{dis}}(R_{i+1}) + \ldots +{\operatorname{dis}}(R_{j-1})\leq 2^{-i+2}$. Next define: $$\overline{X}:={\left\{(x_j) : (x_j,x_{j+1})\in R_j \text{ for all } j\in {\mathbb{N}}\right\}}.$$ To see $\overline{X} \neq {\varnothing}$, let $x_1\in X_1$, and use the (nonempty) correspondences to pick a sequence $(x_1,x_2,x_3,\ldots)$. By construction, $(x_i)\in \overline{X}$.

Define ${\omega}_{\overline{X}}((x_j),(x_j')) = \limsup_{j{\rightarrow}\infty}{\omega}_{X_j}(x_j,x_j')$. We claim that ${\omega}_{\overline{X}}$ is bounded, and thus is a real-valued weight function. To see this, let $(x_j),(x_j') \in {\overline{X}}$. Let $j\in {\mathbb{N}}$. Then we have: $$\begin{aligned}
|{\omega}_{X_j}(x_j,x_j')|&=|{\omega}_{X_j}(x_j,x_j')-{\omega}_{X_{j-1}}(x_{j-1},x'_{j-1})+{\omega}_{X_{j-1}}(x_{j-1},x'_{j-1})-\ldots\\
&\quad -{\omega}_{X_{1}}(x_{1},x'_{1})+{\omega}_{X_{1}}(x_{1},x'_{1})|\\
&\leq |{\omega}_{X_1}(x_1,x'_1)|+ {\operatorname{dis}}(R_1)+{\operatorname{dis}}(R_2)+\ldots+{\operatorname{dis}}(R_{j-1})\\
&\leq |{\omega}_{X_1}(x_1,x'_1)|+ 2
\intertext{But $j$ was arbitrary. Thus we obtain:}
|{\omega}_{\overline{X}}((x_j),(x_j'))| &= \limsup_{j{\rightarrow}\infty}{\omega}_{X_j}(x_j,x_j') \leq |{\omega}_{X_1}(x_1,x'_1)|+ 2< \infty.\end{aligned}$$

\[cl:X-cpt\] $({\overline{X}},{{\omega}_{{\overline{X}}}}) \in {\mathcal{CN}}$. More specifically, ${\overline{X}}$ is a first countable compact topological space, and ${{\omega}_{{\overline{X}}}}$ is continuous with respect to the product topology on ${\overline{X}}\times {\overline{X}}$.

\[Proof of Claim \[cl:X-cpt\]\] We equip $\prod_{i\in {\mathbb{N}}}X_i$ with the product topology. First note that the countable product $\prod_{i\in {\mathbb{N}}} X_i$ of first countable spaces is first countable. Any subspace of a first countable space is first countable, so ${\overline{X}}\subseteq \prod_{i\in {\mathbb{N}}} X_i$ is first countable. By Tychonoff's theorem, $\prod_{i\in {\mathbb{N}}} X_i$ is compact. So to show that ${\overline{X}}$ is compact, we only need to show that it is closed.

If ${\overline{X}}= \prod_{i\in {\mathbb{N}}}X_i$, we would automatically know that ${\overline{X}}$ is compact. Suppose not, and let $(x_i)_{i\in{\mathbb{N}}} \in \left(\prod_{i\in {\mathbb{N}}}X_i \right)\setminus {\overline{X}}$. Then there exists $N\in {\mathbb{N}}$ such that $(x_N,x_{N+1}) \not\in R_N$. Define: $$U:= X_1 \times X_2 \times \ldots \times {\left\{x_N\right\}} \times {\left\{x_{N+1}\right\}} \times X_{N+2} \times \ldots .$$ Since $X_i$ has the discrete topology for each $i\in {\mathbb{N}}$, it follows that ${\left\{x_N\right\}}$ and ${\left\{x_{N+1}\right\}}$ are open. Hence $U$ is an open neighborhood of $(x_i)_{i\in {\mathbb{N}}}$ and is disjoint from $\prod_{i\in {\mathbb{N}}}X_i$. It follows that $\left(\prod_{i\in {\mathbb{N}}}X_i \right)\setminus {\overline{X}}$ is open, hence ${\overline{X}}$ is closed and thus compact.

It remains to show that ${{\omega}_{{\overline{X}}}}$ is continuous. We will show that preimages of open sets in ${\mathbb{R}}$ under ${{\omega}_{{\overline{X}}}}$ are open. Let $(a,b) \subseteq {\mathbb{R}}$, and suppose ${{\omega}_{{\overline{X}}}}{^{-1}}[(a,b)]$ is nonempty (otherwise, there is nothing to show). Let $(x_i)_{i\in {\mathbb{N}}}, (x'_i)_{i\in {\mathbb{N}}} \in {\overline{X}}\times {\overline{X}}$ be such that $${\alpha}:= {{\omega}_{{\overline{X}}}}((x_i)_i,(x'_i)_i) \in (a,b).$$ Write $r':= \min(|{\alpha}-a|,|b-{\alpha}|)$, and define $r:=\tfrac{1}{2}r'$.

Let $N\in {\mathbb{N}}$ be such that $2^{-N+3} < r$. Consider the following open sets: $$\begin{aligned}
U&:={\left\{x_1\right\}}\times {\left\{x_2\right\}} \times \ldots \times {\left\{x_N\right\}} \times X_{N+1} \times X_{N+2} \times \ldots \subseteq \prod_{i\in {\mathbb{N}}}X_i,\\
V&:={\left\{x'_1\right\}}\times {\left\{x'_2\right\}} \times \ldots \times {\left\{x'_N\right\}} \times X_{N+1} \times X_{N+2} \times \ldots \subseteq \prod_{i\in {\mathbb{N}}}X_i.\end{aligned}$$

Next write $A:={\overline{X}}\cap U$ and $B:={\overline{X}}\cap V$. Then $A$ and $B$ are open with respect to the subspace topology on ${\overline{X}}$. Thus $A\times B$ is open in ${\overline{X}}\times {\overline{X}}$. Note that $(x_i)_{i\in {\mathbb{N}}} \in A$ and $(x'_i)_{i\in {\mathbb{N}}} \in B$. We wish to show that $A\times B \subseteq {{\omega}_{{\overline{X}}}}{^{-1}}[(a,b)]$, so it suffices to show that ${{\omega}_{{\overline{X}}}}(A,B) \subseteq (a,b)$.

Let $(z_i)_{i\in {\mathbb{N}}} \in A$ and $(z'_i)_{i\in {\mathbb{N}}} \in B$. Notice that $z_i= x_i$ and $z'_i = x'_i$ for each $i \leq N$. So for $n\leq N$, we have $|{\omega}_{X_n}(z_n,z'_n) - {\omega}_{X_n}(x_n,x'_n)| = 0.$

Next let $n\in {\mathbb{N}}$, and note that: $$\begin{aligned}
&|{\omega}_{X_{N+n}}(z_{N+n},z'_{N+n}) - {\omega}_{X_{N+n}}(x_{N+n},x'_{N+n})|\\
&=|{\omega}_{X_{N+n}}(z_{N+n},z'_{N+n}) - {\omega}_{X_N}(z_N,z'_N) + {\omega}_{X_N}(z_N,z'_N) - {\omega}_{X_{N+n}}(x_{N+n},x'_{N+n})|\\
&=|{\omega}_{X_{N+n}}(z_{N+n},z'_{N+n}) - {\omega}_{X_N}(z_N,z'_N) + {\omega}_{X_N}(x_N,x'_N) - {\omega}_{X_{N+n}(x_{N+n}},x'_{N+n})|\\
&\leq {\operatorname{dis}}(R_{N,N+n}) + {\operatorname{dis}}(R_{N,N+n}) \leq 2^{-N+2} + 2^{-N+2} = 2^{-N+3} < r.\end{aligned}$$ Here the second to last inequality follows from Lemma \[lem:chain-corr\]. The preceding calculation holds for arbitrary $n\in {\mathbb{N}}$. It follows that: $$\limsup_{i {\rightarrow}\infty}{\omega}_{X_i}(x_i,x'_i) - 
\limsup_{i {\rightarrow}\infty}{\omega}_{X_i}(z_i,z'_i) \leq 
\limsup_{i {\rightarrow}\infty}({\omega}_{X_i}(x_i,x'_i)-{\omega}_{X_i}(z_i,z'_i) < r,$$ and similarly $\limsup_{i {\rightarrow}\infty}{\omega}_{X_i}(z_i,z'_i) - 
\limsup_{i {\rightarrow}\infty}{\omega}_{X_i}(x_i,x'_i) < r.$ Thus we have ${{\omega}_{{\overline{X}}}}((z_i)_i,(z'_i)_i) \in (a,b)$. This proves continuity of ${{\omega}_{{\overline{X}}}}$.

Next we claim that $X_i \xrightarrow{{d_{\mathcal{N}}}} \overline{X}$ as $i{\rightarrow}\infty$. Fix $i\in {\mathbb{N}}$. We wish to construct a correspondence $S\in {\mathscr{R}}(X_i,\overline{X})$. Let $y\in X_i$. We write $x_i=y$ and pick $x_1,x_2,\ldots, x_{i-1},x_{i+1},\ldots$ such that $(x_j,_{j+1}) \in R_j$ for each $j\in {\mathbb{N}}$. We denote this sequence by $(x_j)^{x_i=y}$, and note that by construction, it lies in $\overline{X}$. Conversely, for any $(x_j) \in \overline{X}$, we simply pick its $i$th coordinate $x_i$ as a corresponding element in $X_i$. We define: $$\begin{aligned}
S &:=A \cup B, \text{ where }\\
A &:= {\left\{(y,(x_j)^{x_i=y}) : y\in X_i\right\}}\\
B &:= {\left\{(x_i,(x_k)) : (x_k) \in \overline{X}\right\}}\end{aligned}$$ Then $S \in {\mathscr{R}}(X_i,\overline{X})$. We claim that ${\operatorname{dis}}(S) \leq 2^{-i+2}$. Let $z=(y,(x_k)),z'=(y',(x'_k)) \in B$. Let $n\in {\mathbb{N}}, n \geq i$. Then we have: $$\begin{aligned}
|{\omega}_{X_i}(y,y') - {\omega}_{X_n}(x_n,x'_n)|
&=|{\omega}_{X_i}(y,y') - {\omega}_{X_{i+1}}(x_{i+1},x'_{i+1})+
{\omega}_{X_{i+1}}(x_{i+1},x'_{i+1})-\ldots\\
&\quad + {\omega}_{X_{n-1}}(x_{n-1},x'_{n-1})+
{\omega}_{X_{n}}(x_{n},x'_{n})|\\
&\leq {\operatorname{dis}}(R_i) + {\operatorname{dis}}(R_{i+1})+\ldots+{\operatorname{dis}}(R_{n-1})\\
&\leq 2^{-i+1} + 2^{-i} + \ldots + 2^{-n+2}\\
&\leq 2^{-i+2}.
\intertext{This holds for arbitrary $n\geq i$. It follows that we have:}
|{\omega}_{X_i}(y,y') - {\omega}_{\overline{X}}((x_k),(x'_k))|&\leq 2^{-i+2}.\end{aligned}$$ Similar inequalities hold for $z,z' \in A$, and for $z\in A,z'\in B$. Thus ${\operatorname{dis}}(S) \leq 2^{-i+2}$. It follows that ${d_{\mathcal{N}}}(X_i,\overline{X})\leq 2^{-i+1}$. Thus the sequence $([X_i])_i$ converges to $[\overline{X}]\in {\mathcal{CN}}/{\cong^w}$.

Finally, we need to check that $({\mathcal{CN}}/{\cong^w},{d_{\mathcal{N}}})$ is complete. Let $([Y_n])_n$ be a Cauchy sequence in ${\mathcal{CN}}/{\cong^w}$. For each $n$, let $[X_n] \in {\mathcal{F}\mathcal{N}}/{\cong^w}$ be such that ${d_{\mathcal{N}}}([X_n],[Y_n])<\tfrac{1}{n}$. Let ${\varepsilon}> 0$. Then for sufficiently large $m$ and $n$, we have: $${d_{\mathcal{N}}}([X_n],[X_m])\leq {d_{\mathcal{N}}}([X_n],[Y_n])+{d_{\mathcal{N}}}([Y_n],[Y_m])+{d_{\mathcal{N}}}([Y_m],[X_m])<{\varepsilon}.$$ Thus $([X_n])_n$ is a Cauchy sequence in ${\mathcal{F}\mathcal{N}}/{\cong^w}$. By applying what we have shown above, this sequence converges to some $[\overline{X}] \in {\mathcal{CN}}/{\cong^w}$. By applying the triangle inequality, we see that the sequence $([Y_n])_n$ also converges to $[\overline{X}]$. This shows completeness, and concludes the proof.

The result of Theorem \[thm:complete\] can be summarized as follows:

*The limit of a convergent sequence of finite networks is a compact topological space with a continuous weight function.*

The technique of composed correspondences used in the preceding proof can also be used to show that the collection of isometry classes of compact metric spaces endowed with the Gromov-Hausdorff distance is a complete metric space. Standard proofs of this fact @petersen2006riemannian [§10] do not use correspondences, relying instead on a method of endowing metrics on disjoint unions of spaces and then computing Hausdorff distances.

In the proof of Theorem \[thm:complete\], note that the construction of the limit is dependent upon the initial choice of optimal correspondences. However, all such limits obtained from different choices of optimal correspondences belong to the same weak isomorphism class.

Completeness of ${\mathcal{CN}}/\cong^w$ gives us a first useful criterion for convergence of networks. Ideally, we would also want a criterion for convergence along the lines of sequential compactness. In the setting of compact metric spaces, Gromov's Precompactness Theorem implies that the topology induced by the Gromov-Hausdorff distance admits many *precompact families* of compact metric spaces (i.e. collections whose closure is compact) @gromov1981structures [@burago; @petersen2006riemannian]. Any sequence in such a precompact family has a subsequence converging to some limit point of the family. In the next section, we extend these results to the setting of networks. Namely, we show that that there are many families of compact networks that are precompact under the metric topology induced by ${d_{\mathcal{N}}}$.

Precompact families in ${\mathcal{CN}/{\cong^w}}$
-------------------------------------------------

We begin this section with some definitions.

\[Diameter for networks, @dn-part1\] For any network $(X,{\omega}_X)$, define ${\operatorname{diam}}(X):= \sup_{x,x'\in X}|{\omega}_X(x,x')|$. For compact networks, the $\sup$ is replaced by $\max$.

A family $\mathcal{F}$ of weak isomorphism classes of compact networks is *uniformly approximable* if: (1) there exists $D \geq 0$ such that for every $[X] \in \mathcal{F}$, we have ${\operatorname{diam}}(X) \leq D$, and (2) for every ${\varepsilon}> 0$, there exists $N({\varepsilon}) \in {\mathbb{N}}$ such that for each $[X] \in \mathcal{F}$, there exists a finite network $Y$ satisfying ${\mathrm{card}}(Y) \leq N({\varepsilon})$ and ${d_{\mathcal{N}}}(X,Y) < {\varepsilon}$.

The preceding definition is an analogue of the definition of *uniformly totally bounded* families of compact metric spaces @burago [Definition 7.4.13], which is used in formulating the precompactness result in the metric space setting. A family of compact metric spaces is said to be uniformly totally bounded if there exists $D \in {\mathbb{R}}_+$ such that each space has diameter bounded above by $D$, and for any ${\varepsilon}>0$ there exists $N_{\varepsilon}\in {\mathbb{N}}$ such that each space in the family has an ${\varepsilon}$-net with cardinality bounded above by $N_{\varepsilon}$. Recall that given a metric space $(X,d_X)$ and ${\varepsilon}>0$, a subset $S \subseteq X$ is an ${\varepsilon}$-net if for any point $x\in X$, we have $B(x,{\varepsilon})\cap S \neq {\varnothing}$. Such an ${\varepsilon}$-net satisfies the nice property that ${d_{\textrm{GH}}}(X,S) < {\varepsilon}$ @burago [7.3.11]. Thus an ${\varepsilon}$-net is an ${\varepsilon}$-approximation of the underlying metric space in the Gromov-Hausdorff distance.

\[thm:precompactness\] Let $\mathfrak{F}$ be a uniformly approximable family in ${\mathcal{CN}}/\cong^w$. Then $\mathfrak{F}$ is precompact, i.e. any sequence in $\mathfrak{F}$ contains a subsequence that converges in ${\mathcal{CN}}/\cong^w$.

Our proof is modeled on the proof of an analogous result for compact metric spaces proposed by Gromov @gromov1981structures. We use one external fact @dn-part1 [stability of ${\operatorname{diam}}$]: for compact networks $X,Y$ such that ${d_{\mathcal{N}}}(X,Y) < {\varepsilon}$, we have ${\operatorname{diam}}(X) \leq {\operatorname{diam}}(Y) + 2{\varepsilon}$.

\[Proof of Theorem \[thm:precompactness\]\] Let $D \geq 0$ be such that ${\operatorname{diam}}(X) \leq D$ for each $[X]\in \mathfrak{F}$. It suffices to prove that $\mathfrak{F}$ is totally bounded, because Theorem \[thm:complete\] gives completeness, and these two properties together imply precompactness. Let ${\varepsilon}> 0$. We need to find a finite family $\mathcal{G}\subseteq {\mathcal{CN}}/\cong^w$ such that for every $[F] \in \mathfrak{F}$, there exists $[G] \in \mathcal{G}$ with ${d_{\mathcal{N}}}(F,G) < {\varepsilon}$. Define: $${\mathcal}{A}:= {\left\{A \in {\mathcal{F}\mathcal{N}}: {\mathrm{card}}(A) \leq N({\varepsilon}/2),\; 
{d_{\mathcal{N}}}(A,F) < {\varepsilon}/2 \text{ for some } [F]\in \mathfrak{F}\right\}}.$$

Each element of $\mathcal{A}$ is an $n\times n $ matrix, where $1\leq n \leq N({\varepsilon}/2)$. For each $A\in \mathcal{A}$, there exists $[F]\in \mathfrak{F}$ with ${d_{\mathcal{N}}}(A,F) < {\varepsilon}/2$, and by the fact stated above, we have ${\operatorname{diam}}(A) \leq {\operatorname{diam}}(F) + 2({\varepsilon}/2) \leq D+{\varepsilon}$. Thus the matrices in $\mathcal{A}$ have entries in $[-D-{\varepsilon},D+{\varepsilon}]$. Let $N \gg 1$ be such that: $$\frac{2D+2{\varepsilon}}{N} < \frac{{\varepsilon}}{4},$$ and write the refinement of $[-D-{\varepsilon},D+{\varepsilon}]$ into $N$ pieces as: $$W := {\left\{-D-{\varepsilon}+ k\left(\tfrac{2D+2{\varepsilon}}{N}\right) : 0\leq k \leq N\right\}}.$$

Write $\mathcal{A} = \bigsqcup_{i=1}^{N({\varepsilon}/2)}\mathcal{A}_i$, where each $\mathcal{A}_i$ consists of the $i\times i$ matrices of $\mathcal{A}$. For each $i$ define: $$\mathcal{G}_i := {\left\{(G_{pq})_{1\leq p,q \leq i} : G_{pq} \in W\right\}}, \text{ the $i\times i$ matrices with entries in $W$.}$$

Let $\mathcal{G} = \bigsqcup_{i=1}^{N({\varepsilon}/2)}\mathcal{G}_i$ and note that this is a finite collection. Furthermore, for each $A_i \in \mathcal{A}_i$, there exists $G_i\in \mathcal{G}_i$ such that $${\|A_i - G_i\|}_\infty < \frac{{\varepsilon}}{4}.$$

Taking the diagonal correspondence between $A_i$ and $G_i$, it follows that ${d_{\mathcal{N}}}(A_i,G_i) < {\varepsilon}/2$. Hence for any $[F] \in \mathfrak{F}$, there exists $A \in \mathcal{A}$ and $G \in \mathcal{G}$ such that $${d_{\mathcal{N}}}(F,G) \leq {d_{\mathcal{N}}}(F,A) + {d_{\mathcal{N}}}(A,G) < {\varepsilon}/2 + {\varepsilon}/2 = {\varepsilon}.$$ This shows that $\mathfrak{F}$ is totally bounded, and concludes the proof.

Geodesic structure on ${\mathcal{CN}/{\cong^w}}$ {#sec:geodesic}
================================================

Thus far, we have motivated our discussion of compact networks by viewing them as limiting objects of finite networks. By the results of the preceding section, we know that $({\mathcal{CN}/{\cong^w}},{d_{\mathcal{N}}})$ is complete and obeys a well-behaved compactness criterion. In this section, we prove that this metric space is also *geodesic*, i.e. any two compact networks can be joined by a rectifiable curve with length equal to the distance between the two networks.

Geodesic spaces can have a variety of practical implications. For example, geodesic spaces that are also complete and locally compact are *proper* (i.e. any closed, bounded subset is compact), by virtue of the Hopf-Rinow theorem @burago [§2.5.3]. Any probability measure with finite second moment supported on such a space has a *barycenter* @ohta2012barycenters [Lemma 3.2], i.e. a "center of mass". Conceivably, such a result can be applied to a compact, geodesically convex region of $({\mathcal{CN}/{\cong^w}},{d_{\mathcal{N}}})$ to compute an "average" network from a collection of networks. Such a result is of interest in statistical inference, e.g. when one wishes to represent a noisy collection of networks by a single network. Similar results on barycenters of geodesic spaces can be found in @gouic2015existence [@leustean2016barycenters]. We leave a treatment of this topic from a probabilistic framework as future work, and only use this vignette to motivate the results in this section.

We begin with some definitions.

\[Curves and geodesics\] A *curve* on ${\mathcal{N}}$ joining $(X,\omega_X)$ to $(Y,\omega_Y)$ is any continuous map $\gamma:[0,1]\rightarrow {\mathcal{N}}$ such that $\gamma(0)=(X,{\omega}_X)$ and $\gamma(1)=(Y,{\omega}_Y)$. We will write *a curve on ${\mathcal{F}\mathcal{N}}$* (resp. *a curve on ${\mathcal{CN}}$*) to mean that the image of ${\gamma}$ is contained in ${\mathcal{F}\mathcal{N}}$ (resp. ${\mathcal{CN}}$). Such a curve is called a *geodesic* @bridson2011metric [§I.1] between $X$ and $Y$ if for all $s,t\in[0,1]$ one has: $${d_{\mathcal{N}}}(\gamma(t),\gamma(s))=|t-s|\cdot{d_{\mathcal{N}}}(X,Y).$$ A metric space is called a *geodesic space* if any two points can be connected by a geodesic.

The following theorem is a useful result about geodesics:

\[@burago, Theorem 2.4.16\]\[thm:mid\] Let $(X,d_X)$ be a complete metric space. If for any $x,x'\in X$ there exists a midpoint $z$ such that $d_X(x,z)=d_X(z,y)=\tfrac{1}{2}d_X(x,y)$, then $X$ is geodesic.

As a first step towards showing that ${\mathcal{CN}/{\cong^w}}$ is geodesic, we show that the collection of finite networks forms a geodesic space.

\[thm:geodesic\] The metric space $({\mathcal{FN}/{\cong^w}}, {d_{\mathcal{N}}})$ is a geodesic space. More specifically, let $[X],[Y] \in ({\mathcal{FN}/{\cong^w}}, {d_{\mathcal{N}}})$. Then, for any $R\in {\mathscr{R}}^{{\operatorname{opt}}}(X,Y)$, we can construct a geodesic ${\gamma}_R:[0,1] {\rightarrow}{\mathcal{FN}/{\cong^w}}$ between $[X]$ and $[Y]$ as follows: $$\begin{aligned}
&{\gamma}_R(0):=[(X,{\omega}_X)],\, {\gamma}_R(1):=[(Y,d_Y)], \text{ and }{\gamma}_R(t):=[(R,{\omega}_{{\gamma}_R(t)})] \text{ for } t\in (0,1),
\intertext{ where for each $(x,y),(x',y') \in R$ and $t\in(0,1),$} 
&\hspace{0.1\textwidth} {\omega}_{{\gamma}_R(t)}\big((x,y),(x',y')\big):=(1-t)\cdot {\omega}_X(x,x')+t\cdot {\omega}_Y(y,y').\end{aligned}$$

Let $[X],[Y] \in {\mathcal{FN}/{\cong^w}}$. We will show the existence of a curve ${\gamma}: [0,1] {\rightarrow}{\mathcal{F}\mathcal{N}}$ such that ${\gamma}(0)=(X,{\omega}_X)$, ${\gamma}(1)=(Y,{\omega}_Y)$, and for all $s, t \in [0,1]$, $${d_{\mathcal{N}}}({\gamma}(s),{\gamma}(t)) = |t-s| \cdot {d_{\mathcal{N}}}(X,Y).$$ Note that this yields ${d_{\mathcal{N}}}([{\gamma}(s)],[{\gamma}(t)]) = |t-s| \cdot  {d_{\mathcal{N}}}([X],[Y])$ for all $s,t \in [0,1]$, which is what we need to show.

Let $R\in{\mathscr{R}}^{{\operatorname{opt}}}(X,Y)$, i.e. let $R$ be a correspondence such that ${\operatorname{dis}}(R)=2{d_{\mathcal{N}}}(X,Y)$. For each $t\in(0,1)$ define ${\gamma}(t):=\big(R,{\omega}_{\gamma(t)}\big)$, where $${\omega}_{\gamma(t)}\big((x,y),(x',y')\big):=(1-t) \cdot {\omega}_X(x,x')+t \cdot {\omega}_Y(y,y') \quad\text{for all $(x,y),(x',y')\in R$}.$$ Also define ${\gamma}(0)=(X,{\omega}_X)$ and ${\gamma}(1)=(Y,{\omega}_Y)$.

\[cl:ineq\] For any $s,t \in [0,1]$, $${d_{\mathcal{N}}}({\gamma}(s),{\gamma}(t)) \leq |t-s| \cdot {d_{\mathcal{N}}}(X,Y).$$

Suppose for now that Claim \[cl:ineq\] holds. We further claim that this implies, for all $s, t \in [0,1]$, $${d_{\mathcal{N}}}({\gamma}(s),{\gamma}(t)) = |t-s| \cdot {d_{\mathcal{N}}}(X,Y).$$ To see this, assume towards a contradiction that there exist $s_0 < t_0$ such that : $$\begin{aligned}
{d_{\mathcal{N}}}({\gamma}(s_0),{\gamma}(t_0)) &< |t_0 - s_0| \cdot {d_{\mathcal{N}}}(X,Y).\\
\text{Then }{d_{\mathcal{N}}}(X,Y) &\leq {d_{\mathcal{N}}}(X,{\gamma}(s_0)) + {d_{\mathcal{N}}}({\gamma}(s_0),{\gamma}(t_0)) + {d_{\mathcal{N}}}({\gamma}(t_0),Y)\\
&< |s_0-0| \cdot {d_{\mathcal{N}}}(X,Y) + |t_0-s_0|\cdot {d_{\mathcal{N}}}(X,Y) + |1-t_0|\cdot {d_{\mathcal{N}}}(X,Y)\\
&={d_{\mathcal{N}}}(X,Y), \text{ a contradiction}.\end{aligned}$$

Thus it suffices to show Claim \[cl:ineq\]. There are three cases: (i) $s,t \in (0,1)$, (ii) $s=0, t \in (0,1)$, and (iii) $s\in (0,1), t=1$. The latter two cases are similar, so we just prove (i) and (ii). For (i), fix $s,t \in (0,1)$. Notice that $\Delta := \textrm{diag}(R\times R) := {\left\{(r,r):r \in R\right\}}$ is a correspondence in ${\mathscr{R}}(R,R).$ Then we obtain: $$\begin{aligned}
{\operatorname{dis}}(\Delta) &= \max_{(a,a),(b,b) \in \Delta}\vert {\omega}_{{\gamma}(t)}(a,b) - {\omega}_{{\gamma}(s)}(a,b)\vert\\
&= \max_{(x,y),(x',y') \in R}\vert {\omega}_{{\gamma}(t)}((x,y),(x',y')) - {\omega}_{{\gamma}(s)}((x,y),(x',y'))\vert\\
&= \max_{(x,y),(x',y') \in R}\vert (1-t){\omega}_X(x,x') + t\cdot  {\omega}_Y(y,y') - (1-s){\omega}_X(x,x') -s\cdot {\omega}_Y(y,y') \vert\\
&= \max_{(x,y),(x',y') \in R}\vert (s-t){\omega}_X(x,x') - (s-t){\omega}_Y(y,y')\vert\\
&= |t-s| \cdot \max_{(x,y),(x',y') \in R}\vert {\omega}_X(x,x') - {\omega}_Y(y,y')\vert\\
&\leq 2|t-s|\cdot {d_{\mathcal{N}}}(X,Y).\end{aligned}$$ Finally ${d_{\mathcal{N}}}({\gamma}(t),{\gamma}(s))\leq \frac{1}{2}{\operatorname{dis}}(\Delta) \leq |t-s|\cdot {d_{\mathcal{N}}}(X,Y)$.

For (ii), fix $s=0, t\in (0,1)$. Define $R_X = {\left\{(x,(x,y)) : (x,y) \in R\right\}}$. Then $R_X$ is a correspondence in ${\mathscr{R}}(X, R)$. $$\begin{aligned}
{\operatorname{dis}}(R_X) &= \max_{(x,(x,y)),(x',(x',y')) \in R_X}|{\omega}_X(x,x') - (1-t)\cdot {\omega}_X(x,x') - t\cdot {\omega}_Y(y,y')|\\
&=\max_{(x,(x,y)),(x',(x',y')) \in R_X} t\cdot  |{\omega}_X(x,x') - {\omega}_Y(y,y')|  \\
&=t  {\operatorname{dis}}(R) = 2t\cdot  {d_{\mathcal{N}}}(X,Y).\end{aligned}$$ Thus ${d_{\mathcal{N}}}(X,{\gamma}(t)) \leq t \cdot {d_{\mathcal{N}}}(X,Y)$. The proof for case (iii), i.e. that ${d_{\mathcal{N}}}({\gamma}(s),Y) \leq |1-s| \cdot {d_{\mathcal{N}}}(X,Y)$, is similar. This proves Claim \[cl:ineq\], and the result follows.

Notice that a key step in the preceding theorem was to choose an optimal correspondence between two finite networks. This may not be possible, in general, for compact networks. However, using the additional results on precompactness and completeness of ${\mathcal{CN}/{\cong^w}}$, we are able to obtain the desired geodesic structure in Theorem \[thm:geod-inf\]. The proof is similar to the one used by the authors of @ivanov2015gromov to prove that the metric space of isometry classes of compact metric spaces endowed with the Gromov-Hausdorff distance is geodesic.

\[thm:geod-inf\] The complete metric space $({\mathcal{CN}/{\cong^w}},{d_{\mathcal{N}}})$ is geodesic.

Let $[X],[Y] \in {\mathcal{CN}/{\cong^w}}$. It suffices to find a geodesic between $X$ and $Y$, because the distance between any two equivalence classes is given by the distance between any two representatives, and hence we will obtain a geodesic between $[X]$ and $[Y]$.

Let $(X_n)_n, (Y_n)_n$ be sequences in ${\mathcal{F}\mathcal{N}}$ such that ${d_{\mathcal{N}}}(X_n,X)<\tfrac{1}{n}$ and ${d_{\mathcal{N}}}(Y_n,Y)<\tfrac{1}{n}$ for each $n$. For each $n$, let $R_n$ be an optimal correspondence between $X_n$ and $Y_n$, endowed with the weight function $${\omega}_n((x,y),(a,b))=\tfrac{1}{2}{\omega}_{X_n}(x,a)+\tfrac{1}{2}{\omega}_{X_n}(y,b).$$ By the proof of Theorem \[thm:geodesic\], the network $(R_n,{\omega}_n)$ is a midpoint of $X_n$ and $Y_n$.

\[cl:mid\] The collection ${\left\{R_n : n \in {\mathbb{N}}\right\}}$ is precompact.

Assume for now that Claim \[cl:mid\] is true. Then we can pick a sequence $(R_n)$ that converges to some $R \in {\mathcal{CN}}$. Then we obtain: $$\begin{aligned}
{d_{\mathcal{N}}}(X,R) &\leq {d_{\mathcal{N}}}(X,X_n)+{d_{\mathcal{N}}}(X_n,R_n)+{d_{\mathcal{N}}}(R_n,R)\\
&={d_{\mathcal{N}}}(X,X_n) + \tfrac{1}{2}{d_{\mathcal{N}}}(X_n,Y_n)+{d_{\mathcal{N}}}(R_n,R) {\rightarrow}\tfrac{1}{2}{d_{\mathcal{N}}}(X,Y).\end{aligned}$$ Similarly ${d_{\mathcal{N}}}(R,Y) \leq \tfrac{1}{2}{d_{\mathcal{N}}}(X,Y)$. Furthermore, equality holds in both inequalities, because we would get a contradiction otherwise. Thus $R$ is a midpoint of $X$ and $Y$, and moreover, $[R]$ is a midpoint of $[X]$ and $[Y]$. The result now follows by an application of Theorem \[thm:mid\].

It remains to prove Claim \[cl:mid\]. By Theorem \[thm:precompactness\], it suffices to show that ${\left\{R_n\right\}}$ is uniformly approximable.

Since ${d_{\mathcal{N}}}(X_n,X) {\rightarrow}0$ and ${d_{\mathcal{N}}}(Y_n,Y) {\rightarrow}0$, we can choose $D>0$ large enough so that ${\operatorname{diam}}(X_n) \leq \tfrac{D}{2}$ and ${\operatorname{diam}}(Y_n) \leq \tfrac{D}{2}$ for all $n$. Then ${\operatorname{diam}}(R_n) \leq D$ for all $n$.

Let ${\varepsilon}> 0$. Fix $N$ large enough so that $\tfrac{1}{N}<\tfrac{{\varepsilon}}{2}$, and write $N({\varepsilon}) = \max_{n \leq N}{\mathrm{card}}(R_n)$. We wish to show that every $R_n$ is ${\varepsilon}$-approximable by a finite network with cardinality up to $N({\varepsilon})$. For any $n\leq N$, we know $R_n$ approximates itself, and ${\mathrm{card}}(R_n) \leq N({\varepsilon})$. Next let $n > N$. It will suffice to show that $R_n$ is ${\varepsilon}$-approximable by $R_N$.

Let $S, T$ be optimal correspondences between $X_n,X_N$ and $Y_n,Y_N$ respectively. Note that ${d_{\mathcal{N}}}(X_N,X_n)\leq {d_{\mathcal{N}}}(X_N,X) + {d_{\mathcal{N}}}(X,X_n) \leq \tfrac{1}{N} + \tfrac{1}{N} = \tfrac{2}{N}$, and similarly ${d_{\mathcal{N}}}(Y_N,Y_n) \leq \tfrac{2}{N}$. Thus ${\operatorname{dis}}(S) \leq \tfrac{4}{N}$ and ${\operatorname{dis}}(T)\leq \tfrac{4}{N}$. Next write $$Q={\left\{(x,y,x',y') \in R_N\times R_n : (x,x')\in S, (y,y')\in T\right\}}.$$ Observe that since $S$ and $T$ are correspondences, $Q$ is a correspondence between $R_N$ and $R_n$. Next we calculate ${\operatorname{dis}}(Q)$: $$\begin{aligned}
{\operatorname{dis}}(Q)&= \max_{\substack{(x,y,x',y'),\\(a,b,a',b')\in Q}}|{\omega}_N((x,y),(a,b)) - {\omega}_n((x',y'),(a',b'))|\\
&= \max_{\substack{(x,y,x',y'),\\(a,b,a',b')\in Q}}|\tfrac{1}{2}{\omega}_{X_N}(x,a)+\tfrac{1}{2}{\omega}_{Y_N}(y,b) - \tfrac{1}{2}{\omega}_{X_n}(x',a') - \tfrac{1}{2}{\omega}_{Y_n}(y',b'))|\\
&\leq \tfrac{1}{2}\max_{(x,x'),(a,a')\in S}|{\omega}_{X_N}(x,a)-{\omega}_{X_n}(x',a')| + \tfrac{1}{2}\max_{(y,y'),(b,b')\in S}|{\omega}_{Y_N}(y,b)-{\omega}_{Y_n}(y',b')|\\
&=\tfrac{1}{2}{\operatorname{dis}}(S) + \tfrac{1}{2}{\operatorname{dis}}(T) \leq \tfrac{4}{N}.\end{aligned}$$ Thus ${d_{\mathcal{N}}}(R_N,R_n) \leq \tfrac{2}{N} < {\varepsilon}$. This shows that any $R_n$ can be ${\varepsilon}$-approximated by a network having up to $N({\varepsilon})$ points. Thus ${\left\{R_n\right\}}$ is uniformly approximable, hence precompact. Thus Claim \[cl:mid\] and the result follow.

Consider the collection of compact metric spaces endowed with the Gromov-Hausdorff distance. This collection can be viewed as a subspace of $({\mathcal{CN}/{\cong^w}},{d_{\mathcal{N}}})$. It is known (via a proof relying on Theorem \[thm:mid\]) that this restricted metric space is geodesic @ivanov2015gromov. Furthermore, it was proved in @dgh-note that an optimal correspondence always exists in this setting, and that such a correspondence can be used to construct explicit geodesics instead of resorting to Theorem \[thm:mid\]. The key technique used in @dgh-note was to take a convergent sequence of increasingly-optimal correspondences, use a result about compact metric spaces called Blaschke's theorem @burago [Theorem 7.3.8] to show that the limiting object is closed, and then use metric properties such as the Hausdorff distance to guarantee that this limiting object is indeed a correspondence. A priori, such techniques cannot be readily adapted to the network setting, and while one can obtain a convergent sequence of increasingly-optimal correspondences, the obstruction lies in showing that the limiting object is indeed a correspondence. This is why we use the indirect proof via Theorem \[thm:mid\].

\[Branching and deviant geodesics\] It is important to note that there exist geodesics in ${\mathcal{CN}/{\cong^w}}$ that deviate from the straight-line form given by Theorem \[thm:geodesic\]. Even in the setting of compact metric spaces, there exist infinite families of branching and deviant geodesics @dgh-note.

Motif reconstruction and skeletons: The case of compact networks {#sec:compact}
================================================================

In this section, we present our result connecting weak isomorphism, equality of motif sets, and strong isomorphism between skeleta (Theorem \[thm:cpt-sisom\]). The results that we have presented so far have all relied on properties of the ${d_{\mathcal{N}}}$ formulation, independent of the intrinsic topological properties of the associated networks. In particular, for a network $(X,{\omega}_X)$, we required only the minimal amount of coupling between the topology of $X$ and the weight function ${\omega}_X$ given by the assertion that ${\omega}_X$ is continuous. For the results in this section, however, we need to introduce a stronger coupling between ${\omega}_X$ and the topology on $X$.

Recall that we often write $x_n {\rightarrow}x$ to mean that a sequence $(x_n)_{n\in {\mathbb{N}}}$ in a topological space $X$ is converging to $x \in X$, i.e. any open set containing $x$ contains all but finitely many of the $x_n$ terms. We also often write "$(x_n)_{n\in {\mathbb{N}}}$ is eventually inside $A\subseteq X$" to mean that $x_n \in A$ for all but finitely many $n$. Also recall that given a subspace $Z\subseteq X$ equipped with the subspace topology, we say that a particular toplogical property (e.g. convergence or openness) holds *relative $Z$* or *rel $Z$* if it holds in the set $Z$ equipped with the subspace topology. Throughout this section, we use the "relative" terminology extensively as a bookkeeping device to keep track of the subspace with respect to which some topological property holds.

\[defn:coherence\] Let $(X,{\omega}_X) \in {\mathcal{N}}$. We say that $X$ has a *coherent* topology if the following axioms are satisfied for any subnetwork $Z$ of $X$ equipped with the subspace topology:

\[A1\]

A set $A\subseteq Z$ is open rel $Z$ if and only if for any sequence $(x_n)_{n\in {\mathbb{N}}}$ in $Z$ converging rel $Z$ to a point $x\in A$, there exists $N \in {\mathbb{N}}$ such that $x_n \in A$ for all $n \geq N$.

\[A2\]

A sequence $(x_n)_{n\in {\mathbb{N}}}$ in $Z$ converges rel $Z$ to a point $x\in Z$ if and only if ${\omega}_X(x_n,\bullet)|_Z {\xrightarrow{\operatorname{unif.}}}{\omega}_X(x,\bullet)|_Z$ and ${\omega}_X(\bullet,x_n)|_Z {\xrightarrow{\operatorname{unif.}}}{\omega}_X(\bullet,x)|_Z.$

Axiom is a characterization of open sets in first countable spaces; we mention it explicitly for easy reference. Axiom gives a characterization of convergence (and hence of the open sets, via ) in terms of the given weight function. Note that is not a strong assumption: for example, it does not discount the possibility of a sequence converging to non-unique limits, it does not force a space to be Hausdorff, and it does not force convergent sequences to be Cauchy.

\[Heredity of coherence\] An alternative formulation of a coherent topology—without invoking the "any subnetwork $Z$ of $X$" terminology—would be to say that $X$ satisfies , and that is *hereditary*, meaning that any subspace also satisfies . Note that first countability is hereditary, so any subspace of $X$ automatically satisfies .

\[Relation to Kuratowski embedding\] In the setting of a metric space $(X,d_X)$, the map $X {\rightarrow}C_b(X)$ given by $x \mapsto d_X(x,\bullet)$ is an isometry known as the *Kuratowski embedding*. Here $C_b(X)$ is the space of bounded, continuous functions on $X$ equipped with the uniform norm. Since this is an isometry, we know that $x_n {\rightarrow}x$ in $X$ iff $d_X(x_n,\bullet) {\xrightarrow{\operatorname{unif.}}}d_X(x,\bullet)$ in $C_b(X)$.

In the setting of a general network $(X,{\omega}_X)$, we do not start with a notion of convergence of the form $x_n {\rightarrow}x$. However, by continuity of ${\omega}_X$, we are able to use the language of convergence in $C_b(X)$. The intuition behind Axiom is to use convergence in $C_b(X)$ to induce a notion of convergence in $X$, with the appropriate adjustments needed for the asymmetry of ${\omega}_X$.

We use the name "coherent" because it was used in the context of describing the coupling between a metric-like function and its topology as far back as in @pitcher1918foundations.

\[Examples of coherent topologies\] Let $(X,d_X)$ be a compact metric space. Axioms - hold in $X$ by properties of the metric topology and the triangle inequality. Let $(Z,d_Z)$ denote a metric subspace equipped with the restriction of $d_X$. Any subspace of a first countable space is first countable, so $Z$ is first countable and thus satisfies . Axiom holds for $Z$ by the triangle inequality of $d_Z$. Thus the metric topology on $(X,d_X)$ is coherent.

The network $N_2{\left(\begin{smallmatrix}
            {{\alpha}} & {{\beta}}\\
                {{\gamma}} & {{\delta}}
                     \end{smallmatrix}\right)}$ where ${\alpha},{\beta},{\gamma},{\delta}$ are all distinct is a minimal example of an asymmetric network with a coherent topology. In general, for a topology on a finite network to be coherent, it needs to be coarser than the discrete topology. Consider the network $N_2{\left(\begin{smallmatrix}
            {1} & {1}\\
                {1} & {1}
                     \end{smallmatrix}\right)}$ on node set $\{p,q\}$. If we assume that the constant sequence $(p,p,\ldots)$ converges to $q$ in the sense of Axiom , then $\{q\}$ cannot be open for Axiom to be satisfied. However, the trivial topology $\{{\varnothing},\{p,q\}\}$ is coherent. More generally, the discrete topology on the skeleton ${\operatorname{sk}}(X)$ of any finite network $X$ (defined below in §\[sec:cpt-skel\]) is coherent.

The directed network with finite reversibility $({\vec{\mathbb{S}}}^1,{{\omega}_{{\vec{\mathbb{S}}}^1 \!\!,\rho}})$ described in §\[sec:dir-s1\] is a compact, asymmetric network with a coherent topology.

By imposing some control on topology, we are now able to talk about continuous maps between compact networks. The following proposition recovers the familiar notion that isometric maps between metric spaces are continuous.

\[prop:cohrt-cts\] Let $(X,{\omega}_X), (Y,{\omega}_Y)$ be networks with coherent topologies. Suppose $f:X {\rightarrow}Y$ is a weight-preserving map. Then $f$ is continuous.

Let $V'$ be an open subset of $Y$, and write $V:= V' \cap f(X)$. Then $V$ is open rel $f(X)$. We need to show that $U:= f{^{-1}}(V') = f{^{-1}}(V)$ is open. Let $x \in U$, and suppose $(x_n)_n$ is a sequence in $X$ converging to $x$. Then $f(x_n) {\rightarrow}f(x)$ rel $f(X)$. To see this, note that $$\begin{aligned}
{\|{\omega}_Y(f(x_n),\bullet)|_{f(X)} - {\omega}_Y(f(x),\bullet)|_{f(X)}\|} 
&= {\|{\omega}_Y(f(x_n),f(\bullet))|_X - {\omega}_Y(f(x),f(\bullet))|_{X}\|} \\
&= {\|{\omega}_X(x_n,\bullet) - {\omega}_X(x,\bullet)\|},\end{aligned}$$ and the latter converges to 0 uniformly by Axiom for $X$. Similarly, ${\|{\omega}_Y(,f(x_n))|_{f(X)} - {\omega}_Y(\bullet,f(x))|_{f(X)}\|}$ converges to 0 uniformly. Thus by Axiom for $f(X)$, we have $f(x_n) {\rightarrow}f(x)$ rel $f(X)$. But then there must exist $N \in {\mathbb{N}}$ such that $f(x_n) \in V$ for all $n\geq N$. Then $x_n \in U$ for all $n \geq N$. Thus $U$ is open rel $X$ by . This concludes the proof.

The skeleton of a compact network {#sec:cpt-skel}
---------------------------------

We now define the skeleton of a compact network and prove that it is terminal in the sense of Definition \[defn:terminal\].

\[An equivalence relation and a quotient space\] Let $(X,{\omega}_X) \in {\mathcal{N}}$. Define the equivalence relation $\sim$ as follows: $$x \sim x' \text{ iff } {\omega}_X(x,z) = {\omega}_X(x',z) \text{ and } {\omega}_X(z,x) ={\omega}_X(z,x') \text{ for all } z\in X.$$ Next define ${\sigma}: X {\rightarrow}X/\sim$ to be the canonical map sending any $x\in X$ to its equivalence class $[x] \in X/\sim$. Also define ${\omega}_{X/\sim}([x],[x']):={\omega}_X(x,x')$ for $[x],[x'] \in X/\sim$. To check that this map is well-defined, let $a,a' \in X$ be such that $a\sim x$ and $a'\sim x'$. Then, $${\omega}_X(a,a') = {\omega}_X(x,a') = {\omega}_X(x,x'),$$ where the first equality holds because $a\sim x$, and the second equality holds because $a'\sim x'$. We equip $X/\sim$ with the quotient topology, i.e. a set is open in $X/\sim$ if and only if its preimage under ${\sigma}$ is open in $X$. Then ${\sigma}$ is a surjective, continuous map.

Observe that when $X$ is compact, $X/\sim$ is the continuous image of a compact space and so is compact. In general, first countability of a topological space is *not* preserved under a surjective continuous map, but it is preserved when the surjective, continuous map is also open @counterexamples [p. 27]. The following proposition gives a sufficient condition on $X$ which will ensure that $X/\sim$ is first countable.

\[prop:quotient-open\] Suppose $(X,{\omega}_X) \in {\mathcal{N}}$ has a coherent topology. Then the map ${\sigma}: X {\rightarrow}X/\sim$ is an open map, i.e. it maps open sets to open sets.

\[Proof of Proposition \[prop:quotient-open\]\] Let $U\subseteq X$ be open. We need to show ${\sigma}{^{-1}}({\sigma}(U))$ is open. For convenience, define $V:= {\sigma}{^{-1}}({\sigma}(U))$. Let $v \in V$. Then ${\sigma}(v)= [v] = [x]$ for some $x \in U$. Let $(v_n)_{n\in {\mathbb{N}}}$ be any sequence in $X$ such that $v_n {\rightarrow}v$ rel $X$. We first show that $v_n {\rightarrow}x$ rel $X$. We know ${\omega}_X(v_n,\bullet) {\xrightarrow{\operatorname{unif.}}}{\omega}_X(v,\bullet)$ and ${\omega}_X(\bullet,v_n) {\xrightarrow{\operatorname{unif.}}}{\omega}_X(\bullet,v)$ by Axiom . But ${\omega}_X(v,\bullet) = {\omega}_X(x,\bullet)$ and ${\omega}_X(\bullet,v) = {\omega}_X(\bullet,x)$, because $x \sim v$. By , we then have $v_n {\rightarrow}x$ rel $X$. But then there exists $N \in {\mathbb{N}}$ such that $v_n \in U \subseteq V$ for all $n \geq N$. This shows that any sequence $(v_n)$ in $X$ converging rel $X$ to an arbitrary point $v \in V$ must eventually be in $V$. Thus $V$ is open rel $X$, by Axiom . This concludes the proof.

\[The skeleton of a compact network\] Suppose $(X,{\omega}_X) \in {\mathcal{CN}}$ has a coherent topology. The *skeleton of $X$* is defined to be $({\mathrm{sk}}(X),{\omega}_{{\operatorname{sk}}(X)}) \in {\mathcal{CN}}$, where ${\mathrm{sk}}(X):= X/\sim,$ and $$\begin{aligned}
{\omega}_{{\operatorname{sk}}(X)}([x],[x'])&:={\omega}_X(x,x') \text{ for all } [x],[x']\in {\mathrm{sk}}(X).\end{aligned}$$

Observe that ${\mathrm{sk}}(X)$ is compact because $X$ is compact, and first countable by Proposition \[prop:quotient-open\] and the fact that the image of first countable space under an open, surjective, and continuous map is also first countable @counterexamples [p. 27]. Furthermore, ${\omega}_{{\operatorname{sk}}(X)}$ is well defined by the definition of $\sim$.

The following lemma summarizes useful facts about weight preserving maps and the relation $\sim$.

\[lem:wp-maps\] Let $(X,{\omega}_X), (Y,{\omega}_Y) \in {\mathcal{N}}$, and let $f: X {\rightarrow}Y$ be a weight preserving surjection. Then,

1.  $f$ preserves equivalence classes of $\sim$, i.e. $x\sim x'$ for $x,x'\in X$ iff $f(x) \sim f(x')$.

2.  $f$ preserves weights between equivalence classes, i.e. ${\omega}_{X/\sim}([x],[x']) = {\omega}_{Y/\sim}([f(x)],[f(x')])$ for any $[x],[x'] \in X/\sim$.

\[Proof of Lemma \[lem:wp-maps\]\]

For the first assertion, let $x\sim x'$ for some $x,x'\in X$. We wish to show $f(x) \sim f(x')$. Let $y\in Y$, and write $y=f(z)$ for some $z\in X$. Then, $${\omega}_Y(f(x),y) = {\omega}_Y(f(x),f(z)) = {\omega}_X(x,z) = {\omega}_X(x',z) = {\omega}_Y(f(x'),f(z)) = {\omega}_Y(f(x'),y).$$ Similarly we have ${\omega}_Y(y,f(x)) = {\omega}_Y(y,f(x'))$ for any $y\in Y$. Thus $f(x) \sim f(x')$.

Conversely suppose $f(x)\sim f(x')$. Let $z\in X$. Then, $${\omega}_X(x,z) = {\omega}_Y(f(x),f(z)) = {\omega}_Y(f(x'),f(z)) = {\omega}_X(x',z),$$ and similarly we get ${\omega}_X(z,x) = {\omega}_X(z,x')$. Thus $x\sim x'$. This proves the first assertion.

The second assertion holds by definition: $${\omega}_{Y/\sim}([f(x)],[f(x')]) = {\omega}_Y(f(x),f(x')) = {\omega}_X(x,x') = {\omega}_{X/\sim}([x],[x']).\qedhere$$

The following proposition shows that skeletons inherit the property of coherence.

\[prop:skel-cohrt\] Let $(X,{\omega}_X)$ be a compact network with a coherent topology. The quotient topology on $({\operatorname{sk}}(X),{\omega}_{{\operatorname{sk}}(X)})$ is also coherent.

\[Proof of Proposition \[prop:skel-cohrt\]\]

Let $Z$ be any subnetwork of ${\operatorname{sk}}(X)$. Axiom holds for any first countable space, and we have already shown that ${\operatorname{sk}}(X)$ is first countable. Any subspace of a first countable space is first countable, so $Z$ satisfies .

Next we verify Axiom . We begin with the "if" statement. Let $[x] \in Z$ and let $([x_n])_n$ be some sequence in $Z$. Suppose we have $${\omega}_{{\operatorname{sk}}(X)}([x_n],[\bullet])|_{Z} {\xrightarrow{\operatorname{unif.}}}{\omega}_{{\operatorname{sk}}(X)}([x],[\bullet])|_Z,\qquad {\omega}_{{\operatorname{sk}}(X)}([\bullet],[x_n])|_Z {\xrightarrow{\operatorname{unif.}}}{\omega}_{{\operatorname{sk}}(X)}([\bullet],[x])|_Z.$$ Then we also have the following: $${\omega}_{X}(x_n,\bullet)|_{{\sigma}{^{-1}}(Z)} {\xrightarrow{\operatorname{unif.}}}{\omega}_{X}(x,\bullet)|_{{\sigma}{^{-1}}(Z)},\qquad {\omega}_{X}(\bullet,x_n)|_{{\sigma}{^{-1}}(Z)} {\xrightarrow{\operatorname{unif.}}}{\omega}_{X}(\bullet,x)|_{{\sigma}{^{-1}}(Z)}.$$ Since $X$ is coherent and ${\sigma}{^{-1}}(Z)$ is a subnetwork, it follows by Axiom that $x_n {\rightarrow}x$ rel ${\sigma}{^{-1}}(Z)$.

Let $V\subseteq Z$ be an open set rel $Z$ containing $[x]$. We wish to show $[x_n] {\rightarrow}[x]$ rel $Z$, so it suffices to show that $V$ contains all but finitely many of the $[x_n]$ terms. Since $Z$ has the subspace topology, we know that $V = Z \cap V'$ for some open set $V' \subseteq {\operatorname{sk}}(X) = {\sigma}(X)$. Write $U':= {\sigma}{^{-1}}(V')$. By continuity of ${\sigma}$, $U'$ is open. Write $U:= {\sigma}{^{-1}}(Z) \cap U'$. Then $U$ is open rel ${\sigma}{^{-1}}(Z)$. Since $x_n {\rightarrow}x$ rel ${\sigma}{^{-1}}(Z)$, all but finitely many of the $x_n$ terms belong to $U$. Thus all but finitely many of the $[x_n]$ terms belong to $V$. Thus $[x_n] {\rightarrow}[x]$ rel $Z$.

Now we show the "only if" statement. First we invoke the Axiom of Choice to pick a representative from each equivalence class of $X/\sim$. We denote this collection of representatives by $Y$ and give it the subspace topology. Define ${\tau}:= {\sigma}|_Y$. Then ${\tau}:Y {\rightarrow}{\operatorname{sk}}(X)$ is a bijection given by $x \mapsto [x]$. By the discussion following Definition \[defn:coherence\], we know that $Y$ is coherent.

Let $([x_n])_n$ be a sequence in $Z$ converging rel $Z$ to some $[x]\in Z$. First we show $x_n {\rightarrow}x$ rel $Y$. Let $A \subseteq Y$ be an open set rel $Y$ containing $x$. Then ${\tau}(A)$ is an open set rel ${\tau}(Y) = {\operatorname{sk}}(X)$ containing $[x]$ (Proposition \[prop:quotient-open\]). In particular, ${\tau}(A) \cap Z$ is open rel $Z$. Thus $([x_n])_n$ is eventually inside ${\tau}(A)\cap Z$, in particular ${\tau}(A)$, by the definition of convergence rel $Z$. Because ${\tau}$ is a bijection, we have that $(x_n)_n = ({\tau}{^{-1}}([x_n])_n$ is eventually inside $A$. Thus any open set rel $Y$ containing $x$ also contains all but finitely many terms of $(x_n)_n$. It follows by the definition of convergence that $x_n {\rightarrow}x$ rel $Y$.

Since $Y$ is coherent, it follows by Axiom that we have ${\omega}_X(x_n,\bullet)|_Y {\xrightarrow{\operatorname{unif.}}}{\omega}_X(x,\bullet)|_Y$ and ${\omega}_X(\bullet,x_n)|_Y {\xrightarrow{\operatorname{unif.}}}{\omega}_X(\bullet,x)|_Y$. By the definition of $\sim$, we then have: $${\omega}_{{\operatorname{sk}}(X)}([x_n],[\bullet]) = {\omega}_X(x_n,\bullet)|_Y {\xrightarrow{\operatorname{unif.}}}{\omega}_X(x,\bullet)|_Y = {\omega}_{{\operatorname{sk}}(X)}([x],[\bullet]).$$ Similarly we have ${\omega}_{{\operatorname{sk}}(X)}([\bullet],[x_n]) {\xrightarrow{\operatorname{unif.}}}{\omega}_{{\operatorname{sk}}(X)}([\bullet],[x])$. This shows the "only if" statement.

This verifies Axiom for $Z$. Since $Z \subseteq {\operatorname{sk}}(X)$ was arbitrary, this concludes the proof.

In addition to coherence, the skeleton has the following useful property.

\[prop:skel-hdrf\] Let $(X,{\omega}_X)$ be a compact network with a coherent topology. Then $({\operatorname{sk}}(X),{\omega}_{{\operatorname{sk}}(X)})$ is Hausdorff.

\[Proof of Proposition \[prop:skel-hdrf\]\] Let $[x]\neq [x'] \in {\operatorname{sk}}(X)$. By first countability, we take a countable open neighborhood base ${\left\{U_n : n \in {\mathbb{N}}\right\}}$ of $[x]$ such that $U_1 \supseteq U_2 \supseteq U_3 \ldots $ (if necessary, we replace $U_n$ by $\cap_{i=1}^n U_i$). Similarly, we take a countable open neighborhood base ${\left\{V_n : n \in {\mathbb{N}}\right\}}$ of $[x']$ such that $V_1 \supseteq V_2 \supseteq V_3 \ldots $. To show that ${\operatorname{sk}}(X)$ is Hausdorff, it suffices to show that there exists $n \in {\mathbb{N}}$ such that $U_n \cap V_n = {\varnothing}$.

Towards a contradiction, suppose $U_n \cap V_n \neq {\varnothing}$ for each $n \in {\mathbb{N}}$. For each $n\in {\mathbb{N}}$, let $[y_n] \in U_n \cap V_n$. Any open set containing $[x]$ contains $U_N$ for some $N \in {\mathbb{N}}$, and thus contains $[y_n]$ for all $n \geq N$. Thus $[y_n] {\rightarrow}[x]$ rel ${\operatorname{sk}}(X)$. Similarly, $[y_n] {\rightarrow}[x']$ rel ${\operatorname{sk}}(X)$. Because ${\operatorname{sk}}(X)$ has a coherent topology (Proposition \[prop:skel-cohrt\]) and thus satisfies Axiom , we then have: $$\begin{aligned}
{\omega}_{{\operatorname{sk}}(X)}([x'],[\bullet]) &= {\operatorname{unif}\lim}_n{\omega}_{{\operatorname{sk}}(X)}([y_n],[\bullet]) = {\omega}_{{\operatorname{sk}}(X)}([x],[\bullet]),\\ {\omega}_{{\operatorname{sk}}(X)}([\bullet],[x']) &= {\operatorname{unif}\lim}_n{\omega}_{{\operatorname{sk}}(X)}([\bullet],[y_n]) = {\omega}_{{\operatorname{sk}}(X)}([\bullet],[x]).\end{aligned}$$ But then $x \sim x'$ and so $[x]=[x']$, a contradiction.

We are now ready to prove that skeletons are terminal, in the sense of Definition \[defn:terminal\] (also recall Definitions \[defn:automorph\] and \[defn:poset\]).

\[Skeletons are terminal\]\[thm:skel-terminal\] Let $(X,{\omega}_X) \in {\mathcal{CN}}$ be such that the topology on $X$ is coherent. Then $({\mathrm{sk}}(X),{\omega}_{{\operatorname{sk}}(X)}) \in {\mathcal{CN}}$ is terminal in ${\mathfrak}{p}(X)$.

\[Proof of Theorem \[thm:skel-terminal\]\] Let $Y\in {\mathfrak}{p}(X)$. Let $f:X {\rightarrow}Y$ be a weight preserving surjection. We first prove that there exists a weight preserving surjection $g:Y {\rightarrow}{\mathrm{sk}}(X)$.

Since $f$ is surjective, for each $y\in Y$ we can write $y=f(x_y)$ for some $x_y\in X$. Then define $g:Y {\rightarrow}{\mathrm{sk}}(X)$ by $g(y):=[x_y]$.

To see that $g$ is surjective, let $[x]\in {\mathrm{sk}}(X)$. Write $y = f(x)$. Then there exists $x_y \in X$ such that $f(x_y) = y$ and $g(y) = [x_y]$. Since $f$ preserves equivalence classes (Lemma \[lem:wp-maps\]) and $f(x_y) = f(x)$, we have $x\sim x_y$. Thus $[x_y] = [x]$, and so $g(y) = [x]$.

To see that $g$ preserves weights, let $y,y'\in Y$. Then, $${\omega}_Y(y,y') = {\omega}_Y(f(x_y),f(x_{y'})) = {\omega}_X(x_y,x_{y'})  = {\omega}_{{\operatorname{sk}}(X)}([x_y],[x_{y'}]) = {\omega}_{{\operatorname{sk}}(X)}(g(y),g(y')).$$ This proves that the skeleton satisfies the first condition for being terminal.

Next suppose $g: Y {\rightarrow}{\mathrm{sk}}(X)$ and $h:Y {\rightarrow}{\mathrm{sk}}(X)$ are two weight preserving surjections. We wish to show $h=\psi\circ g$ for some $\psi \in {\operatorname{Aut}}({\mathrm{sk}}(X))$.

For each $[x]\in {\mathrm{sk}}(X)$, we use the surjectivity of $g$ to pick $y_x\in Y$ such that $g(y_x) = [x]$. Then we define $\psi: {\mathrm{sk}}(X) {\rightarrow}{\mathrm{sk}}(X)$ by $\psi([x]) = \psi(g(y_x)):=h(y_x)$.

To see that $\psi$ is surjective, let $[x] \in {\mathrm{sk}}(X)$. Since $h$ is surjective, there exists $y'_x \in Y$ such that $h(y'_x) = [x]$. Write $[u]=g(y_x')$. We have already chosen $y_u$ such that $g(y_u) = [u]$. Since $g$ preserves equivalence classes (Lemma \[lem:wp-maps\]), it follows that $y'_x \sim y_u$. Then, $$\psi([u]) = \psi(g(y_u)) = h(y_u) = h(y'_x) = [x],$$ where the second-to-last equality holds because $h$ preserves equivalence classes (Lemma \[lem:wp-maps\]).

To see that $\psi$ is injective, let $[x],[x'] \in {\mathrm{sk}}(X)$ be such that $\psi([x]) =h(y_x) = h(y_{x'})= \psi([x'])$. Since $h$ preserves equivalence classes (Lemma \[lem:wp-maps\]), we have $y_x \sim y_{x'}$. Next, $g(y_x) = [x]$ and $g(y_{x'}) = [x']$ by the choices we made earlier. Since $y_x \sim y_{x'}$ and $g$ preserves clusters, we have $g(y_x) \sim g(y_x')$. Thus $[x] = [x']$.

Next we wish to show that $\psi$ preserves weights. Let $[x],[x'] \in {\mathrm{sk}}(X)$. Then, $$\begin{aligned}
{\omega}_{{\operatorname{sk}}(X)}(\psi([x]),\psi([x'])) = {\omega}_{{\operatorname{sk}}(X)}(h(y_x),h(y_{x'})) = {\omega}_Y(y_x,y_{x'}) &= {\omega}_{{\operatorname{sk}}(X)}(g(y_x),g(y_{x'}))\\
& = {\omega}_{{\operatorname{sk}}(X)}([x],[x']).\end{aligned}$$

Thus $\psi$ is a bijective, weight preserving automorphism of ${\mathrm{sk}}(X)$. Finally we wish to show that $h=\psi\circ g$. Let $y\in Y$, and write $g(y) = [x]$ for some $x \in X$. Since $g$ preserves equivalence classes (Lemma \[lem:wp-maps\]), we have $y\sim y_x$, where $g(y_x) = [x]$. Then, $$\psi(g(y)) = \psi([x]) = \psi(g(y_x)) = h(y_x) = h(y),$$ where the last equality holds because $h$ preserves equivalence classes (Lemma \[lem:wp-maps\]). Thus for each $y\in Y$, we have $h(y) = \psi(g(y))$. This shows that the skeleton satisfies the second condition for being terminal. We conclude the proof.

Reconstruction via motifs and skeletons
---------------------------------------

Our goal in this section is to prove that weak isomorphism, equality of motif sets, and strong isomorphism between skeleta are equivalent in the setting of compact networks with coherent topologies. However, we need to preface this theorem by proving some preparatory results.

\[prop:wp-motifs\] Let $(X,{\omega}_X), (Y,{\omega}_Y)$ be compact networks such that ${\mathrm{M}}_n(X) = {\mathrm{M}}_n(Y)$ for all $n \in {\mathbb{N}}$. Suppose $X$ contains a countable subset $S_X$. Then there exists a weight-preserving map $f: S_X {\rightarrow}Y$.

\[Proof of Proposition \[prop:wp-motifs\]\] We proceed via a diagonal argument. Write $S_X= {\left\{x_1,x_2,\ldots, x_n,\ldots\right\}}$. For each $n \in {\mathbb{N}}$, let $f_n : S_X {\rightarrow}Y$ be a map that preserves weights on ${\left\{x_1,\ldots, x_n\right\}}$. Such a map exists by the assumption that ${\mathrm{M}}_n(X)={\mathrm{M}}_n(Y)$.

Since $Y$ is first countable and compact, hence sequentially compact, the sequence $(f_n(x_1))_n$ has a convergent subsequence; we write this as $(f_{1,n}(x_1))_n$. Since $f_k$ is weight-preserving on ${\left\{x_1,x_2\right\}}$ for $k \geq 2$, we know that $f_{1,n}$ is weight-preserving on ${\left\{x_1,x_2\right\}}$ for $n \geq 2$. Using sequential compactness again, we have that $(f_{1,n}(x_2))_n$ has a convergent subsequence $(f_{2,n}(x_2))_n$. This sequence converges at both $x_1$ and $x_2$, and $f_{2,n}$ is weight-preserving on ${\left\{x_1,x_2\right\}}$ for $n \geq 2$. Proceeding in this way, we obtain the diagonal sequence $(f_{n,n})_n$ which converges pointwise on $S_X$. Furthermore, for any $n \in {\mathbb{N}}$, $f_{k,k}$ is weight-preserving on ${\left\{x_1,\ldots, x_n\right\}}$ for $k \geq n$.

Next define $f:S_X {\rightarrow}Y$ by setting $f(x):=\lim_n f_{n,n}(x)$ for each $x \in S_X$. It remains to show that $f$ is weight-preserving. Let $x_n,x_m \in S_X$, and let $k \geq \max(m,n)$. Then ${\omega}_X(x_n,x_m) = {\omega}_Y(f_{k,k}(x_n),f_{k,k}(x_m))$. Using (sequential) continuity of ${\omega}_Y$, we then have: $${\omega}_Y(f(x_n),f(x_m)) = {\omega}_Y(\lim_kf_{k,k}(x_n),\lim_kf_{k,k}(x_m)) = \lim_k {\omega}_Y(f_{k,k}(x_n),f_{k,k}(x_m)) =  {\omega}_X(x_n,x_m).$$ In the second equality above, we used the fact that a sequence converges in the product topology iff the components converge. Since $x_n,x_m \in S_X$ were arbitrary, this concludes the proof.

\[prop:wp-extn\] Let $(X,{\omega}_X),(Y,{\omega}_Y)$ be compact networks. Suppose $f: S_X {\rightarrow}Y$ is a weight-preserving function defined on a countable dense subset $S_X \subseteq X$. Then $f$ extends to a weight-preserving map on $X$.

\[Proof of Proposition \[prop:wp-extn\]\] Let $x\in X\setminus S_X$. By first countability, we take a countable neighborhood base ${\left\{U_n : n \in {\mathbb{N}}\right\}}$ of $x$ such that $U_1 \supseteq U_2 \supseteq U_3 \ldots $ (if necessary, we replace $U_n$ by $\cap_{i=1}^nU_i$). For each $n \in {\mathbb{N}}$, let $x_n \in U_n \cap S_X$. Then $x_n {\rightarrow}x$. To see this, let $U$ be any open set containing $x$. Then $U_n \subseteq U$ for some $n \in {\mathbb{N}}$, and so $x_k \in U_n \subseteq U$ for all $k \geq n$.

Because $Y$ is compact and first countable, hence sequentially compact, the sequence $(f(x_n))_n$ has a convergent subsequence; let $y$ be its limit. Define $f(x) = y$. Extend $f$ to all of $X$ this way.

We need to verify that $f$ is weight-preserving. Let $x,x' \in X$. Invoking the definition of $f$, let $(x_n)_n, (x'_n)_n$ be sequences in $S_X$ converging to $x,x'$ such that $f(x_n) {\rightarrow}f(x)$ and $f(x'_n) {\rightarrow}f(x')$. By sequential continuity and the standard result that a sequence converges in the product topology iff the components converge, we have $$\lim_n {\omega}_Y(f(x_n),f(x'_n)) = {\omega}_Y(f(x),f(x')); \qquad
\lim_n {\omega}_X(x_n,x'_n) = {\omega}_X(x,x').$$

Let ${\varepsilon}> 0$. By the previous observation, fix $N \in {\mathbb{N}}$ such that for all $n\geq N$, we have $|{\omega}_Y(f(x_n),f(x'_n)) - {\omega}_Y(f(x),f(x'))| < {\varepsilon}$ and $|{\omega}_X(x_n,x'_n) - {\omega}_X(x,x')| < {\varepsilon}$. Then, $$\begin{aligned}
|{\omega}_X(x,x') - {\omega}_Y(f(x),f(x'))| &= |{\omega}_X(x,x') - {\omega}_X(x_n,x'_n) + {\omega}_X(x_n,x'_n) - {\omega}_Y(f(x),f(x'))|\\
& \hspace{-4em} \leq |{\omega}_X(x,x') - {\omega}_X(x_n,x'_n)| + |{\omega}_X(f(x_n),f(x'_n)) - {\omega}_Y(f(x),f(x'))| < 2{\varepsilon}.\end{aligned}$$ Thus ${\omega}_X(x,x') = {\omega}_Y(f(x),f(x'))$. Since $x,x' \in X$ were arbitrary, this concludes the proof.

The next result generalizes the result that an isometric embedding of a compact metric space into itself is automatically surjective @burago [Theorem 1.6.14]. However, before presenting the theorem we first discuss an auxiliary construction that is used in its proof.

\[The canonical pseudometric of a network\] \[defn:canonical-pseudo\] Let $(X,{\omega}_X)$ be any network. For any subset $A\subseteq X$, define $\Gamma_A:X\times X {\rightarrow}{\mathbb{R}}_+$ by $$\Gamma_A(x,x'):=\max\big(\sup_{a\in A}|{\omega}_X(x,a) - {\omega}_X(x',a)|,\sup_{a\in A}|{\omega}_X(a,x) - {\omega}_X(a,x')|\big).$$ Then $\Gamma_A$ satisfies symmetry, triangle inequality, and $\Gamma_A(x,x) = 0$ for all $x \in X$. Thus $\Gamma_A$ is a pseudometric on $X$. Moreover, $\Gamma_A$ is a bona fide metric on ${\operatorname{sk}}(A)$. The construction is "canonical" because it does not rely on any coupling between the topology of $X$ and ${\omega}_X$: even the continuity of ${\omega}_X$ is not necessary for this construction.

Next, for any $E\subseteq X$ and any $y\in X$, define $\Gamma_A(y,E):=\inf_{y'\in E}\Gamma_A(y,y')$. Then $\Gamma_A(\bullet,E)$ behaves as a proxy for the "distance to a set" function, where the set is fixed to be $E$.

\[thm:chrt-surj\] Let $(X,{\omega}_X)$ be a compact network with a coherent, Hausdorff topology. Suppose $f:X {\rightarrow}X$ is a weight-preserving map. Then $f$ is surjective.

\[Proof of Theorem \[thm:chrt-surj\]\] Towards a contradiction, suppose $f(X) \neq X$. By Proposition \[prop:cohrt-cts\], $f$ is continuous. Define $X_0:=X$, and $X_n:=f(X_{n-1})$ for each $n \in {\mathbb{N}}$. The continuous image of a compact space is compact, and compact subspaces of a Hausdorff space are closed. Thus we obtain a decreasing sequence of nonempty compact sets $X_0 \supseteq X_1 \supseteq X_2 \supseteq \ldots$. Then $Z:= \cap_{n\in {\mathbb{N}}} X_n$ is nonempty and compact, hence closed.

We now break up the proof up into several claims.

$f(Z) = Z.$

To see this, first note that $f(\cap_{n\in {\mathbb{N}}}X_n) \subseteq \cap_{n\in {\mathbb{N}}}f(X_n) \subseteq Z$. Next let $v \in Z$. For each $n\in {\mathbb{N}}$, let $u_n \in X_n$ be such that $f(u_n) = v$. Since singletons in a Hausdorff space are closed, we know that ${\left\{v\right\}}$ is closed. By continuity, it follows that $f{^{-1}}({\left\{v\right\}})$ is closed.

By sequential compactness, the sequence $(u_n)_n$ has a convergent subsequence that converges to some limit $u$. Since each $u_n \in f{^{-1}}({\left\{v\right\}})$ and a closed set contains its limit points, we then have $u \in f{^{-1}}({\left\{v\right\}})$. Thus $f(u) = v$, and $v \in f(Z)$. Hence $Z = f(Z)$. This proves the claim.

Let $x \in X_0 \setminus X_1$. Define $x_0:=x$, and for each $n \in {\mathbb{N}}$, define $x_n:=f(x_{n-1})$. Then $(x_n)_n$ is a sequence in the sequentially compact space $X$, and so it has a convergent subsequence $(x_{n_k})_k$. Let $z$ be the limit of this subsequence.

$z \in Z$.

To see this, suppose towards a contradiction that $z \not\in Z$. Then there exists $N\in {\mathbb{N}}$ such that $z \not\in X_N$. Since $X_N$ is closed, we have that $X\setminus X_N$ is open. By the definition of convergence, $X\setminus X_N$ contains all but finitely many terms of the sequence $(x_{n_k})_k$. But each $x_{n_k}$ belongs to $X_{n_k}$, which is a subset of $X_N$ for sufficiently large $k$. Thus infinitely many terms of the sequence $(x_{n_k})_k$ belong to $X_N$, a contradiction. Hence $z\in Z$.

Now we invoke the $\Gamma_\bullet$ construction as in Definition \[defn:canonical-pseudo\].

For any $E\subseteq X$ and any $y \in E$, $$\Gamma_E(y,Z) = \Gamma_{f(E)}(f(y),f(Z)).$$

To see this claim, fix $y\in E$. Let $v\in f(Z)$. Then $v =f(y') $ for some $y' \in Z$, and $\Gamma_{f(E)}(f(y),v) = \Gamma_E(y,y')$. To see the latter assertion, let $u\in f(E)$; then $u =f(y'') $ for some $y'' \in E$. Because $f$ is weight-preserving, we then have: $$\begin{aligned}
|{\omega}_X(f(y),u)-{\omega}_X(v,u)| = |{\omega}_X(f(y),f(y''))-{\omega}_X(f(y'),f(y''))| &= |{\omega}_X(y,y'') - {\omega}_X(y',y'')|,\\
|{\omega}_X(u,f(y))-{\omega}_X(u,v)| = |{\omega}_X(f(y''),f(y))-{\omega}_X(f(y''),f(y'))| &= |{\omega}_X(y'',y) - {\omega}_X(y'',y')|.\end{aligned}$$ The preceding equalities show that for each $v \in f(Z)$, there exists $y'\in Z$ such that $\Gamma_{f(E)}(f(y),v) = \Gamma_E(y,y')$. Conversely, for any $y'\in Z$, we have $\Gamma_{f(E)}(f(y),f(y')) = \Gamma_E(y,y')$. It follows that $\Gamma_{f(E)}(f(y),f(Z)) = \Gamma_E(y,Z)$.

$\Gamma_{X}(x,Z) = 0$.

To see this, assume towards a contradiction that $\Gamma_X(x,Z) = {\varepsilon}> 0$ ($\Gamma_X$ is positive by definition). Since $f(Z) = Z$, we have by the preceding claim that $\Gamma_X(x,Z) = \Gamma_{f(X)}(f(x),Z) = \ldots = \Gamma_{f^n(X)}(f^n(x),Z)$ for each $n \in {\mathbb{N}}$. In particular, for any $k \in {\mathbb{N}}$, $${\varepsilon}= \Gamma_{f^{n_k}(X)}(f^{n_k}(x),Z) \leq  \Gamma_{f^{n_k}(X)}(f^{n_k}(x),z) \leq \Gamma_X(f^{n_k}(x),z).$$ Here the first inequality follows because the left hand side includes an infimum over $z \in Z$, and the second inequality holds because the right hand side includes a supremum over a larger set.

Since $x_{n_k} {\rightarrow}z$ rel $X$, we have by Axiom that $${\|{\omega}_X(x_{n_k},\bullet) - {\omega}_X(z,\bullet)\|} {\xrightarrow{\operatorname{unif.}}}0
,\qquad 
{\|{\omega}_X(\bullet,x_{n_k}) - {\omega}_X(\bullet,z)\|} {\xrightarrow{\operatorname{unif.}}}0.$$ Thus for large enough $k$, we have: $$\sup_{y\in X}|{\omega}_X(x_{n_k},y) - {\omega}_X(z,y)|< {\varepsilon}, \qquad 
\sup_{y\in X_{n_k}}|{\omega}_X(y,x_{n_k}) - {\omega}_X(y,z)| < {\varepsilon}.$$ Thus $\Gamma_{X}(f^{n_k}(x),z) < {\varepsilon}$, which is a contradiction. This proves the claim.

Recall that by assumption, $x\not\in Z$. For each $n \in {\mathbb{N}}$, let $z_n \in Z$ be such that $\Gamma_X(x,z_n) < 1/n$. Then for each $x'\in X$, we have $$\begin{aligned}
\max{\left(}|{\omega}_X(x,x') - {\omega}_X(z_n,x')|,|{\omega}_X(x',x) - {\omega}_X(x',z_n)|{\right)}&< 1/n, \text{ i.e. }\\
\max {\left(}{\|{\omega}_X(x,\bullet) - {\omega}_X(z_n,\bullet)\|}, {\|{\omega}_X(\bullet,x) - {\omega}_X(\bullet,z_n)\|}{\right)}&< 1/n.\end{aligned}$$ Thus the sequence $(z_n)_n$ converges to $x$, by Axiom . Hence any open set containing $x$ also contains infinitely many points of $Z$ that are distinct from $x$. Thus $x$ is a limit point of the closed set $Z$, and so $x \in Z$. This is a contradiction.

Recall that a topological space is *separable* if it contains a countable dense subset.

\[thm:cpt-sisom\] Suppose $(X,{\omega}_X), (Y,{\omega}_Y)$ are separable, compact networks with coherent topologies. Then the following are equivalent:

1.  $X \cong^w Y$. \[item:cpt-wisom\]

2.  ${\mathrm{M}}_n(X) = {\mathrm{M}}_n(Y)$ for all $n \in {\mathbb{N}}$.\[item:cpt-motifs\]

3.  ${\operatorname{sk}}(X) \cong^s {\operatorname{sk}}(Y)$.\[item:cpt-skel\]

\[Proof of Theorem \[thm:cpt-sisom\]\]

(\[item:cpt-motifs\]) follows from (\[item:cpt-wisom\]) by the stability of motif sets (Theorem \[thm:motif-stab\]). (\[item:cpt-wisom\]) follows from (\[item:cpt-skel\]) by the triangle inequality of ${d_{\mathcal{N}}}$. We need to show that (\[item:cpt-motifs\]) implies (\[item:cpt-skel\]).

First observe that ${\operatorname{sk}}(X)$, being a continuous image of the separable space $X$, is separable, and likewise for ${\operatorname{sk}}(Y)$. Let $S_X, S_Y$ denote countable dense subsets of ${\operatorname{sk}}(X)$ and ${\operatorname{sk}}(Y)$. Next, because ${d_{\mathcal{N}}}(X,{\operatorname{sk}}(X)) = 0$, an application of Theorem \[thm:motif-stab\] shows that ${\mathrm{M}}_n(X) = {\mathrm{M}}_n({\operatorname{sk}}(X))$ for each $n\in {\mathbb{N}}$. The analogous result holds for ${\operatorname{sk}}(Y)$. Thus ${\mathrm{M}}_n({\operatorname{sk}}(X)) = {\mathrm{M}}_n({\operatorname{sk}}(Y))$ for each $n \in {\mathbb{N}}$. Since $X$ and $Y$ have coherent topologies, so do ${\operatorname{sk}}(X)$ and ${\operatorname{sk}}(Y)$, by Proposition \[prop:skel-cohrt\]. By Propositions \[prop:wp-motifs\] and \[prop:wp-extn\], there exist weight-preserving maps ${\varphi}: {\operatorname{sk}}(X) {\rightarrow}{\operatorname{sk}}(Y)$ and $\psi:{\operatorname{sk}}(Y) {\rightarrow}{\operatorname{sk}}(X)$. Define $X^{(1)}:=\psi({\operatorname{sk}}(Y))$ and $Y^{(1)}:= {\varphi}({\operatorname{sk}}(X))$. Also define ${\varphi}_1$ and $\psi_1$ to be the restrictions of ${\varphi}$ and $\psi$ to $X^{(1)}$ and $Y^{(1)}$, respectively. Finally define $X^{(2)}:= \psi_1(Y^{(1)})$ and $Y^{(2)}:= {\varphi}_1(X^{(1)})$. Then we have the following diagram.

\(11) at (0,2) <span>${\operatorname{sk}}(X)$</span>; (12) at (0,0) <span>${\operatorname{sk}}(Y)$</span>; (21) at (3,2) <span>$X^{(1)}$</span>; (22) at (3,0) <span>$Y^{(1)}$</span>; (31) at (6,2) <span>$X^{(2)}$</span>; (32) at (6,0) <span>$Y^{(2)}$</span>;

at (1.5,0) <span>$\supseteq$</span>; at (1.5,2) <span>$\supseteq$</span>; at (4.5,0) <span>$\supseteq$</span>; at (4.5,2) <span>$\supseteq$</span>;

\(11) edge node\[above, pos=0.25\]<span>${\varphi}$</span>(22); (12) edge node\[pos=0.15, above\]<span>$\psi$</span>(21); (21) edge node\[above, pos=0.25\]<span>${\varphi}_1$</span>(32); (22) edge node\[pos=0.15, above\]<span>$\psi_1$</span>(31);

Now $\psi \circ {\varphi}$ is a weight-preserving map from ${\operatorname{sk}}(X)$ into itself. Furthermore, it is continuous by Proposition \[prop:cohrt-cts\]. Since ${\operatorname{sk}}(X)$ is Hausdorff (Proposition \[prop:skel-hdrf\]), an application of Theorem \[thm:chrt-surj\] now shows that $\psi\circ {\varphi}: {\operatorname{sk}}(X) {\rightarrow}{\operatorname{sk}}(X)$ is surjective. It follows from Definition \[defn:terminal\] that $\psi\circ {\varphi}$ is an automorphism of ${\operatorname{sk}}(X)$, hence a bijection. It follows that ${\varphi}$ is injective. The dual argument for ${\varphi}\circ \psi$ shows that $\psi$ is also injective.

Since $\psi\circ{\varphi}({\operatorname{sk}}(X)) = X^{(2)} = {\operatorname{sk}}(X)$ and $X^{(2)} \subseteq X^{(1)} \subseteq {\operatorname{sk}}(X)$, we must have $X^{(1)} = {\operatorname{sk}}(X)$. Similarly, $Y^{(1)} = {\operatorname{sk}}(Y)$. Thus ${\varphi}:{\operatorname{sk}}(X) {\rightarrow}{\operatorname{sk}}(Y)$ and $\psi:{\operatorname{sk}}(Y) {\rightarrow}{\operatorname{sk}}(X)$ are a weight-preserving bijections. In particular, we have ${\operatorname{sk}}(X) \cong^s {\operatorname{sk}}(Y)$. This concludes the proof.

Discussion {#sec:discussion}
==========

In this paper, we proved that compact networks (equipped with pullback topologies) can be reconstructed from their motif sets. This result should be viewed as an extension of a result of Gromov on reconstruction of metric spaces from curvature classes. One of the key concepts necessary in proving our result was the notion of weak isomorphism that we developed in prior work. In the current paper, we also closed the gap between strong and weak isomorphism that arose in our previous work by showing that two compact networks (equipped with pullback topologies) are weakly isomorphic if and only if their skeleta are strongly isomorphic. We also constructed interesting families of compact, asymmetric networks equipped with pullback topologies that fall within the scope of our results.

In the intervening sections, we further explored the properties of the metric space ${\mathcal{CN}}/{\cong^w}$ obtained by quotienting out weak isomorphism classes. We proved that this space is complete, exhibits rich precompact families, and is geodesic. Moreover, we produced examples to show that: (1) geodesics may branch, and (2) there may be multiple geodesics joining two points in this space.

This paper should be viewed as the second part in a two-part series of papers laying out the theoretical foundations of the network distance ${d_{\mathcal{N}}}$. Whereas the current work is more theoretical, the reader who is interested in the practical aspects of applying ${d_{\mathcal{N}}}$ to real network data should consult our prior work, where we discuss the computation of ${d_{\mathcal{N}}}$ in detail.

Acknowledgments {#acknowledgments .unnumbered}
---------------

This work is partially supported by the National Science Foundation under grants CCF-1526513 and IIS-1422400. Facundo Mémoli acknowledges support from the Mathematical Biosciences Institute at the Ohio State University.

{'source': 'arXiv_out/1804'}