# Geometric Sampling of Networks

Vladislav Barkanass, Jürgen Jost and Emil Saucan∗ ORT Braude College of
Technology, Karmiel 2161002, Israel, and Jürgen Jost, Max Planck Institute for
Mathematics in the Sciences, Leipzig 04103, Germany, and Emil Saucan, ORT
Braude College of Technology, Karmiel 2161002, Israel<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
∗ Corresponding author<EMAIL_ADDRESS>
###### Abstract.

Motivated by the methods and results of manifold sampling based on Ricci
curvature, we propose a similar approach for networks. To this end we make
appeal to three types of discrete curvature, namely the graph Forman-, full
Forman- and Haantjes-Ricci curvatures for edge-based and node-based sampling.
We present the results of experiments on real life networks, as well as for
square grids arising in Image Processing. Moreover, we consider fitting Ricci
flows and we employ them for the detection of networks’ backbone. We also
develop embedding kernels related to the Forman-Ricci curvatures and employ
them for the detection of the coarse structure of networks, as well as for
network visualization with applications to SVM. The relation between the Ricci
curvature of the original manifold and that of a Ricci curvature driven
discretization is also studied.

J. Jost and E. Saucan were partly supported by the German-Israeli Foundation
Grant I-1514-304.6/2019.

##  1\. Introduction

People study and make appeal to the coarse geometry of networks, constantly
and for a long time now, whether they do it conscientiously (rarely) or not
(in most cases). We shall demonstrate this shortly, however, to make this even
clear, let us specify what we, informally, mean by “Coarse Geometry”: The
study of the geometric (topological) properties, without “looking at” the
small scales. In other words, one does not discern between objects that,
viewed from sufficiently far away, look the same. Perhaps the simplest and
immediate example of such a large scale geometry (or, in John Lott’s
suggestive words, “Mr. Magoo geometry”) is given by the integer grid in the
Euclidean plane. (For more insights and technical definitions and results,
see, e.g [21], [45], [30], as well as Appendix 1.)

The Complex Networks community has been exposed to this approach – and makes
by now use of it – via the notion of Gromov hyperbolicity, itself stemming
from Gromov’s seminal work on hyperbolic groups [20]. The – perhaps somewhat
theoretical in the eyes of many practitioners – notion above is connected to
the notion of network backbone, underlying the long-distance relations between
major network regions. Indeed, the connection between negative curvature and
these “communication highways” in networks has been emphasized in [40]. We
recall below its formal definition, as introduced in [69]:

######  Definition 1.1.

We denote the _backbone_ of a network $G=\\{V,E\\}$ as a subnetwork
$G^{\prime}=\\{V^{\prime},E^{\prime}\\}$ ($V^{\prime}\subseteq V$,
$E^{\prime}\subseteq E$) that captures structurally important nodes (_hubs_)
and edges (_bridges_). A node is typically termed _hub_ if it has a high
degree and a high betweenness centrality. _Bridges_ denote edges that govern
the mesoscale structure of $G$, for instance by forming long-range connections
between communities. The backbone $G^{\prime}$ is _structure-preserving_ ,
i.e., its structural features (e.g., node degree distribution, community
structure) are representative of $G$.

The intuition behind this definition is quite simple: Since high-degree nodes
(hubs) form the centers of the major network communities, the edges that form
strong connections between them bridge the corresponding communities. The
motivation for the study of the network backbone stemmed from Communication
Networks, more precisely from that of the Internet, where it is a quite
technical and specific term: The edges belonging to the backbone represent the
Internet’s “highways”, and are therefore physically implemented by the fastest
existing optical connections. Moreover, they are owned and operated by the so
called network backbone providers (NBPs), who are mainly governments and the
largest telecommunication companies (see, e.g., [39]). However, the rational
behind the notion of backbone is not restricted solely to the Internet, but it
also arises naturally in Social Networks [3], and beyond [6].

Before passing further on, let us mention here that the network backbone is
also referred to the core of the network [39]. It is precisely this more
geometric term which we have in mind in our approach here in, where networks
are viewed as 1-dimensional versions of manifolds, endowed with a coarse
geometry.

Another, older, far better known, and permeating almost (if not) all of large
scale applications of Computer Science, inadvertent application of coarse
geometry is sampling. Indeed, by choosing certain points in a space, and
discarding the “less important” points in their neighborhood, in conjunction
(in many instances), with the related process of clustering, one in effect
discards the small scale structure, as encoded in the discarded vicinities,
and rather concentrates on the large scale, i.e. coarse structure. Clearly
sampling the “heavy” curvature nodes or edges in a network, and using them as
clustering centers is natural. In fact, such clustering based on the
combinatorial version of Gaussian curvature, that is the clustering
coefficient has been employed for clustering in networks for quite some time
now [65], and it was only natural to extend this method to a proper notion of
metric curvature that allows of the incorporation of weights, be they node or
edge weights, accounting for the simultaneous presence of the two types of
weights as well [53]. Thus we connect the two interpretations of the notion of
coarse geometry, namely the global one, motivated largely by Gromov’s
hyperbolicity, and the local one, (as opposed to the infinitesimal one),
obtained by the approximation of manifolds by networks. We shall show,
moreover, that sampling by Ricci curvature, is not just an heuristic,
empirical procedure, and it has, in fact, deep mathematical justifications
that also point to its full potential. We shall prove our assertion in Section
5 below.

The reminder of this paper is structured as follows: In the next section we
bring the mathematical background, motivating our thrust for a Ricci curvature
driven sampling of networks. Section 3 is dedicated to the introduction of
three types of discrete Ricci curvature, namely graph Forman, full Forman and
Haantjes Ricci curvatures, that we deem particularly suited for the networks’
sampling task as well to first experiments, on real-life networks as well as
square grids that arise in Imaging. Furthermore, fitting Ricci flows are
considered and applied to the networks’ backbone detection. By “fitting”, we
mean Ricci flows in which the role of the Ricci curvature is taken by any of
the consider discretization. We follow in Section 4 with an application of the
Forman Ricci curvatures and associated Bochner Laplacians to the study of the
coarse geometry of networks, via the development of fitting embedding kernels.
An application to the visualization of kernel spaces and networks is also
presented. In Section5we return to the motivating manifold sampling and show
the connections between the Ricci curvature of the given manifold and the
Forman curvatures of the resulting discretizations. The last section comprises
a terse summary of the paper and an outlook towards the directions of further
study that we deem more important.

##  2\. Background: Ricci Curvature Based Sampling of Manifolds

Sampling by curvature, namely choosing the sampling points whose metric
density is inverse proportional to curvature has been rediscovered and applied
in Imaging and Graphics, as well as in more theoretical problems a number of
times. (The relevant bibliography is far too extensive to include in the
present paper, therefore we rather point the reader to the articles mentioned
above and to the sources mentioned therein.) The most general method is
perhaps the one in [54], that also extends it to the sampling of more general
signals.

However, all the approaches mentioned above are based on extrinsic curvature,
thus in practice necessitating first finding an isometric embedding in
$\mathbb{R}^{n}$, a problem that is highly nontrivial for abstract
manifolds.111This being in contrast with the Imaging/Graphics case where
images/meshes are already embedded in $\mathbb{R}^{3}$. Therefore, it is
highly desirable to find a sampling method based on intrinsic curvature.
Fortunately, it turns out that the basis for such a method exists for a long
time in Geometry [22], and it is based on Ricci curvature (see, e.g. [29]),
which is an intrinsic quantity.

Before proceeding further, let us emphasize that the choice of Ricci
curvature, instead, for instance, of scalar curvature [29], is not just a whim
or fad, and stems from the absorption of the fundamental fact that networks
are determined not by their members (nodes), but rather by their connections
(edges), and Ricci curvature is, on networks, a quantity attached to edges (as
discretizations of vectors).

The basic idea resides in the constriction of so called efficient packings:

######  Definition 2.1.

Let $\in M^{n}$ be a Riemannian manifolds and let $p_{1},\ldots,p_{n_{0}}$ be
points $\in M^{n}$, satisfying the following conditions:

  1. (1)

The set $\\{p_{1},\ldots,p_{n_{0}}\\}$ is an $\varepsilon$-net on $M^{n}$,
i.e. the balls $\beta^{n}(p_{k},\varepsilon)$, $k=1,\ldots,n_{0}$ cover
$M^{n}$;

  2. (2)

The balls (in the intrinsic metric of $M^{n}$)
$\beta^{n}(p_{k},\varepsilon/2)$ are pairwise disjoint.

Then the set $\mathcal{N}=\\{p_{1},\ldots,p_{n_{0}}\\}$ is called a minimal
$\varepsilon$-net and the packing with the balls
$\beta^{n}(p_{k},\varepsilon/2)$, $k=1,\ldots,n_{0}$, is called an efficient
packing. The set $\\{(k,l)\,|\,k,l=1,\ldots,n_{0}\;{\rm
and}\;\beta^{n}(p_{k},\varepsilon)\cap\beta^{n}(p_{l},\varepsilon)\neq\emptyset\\}$
is called the intersection pattern of the minimal $\varepsilon$-net of the
efficient packing.

There exists a canonical simplicial complex having as vertices the centers of
the balls $\beta^{n}(p_{k},\varepsilon)$, which is constructed by adding a
$k$-simplex for every collection of $k+1$ balls with nonempty intersection.

Following Kanai [30], we call the graph $G(\mathcal{N})$ given by the
1-skeleton of the simplicial complex constructed above a discretization of
$X$, with separation $\varepsilon$ and covering radius $\varepsilon$ (or a
$\varepsilon$-separated net). Further more, we say that $G(\mathcal{N})$ has
bounded geometry iff there exists $\rho_{0}>0$, such that
$\rho(p)\leq\rho_{0}$, for any vertex $p\in\mathcal{N}$, where $\rho(p)$
denotes the degree of $p$ (i.e. the number of neighbours of $p$). Furthermore,
in the case of unbounded manifolds, we add, to the conditions in Definition
2.1 above, the following requirement:

(3) The graph $\mathcal{N}$ is maximal with respect to inclusion.

If $M^{n}$ is a closed, connected n-dimensional Riemannian manifold such that
it has sectional curvature $k_{M}$ bounded from below by $k$, ${\rm
diam}M^{n}$ bounded from above by $D$, and ${\rm Vol}M^{n}$ is bounded from
below by $v$, such $\varepsilon$-nets can be constructed by taking any maximal
set of points with disjoint $\varepsilon/2$-balls, and the geometric
generation process of such a maximal set is based on the close connection
between the growth rate of volumes of balls in manifolds and Ricci curvature.
Moreover, since only volumes of balls arguments are employed, one can replace
the last condition by the more general one ${\rm Ric}_{M}\geq(n-1)k$ (see,
e.g., [32]). Furthermore, the connection between volume and Ricci curvature
can be extended to more general measures and to the generalized Ricci
curvature developed by Lott-Villani [36] and Sturm [61]. Therefore, it is
natural to seek and generalize the results of Grove and Petersen [22] to
metric measure spaces. Such an extension of the classical case construction to
the metric measure spaces context does, indeed exist [50].

Most importantly, the discretizations rendered in the process of proof, are,
indeed, coarsely equivalent (coarsely isometric) – see Definition 4.1 – to the
original metric measure space, in a manner that is quite deep (see [50],
Theorem 5.6 and Theorem 5.11, as well as their corollaries). Still, the most
important consequence, from our point of view, appears already in [50],
Corollary 4.6, namely the fact that the graphs (networks) obtained encode the
essential topology (homotopy) of the sampled space. Moreover, it is a
byproduct of the construction (see [22], [50]) that even if the graph-based
reconstruction of the given space is only a coarse one, the number of such
“guesses” is finite, and is, moreover, independent of the specific geometry of
the manifold and the measure, and it depends only on bounds on dimension,
volume, curvature and diameter.

It is therefore, only natural and intuitive to expect that a similar Ricci
curvature based sampling should apply to weighted networks, viewed as metric
measure spaces (with measures concentrated at the nodes and metric prescribed
by the edge weights), should encode the essential topology of the network.

######  Remark 2.2.

However, while most researchers have come to view graphs/networks as metric
spaces, the model of metric measure spaces for weighted networks, is yet to be
widely adopted by the Complex Networks community, even though it is a most
natural way of describing the properties of such objects. To this end, a
natural idea is to incorporate the node weights and edge weights into one
expressive metric, thus rendering any weighted network into a “honest to God”
metric space, whose geometric properties (curvature, geodesics, embeddings,
etc.) can than be investigated with (more-or-less) classical tools. (An
example of such a comprehensive metric is the so called degree path metric –
see, e.g. [31]. Another well known such metric is the resistance metric (see,
e.g. [15]). For the convenience of the reader we have expanded on these
important metrics in Appendix 3.)

It is worth noting that, initially, only edge weights were considered, and for
such weights a global metric is standard, namely the so called path metric
(which Computer Science students commonly confuse with the most popular
algorithm for its computations, namely the Dijkstra algorithm.) A number of
modeling problems, in particular some of Mathematical Biology motivated lately
the search for “good” metrics that take into account node weights exclusively.
(For such an example see, for instance, [53].) From the applications viewpoint
it become clear quite early that a comprehensive model of networks should
include both edge and node weights (and that the combinatorial model is, a
fortiori, quite unsatisfactory). The reason that such complete sets of weights
were not previously employed in large scale experimental studies was due to
the lack of a large enough sample of available data sets. However, as the
field of Complex Networks evolved and expanded, better data sets have been
published, thus the focus of the community is finally shifting towards the
study of such networks.

The discussion above raises the natural question whether there exists an
optimal metric, at least for understanding of the problems studied in the
present paper. The somewhat disappointing (but expectable) answer is that
there is no “best” metric fitted for the study of all networks, not even for
the study of a certain type of discrete Ricci curvature and its flow. From the
empirical networks viewpoint this fact is easily understandable: Each
community has developed its specific metric or set of metrics which best serve
its needs, in the sense that they closely model the type of network that
represents the object of interest for that group. (In certain settings, a
natural metric, up to minor variations, imposes itself, such in the case of
Imaging – see the relevant examples in the sequel. The same holds true for
electric networks, where the resistance metric is the default one.) These ad
hoc metrics might differ widely from the standard, mathematically motivated
ones mentioned above and, as such, they do not necessarily behave as well in
concordance with the various type of curvatures. From a mathematical
viewpoint, it is important to remember that the discrete Ricci curvatures
captures different aspects of the classical notion (the Forman-Ricci
curvatures vs. the Haantjes curvature), or include higher dimensional aspects
of the networks (full Forman and Haantjes, vs. graph Forman). Therefore, their
behaviors in conjunction with the various metrics also diverge widely. It is,
therefore, advisable to understand their comparative behavior using the same
background metric. This is the approach adopted herein, where the standard
path metric was employed. Note that using that, when using a common metric,
various discretization capture the same essential behavior of evolving
networks – see [47]. Moreover while from a mathematician’s viewpoint, the
degree path metric is apparently ideal (as the number of studies employing it
seems to suggest), in practice its connection with a specific type of discrete
curvature, e.g. Olliver-Ricci curvature, is far less strong than expected. In
fact, for certain types of Semantic Networks, the probabilistic version of the
resistance metric (see Appendix 3) is by far the best suited [13]. Thus the
problem of determining the best suited metric to be used with a specific
discrete Ricci curvature, for each type of network, deserves an extensive
experimental study, whose scope and breadth are far beyond those of the
present paper.

Yet another – and simpler – generalization of Ricci curvature to metric
measure spaces has been devised, based on the works of Bakry, Emery and Ledoux
[1, 2]. More specifically, they consider manifolds with density, i.e.
Riemannian manifolds $M^{n}$, additionally endowed, with a smooth, positive
density function $\Psi=\Psi(x)$, that induces weighted $n$\- and
$(n-1)$-volumes, e.g. in the classical cases $n=2$ and $n=3$, volume, area and
length. More precisely, the volume, area and length elements $dV,dA,ds$ of the
weighted manifold $(M^{n},\Psi)$ are given by:

$dV=\Psi dV_{0},dA=\Psi dA_{0},ds=\Psi ds_{0}\,,$

where $dV_{0}$ represents the natural (Riemannian) volume element of $M^{n}$,
etc. Usually density functions of the type $\Psi(x)=e^{-\varphi(x)}$ are
considered. (However more general density functions have also been studied –
see [37].)

The Bakry, Emery and Ledoux generalization to manifolds with density of Ricci
curvature is defined as:

(2.1) ${\rm Ric_{\varphi}}={\rm Ric}+{\rm Hess}\varphi\,,$

(where Hess denotes the Hessian matrix). It is important for us to note that,
for surfaces, Ricci curvature reduces, essentially, to Gaussian curvature $K$,
more precisely $K=\frac{1}{2}{\rm Ric}$. Another, closely related, but perhaps
more intuitive, generalization of Gaussian curvature for weighted surfaces is
due to Corwin et al. [14], namely:

(2.2) $K_{\varphi}=K+\Delta\varphi\,,$

where $\Delta\varphi$ denotes the Laplacian of $\varphi$. It should be
stressed that this represents a natural generalization: It reduces to the
usual Gaussian curvature (up to a multiplicative constant) for
$\varphi\equiv{\rm const.}$ and, moreover, it also satisfies a generalized
Gauss-Bonnet Theorem. The reader should note that, unlike Morgan [37], but
following other authors, and, moreover, in concordance with Forman’s work, we
adopt here the “+” convention for the sign of the Hessian and Laplacian
commonly, since this is more intuitive, at least in the context of Imaging
where weights, that is grayscale values are always positive. This simpler
approach can be indeed applied to the sampling of images, where grayscale
value can be interpreted as a measure (distribution) over the pixels’ grid
[35]. This fact further encourages us to extend the Ricci curvature-based
sampling to Complex Networks.

##  3\. Discrete Ricci Curvature

There are several ways of incorporating both node and edge weights into a
comprehensive Ricci curvature for networks. Since a full explanation of the
ideas and techniques employed in devising the notions below would take us too
far afield, and, furthermore, we have detailed this in previous works and,
moreover, in the present paper we employ these discrete notions of Ricci
curvature only in the practical, network context, we do not develop these
definitions here, but rather restrict ourselves essentially to bringing the
relevant formulas.

The simplest (from a computational viewpoint) type of network Ricci curvature
is the 1-dimensional (graph) version introduced in [60] of Forman’s Ricci
curvature [24], originally devised for weighted $CW$ complexes of dimension
$\geq 2$. It is derived from the classical Bochner-Weitzenböck formula of
Riemannian Geometry [29], that connects the Bochner (or Hodge) Laplacian on a
manifold and its various curvatures, namely

(3.1) $\Box_{p}=dd^{*}+d^{*}d=\nabla_{p}^{*}\nabla_{p}+{\rm Curv}(R)\,,$

where $\Box_{p}$ denotes the Riemann-Laplace operator $\Box_{p}$ on $p$-forms,
$\nabla_{p}^{*}\nabla_{p}$ is the Bochner (or rough) Laplacian and ${\rm
Curv}(R)$ is an expression of the curvature tensor with linear coefficients
where $\nabla_{p}$ denotes the covariant derivative operator.

Forman [24] demonstrated that an analogue of the Bochner-Weitzenböck formula
holds in the general setting of CW complexes, of which graphs and polyhedra
are particular cases. More precisely, he showed that there exists a canonical
decomposition of the form:

(3.2) $\Box_{p}=B_{p}+F_{p}\,,$

where $B_{p}$ is a non-negative operator and $F_{p}$ is a diagonal matrix.
$B_{p}$ and $F_{p}$ are called, in analogy with the classical Bochner-
Weitzenböck formula, the combinatorial Laplacian and the combinatorial
curvature function, respectively.

In particular, for $p=1$, we obtain

(3.3)
$\displaystyle\Box_{1}p(e)=\Box_{1}(e,e)=\frac{w(v_{1})}{w(e)}+\frac{w(v_{2})}{w(e)}\,;$

where $v_{1},v_{2}$ are the end nodes of the edge $e$, and
$w(v_{1}),w(v_{2}),w(e)$ represent their respective weights. (For the
definition in the general case, see Appendix 2.)

Then, given a $p$-dimensional cell $\alpha=\alpha^{p}$, one defines the
curvature function $F_{p}:C_{p}\rightarrow C_{p}$

(3.4) $\displaystyle\mathcal{F}_{p}(\alpha)=\langle
F_{p}(\alpha),\alpha\rangle.$

In the special case of dimension $p=1$ one defines, by analogy with the
classical case, the discrete (weighted) Forman-Ricci curvature on
$\alpha=\alpha^{1}$, i.e. 1-cells (edges), namely

(3.5) $\displaystyle{\rm Ric_{F}}(\alpha)=\mathcal{F}_{1}(\alpha).$

Before proceeding further, let us note the similarity between Formula (2.2)
and Forman’s Formula (3.2), and the (essential) identification of Gaussian and
Ricci curvature in the surface case, further suggest Forman’s Ricci curvature
as a possible sampling tool. Furthermore, this similarity suggests that
theleft-hand term $\Box_{1}$ can be interpreted not just like a “corrected”
Laplacian, but also as a “adjusted” curvature. Thus, one is conducted towards
a possible sampling of networks based on Forman-Bochner Laplacian, instead of
its Ricci curvature counterpart. This coupling with a Laplacian, that opens
further directions for possible applications, represents yet another
advantage, besides its computational simplicity, of Forman’s curvature over
Ollivier’s one.

While the formula of ${\rm Ric_{F}}$ in the case of generic $n$-dimensional
$CW$ complexes is quite complicated (see Appendix 2), in the 1-dimensional
case, that is of graphs/networks, it reduces to the following elementary
formula:

(3.6)
$\mathbf{F}(e)=w(e)\left(\frac{w(v_{1})}{w(e)}+\frac{w(v_{2})}{w(e)}-\sum_{e(v_{1})\
\sim\ e,\ e(v_{2})\ \sim\
e}\left[\frac{w(v_{1})}{\sqrt{w(e)w(e(v_{1}))}}+\frac{w(v_{2})}{\sqrt{w(e)w(e(v_{2}))}}\right]\right)\,;$

where $\mathbf{F}$ denotes the Forman-Ricci curvature for networks222notice
the change of notation for clarity reasons, and where

  * •

$e$ denotes the edge under consideration between two nodes $v_{1}$ and
$v_{2}$;

  * •

$w(e)$ denotes the weight of the edge $e$ under consideration;

  * •

$w(v_{1}),w(v_{2})$ denote the weights associated with the nodes $v_{1}$ and
$v_{2}$, respectively;

  * •

$e(v_{1})\sim e$ and $e(v_{2})\sim e$ denote the set of edges incident on
nodes $v_{1}$ and $v_{2}$, respectively, after excluding the edge $e$ under
consideration which connects the two nodes $v_{1}$ and $v_{2}$, i.e.
$e(v_{1}),e(v_{2})\neq e$.

While, as discussed above, we are mainly interested in edge-centric measures,
and more specifically in Ricci curvature, one can also define the Forman-
scalar curvature, in manner similar to the $PL$ manifolds case pioneered by
Stone [61] (see also [18]), to be

(3.7) $\kappa_{{\bf F}(v)}={\bf F}(v)=\sum_{e_{k}\sim v}{\rm
Ric}_{F}(e_{k})\,;$

where $e_{k}\sim v$ denotes the edges $e_{k}$ adjacent to the vertex $v$.

For 2-dimensional complexes the formula of the Forman-Ricci curvature is only
slightly more complicated:

(3.8) ${\rm Ric}_{\rm F}(e)=w(e)\left[\left(\sum_{e\sim
f}\frac{w(e)}{w(f)}+\sum_{v\sim e}\frac{w(v)}{w(e)}\right)\right.$ $\hskip
75.39963pt-\left.\sum_{\hat{e}\parallel e}\left|\sum_{\hat{e},e\sim
f}\frac{\sqrt{w(e)\cdot w(\hat{e})}}{w(f)}-\sum_{v\sim
e,v\sim\hat{e}}\frac{w(v)}{\sqrt{w(e)\cdot w(\hat{e})}}\right|\right]\;;$

where “$\hat{e}\parallel e$” denotes that the edges $\hat{e}$ and $e$ are
parallel, that is they can both belong to a common 2-dimensional face, or have
a common vertex, but not both, simultaneously; and where “$\sim$” has the same
significance as in the previous formula (i.e. incidence).

There are two special cases extremely important in applications. The first
case is that of square grids, as they arise most naturally in Imaging. Due to
the specific (and evident) parallelism relationship, the resulting formula
attains the following simple form:

(3.9) ${\rm
Ric}_{F}(e_{0})=w(e_{0})\left[\left(\frac{w(e_{0})}{w(c_{1})}+\frac{w(e_{0})}{w(c_{2})}\right)-\left(\frac{\sqrt{w(e_{0})w(e_{1})}}{w(c_{1})}+\frac{\sqrt{w(e_{0})w(e_{2})}}{w(c_{2})}\right)\right]\,,$

The second special case is that of $PL$ manifolds and, more generally, of
graphs and networks where the only 2-cycles are triangles. This type of
structure is, again, relevant in Graphics and related fields. Moreover, it is
precisely the type of graph (network) that we developed and discussed above.
The fitting formula is

(3.10) ${\rm
Ric}_{F}(e)=w(e)\left[\sum_{t>e}\frac{w(e)}{\omega(t)}+\left(\frac{w(v_{1})}{w(e)}+\frac{w(v_{2})}{w(e)}\right)\right.$
$\hskip 113.81102pt\left.-\sum_{\tilde{e}\sim
e}\left|\sum_{t>e,\,t>\tilde{e}}\frac{\sqrt{w(e)w(\tilde{e})}}{w(t)}-\sum_{v<e,\,v<\tilde{e}}\frac{w(v)}{\sqrt{w(e)w(\tilde{e})}}\right|\right]\,.$

where “$t>e$” denotes that the edge $e$ is a face of the triangle (2-cycle)
$t$.

To differentiate between the 1- and 2-dimensional versions of Forman-Ricci
curvature, we shall refer to the former as the graph or reduced Forman-Ricci
curvature, and to the later as the full Forman-Ricci curvature (or simply the
Forman-Ricci curvature).

Again, we can define the fitting scalar curvature, in a similar manner:

(3.11) $\kappa_{{\rm Ric}_{F}}(v)={\rm Ric}_{F}(v)=\sum_{e_{k}\sim v}{\rm
Ric}_{F}(e_{k})\,;$

where, again, $e_{k}\sim v$ stands for all the edges $e_{k}$ adjacent to the
vertex $v$.

######  Remark 3.1.

Note that, while we concentrated above on Forman’s Ricci curvature, one can
substitute instead Ollivier’s discretization [42], [43], as it is widely
employed in Network Theory (see, e.g. [64], [40], [41], [48], [49]). We
preferred Forman’s curvature for a number of reasons, perhaps not the least of
them being its clear computational advantages, as well as for the easy manner
in which it extends to higher dimension. An additional advantage we already
mentioned above, namely that by its defining formula it comes coupled with a
Laplacian, also allows us to explore new directions of study – See Section 4
below.

The third type of discrete Ricci curvature that we have considered in our
experiments is one that we recently introduced [56], [57], namely the
Haantjes-Ricci curvature [25]. In contrast with Forman-Ricci curvature, whose
definition is based on the discretization of and advanced techniques in
Riemannian Geometry, namely the Bochner-Weitzenböck formula (see for instance
[29]), Haantjes curvature is derived from a purely metric notion [25] devised
originaly to study curves in metric spaces. Before we can define this new type
of Ricci curvature, we first have to introduce the curvature of paths and
cycles:

Given a curve $c$ in a metric space $(X,d)$, and $p,q,r$ points on $c$, $p$
between $q$ and $r$, the Haantjes curvature of the curve $c$, at the point $p$
is defined as

(3.12) $\kappa_{H}^{2}(p)=24\lim_{q,r\rightarrow
p}\frac{l(\widehat{qr})-d(q,r)}{\big{(}d(q,r)\big{)}^{3}}\,;$

where $l(\widehat{qr})$ denotes the length, in the intrinsic metric induced by
$d$, of the arc $\widehat{qr}$. In the network case, $\widehat{qr}$ is
replaced by a path $\pi=v_{0},v_{1},\ldots,v_{n}$, and the subtending chord by
edge $e=(v_{0},v_{n})$. When discretizing this notion we should start from the
following two observations: (a) The limiting process has no meaning in this
discrete case; (b) The normalizing constant “24” which ensures that, the limit
in the case of smooth planar curves will coincide with the classical notion,
is redundant in the discrete setting setting. We are thus led to the following
definition of the Haantjes curvature of a simple path $\pi$:

(3.13)
$\kappa_{H}^{2}(\pi)=\frac{l(\pi)-l(v_{0},v_{n})}{l(v_{0},v_{n})^{3}}\,;$

where $l(v_{0},v_{n})=d(v_{0},v_{n})$, where, as above, $e=(v_{0},v_{n})$
represents an edge and where $l$ denotes the length, in the considered metric
$d$. (If no specific metric is given, one can always metricize an edge
weighted graph using the standard path metric – see, e.g. [15].) In
particular, in the case of the combinatorial metric, we obtain that, for path
$\pi=v_{0},v_{1},\ldots,v_{n}$ as above, $\kappa_{H}(\pi)=\sqrt{n-1}$. It is
important to note that considering simple paths does not represent any
restriction, since a metric arcs are, by definition, simple curves. However,
to capture in the discrete context the local nature of the Ricci (and scalar)
curvature, as well as to make computations feasible, we shall restrict to
paths $\pi$ such that $\pi^{*}=v_{0},v_{1},\ldots,v_{n},v_{0}$ is an
elementary cycle.

In the case of general edge weights, one can not apply directly the Haantjes
curvature, since in this case the network is not necessarily a metric space,
given that the total weight $w(\pi)$ of a path $\pi=v_{0},v_{1},\ldots,v_{n}$
is not necessarily smaller than the weight of its subtending chord
$e=(v_{0},v_{n})$. In fact, a graph endowed with general weighted graphs will
not constitute a metric space, since such weights can (and usually will) fail
the triangle inequality. However, it is still possible to use the Haantjes
curvature, and we even can turn this to our own advantage, by reversing the
roles of $w(\pi)$ and $w(v_{0},v_{n})$ in the definition of the Haantjes
curvature and assigning a minus sign to the curvature of cycles for which this
occurs. In consequence, this approach allows us to define a variable sign
Haantjes curvature of cycles (hence, as it will become clear below, a Ricci
curvature as well), even if the given network is not a directed one.

Before proceeding further, it should be noted that the case when
$w(v_{0},v_{1},\ldots,v_{n})=w(v_{0},v_{n})$, i.e., that of zero curvature of
the 2-cell $\mathfrak{c}$ with
$\partial\mathfrak{c}=v_{0},v_{1},\ldots,v_{n},v_{0}$, straightforwardly
corresponds to the splitting case for the path metric induced by the weights
$w(v_{i},v_{i+1})$.

We can now define Haantjes-Ricci curvature in a straightforward manner, as

(3.14) $\kappa_{H}(e)={\rm Ric}_{H}(e)=\sum_{\pi\sim e}\kappa_{H}(\pi)\,;$

where $\pi\sim e$ denote the paths that connect the vertices adjacent to the
edge $e$.

Moreover, as for the Forman-Ricci curvatures, one can also define the
Haantjes-scalar curvature:

(3.15) $\kappa_{H}(v)={\rm scal}_{H}(v)=\sum_{e_{k}\sim v}{\rm
Ric}_{H}(e_{k})\,;$

where $e_{k}\sim v$ stands for all the edges $e_{k}$ adjacent to the vertex
$v$.

Figure 1. A small combinatorial network (i.e. with all vertex and edge weights
equal to 1) based on the well known “Dolphins” social network [32],
emphasizing the differences between the three types of Ricci curvature
considered. ${\rm Ric}_{H}(e_{1})$ is zero, since there are no cycles (faces)
adjacent to $e_{1}$ and ${\bf F}(e_{1})$ also equals $0$ (as it is really seen
from the degrees of its end vertices) and, moreover, so does ${\rm
Ric}_{F}(e_{1})$, since in this case it coincides, due to the absence of
adjacent faces, with ${\bf F}(e_{1})$. ${\rm Ric}_{H}(e_{2})=\sqrt{2}$, given
that there is only one face – a triangle – adjacent to $e_{2}$. Degree
counting easily renders ${\bf F}(e_{2})=-1$, and ${\rm Ric}_{F}(e_{2})=2$. In
the case of $e_{3}$, degree counting renders ${\bf F}(e_{3})=-4$. Since the
edge $e_{3}$ is adjacent to 2 triangles and a quadrangle, ${\rm
Ric}_{H}(e_{3})=2\sqrt{2}+\sqrt{3}$, while given the fact that there is only
one edge parallel to $e_{3}$, namely $(v_{7}v_{8})$, we obtain that ${\bf
F}(e_{2})=-4$.

###  3.1. Curvature Based Sampling

As we have already emphasized in the introduction, Ricci curvature allows us
not only to focus on the edge-centric study of networks, but also to analyze
the distribution and role of higher order correlation in networks. It follows,
therefore, that an edge-based sampling is the natural one, if one wishes to
explore the edge and higher order correlations structure. Nevertheless, the
classical graph-theoretical approach to networks is still relevant, thus we
also explore the vertex-based networks’ sampling and compare it to the edge
based one.

We first exemplify the network sampling using all the types of curvatures
introduced above on two examples of real-life weighted networks:333We restrict
only to these so not to overextend the experiments section. The classical
“Kangaroo” one, which due to its small size allows one to better relate the
computations to the network structure, and the increasingly popular “Les
Misérables” one, describing the relationships between the characters in the
classical Hugo novel. The data for all the networks, except that for the “C.
elegans”, was downloaded from the KONECT website [32]; in the later case the
source is [12]. For each network and each type of curvature, both edge (Ricci
curvature) based and vertex (scalar curvature) are included. In the original
network, Ricci curvature is depicted according to the standard method, i.e.
edge thickness being proportional to the absolute value of the curvature,
whereas sign is indicated using the (standard) color code: Red color for
negative curvature and blue color for positive one. All the considered
networks are weighted ones – for the nature of the specific weights the reader
is referred to [32], [12] and the references therein. The sampling method
adopted here is the simplest, yet widely adopted one of high-pass filtering
the curvature with high absolute curvature. More precisely, for a prescribed
percentage of absolute curvature, the vertices with curvature below the chosen
threshold are removed, together with the edges adjacent to them, in case that
vertex-based sampling is adopted. I the case when edge-based sampling is
chosen, the procedure is similar, with the evident difference that, in this
case, edges are removed. Note that in this case the ends of the deleted edges
are not removed, except in the case of so called leaves (i.e. edges with at
least one vertex of degree 1). The percentages differ from a network to
another and from a type of curvature to another and they were chosen such that
approximatively the same number of vertices would be retained.

Figure 2. The graph Forman-Ricci curvature based sampling by vertices (middle)
and by edges (below) of a Kangaroo social network (above). Here 40$\%$ of the
edges were retained, yet the main features of the image is still clearly
visible.

Figure 3. The Graph Forman-Ricci curvature edges-based sampling (middle) and
by vertices-based (below) of the Les Misérables social network (above).

Figure 4. The Graph Forman-Ricci curvature based sampling (left) of a
classical test image (right). Here 20$\%$ of the edges were retained, yet the
main features of the image is still clearly visible. Note the mostly red
coloring of the resulting curvature images, showing that, except at a sparse
set of pixels, the graph Forman-Ricci curvature is negative.

Ideally one should include in the computation of the full Forman-Ricci
curvature all the cycles. However, determining them is a computationally
costly operation, especially so since higher order cycles (faces) are quite
common in real-life networks [69]. Nevertheless, in the study of real-life
networks, one can discard, at least in first approximation, the higher order
faces. Indeed, both in social and biological networks, higher order cycles
represent weaker connections, that should be taken, at best, with a lower
weight signifying their reduced contribution (or probability of existence). In
fact, and due partially to the powerful theoretical tools available in this
case, the study of higher order correlations is commonly restricted only to
order 3 ones (i.e. triangles). Given these considerations, and the fact that
we are here only proposing a new paradigm for networks sampling, rather than
concentrating for the extensive study of a specific (type of) network, we
restrict our computations to 3- and 4-cycles, that is to faces that are
triangles or quadrangles.

Figure 5. The full Forman-Ricci curvature-based sampling by vertices (middle)
and by edges (below) of a Kangaroo social network (above). Here 40$\%$ of the
edges were retained.

Figure 6. The full Forman-Ricci curvature-based sampling by vertices (middle)
and by edges (below) of the Les Misérables social network (above). Here 10$\%$
of the edges were retained.

The results of the vertex- and edge-based sampling, using the various
considered Ricci curvatures, of a couple of well-known social networks are
depicted in Figures 2-4 and 5-7. Let us note that at least for medium sized
and large scale networks, the “common core” of obtained by the intersection of
the sampling results using the different curvatures can be quite small,
illustrating the fact that each of the curvatures captures quite different
different properties of the network, as it is the case with the various
discretizations of any classical curvature. Thus the core represents the
subgraph that comprises the essential geometric properties of a network. Note
also that for smaller networks and/or larger percentage of remaining nodes,
the cores are both larger and closer to each of the sampling results.

Figure 7. The common “core” (below), i.e. set of vertices of the “Les
Misérables” network after sampling by all of the curvatures considered (above,
from left to right: Haantjes, graph Forman, full Forman). In each of the cases
$15\%$ of the original vertices were retained. Note that the resulting,
sampled networks are widely different. Moreover, note that the common nodes
(in red, below) is quite restricted. This is a direct consequence of the fact
that different discretizations of Ricci curvature capture diverse properties
of the classical notion, thus rendering a small set of nodes and edges that
capture the most essential geometric properties of the network.

In addition to these real life networks we are also including the example of a
regular square grid as it arises naturally in Imaging – See Figures 4, 8 and
9. More precisely, nodes denote centers of pixels and edges connect adjacent
pixels, edge weights (lengths) are given by the differences in height, that is
gray scale intensity of the image, and areas of the resulting 2-cells
(quadrangles) are obtained, via Heron’s formula from the edge lengths. (For
details and illustrations see [4].) The color scheme adopted for sign
depiction is the same as before. Given the construction of the network and its
weights, only vertex sampling sampling is considered. As one can see from the
results depicted in Figure 4, when the sampling was applied to a classical
test image, even when retaining only 25$\%$ of the original nodes (pixels) the
original image is still quite easily recognizable and, moreover, curvature
does indeed function as an edge detector, as expected. (See also [50] and the
references therein.)

Figure 8. The full Forman-Ricci curvature based sampling of the “Cameraman”
(left) compared to the graph Forman-Ricci curvature based one (right). Here,
again, 20$\%$ of the edges were retained. Note that both blue and red edges
are visible, showing that full Forman-Ricci curvature takes both positive and
negative values.

Besides the two versions of Forman-Ricci curvature we experimented with the
Haantjes-Ricci curvature. Again, as in case of the full Forman-Ricci curvature
(and for the same reasons), we restrict ourselves to 3- and 4-cycles. In
addition to its applicability to networks, it is a natural curvature measure
for images [51]. However, in this case the obtained results are not as
promising as those obtained using the full Forman-Ricci curvature, given than
for images, that is for surfaces embedded in $\mathbb{R}^{3}$, it takes only
positive values – see Figure 9.

Figure 9. The Haantjes-Ricci curvature based sampling (left) of a classical
test image (right). Here again 20$\%$ of the edges were retained and the main
features of the image are still clearly visible. However, it is evident that
Haantjes curvature is outperformed, in the case of images, by both Forman
curvatures. Note the blue coloring of the resulting curvature image, showing
that the Haantjes-Ricci curvature is positive, a fact that follows from it
being computed using the usual distances in Euclidean space.

####  3.1.1. Ricci flow

Besides the simple, direct approach to sampling that filters out a certain,
prescribed percentage of edges, a more automatic – and with far deeper
theoretical motivation – exists, namely the one based on the Ricci flow [68],
[69], [59]. This approach not only is preferable, since it captures the
evolution of the network “under its own pressure”, but it also seems
especially effective in determining the so called network backbone [67].

In contrast with our previous experiments in [66], [67], [69], we employ here
the normalized flow, in order to ensure that the metric does not contract
(i.e. the weights do not converge to zero) and the network does not collapse
to a node in the limit. This normalized flow for networks is defined, in
analogy with that for surfaces (see, e.g. [23]), as

(3.16) $\displaystyle\frac{\partial\omega(e)}{\partial
t}=-\left(\rm{Ric}\left(\omega(e)\right)-\rm{\overline{Ric}}\right)\cdot\omega(e)\,;$

where $\rm{\overline{Ric}}$ denotes the mean Ricci curvature, and ${\rm Ric}$
stand for the graph Forman, full Forman or Haantjes Ricci curvature, according
to the chosen curvature. Also, since in the setting of networks time is also
assumed to evolve in discrete steps and each “clock” (that is, time step) has
a length of 1, the Ricci flow takes the following form:

(3.17)
$\displaystyle\tilde{\omega}(e)-\omega(e)=-\left(\rm{Ric}\left(\omega(e)\right)-\rm{\overline{Ric}}\right)\cdot\omega(e)\,;$

where $\tilde{\omega}(e)$ denotes the new (updated) value of $\omega(e)$ (and
$\omega(e)$ is the original i.e. given - one).

To emphasize its capabilities, we illustrate the flow on a larger network,
more precisely on the “Windsurfers” social network [32] – see Figures 10-12.
Note that a certain lower threshold for the edge weights needs to be
predetermined, so “noise”, that is to say edges with weights close to zero
would not be included in the next iteration. In the experiments included here
we have chosen to adopt a rather rather high threshold, such that at each
step, at least $90\%$ of the edges appearing in the previous step would be
preserved. Furthermore, in the computations using the graph Forman-Ricci
curvature, the need to normalize curvature arose, in order to prevent abrupt
jumps/collapses in curvature. However, no such normalization was needed for
the Haantjes-Ricci curvature flow, a fact that seems to point to a relative
advantage of this type of curvature, over the graph Forman one, as it seems to
preclude fast collapse.

Figure 10. The “Windsurfers” network and its evolution under the graph Forman-
Ricci flow. In descending order, from above: The original network, and the
network after 1, 3 and 5 iterations, respectively.

Figure 11. The “Windsurfers” network and its evolution under the full Forman-
Ricci flow. In descending order, from above: The original network, and the
network after 1, 3 and 5 iterations, respectively. Note that, at least in this
example, the Haantjes-Ricci flow is decreasing the size of the evolving
network faster than the graph Ricci curvature.

Figure 12. The “Windsurfers” network and its evolution under the Haantjes-
Ricci flow. In descending order, from above: The original network, and the
network after 1, 3 and 5 iterations, respectively. Note that, at least in this
example, the Haantjes-Ricci flow is decreasing the size of the evolving
network faster than the graph Ricci curvature.

Note that, even only a very small number of iterations were considered, Ricci
curvature evolves, as expected from the theory in the smooth and combinatorial
(circle-packing based) cases, to a constant. This phenomenon is most manifest
in the Graph Forman-Ricci flow, and the least evident for the Full Forman-
Ricci flow. Beyond the specific convergence speeds of each of the flows, this
phenomenon occurs probably because, as already mentioned above, only
triangular and quadrangular faces were considered, a fact which greatly
simplifies and speeds-up computations, but also changes drastically the
topology of the evolving 2-complex.

Figure 13. The evolution of curvature of the “Windsurfers” network under each
of the studied Ricci flows. In descending order, from above: The Graph Forman-
Ricci curvature flow, Full Forman-Ricci curvature flow and the Haantes-Ricci
flow. Observe the extremely fast convergence towards a constant under the
Graph Forman-Ricci curvature flow.

######  Remark 3.2.

As noted in [66] a scalar (Yamabe) flow is also possible. However, here we
concentrated on the Ricci curvature, that is to say edge-centric approach.

##  4\. Coarse Embedding and an Application to SVM

A common theme in Geometry and in many of its applications (in some cases
still in a non-deliberate manner) is the embedding, with least distortion, of
a given structure/space, in a familiar, larger ambient space. For instance, in
classical Geometry and Topology, this ambient space is usually
$\mathbb{R}^{n}$, for some $n$ large enough, whereas any metric space is
isometrically embeddable in $l^{\infty}$. Also, more recently, embeddings of
networks in the Hyperbolic Plane $\mathbb{H}^{2}$ or Space $\mathbb{H}^{3}$
have become quite common (see, e.g. [7] and the references therein).

It is therefore most natural to ask, not only if a coarse embedding (viewed as
a metric measure space) of a weighted graph exists, but also whether there
exists an “automatic” procedure to achieve such an embedding. By a coarse
embedding of a metric space $(X,d)$ into another metric space $(Y,\rho)$, we
mean a map $i:X\rightarrow Y$, such that there exist increasing, unbounded
functions $\eta_{1},\eta_{2}:\mathbb{R}\rightarrow\mathbb{R}$, such that

(4.1)
$\eta_{1}(d(x_{1},x_{2}))\leq\rho(i(x_{1}),i(x_{2}))\leq\eta_{2}(d(x_{1},x_{2}))\,,$

for any $x_{1},x_{2}\in X$.

The “automatic” embedding method we alluded to above is one that is canonical
in SVM techniques, and classical in Fourier Analysis and its various
applications, in particular in Signal and Image Processing, namely that of
reproducing kernels. Recall the following

######  Definition 4.1.

Given a set $X$, symmetric kernel is a symmetric function $k:X\times
X\rightarrow\mathbb{R}$, i.e. $k(x,y)=k(y,x)$, for any $x,y\in X$.

A kernel $k$ is said to have

  1. (1)

positive type if the matrix $K_{m}=\\{k(x_{i},x_{j})\\}_{i,j=1}^{m}$ is
positive semidefinite for all $m\in\mathbb{N}$;

and

  2. (2)

negative type if the matrix $K_{m}=\\{k(x_{i},x_{j})\\}_{i,j=1}^{m}$ is
negative semidefinite for all $m\in\mathbb{N}$;

Positive and negative type kernels are interrelated by the following classical
result

######  Proposition 4.2 (Schoenberg’s Lemma).

Let $k$ be a symmetric kernel on set $X$. Then the following statements are
equivalent:

  1. (1)

The kernel $k$ is of negative type;

  2. (2)

The kernel $\kappa={\rm exp}(-tk)$ is of positive type, for each $t>0$.

(For a proof see, e.g. [45].)

From Schoenberg’s Lemma and the fact that $k^{\alpha}$ can be written as

$k^{\alpha}(x,y)=C\int_{0}^{\infty}(1-e^{-t\kappa(x,y)})t^{-\alpha/2-1}dt\,$

where $C=C_{\alpha}$ is a positive constant, it follows (cf. [45]) that
following corollary hods:

######  Corollary 4.3.

Let $k\geq 0$ be a kernel of negative type on $X$. Then
$\kappa=\kappa^{\alpha}$ is also of negative type, for any $0<\alpha<1$.

######  Remark 4.4.

An (effectively coarse) embedding method for networks as well as higher
dimensional spaces was proposed in [51]. While the approach suggested therein
applies to more general spaces than networks and, the embedding space is the
familiar $\mathbb{R}^{n}$, it still is less than intuitive, since it makes
appeal to a family of quasi-metrics. While this approach allows for the the
network to be studied at many scales, it is also more complicated then the one
adopted here (and based on the path degree metric). Furthermore, the method
introduced herein has also the advantage of coming in conjunction with a
reproducing kernel, that allows for the automation required in SVM related
applications. Therefore, the corollary above shows that a way of studying
networks at many scales, akin to the one in [51], exists also in the coarse
embedding (kernel) approach.

Since the operators $\Box_{1}$ and $B_{1}$ are symmetric as functions of the
end nodes $u,v$ of an edge $e=(u,v)$, they define (in analogy to the classical
Laplacian) reproducing kernels $k_{\Box},k_{B}$ on any given network.
Moreover, since by its very construction/definition $B_{p}$ is a positive
semidefinite, it follows that $k_{p}$ is also positive semidefinite (i.e. a
“classical” reproducing kernel). By a direct application of a classical result
(for a proof, see, e.g. [45], Theorem 11.15), we get

######  Theorem 4.5.

Let $k$ be a symmetric kernel on $X$. Then,

  1. (1)

If $k$ is of positive type, then there exists a map
$\varPhi:X\rightarrow\mathcal{H}$, where $\mathcal{H}$ is a real Hilbert
space, such that $k(x,y)=<\varPhi(x),\varPhi(y)>$, for any $x,y\in X$.

  2. (2)

If $k$ is of negative type and, furthermore, $k(x,x)=0$ for any $x\in X$, then
there exists a map $\varPhi:X\rightarrow\mathcal{H}$, where $\mathcal{H}$ is a
real Hilbert space, such that $k(x,y)=||\varPhi(x)-\varPhi(y)||^{2}$, for any
$x,y\in X$.

Moreover, ${\bf F}$ and ${\rm Ric}_{F}$ are both symmetric functions (again
viewed as acting on pairs of nodes defining edges), thus kernels $k_{\bf F}$
and $k_{{\rm Ric}_{F}}$ can be defined. However, neither version of Forman’s
Ricci curvature is positive, therefore a mapping into a real Hilbert space, as
for the Laplacians, is not possible for these curvature-based kernels. In
fact, ${\bf F}$ is not negative only if both its end nodes have degree 2, that
is only the degenerate case of cycles and graph “spurious” vertices of degree
2, i.e graph subdivisions homeomorphic to a “good” graph can have edges of
non-negative curvature. It can, therefore, be surmised that proper networks
have pure Forman curvature ${\bf F}<0$. (Note that this does not hold for
${\rm Ric}_{F}$.)

Unfortunately, part (2) of the theorem above (the one regarding negative type
operators) does not hold, since it requires that $k(x,x)=0$, for all $x\in X$,
which, of course, does not hold neither for $\Box_{1}$, nor for $B_{1}$.
However, one can still map the kernels $k_{\Box},k_{B}$ to a Hilbert space
precisely as above, after modifying them into fitting related positive
operators, by putting
$k^{*}_{\Box}=e^{-k_{\Box}};\>\>k^{*}_{B}=e^{-k_{B}}$.444In fact, for every
$t>0$, the kernels $k^{*,t}_{\Box}(x,y)=e^{-tk_{\Box}(x,y)};$,
$k^{*,^{t}}_{B}(x,y)=e^{-tk_{B}(x,y)}$ are of positive type (see [45],
Proposition 11.12.

Moreover (and perhaps more important in our context) there exists a coarse
embedding of any (finite) network into a (real) Hilbert space. This follows
from the fact that, for instance, $e^{-k_{F}}$ is a positive kernel, and from
the fact that the kernel $k_{F}$, is effective i.e. the edges
$\\{e=(x,y)\,|\,|k(e)|<K\\}$, $K>0$ generate the coarse structure of the
network (see [45] for technical details), which, given in the case at hand, of
finite networks, can naturally to be taken as the discrete coarse structure
generated by sets that contain only a finite number of points (nodes) off the
diagonal. Therefore we can apply the following result:

######  Theorem 4.6 ([45], Theorem 11.16.).

Let $X$ be a coarse space. Then the following statements are equivalent:

  1. (1)

$X$ can be coarsely embedded into a Hilbert space.

  2. (2)

There exists an effective negative type kernel on $X$.

In fact, the observation above can be strengthened in more than one way: On
the one hand, the result can be applied to any of the kernels above, not only
the one considered above. Furthermore, due to finiteness, one can relax the
effectiveness condition by dispensing with the absolute value in the defining
inequality. On the other hand, the Forman-Ricci curvature kernels are
effective even if one considers $\varepsilon$-nets obtained from the geometric
sampling of non-compact Riemannian manifolds with Ricci curvature bounded from
below, given that the sampling procedure is essentially the same as for the
compact ones (see [30] for the classical case and [50] for the generalization
to metric measure spaces). The only difference between the compact case and
the one at hand is that one has to relax somewhat the coarseness isometry
definition and the resulting $\varepsilon$-net, endowed with the combinatorial
metric (i.e. with edge lengths $\equiv 1$), will be only roughly isometric to
the given manifold, where rough isometry is defined as follows:

######  Definition 4.7 (Rough isometry).

Let $(X,d)$ and $(Y,\delta)$ be two metric spaces, and let $f:X\rightarrow Y$
(not necessarily continuous). $f$ is called a rough isometry iff

  1. (1)

There exist $a\geq 1$ and $b>0$, such that

$\frac{1}{a}d(x_{1},x_{2})-b\leq\delta(f(x_{1}),f(x_{2}))\leq
ad(x_{1},x_{2})+b\,,$

  2. (2)

there exists $\varepsilon_{1}>0$ such that

$\bigcup_{x\in X}{B(f(x),\varepsilon_{1})}=Y;$

(that is $f$ is $\varepsilon_{1}$-full.)

It follows that all types of kernels based on Forman’s discretization of the
Bochner-Weitzenböck may be applied in the variety of SVM problems where
kernels are usually employed, such as clustering and classification. In
particular, one can compute the so called kernel distance [28], [44]:

######  Definition 4.8.

Given a similarity function (kernel)
$K:\mathbf{R}^{d}\times\mathbf{R}^{d}\rightarrow\mathbf{R}$, such that
$K(p,p)=1$, for any $p\in\mathbb{R}^{d}$, and given sets
$P,Q\subset\mathbf{R}^{d}$, the kernel distance $D_{K}(P,Q)$ is defined as

(4.2) $D_{K}(P,Q)=\sqrt{\sum_{p\in P}\sum_{p^{\prime}\in
P}K(p,p^{\prime})-2\sum_{p\in P}\sum_{q\in Q}K(p,q)+\sum_{q\in
Q}\sum_{q^{\prime}\in Q}K(q,q^{\prime})}\,.$

######  Remark 4.9.

$D_{K}(P,Q)$ is not a metric if $K$ is not positive definite.

Note that in the special case $P=\\{p\\},Q=\\{q\\}$, we obtain
$D^{2}_{K}(P,Q)=2(1-K(p,q))$, thus $1-K(p,q)$ can be viewed as a proper
squared distance, since $1-K(p,p)=0$.

######  Remark 4.10.

The quantity $\kappa(P,Q)=\sum_{p\in P}\sum_{q\in Q}K(p,q)$ is called the
cross-similarity (of $P$ and $Q$), thus $D_{K}(P,Q)$ can be expressed, more
simply, in terms of the cross similarity, rather then in means of the kernel
as $\kappa(P,P)-2\kappa(P,Q)+\kappa(Q,Q)$.

A first application of the kernel distance is in the visualization of kernel
spaces and data in general [62], [28]. The embedding method employed here is
the so called mutidimensional scaling (MDS) one (see, e.g. [8]). More
precisely, given $N$ points $p_{1},\ldots,p_{N}$, we can approximate their
position in a kernel space $\mathcal{H}\subset\mathbb{R}^{d}$ by
$y_{1},\ldots,y_{N}\in\mathbb{R}^{d}$, by minimizing the cost-function

(4.3) $J=\sum_{i=1}^{N}\sum_{j>i}^{N}(||y_{i}-y_{j}||-D_{ij})^{2}\,;$

where $D_{ij}=D_{K}(p_{i},p_{j})$.

We illustrate this application below, using the Graph Forman-Ricci curvature,
on two real-life networks, namely the simple, illustrative “Kangaroo” network,
and on the larger “Les Misérables” one. As the second example proves, this
visualization method is quite efficient at distinguishing various clusters in
a large network, due to the high degree of separation that higher dimensional
spaces afford. In these examples, to numerically determine the minimum of the
cost-function $J$ we made appeal to the classical Douglas-Rachford algorithm
[17]. We have illustrated these examples in Figures 13 and 14 below.

Figure 14. Two views of the “Kangaroo” Graph Forman-Ricci curvature derived,
kernel-based, embedding in $\mathbb{R}^{3}$ which reveal that the network
essentially consist from one large cluster. The the attained minimum for the
cost function in this case is $J=23.841747$.

Figure 15. Two views of the Graph Forman-Ricci curvature derived, kernel-based
embedding of the “Les Misérables” characters network. Here the attained
minimum for the cost function is $J=42.264625$. Note that the kernel-based
embedding into $\mathbb{R}^{3}$ clearly distinguishes the clusters around each
of the main characters in Hugo’s novel, connected by the relations between
them.

Furthermore, we have implemented the $\square_{1}$ based embedding. Perhaps
contrary to the common wisdom, and thus somewhat unexpected, the Graph Forman-
Ricci curvature renders a far better separation into clusters than the
considered Laplacian. – See Figure 16.

Figure 16. Graph Forman-Ricci (above) vs. $\square_{1}$ (below) kernel-based
embedding of the “C. Elegans” network [12]. Note the far better separation
properties of the curvature based embedding. This ability has as a penalty a
higher minimum of the cost function $J$, namely 404.342321 for the curvature-
based kernel, as compared to 283.640003 for the Laplacian-based kernel.

The kernel embedding method not only is useful in the visualization of
networks, it also (and perhaps more importantly) allows us to embed large
complex networks into the familiar Euclidean space. Consequently one can
employ well established and intuitive sampling methods of data points and sets
in the usual ambient space.

##  5\. From Manifold Sampling to Network Sampling

Given that the discretizations of sampled manifolds are graphs (moreover, also
named $\varepsilon$-nets), conducts one to pose the following natural
question, namely weather there is a connection between the curvature bounds of
the given manifold and the discrete curvature of the resulting graph, more
specifically their Forman-Ricci curvature. The answer to this question is
positive, as we shall demonstrate below.

######  Remark 5.1.

This fact , in conjunction with the result in [52] on the connection between
classical (smooth) curvature of a given Riemannian manifold and the
combinatorial curvature of an approximating $PL$ manifold, significantly
improves our understanding of the interrelations between the curvature of an
underlying smooth manifold and its various discretizations.

The proof follows easily from the following essential properties of efficient
packings that are used in the proof of the Grove and Peterson’s result
mentioned in Section 2:

Let $M^{n}$ be a an $n$-dimensional Riemannian manifold, such that ${\rm
Ric}_{M}\geq(n-1)k$, and let $D$ denote the upper bound of the diameter of
$M^{n}$. Then the following lemmas hold:

######  Lemma 5.2 ([22], Lemma 3.2).

There exists $n_{1}=n_{1}(n,k,D)$, such that if $\\{p_{1},\ldots,p_{n_{0}}\\}$
is a minimal $\varepsilon$-net on $M^{n}$, then $n_{0}\leq n_{1}$.

######  Lemma 5.3 ([22], Lemma 3.3).

There exists $n_{2}=n_{2}(n,k,D)$, such that for any $x\in M^{n}$,
$\left|\\{j\,|\,j=1,\ldots,n_{0}\;{\rm
and}\;\beta^{n}(x,\varepsilon)\cap\beta^{n}(p_{j},\varepsilon)\neq\emptyset\\}\right|\leq
n_{2}$, for any minimal $\varepsilon$-net $\\{p_{1},\ldots,p_{n_{0}}\\}$.

######  Lemma 5.4 ([22], Lemma 3.4).

Let $M_{1}^{n},M_{2}^{n}$, be manifolds having the same bounds $k=k_{1}=k_{2}$
and $D=D_{1}=D_{2}$ (see above) and let $\\{p_{1},\ldots,p_{n_{0}}\\}$ and
$\\{q_{1},\ldots,q_{n_{0}}\\}$ be minimal $\varepsilon$-nets with the same
intersection pattern, on $M_{1}^{n}$, $M_{2}^{n}$, respectively. Then there
exists a constant $n_{3}=n_{3}(n,k,D,C)$, such that if
$d(p_{i},p_{j})<C\cdot\varepsilon$, then
$d(q_{i},q_{j})<n_{3}\cdot\varepsilon$.

In other words, by using curvature-based sampling, the resulting
$\varepsilon$-nets (discretizations) have a number of properties, listed below
in the same order as the implying lemmas, that are essential in the sampling
task:

  1. (1)

There is an upper bound on the number of sampling points.

  2. (2)

The vertex degree is bounded from above.

  3. (3)

The distances between sampling points are bounded from above, that is to say
the lengths of the edges of the discretization are. Here the distance is the
intrinsic distance on the sampled manifold. However, in practice on can (and
commonly does, in Graphics and Imaging applications) replace the intrinsic
distances with the Euclidean ones in a piecewise-flat approximation obtained
via an isometric embedding in a higher dimensional Euclidean space. (See [54]
and the references therein, as well as [55] for concrete bounds for the
relation between the intrinsic and approximated distances.)

######  Remark 5.5.

The lemmas above also hold in the more general case of metric measure spaces
with a lower bound on the generalized Ricci curvature ${\rm CD}(K,N)$ [50].
While we do not cite the precise statements here, in order to avoid
unnecessary technical complications, the reader should recall that these, as
well all the results below also hold for metric measure spaces with
generalized Ricci curvature bounded from below.

Let us examine the implications to the networks’ sampling setting of each of
the properties above:

The implications of Property (1) are the clearest from the Signal and Image
Processing viewpoint: Given a prescribed precision of approximation
($\varepsilon$), there there exists an upper bound on the number of required
sampling points (that depends on dimension, curvature bound and diameter).

Property (2) is the one that allows for the basic connection with the Forman-
Ricci curvature of the $\varepsilon$-separated net. Indeed, since for networks
endowed with combinatorial weights (that is to say equal to 1), the formula
for the simple graph Forman-Ricci curvature has the following alluring form:

(5.1) $\mathbf{F}(e)=4-{\rm deg}(v_{1})-{\rm deg}(v_{2});$

where $v_{1},v_{2}$ are the end nodes of the edge $e$, property (2) translates
to the following

######  Lemma 5.6.

Let $G(\mathcal{N})$ be a $\varepsilon$-separated net of a bounded manifold
$M$. Then the graph Forman-Ricci curvature of $G(\mathcal{N})$ is bounded from
below; more precisely

(5.2) $\mathbf{F}(e)\geq K_{1};{\rm for\;any}\;e\;{\rm
edge\;of}\;G(\mathcal{N})\,;$

where $K_{1}=1-2n_{2}$ and $n_{2}=n_{2}(n,k,D)$ is given by Lemma 5.3 above.

In fact, the result above extends, in view to a result of Kanai [30], to all
discretizations of bounded curvature of a given manifold $M$. More precisely,
we have that

######  Theorem 5.7 ([30], Lemma 2.5).

Let $M^{n}$ be a complete Riemannian manifold, such that ${\rm
Ric}_{M}\geq(n-1)k$, and let $G(\mathcal{N})$ be a discretization of $M^{n}$.
Then $(M^{n},d)$ and $(G,\mathbf{d})$, where $d$ is the Riemannian metric and
$\mathbf{d}$ is the combinatorial metric, are roughly isometric.

Therefore, it follows that we can also state

######  Lemma 5.8.

Let $M^{n}$ be a complete Riemannian manifold, such that ${\rm
Ric}_{M}\geq(n-1)k$, and let $G(\mathcal{N})$ be a discretization of $M^{n}$,
endowed with the combinatorial metric. Then the graph Forman-Ricci curvature
of $G(\mathcal{N})$ is bounded from below; more precisely

(5.3) $\mathbf{F}(e)\geq K_{2};{\rm for\;any}\;e\;{\rm
edge\;of}\;G(\mathcal{N})\,;$

where $K_{2}=1-2k_{1}$, and $k_{1}$ is the upper bound on the degrees of the
vertices of $G(\mathcal{N})$.

######  Remark 5.9.

In view of the results in [50], Lemmas 5.6 and 5.8 above both readily adapt to
metric measure spaces with generalized Ricci curvature bounded from below.

Moreover, the lower bound on the Ricci curvature translates to a similar bound
on the graph Forman-Ricci curvature of a discretization, even if this is not
endowed with the discrete metric, but rather with the (arguably more natural)
induced metric. (By this we mean that the length of an edge equals the
distance on $M^{n}$ between its edge points.)

######  Proposition 5.10.

Let $M^{n}$ be a Riemannian manifold with Ricci curvature bounded from below,
i.e. ${\rm Ric}_{M}\geq(n-1)k$ and let $G(\mathcal{N})$ be a discretization
with bounded geometry, having edge weights equal to the Riemannian distance
between the end points. Then the graph Forman-Ricci curvature is also bounded.

###### Proof.

First of all, let us note that the node (vertex) weights also need to be
prescribed. There are a number of natural possibilities: The combinatorial
weight 1, the degree ${\rm deg}(v)$ and the weighted degree ${\rm
deg}_{w}(v)=\frac{1}{{\rm deg}(v)}\sum_{e\sim v}w(e)$. The first one is less
fitting in this geometric context, while the last one introduces the edge
weights again, thus is repetitive in its modeling capacity. We settle,
therefore, for the second option, i.e. $w(v)={\rm deg}(v)$, even though, for
the purpose of this proof, no specific choice is necessary.

Recall that by Formula (3.6), the graph Forman-Ricci curvature is

$\mathbf{F}(e)=w(e)\left(\frac{w(v_{1})}{w(e)}+\frac{w(v_{2})}{w(e)}-\sum_{e(v_{1})\
\sim\ e,\ e(v_{2})\ \sim\
e}\left[\frac{w(v_{1})}{\sqrt{w(e)w(e(v_{1}))}}+\frac{w(v_{2})}{\sqrt{w(e)w(e(v_{2}))}}\right]\right)\,;$

Therefore, $\mathbf{F}(e)$ is bounded iff the edge weights are bounded away
from zero (independently of the specific choice of node weights). For bounded
manifolds this fact follows immediately from the finiteness Property 1. (In
fact, Property 3 gives also an upper bounds for the weights.) For non-compact
manifolds with bounded curvature, it follows from Kanai’s Theorem that there
exists $C_{1},C_{2}>0$ such that $C_{1}\leq w(e)\leq C_{2}$, thus the desired
property also holds in this case.

∎

######  Remark 5.11.

Again, by applying the results in [50], the proposition above extends to
metric measure spaces with generalized Ricci curvature bounded from above as
well.

However, Property 3 does not suffice to assure a similar connection between
the given upper bound on the curvature of a Riemannian manifold $M$ and one on
the full Forman curvature of a discretization $G(\mathcal{N})$ of $M$. Indeed,
in computing the full Forman curvature, one has to take into account not just
the edge weights (lengths), but also the weights of the 2-faces, which in this
case should naturally be taken as the areas of the corresponding $PL$ (or,
rather, piecewise flat approximation). (To this end, we can assume, of course,
that $M$ is isometrically embedded in some $\mathbf{R}^{N}$, for $N$
sufficiently large.) Recall also that in the sampling process one produces, in
fact, simplicial complexes (triangulations), thus 2-face areas are readily
computable from the edge lengths. Unfortunately, isometry does not imply non-
collapse of area (for some extreme and important examples, see [9]).
Therefore, in order to obtained the desired result, we have to ensure that
such collapse does not occur. This requirement is fulfilled if the given
triangulation induce by the $\varepsilon$-net is thick (or fat); where
thickness is defined as follows

######  Definition 5.12.

Let $\tau\subset\mathbb{R}^{n}$ ; $0\leq k\leq n$ be a $k$-dimensional
simplex. The thickness $\varphi$ of $\tau$ is defined as being:

(5.4) $\varphi=\varphi(\tau)=\inf_{\hskip
11.38092pt\sigma\leqslant\tau\raisebox{-7.11317pt}{\mbox{\scriptsize${\rm
dim}\,\sigma=j$}}}\\!\\!\frac{\rm Vol_{j}(\sigma)}{\rm diam^{j}\,\sigma}\;.$

The infimum is taken over all the faces of $\tau$, $\sigma\leqslant\tau$, and
${\rm Vol}_{j}(\sigma)$ and ${\rm diam}\,\sigma$ stand for the Euclidian
$j$-volume and the diameter of $\sigma$ respectively. (If ${\rm
dim}\,\sigma=0$, then ${\rm Vol}_{j}(\sigma)=1$, by convention.) A simplex
$\tau$ is $\varphi_{0}$-thick, for some $\varphi_{0}>0$, if
$\varphi(\tau)\geq\varphi_{0}$. A triangulation (of a submanifold of
$\mathbb{R}^{n}$) $\mathcal{T}=\\{\sigma_{i}\\}_{i\in\bf I}$ is
$\varphi_{0}$-thick if all its simplices are $\varphi_{0}$-thick. A
triangulation $\mathcal{T}=\\{\sigma_{i}\\}_{i\in\bf I}$ is thick if there
exists $\varphi_{0}>0$ such that all its simplices are $\varphi_{0}$-thick.

Since any Riemannian manifold, satisfying only mild topological finiteness
conditions (with or without boundary) admits a fat triangulation – see e.g.
[50] and the references therein, it follows that any $\varepsilon$-net can be
improved to render a thick triangulation. Furthermore, during the thickening
process the edge lengths (weights) are modified only slightly, given that one
uses to this end only $\varepsilon$-moves (see [38], [11] for technical
details). Given the facts above and recalling that, by Formula (3.8), the full
Forman-Ricci curvature is expressed by

${\rm Ric}_{\rm F}(e)=\omega(e)\left[\left(\sum_{e\sim
f}\frac{\omega(e)}{\omega(f)}+\sum_{v\sim
e}\frac{\omega(v)}{\omega(e)}\right)\right.$ $\hskip
75.39963pt-\left.\sum_{\hat{e}\parallel e}\left|\sum_{\hat{e},e\sim
f}\frac{\sqrt{\omega(e)\cdot\omega(\hat{e})}}{\omega(f)}-\sum_{v\sim
e,v\sim\hat{e}}\frac{\omega(v)}{\sqrt{\omega(e)\cdot\omega(\hat{e})}}\right|\right]\;;$

we have in fact proven the following theorem:

######  Theorem 5.13.

Any Riemannian manifold with Ricci curvature bounded from below admits a
discretization with bounded full Forman-Ricci curvature.

######  Remark 5.14.

This result can also be extended to manifolds satisfying a generalized Ricci
curvature bound by applying [50], Proposition 4.7.

Before concluding this section, let us note that, in the process of simplex
thickening, a (finite) number of subdivisions is required. In consequence, the
resulting triangulation and the discretization associated to it will have a
larger number of vertices, with degrees that do not depend simply on
dimension, diameter and curvature. Therefore, the need for a simplification of
the resulting network might arise in its turn. To this end, a Forman-Ricci
curvature (of either kind) sampling would be applicable. Since the degrees of
the additional vertices are a function depending solely of the dimension of
the subdivided simplex, it is therefore quite probable that, at least when
considering the discrete metric and applying graph Forman-Ricci curvature, the
remaining nodes (and edges) would mostly still be the ones of the initial
triangulation.

##  6\. Conclusion and Outlook

We have introduced a number of curvature measures and derived flows, as well
as developing a family of coarse embedding kernels derived from some of them
or from related operators. Furthermore, we have illustrated the ideas above on
a sample of small and medium size networks, as well as on test images.
However, these can represent only a preamble to an in-depth examination of
these new tools. Therefore, first and foremost, there is the need for
systematic experiments with large scale networks. It should be noted that this
construction of networks, from manifolds to triangulations, and their
subsequent simplification via curvature-based sampling is of high relevance in
Deep Learning [33], [34].

A number of specific further directions of study impose themselves:

  * •

While, as we have discussed in detail, we are driven by the edge and higher
order correlations centered approach, the node based one is still relevant.
Therefore, the exploration of the capabilities of the (scalar curvature)
Yamabe flow is a natural and interesting venue of research.

  * •

Of particular interest is the exploration of flows in the study of the long-
time evolution of (hyper-)networks [69]. To this end, flows derived from all
the types of curvature herein should be examined.

  * •

Experiments with curvature-driven triangulations of manifolds and their
sampling, especially for such manifolds as arising in Deep Learning (see
references mentioned above) should definitely represent a future goal.

  * •

One should try other embedding techniques than the one used herein, for
instance the so called local linear embedding [46].

  * •

Besides the kernel embedding method embraced in the present paper, one should
explore another, and perhaps better established approach, that is the one
using the eigenvectors and eigenfunctions of the Laplacian for embedding and
sampling, where the classical graph Laplacian is replaced by the Bochner and
rough ones. Furthermore, given that they exist for each and every dimension up
to the maximal one, they suggest themselves as a potentially powerful method
of studying hypernetworks/complexes at many scales.

  * •

The stronger results connecting Forman curvatures of discretizations, namely
the convergence of the said curvatures to their manifold counterparts, as well
as of the associated Laplacians to the smooth ones, is a goal that definitely
should be pursued.

## Acknowledgement

We would like to thank the anonymous reviewers, as well Frank Morgan for their
valuable critique and constructive suggestions which greatly helped improve
our paper.

## Appendix 1: Coarse Spaces

We bring below the formal definition of a coarse space and give some basic
examples, which in part are also relevant to our work. To this end we first
need a couple of preliminary definitions:

######  Definition 6.1.

Let $X$ be a set and let $E,E_{1},E_{2}\subseteq\mathcal{P}(X\times X)$.

  1. (1)

$E^{-1}=\\{(x^{\prime},x)\,|\,(x,x^{\prime})\in E\\}$ is called the inverse of
$E$.

  2. (2)

$E_{1}\circ E_{2}=\\{(x_{1},x_{2})\,|\,(x_{1},x)\in E_{1}\,,(x,x_{2})\in
E_{2}\\}$ is called the product of $E_{1}$ and $E_{2}$.

######  Definition 6.2.

Let $X$ be a set and let $\mathcal{E}\subseteq\mathcal{P}(X\times X)$, such
that the diagonal $\Delta(X)\subset\mathcal{E}$ and such that $\mathcal{E}$ is
closed under the formation of subsets, inverses, products and (finite) unions.
$\mathcal{E}$ is called a coarse structure on $X$, and $(X,\mathcal{E})$ is
called a coarse space. Furthermore, the sets $E\in\mathcal{E}$ are called the
controlled sets or the entourages for the coarse structure.

######  Examples 6.3.

We bring below a number of important examples.

  1. (1)

$\mathcal{E}=\mathcal{P}(X\times X)$ is called the maximal coarse structure on
$X$.

  2. (2)

Let $\mathcal{E}\subseteq\mathcal{P}(X\times X)$ such that it contains only a
finite number of points $(p,q)\notin\Delta(X)$. Then $\mathcal{E}$ is a coarse
structure on $X$ called the discrete coarse structure on $X$.

  3. (3)

Let $(X,d)$ be a metric space and let
$\mathcal{E}=\\{E\,|\,E\subseteq\mathcal{P}(X\times X)\\}$ such that
$\sup\\{d(x_{1},x_{2})\,|\,(x_{1},x_{2})\in E\\}$ is finite. Then
$\mathcal{E}$ is a coarse structure on $X$ called the bounded coarse structure
on $X$.

For further properties and characterizations of coarse spaces see [45].

## Appendix 2: The General Formulas for the Forman-Laplacian and Curvature
Functions

We bring below the general formulas for the Forman-Laplacian and curvature
functions. For more background on $CW$ complexes we refer the reader to
Forman’s paper [24] as well as to [26].

Let $M$ be a (positively) weighted quasiconvex regular $CW$ complex, let
$\alpha=\alpha^{p}\in M$ a $p$-dimensional cell and let $w(\alpha)$ denote its
weight. While general weights are possible, making the combinatorial Ricci
curvature extremely versatile, it is suffices (cf. [24]), Theorem 2.5 and
Theorem 3.9) to restrict oneself only to so called standard weights:

######  Definition 6.4.

The set of weights $\\{w_{\alpha}\\}$ is called a standard set of weights iff
there exist $w_{1},w_{2}>0$ such that given a $p$-cell $\alpha^{p}$, the
following holds:

$w(\alpha^{p})=w_{1}\cdot w_{2}^{p}\,.$

(Note that the combinatorial weights $w_{\alpha}\equiv 1$ represent a set of
standard weights, with $w_{1}=w_{2}=1$.)

Using standard weights, we obtain the following formula for the Forman-
Laplacian

(6.1)
$\displaystyle\Box_{p}(\alpha_{1}^{p},\alpha_{2}^{p})=\sum_{\begin{subarray}{c}\beta^{p+1}>\alpha_{1}^{p}\\\
\beta^{p+1}>\alpha_{2}^{p}\end{subarray}}\epsilon_{\alpha_{1},\alpha_{2},\beta}\frac{\sqrt{\omega(\alpha_{1}^{p})\omega(\alpha_{2}^{p})}}{\omega(\beta^{p+1})}+\sum_{\begin{subarray}{c}\gamma^{p-1}<\alpha_{1}^{p}\\\
\gamma^{p-1}<\alpha_{2}^{p}\end{subarray}}\epsilon_{\alpha_{1},\alpha_{2},\gamma}\frac{\omega(\gamma^{p-1})}{\sqrt{\omega(\alpha_{1}^{p})\omega(\alpha_{2}^{p})}}\,,$

where, for instance $\alpha<\beta$ denotes that $\alpha$ is a face of $\beta$,
and
$\epsilon_{\alpha_{1},\alpha_{2},\beta},\epsilon_{\alpha_{1},\alpha_{2},\gamma}\in\\{-1,+1\\}$
represent the respective incidence numbers of the cells $\beta$ relative to
$\alpha_{i}$, and $\alpha_{i}$ relative to $\gamma$, $i=1,2$, respectively.
(see [26]).

Furthermore, we also obtain the formula for the curvature functions, namely

(6.2) $\displaystyle\begin{aligned}
\mathcal{F}(\alpha^{p})&=\omega(\alpha^{p})\Big{[}\Big{(}\sum_{\beta^{p+1}>\alpha^{p}}\frac{\omega(\alpha^{p})}{\omega(\beta^{p+1})}\;+\sum_{\gamma^{p-1}<\alpha^{p}}\frac{\omega(\gamma^{p-1})}{\omega(\alpha^{p})}\Big{)}\\\
&\quad-\sum_{\alpha_{1}^{p}\parallel\alpha^{p},\alpha_{1}^{p}\neq\alpha^{p}}\Big{|}\sum_{\begin{subarray}{c}\beta^{p+1}>\alpha_{1}^{p}\\\
\beta^{p+1}>\alpha^{p}\end{subarray}}\frac{\sqrt{\omega(\alpha^{p})\omega(\alpha_{1}^{p})}}{\omega(\beta^{p+1})}\>-\sum_{\begin{subarray}{c}\gamma^{p-1}<\alpha_{1}^{p}\\\
\gamma^{p-1}<\alpha^{p}\end{subarray}}\frac{\omega(\gamma^{p-1})}{\sqrt{\omega(\alpha^{p})\omega(\alpha_{1}^{p})}}\Big{|}\>\;\Big{]}\,;\end{aligned}$

where $\alpha<\beta$ denotes $\alpha$ being a face of $\beta$ and
$\alpha_{1}\parallel\alpha_{2}$ parallel faces $\alpha_{1}$ and $\alpha_{2}$,
the notion of parallelism being defined as follows:

######  Definition 6.5.

Let $\alpha_{1}=\alpha_{1}^{p}$ and $\alpha_{2}=\alpha_{2}^{p}$ be two
p-cells. $\alpha_{1}$ and $\alpha_{2}$ are said to be parallel
($\alpha_{1}\parallel\alpha_{2}$) iff either: (i) there exists
$\beta=\beta^{p+1}$, such that $\alpha_{1},\alpha_{2}<\beta$; or (ii) there
exists $\gamma=\beta^{p-1}$, such that $\alpha_{1},\alpha_{2}>\gamma$ holds,
but not both simultaneously. (For example, in Fig. 1,
$e_{1},e_{2},e_{3},e_{4}$ are all the edges parallel to $e_{0}$.)

## Appendix 3: Standard Metrics on Weighted Graphs

We present here briefly the two metric on graphs taking into account both node
and edge weights that we mentioned in the main part of the paper.

  * •

The degree path metric was fist introduced in [16] and further expanded upon
in [27]. It is closely associated with the (combinatorial) Laplacian, as well
as with the random walk on a graph, and as such is widely used in theoretical
studies of the Geometry of graphs.

######  Definition 6.6.

Let $(X,m,w)$ be a node and edge weighted graph, $m$ denoting the node
weights, and $w$ the edge weights. Then the function $\rho:X\times
X\rightarrow[0,\infty)$,

$\rho(x,y)=\inf_{\pi}\sum_{i=1}^{n}\left(\max\\{d(x_{i-1}),d(x_{i})\\}\right)^{-1/2}\,;$

where the infimum is taken all paths $\pi=x=x_{0}x_{1}\ldots x_{n}=y$, and
where $d$ denotes the weighted degree

$d(x)=\frac{1}{m(x)}\sum_{y\sim x}w(x,y)\,,$

represents a metric on $X$.

Since, one the one hand, the larger the degree of a node $x$, the faster the
random walk leaves it and, on the other hand, by the definition of $\rho$, the
larger the degree of any of the vertices $x,y$, the smaller the distance
$\rho(x,y)$ between them, it follows that the faster the jump along an edge,
the shorter the edge is in w.r.t. the metric $\rho$. (For more details, such
as the analogy with the Riemannian manifolds case, see [31] and the references
contained therein.)

  * •

As its name suggests, the definition of the resistance metric is motivated by
electrical networks, and $1/\Omega(x,y)$ represents an abstraction of the
notion of electrical conductance and, as such, measures the connectivity along
the edge $e$ connecting the nodes $x$ and $y$. More precisely, we have the
following definition:

######  Definition 6.7.

Let $G$ be as above. The resistance metric $\Omega$ on $G$ is defined as

(6.3) $\Omega(x,y)=\frac{1}{\sum_{t\in V}f(t)r(t,y)}\,;;$

where

$r=\left\\{\begin{array}[]{ll}\mbox{$\frac{1}{w(e)}$}\,,&\mbox{$x\sim
y$}\,;\\\ 1\,,&\mbox{$x\not\sim y$}\end{array}\right.$

and where $f:V\rightarrow[0,1]$ is the unique function such that (a)
$f(x)=1,f(y)=0$; and (b) $\sum_{z\in V}(f(t)-f(z))r(t,z)=0$, for any $t\neq
x,y$.

The resistance metric represents the weighted average of all the paths $\pi$
of ends $x$ and $y$, and it is, therefore, best used when the number of such
paths is important.

It is however, essentially a vertex-weights induced metric, except for the
role of the function $f$ which is defined on the set of vertices. The
following probabilistic interpretation however allows us to view the
resistance metric as being induce both by vertex and edge weights:

$\Omega(x,y)=\frac{1}{d(x){\rm Pr}(x\rightarrow y)}\,;$

where $d$ denotes here the degree of $x$ and ${\rm Pr}(x\rightarrow y)$ is the
probability of a random walk starting from $x$ to reach $y$ before it returns
to $x$. (For more details see [15] and the references therein.) If one
considers, as it is commonly done, that the jump probability to any of the
neighbors of a given vertex is equal, than this probability is viewed as a
weight on the said vertex, thus allowing us to consider $\Omega$ as a metric
on a node and edge weighted graph.

## References

  * [1] D. Bakry and M. Émery, Diffusions hypercontractives, J. Azéma and M. Yor, eds., Séminaire de Probabilités XIX 1983/4 (A. Dold and B. Eckmann, eds.), Lecture Notes Math., 1123, Springer-Verlag, 177–206, 1985.
  * [2] D. Bakry and M. Ledoux, Lévy-Gromov’s isoperimetric inequality for an infinite dimensional diffusion generator, Invent. Math. 123, 259–281, 1996.
  * [3] L. Backstrom and J. Kleinberg, Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook, Proceedings of the 17th ACM conference on Computer supported cooperative work & social computing, (2014), pp. 831-841.
  * [4] V. Barkanass, W. Chen, N. Lei and E. Saucan, Textures Curvature – Do Stochastic Textures Exist?, in preparation, 2020.
  * [5] F. Bauer, J. Jost and S. Liu, Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator, Mathematical research letters, 19, 1185–1205, 2012.
  * [6] A. R. Benson, D. F. Gleich, and J. Leskovec, Higher-order organization of complex networks, Science, 353, 163-166, 2016.
  * [7] M. Boguná, I. Bonamassa, M. De Domenico, S. Havlin, D. Krioukov & M. Serrano, Network geometry arXiv preprint arXiv:2001.03241, 2020.
  * [8] I. Borg and P. J. F. Groenen, Modern Multidimensional Scaling: Theory and Applications, Springer, 2010.
  * [9] Yu. D. Burago and V. A. Zalgaller, Isometric piecewise linear immersions of two-dimensional manifolds with polyhedral metrics into $\mathbb{R}^{3}$, St. Petersburg Math. J. 7(3), 369–385, 1966.
  * [10] I. Chavel, Riemannian geometry – A Modern Introduction, Cambridge Tracts in Mathematics 108, Cambridge University Press, 1993.
  * [11] J. Cheeger, W. Müller and R. Schrader, On the Curvature of Piecewise Flat Spaces, Comm. Math. Phys. 92, 405–454, 1984.
  * [12] A. Cho, J. Shin, S. Hwang, C. Kim, H. Shim, H. Kim, H. Kim, I. Lee, WormNet v3, http://www.inetbio.org/wormnet, 2014.
  * [13] H. Cohen, A. Maril and E. Saucan, in preparation, 2021.
  * [14] I. Corwin, N. Hoffman, S. Hurder, V. Šešum and Y. Xu, Differential Geometry of Manifolds with Density, Rose Hulman Undergraduate Journal of Mathematics, 7(1), 15pp, 2006.
  * [15] M. Deza and E. Deza, Encyclopedia of Distances, Springer, Berlin, 2009.
  * [16] J. Dodziuk and W. S. Kendall, Combinatorial Laplacians and isoperimetric inequality, From local times to global geometry, control and physics, Pitman Res. Notes Math. Ser. 150, Longman Sci. Tech., Harlow, 68–74, 1986.
  * [17] J. Douglas and H. H. Rachford, On the numerical solution of heat conduction problems in two or three space variables, T. Am. Math. Soc. 82, 421–439, 1956.
  * [18] A. L. Gibbs and F. E. Su, On Choosing and Bounding Probability Metrics, International Statistical Review 70(3), 419–435, 2002.
  * [19] T. R. Grant, Dominance and Association among Members of a Captive and a Free-ranging Group of Grey Kangaroos (_Macropus giganteus_), Anim. Behav. 21(3), 449–456, 1973.
  * [20] M. Gromov, Hyperbolic groups, in Gersten, Steve M. Essays in group theory, MSRI Publications 8, 75–263, Springer, New York, 1987.
  * [21] M. Gromov, Metric structures for Riemannian and non-Riemannian spaces, Progress in Mathematics, 152, Birkhauser, Boston, 1999.
  * [22] K. Grove and P. Petersen, Bounding homotopy types by geometry. Ann. of Math. 128, 195–206, 1988.
  * [23] X. D. Gu and S.-T. Yau, Computational Conformal Geometry. International Press, Somerville, MA, 2008.
  * [24] R. Forman, Bochner’s Method for Cell Complexes and Combinatorial Ricci Curvature, Discrete and Computational Geometry, 29(3), 323–374, 2003.
  * [25] J. Haantjes, Distance geometry. Curvature in abstract metric spaces. Proc. Kon. Ned. Akad. v. Wetenseh. 50, 496–508, 1947.
  * [26] A. Hatcher, Algebraic Topology, Cambridge University Press, 2001.
  * [27] X. Huang, On stochastic completeness of complete graphs, PhD Thesis, Bielefeld University, 2011.
  * [28] S. Joshi, R. V. Kommaraji, J. M. Phillips, and S. Venkatasubramanian, “Comparing distributions and shapes using the kernel distance,” in Proceedings of the 27th annual ACM symposium on Computational geometry, ser. SoCG ’11. New York, NY, USA: ACM, 47–56, 2011
  * [29] J. Jost, Riemannian Geometry and Geometric Analysis. 7 edn. Springer International Publishing, 2017.
  * [30] M. Kanai, Rough isometries, and combinatorial approximations of geometries of non- compact Riemannian manifolds, J. Math. Soc. Japan 37, 391–413, 1985.
  * [31] M. Keller, Intrinsic Metrics on Graphs: A Survey, In: Mugnolo D. (eds) Mathematical Technology of Networks. Springer Proceedings in Mathematics & Statistics, 128, Springer, Cham, 2015.
  * [32] J. Kunegis, Les Miserables, part of the KONECT – The Koblenz Network Collection, in Proc. Int. Conf. on World Wide Web Companion, 1343–1350, http://dl.acm.org/citation.cfm?id=2488173, 2013.
  * [33] N. Lei, D. An, Y. Guo, K. Su, S. Liu, Z. Luo, S.-T. Yau and D. X. Gu, Geometric Understanding of Deep Learning, Engineering, 6(3), 361–374, 2020.
  * [34] N. Lei, K. Su, L. Cui, S.T. Yau and D. X. Gu, A Geometric View of Optimal Transportation and Generative Model, Computer Aided Geometric Design, 68 1–21, 2019.
  * [35] S. Lin, Z. Luo, J. Zhang and E. Saucan, Generalized Ricci Curvature Based Sampling and Reconstruction of Images, Proceedings of EUSIPCO 2015, 604–608, 2015.
  * [36] J. Lott and C. Villani, Ricci curvature for metric-measure spaces via optimal transport, Ann. of Math., 169(3), 903–991, 2009.
  * [37] F. Morgan, Manifolds with density, Notices Amer. Math. Soc. 52, 853–858, 2005.
  * [38] J. R. Munkres, Elementary Differential Topology. (rev. ed.) Princeton University Press, Princeton, N.J., 1966.
  * [39] M. Newman, Networks, Oxford University Press, 2018.
  * [40] C. Ni, Y. Lin, J. Gao, X. D. Gu, and E. Saucan, Ricci curvature of the internet topology, Proceedings of INFOCOM, 2758–2766. IEEE, 2015.
  * [41] C. Ni, Y. Lin, F. Luo, and J. Gao, Community detection on networks with Ricci flow,  Scientific Reports, 9(1), 1–12, 2019.
  * [42] Y. Ollivier, Ricci curvature of Markov chains on metric spaces, Journal of Functional Analysis. 256(3), 810–864, 2009.
  * [43] Y. Ollivier, A survey of Ricci curvature for metric spaces and Markov chains, Probabilistic approach to geometry 57, 343–381, 2010.
  * [44] J. M. Phillips and S. Venkatasubramanian, A gentle introduction to the kernel distance, Technical Report arXiv:1103.1625, Arxiv.org, 2011.
  * [45] J. Roe, Lectures on Coarse Geometry, University Lecture Series 31, AMS, Providence, RI, 2003.
  * [46] S. Roweis and L. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science, 290(5500), 2323–-2326, 2000.
  * [47] A. Samal, H. K. Pharasi, S. J. Ramaia, E. Saucan, J. Jost, and A. Chakraborti, Network Geometry and Market Instability, to appear in Royal Society Open Science (RSOS), 2021.
  * [48] R. Sandhu, T. Georgiou, E. Reznik, L. Zhu, I. Kolesov, Y. Senbabaoglu and A. Tannenbaum, Graph curvature for differentiating cancer networks, Scientific Reports 5, 1–13, 2015.
  * [49] R. Sandhu, T. Georgiou, and A. Tannenbaum, Market fragility, systemic risk, and Ricci curvature, arXiv:1505.05182, 2015.
  * [50] E. Saucan, Curvature based triangulation of metric measure spaces, Contemporary Mathematics, 554, 207–227, 2011.
  * [51] E. Saucan, Metric Curvatures Revisited – A Brief Overview, book-chapter, Springer Lecture Notes in Mathematics (LNM) 2184, 63–114, 2017.
  * [52] E. Saucan, Discrete Morse Theory, Persistent Homology and Forman-Ricci Curvature, arxiv:submit/3078713, 2020.
  * [53] E. Saucan and E. Appleboim, Curvature Based Clustering for DNA Microarray Data Analysis, LNCS, 3523, 405–412, Springer-Verlag, 2005.
  * [54] E. Saucan, E. Appleboim and Y.Y. Zeevi, Sampling and Reconstruction of Surfaces and Higher Dimensional Manifolds, J. Math. Imaging Vis., 30(1), 105–123, 2008.
  * [55] E. Saucan, E. Appleboim and Y.Y. Zeevi, Geometric Approach to Sampling and Communication, Sampl. Theory Signal Image Process., 11(1), 1-24, 2012.
  * [56] E. Saucan, A. Samal and J. Jost, A Simple Differential Geometry for Networks and its Generalizations, Proceedings of COMPLEX NETWORKS AND THEIR APPLICATIONS VIII, COMPLEX NETWORKS 2019 (SCI) 881, 943–954, Springer, 2020.
  * [57] E. Saucan, A. Samal and J. Jost, A Simple Differential Geometry for Complex Networks, arXiv:2004.11112v2 [math.MG], to appear in Network Science, 2020.
  * [58] J. Sia, E. Jonckheere, E. and P. Bogdan, Ollivier-Ricci curvature-based method to community detection in complex networks,  Scientific Reports, 9(1), 1–12, 2019.
  * [59] E. Sonn, E. Saucan, E. Appelboim and Y. Y. Zeevi, Ricci Flow for Image Processing, Proceedings of IEEEI 2014, 2014.
  * [60] R. P. Sreejith, K. Mohanraj, J. Jost, E. Saucan and A. Samal, Forman curvature for complex networks, Journal of Statistical Mechanics: Theory and Experiment (J. Stat. Mech.), 063206, (http://iopscience.iop.org/1742-5468/2016/6/063206), 2016.
  * [61] K.-T. Sturm, On the geometry of metric measure spaces. I and II, Acta Math., 196, 65-131 and 133-177, 2006.
  * [62] L. Szymanski, B. McCane, Visualising Kernel Spaces, on Proceedings of Image and Vision Computing New Zealand (IVCNZ), pp. 449–452, 2011.
  * [63] C. Villani, Optimal Transport, Old and New, Grundlehren der mathematischen Wissenschaften 338, Springer, Berlin-Heidelberg, 2009.
  * [64] C. Wang, E. Jonckheere and R. Banirazi, Wireless Network Capacity versus Ollivier-Ricci Curvature under Heat-Diffusion (HD) Protocol. Proceedings of ACC 2014, 3536–3541, 2014.
  * [65] D. J.Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature, 393(6684), 440–442, 1988.
  * [66] M. Weber, J. Jost and E. Saucan, Forman-Ricci flow for change detection in large dynamical data sets, Axioms, 5(4), 26; doi: 10.3390/axioms5040026, 2016.
  * [67] M. Weber, J. Jost and E. Saucan, Detecting the Coarse Geometry in Networks, International Workshop on Complex Networks and their Applications (NIPS 2018), 706–717, Springer, Cham, 2018.
  * [68] M. Weber, E. Saucan and J. Jost, Characterizing Complex Networks with Forman-Ricci curvature and associated geometric flows, J Complex Netw, 5 (4): 527–550, 2017.
  * [69] M. Weber, E. Saucan and J. Jost, Coarse geometry of evolving networks, J Complex Netw, 6(5), 706–732, 2018.