A Review of and Some Results for Ollivier–Ricci Network Curvature

Abstract

Characterizing topological properties and anomalous behaviors of higher-dimensional topological spaces via notions of curvatures is by now quite common in mainstream physics and mathematics, and it is therefore natural to try to extend these notions from the non-network domains in a suitable way to the network science domain. In this article we discuss one such extension, namely Ollivier’s discretization of Ricci curvature. We first motivate, define and illustrate the Ollivier–Ricci Curvature. In the next section we provide some “not-previously-published” bounds on the exact and approximate computation of the curvature measure. In the penultimate section we review a method based on the linear sketching technique for efficient approximate computation of the Ollivier–Ricci network curvature. Finally in the last section we provide concluding remarks with pointers for further reading.

1. Introduction

It is by now quite common in mainstream physics and mathematics [1,2] to characterize topological properties and anomalous behaviors of higher-dimensional topological spaces via notions of (local and global) curvatures of these spaces, e.g., in general relativity, extreme variations of four dimensional space-time curvatures via geodesic incompleteness lead to characterizations of black-holes [3]. It is therefore natural to try to extend these notions from the non-network domains e.g., from continuous metric spaces or from higher-dimensional geometric objects) in a suitable way to the network science domain so that non-trivial new topological characteristics of networks can be captured. There are several ways this can be achieved; we briefly mention two other approaches before proceeding with the approach that is the main topic of this paper. Note that such extensions need to overcome at least two key challenges, namely that (i) networks are discrete (non-continuous) objects, and that (ii) networks may not necessarily have an associated natural geometric embedding.

One notion of network curvature that has been well-studied in the network theory literature, first suggested by Gromov in a non-network group theoretic context [4], is the Gromov-hyperbolic curvature. First defined for infinite continuous metric space [2], the measure was later adopted for finite graphs. Usually the measure is defined via properties of geodesic triangles or via equivalent (in a sense that can be made precise) 4-node conditions, though Gromov originally defined the measure using Gromov-product nodes in [4]. Informally any infinite metric space has a finite Gromov-hyperbolicity measure if it behaves metrically in the large scale as a negatively curved Riemannian manifold, and thus the value of this measure can be correlated to the standard scalar curvature of a hyperbolic manifold. Intuitively, for a finite network the measure is based on the properties of the set of exact and approximate geodesics of the network. There is a large body of research works dealing with theoretical and empirical aspects of this measure, e.g., see [5,6,7,8,9,10] for theoretical aspects, and see [11,12,13] for empirical aspects with applications to real-world networks.

A second notion of curvature is the applying Forman’s discretization of Ricci curvature for (polyhedral or CW) complexes (the “Forman–Ricci curvature”) [14] to networks. Informally, one applies the Forman-Ricci curvature to networks by topologically associating components (sub-graphs) of the given graphs with higher-dimensional objects. The topological association itself can be carried out several ways. Although this type of curvature originated relatively recently, there are already a number of papers investigating properties of these measures and applying them to real-world networks, e.g., see [8,15,16,17,18].

The network curvature discussed in this paper is another discretization of Ricci curvature, namely Ollivier’s discretization [19,20,21,22], henceforth dubbed as the “Ollivier–Ricci curvature”. Both Ollivier–Ricci curvature and Forman-Ricci curvature assign measures that assign a number to each edge of the given network, but the numbers are calculated in quite different ways in these two curvatures since they capture different metric properties of a Riemannian manifold. The reader is referred to the paper by [15] for a comparative analysis of these two measures. In addition to the network curvatures measures discussed above, researchers have also explored other notions of curvature, such as the one based on circle packings by Chow and Luo [23].

Basic Notations and Terminologies

To simplify exposition, we assume in this paper that the given network (In this paper the terms “graph” and “network” will be used interchangeably.) $G=(V,E)$ is an undirected unweighted connected graph; generalization of the corresponding definitions and concepts to the case of non-negative edge weights is mostly straightforward. The following notations will be used in the rest of this paper.

▷

For a node $v\in V$, $\mathsf{Nbr}(v)=\{u|\{v,u\}\in E\}$ denotes the set of neighbors of v, and $deg(v)=|\mathsf{Nbr}(v)|$ denotes the degree of v.

▷

${\mathrm{dist}}_G(u,v)$ (or simply $\mathrm{dist}(u,v)$) denote the distance (i.e., number of edges in a shortest path) between the nodes u and v in G.

2. Ollivier–Ricci Curvature: Motivation, Definition and Illustration

In this section, we provide the formal definition of the Ollivier–Ricci curvature. First, we need to define the so-called Earth Mover’s Distance (Emd) (also known as the $L_1$ transportation distance, the $L_1$ Wasserstein distance and the Monge-Kantorovich-Rubinstein distance) [24,25,26,27]. For the purpose of this paper, it suffices to define the distance in the discrete setting of a network as follows. Suppose that we have two probability distributions ${\mathbb{P}}_1$ and ${\mathbb{P}}_2$ on a subset $\varnothing \subset V^{\prime }\subseteq V$ of nodes, i.e., two real numbers $0\le {\mathbb{P}}_1(v),{\mathbb{P}}_2(v)\le 1$ for every node $v\in V^{\prime }$ with ${\sum }_{v\in V^{\prime }}{\mathbb{P}}_1(v)={\sum }_{v\in V^{\prime }}{\mathbb{P}}_2(v)=1$. We can think of every number ${\mathbb{P}}_1(v)$ as the maximum total amount of “earth” (dirt) at node v that can be moved to other nodes, and every number ${\mathbb{P}}_2(v)$ as the maximum total amount of earth node v can store in its storage. The cost of transporting one unit of earth from node u to node v is ${\mathrm{dist}}_G(u,v)$, and the goal is to satisfy the storage requirement of all nodes by moving earths as needed while minimizing the total transportation cost. Letting the variable $z_{u,v}\in [0,1]$ denote the amount of shipment from node u to node v in an optimal solution, Emd for the two probability distributions ${\mathbb{P}}_1$ and ${\mathbb{P}}_2$ on $V^{\prime }$ can be formulated as the linear programming ($\mathsf{LP}$) problem shown in Figure 1 which can be solved in polynomial time. One can also think of the Emd solution as the distance between two probability distributions ${\mathbb{P}}_1$ and ${\mathbb{P}}_2$ on the set of nodes $V^{\prime }$ based on the shortest-path metric on G. We will use the notation Emd$(V^{\prime },{\mathbb{P}}_1,{\mathbb{P}}_2)$ to denote the value of the objective function in an optimal solution of the $\mathsf{LP}$ in Figure 1.

For an intuitive understanding of the connection of Emd to Ollivier–Ricci curvature for networks, we informally recall one way of defining Ricci curvature measure for a smooth Riemannian manifold. The Ricci curvature at a point x in the manifold along a direction can be thought of transporting a small ball centered at x along that direction and measuring the “distortion” of that ball. The role of the direction is captured by the edge $\{u,v\}$, the roles of the balls at the two nodes are played by the distributions ${\mathbb{P}}_1$ and ${\mathbb{P}}_2$, and the role of the distortion due to transportation is captured by the Emd measure. More precisely, given our input graph $G=(V,E)$ and an edge $\{u,v\}\in E$, the paper [20] uses the Emd measure to define the “course Ricci curvature” Ric$(u,v)$ along the edge $\{u,v\}$ in the following manner (see Figure 2 for an illustration):

►

Let $V^{\prime }$ be the set of nodes $V_{u,v}\stackrel{\mathrm{def}}{=}\{u,v\}\cup \mathsf{Nbr}(u)\cup \mathsf{Nbr}(v)$.

►

Let the probability distributions ${\mathbb{P}}_1$ and ${\mathbb{P}}_2$ be uniform distributions (If the given graph is non-negative node weights then another option is to normalize the restrictions of these node weights to the sub-graph $H_{u,v}$ and use them for the distributions ${\mathbb{P}}_1$ and ${\mathbb{P}}_2$.) ${\mathbb{P}}_u$ and ${\mathbb{P}}_v$, respectively, over the nodes in $\{u\}\cup \mathsf{Nbr}(u)$ and $\{v\}\cup \mathsf{Nbr}(v)$, respectively, i.e.,

$$\begin{array}{c}{\mathbb{P}}_u(x)\stackrel{\mathrm{def}}{=}{\mathbb{P}}_1(x)=\left\{\begin{array}{cc}\frac{1}{|\{u\}\cup \mathsf{Nbr}(u)|},\hfill & \mathrm{if}x\in \{u\}\cup \mathsf{Nbr}(u)\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.\\ {\mathbb{P}}_v(x)\stackrel{\mathrm{def}}{=}{\mathbb{P}}_2(x)=\left\{\begin{array}{cc}\frac{1}{|\{v\}\cup \mathsf{Nbr}(v)|},\hfill & \mathrm{if}x\in \{v\}\cup \mathsf{Nbr}(v)\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.\end{array}$$

(1)

►

Remembering that ${\mathrm{dist}}_G(u,v)=1$ for an edge $\{u,v\}\in E$, we can then define the course Ricci curvature as (cf. [20] (Definition 3)):

$$\begin{array}{c}\mathrm{R}\mathrm{IC}(u,v)=1-\frac{\mathrm{E}\mathrm{MD}(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)}{{\mathrm{dist}}_G(u,v)}\equiv \mathrm{R}\mathrm{IC}(u,v)=1-\mathrm{E}\mathrm{MD}(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)\end{array}$$

(2)

The measure can easily be extended for graphs with non-negative edge weights; redefine $\mathrm{dist}(u,v)$ to be minimum total weight over all possible paths between u and v and use the equation:

$$\mathrm{R}\mathrm{IC}(u,v)=1-\frac{\mathrm{E}\mathrm{MD}(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)}{{\mathrm{dist}}_G(u,v)}$$

Some authors also define the discrete Ricci curvature Ric$(u)$ for a node $u\in V$ by taking the average of the discrete Ricci curvarure over all edges incident on u, e.g., by letting Ric$(u)=\frac{{\sum }_{\{u,v\}\in E}\mathrm{R}\mathrm{IC}(u,v)}{deg(u)}$.

An Illustration of Computing the Value of Ric$(u,v)$ For a Two-dimensional Grid

Consider an infinite two-dimensional grid on the plane and any edge $\{u,v\}$ of the grid as shown in Figure 3. Note that any node of the grid has exactly 4 neighbors, thus ${\mathbb{P}}_u(x)=\left\{\begin{array}{cc}\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$5$}\right.,\hfill & \mathrm{if}x\in \{u\}\cup \mathsf{Nbr}(u)\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$ and ${\mathbb{P}}_v(x)=\left\{\begin{array}{cc}\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$5$}\right.,\hfill & \mathrm{if}x\in \{v\}\cup \mathsf{Nbr}(v)\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$. Moreover, the set of nodes $\mathsf{Nbr}(u)\backslash \{v\}$ and $\mathsf{Nbr}(v)\backslash \{u\}$ are disjoint, thus it is easy to see that Emd$(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)=1$ (see Figure 3). Using (2) we therefore get Ric$(u,v)=0$.

3. Exact and Approximate Computation of Ric$(\mathit{u},\mathit{v})$

Note that any node $x\in V_{u,v}$ with either ${\mathbb{P}}_u(x)=0$ or ${\mathbb{P}}_v(x)=0$ can be ignored in the calculation of Emd$(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)$. Thus, a straightforward calculation of Ric$(u,v)$ requires the following two steps:

▷

Find the pair-wise distances between the nodes in $\mathsf{Nbr}(u)$ and $\mathsf{Nbr}(v)$. This can be done in $O(n^{\omega }logn)$ using Seidel’s algorithm [28] where n is the number of nodes and $\omega$ be the value such that two $n\times n$ matrices can be multiplied in $O(n^{\omega })$ time; the smallest current value of $\omega$ is slightly less than $2.373$ [29].

▷

Solve an $\mathsf{LP}$ with $O(deg(u)deg(v))$ variables and $O(deg(u)deg(v))$ constraints via standard $\mathsf{LP}$ solvers such as the interior-point method. Alternatively, the $\mathsf{LP}$ can be solved by minimum-cost network flow algorithms by viewing it as a transportation problem, e.g., see [30].

However, the calculation of Emd$(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)$ (and therefore Ric$(u,v)$) can be further simplified if we make some more observations.

Consider a pair of nodes $u^{\prime }\in \mathsf{Nbr}(u)$ and $v^{\prime }\in \mathsf{Nbr}(v)$ for an edge $\{u,v\}\in E$. Note that there are only four possible values of ${\mathrm{dist}}_G(u^{\prime },v^{\prime })$: ${\mathrm{dist}}_G(u^{\prime },v^{\prime })=0$ if $u^{\prime }=v^{\prime }$, ${\mathrm{dist}}_G(u^{\prime },v^{\prime })=1$ if $\{u^{\prime },v^{\prime }\}\in E$, ${\mathrm{dist}}_G(u^{\prime },v^{\prime })=2$ if there is a path of length 2 between $u^{\prime }$ and $v^{\prime }$, and ${\mathrm{dist}}_G(u^{\prime },v^{\prime })=3$ for all other cases. Thus, to to find all pair-wise distances between the nodes in $\mathsf{Nbr}(u)$ and $\mathsf{Nbr}(v)$ we only need to check for paths up to length 3, which can be done faster in $O(n^{\omega })$ time using Seidel’s algorithm [28] again.

For further discussion, consider the total variation distance (Tvd) between the two distributions ${\mathbb{P}}_u$ and ${\mathbb{P}}_v$ on the set of nodes in $V_{u,v}$:

$$||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}\stackrel{\mathrm{def}}{=}\frac{1}{2}\left(\sum _{v^{\prime }\in V_{u,v}}\left(|{\mathbb{P}}_u(v^{\prime })-{\mathbb{P}}_v(v^{\prime })|\right)\right)$$

Note that $||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}$ can be trivially computed in $O(deg(u)+deg(v))$ time.

Proposition 1.

$1-3||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}\le \mathrm{R}\mathrm{IC}(u,v)\le 1-||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}$.

Proof. 

Since every pair of non-identical nodes $u^{\prime },v^{\prime }\in V_{u,v}$ satisfy $1\le {\mathrm{dist}}_G(u^{\prime },v^{\prime })\le 3$, we have $||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}\le \mathrm{E}\mathrm{MD}(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)\le 3||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}$ which imply the claimed result via definition of $\mathrm{R}\mathrm{IC}(u,v)$.  □

The bound in Proposition 1 may not necessarily be a tight approximation for Ric$(u,v)$; for example, for the grid in Figure 3 we get $||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}=\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$5$}\right.$ giving $-\raisebox{1ex}{$4$}\!\left/ \!\raisebox{-1ex}{$5$}\right.\le \mathrm{R}\mathrm{IC}(u,v)\le \raisebox{1ex}{$2$}\!\left/ \!\raisebox{-1ex}{$5$}\right.$ as an approximation to the actual value of Ric$(u,v)=0$.

For development of further bounds, consider the edge $\{u,v\}\in E$. Assume without loss of generality that $deg(u)\le deg(v)$ and G has 4 or more nodes, thus $deg(v)\ge 2$. Suppose that u and v have $0\le \ell \le deg(u)$ common neighbour nodes as shown pictorially below:

$$\begin{array}{c}\begin{array}{c}\mathsf{Nbr}(u)=\{\stackrel{k+\ell =deg(u)-1\ge \ell +1\mathrm{nodes}}{\overbrace{p_1,p_2,\dots ,p_k,q_1,q_2,\dots ,q_{\ell }}}\}\\ \{\underset{m+\ell =deg(v)-1\ge \ell +1\mathrm{nodes}}{\underbrace{\underset{\begin{array}{c}\ell \ge 0\mathrm{common}\\ \mathrm{neighbours}\end{array}}{\underbrace{q_1,q_2,\dots ,q_{\ell }}},r_1,r_2,\dots ,r_m}}\}=\mathsf{Nbr}(v)\end{array}\end{array}$$

Note that the two probability vectors ${\mathbb{P}}_u$ and ${\mathbb{P}}_v$ for the edge $\{u,v\}$ are as shown below:

	$p_1$	⋯	$p_k$	$q_1$	⋯	$q_{\ell }$	u	$r_1$	⋯	$r_m$	v
${\mathbb{P}}_u=$	$(\frac{1}{deg(u)+1}$	⋯	$\frac{1}{deg(u)+1}$	$\frac{1}{deg(u)+1}$	⋯	$\frac{1}{deg(u)+1}$	$\frac{1}{deg(u)+1}$	0	⋯	0	$\frac{1}{deg(u)+1})$
${\mathbb{P}}_v=$	$(0$	⋯	0	$\frac{1}{deg(v)+1}$	⋯	$\frac{1}{deg(v)+1}$	$\frac{1}{deg(v)+1}$	$\frac{1}{deg(v)+1}$	⋯	$\frac{1}{deg(v)+1}$	$\frac{1}{deg(v)+1})$

By our assumption $\frac{1}{deg(u)+1}\ge \frac{1}{deg(v)+1}$, and thus a straightforward calculation gives the following value for $||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}$:

$$\begin{array}{c}\hfill ||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}=\frac{1}{2}\times \left(\frac{k}{deg(u)+1}+\frac{m}{deg(v)+1}+(\ell +2)\times \left(\frac{1}{deg(u)+1}-\frac{1}{deg(v)+1}\right)\right)\\ \hfill =\frac{\frac{k+\ell }{2}+1}{deg(u)+1}+\frac{\frac{m-\ell }{2}-1}{deg(v)+1}=\frac{1}{2}+\frac{(deg(v)+1)-2(\ell +2)}{2(deg(v)+1)}=1-\frac{\ell +2}{deg(v)+1}\end{array}$$

(3)

Proposition 2.

$-2+3\frac{\ell +2}{deg(v)+1}\le \mathrm{R}\mathrm{IC}(u,v)\le \frac{\ell +2}{deg(v)+1}$, and in particular it always holds that $-2<\mathrm{R}\mathrm{IC}(u,v)\le 1$.

Proof. 

Plugging the bound (3) in Proposition 1 proves the first claim. To prove the second claim, note that $0<\frac{\ell +2}{deg(v)+1}\le 1$.  □

For further bounds, suppose that there exists a $\gamma \in \{1,2,3\}$ such that for any two distinct nodes $u^{\prime }\in \mathsf{Nbr}(u)$ and $v^{\prime }\in \mathsf{Nbr}(v)$ we have $\mathrm{dist}(u^{\prime },v^{\prime })$ is exactly $\gamma$. In that case, it follows that

$$\mathrm{E}\mathrm{MD}(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)=\gamma \times ||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}\Rightarrow \mathrm{R}\mathrm{IC}(u,v)=1-\gamma \times ||{\mathbb{P}}_u-{\mathbb{P}}_v{||}_{\mathrm{T}\mathrm{VD}}=1-\gamma +\frac{\gamma (\ell +2)}{deg(v)+1}$$

Now, suppose that G has no cycles of 5 of fewer edges containing the edge $\{u,v\}$ (a tree is a trivial example of such a graph). This implies $\gamma =3$ and $\ell =0$, giving the following bound.

Proposition 3.

If G has no cycles of 5 of fewer edges containing the edge $\{u,v\}$ then $\mathrm{R}\mathrm{IC}(u,v)$ is precisely $-2+\frac{6}{deg(v)+1}\le 0$ and can be computed in $O(deg(u)+deg(v))$ time.

4. Review of Efficient Approximate Computation of Ric$(\mathit{u},\mathit{v})$ via Linear Sketching

It is clear that a crucial bottleneck in computing Ric$(u,v)$ for an arbitrary graph $G=(V,E)$ is the computation of Emd$(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)$ since it seems to require solving a linear program with $O(deg(u)deg(v))$ variables and $O(deg(u)deg(v))$ constraints (note that in the worst case $deg(u)deg(v)$ can be as large as $\Theta (n^2)$ when n is the number of nodes of G). In this section we review a non-trivial approach for computing Emd$(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)$ provided we settle for a slightly non-optimal solution for Emd$(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)$.

Linear sketching is a popular method to perform approximate computations on large data sets using dimensionality reduction [31]. The general (informal) intuition behind linear sketching is to take linear projections of the given data set and then use these projections to provide solutions to the original problem. Significant research has been done on the problem of estimating Emd using linear sketches for general metric spaces [32,33,34,35,36]. In this section, we discuss the results by McGregor and Stubbs [37] to approximately estimate Emd on a graph metric (i.e., metric induced by inter-node distances in a graph, as is the case for computing Ric$(u,v)$). Recall that our bottleneck is the computation of $\mathrm{E}\mathrm{MD}(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)$ for the given graph G.

The first step is to transform the problem of computing $\mathrm{E}\mathrm{MD}(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)$ by standard techniques to the following equivalent problem which will be denoted by Emd${}_{\mathsf{d}}$. Given two multi-sets $\mathcal{A},\mathcal{B}\subseteq \mathcal{X}$ over a ground set $\mathcal{X}$ with $|\mathcal{A}|=|\mathcal{B}|=k$, and a metric $\mathsf{d}:\mathcal{X}\times \mathcal{X}\mapsto {\mathbb{R}}^{+}$ on $\mathcal{X}$, compute the minimum-cost of perfect matching between $\mathcal{A}$ and $\mathcal{B}$, i.e., using ${\pi }_{\mathcal{A},\mathcal{B}}$ to denote a 1-1 mapping from $\mathcal{A}$ to $\mathcal{B}$, we need to compute

$$\begin{array}{c}{\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})=\underset{{\pi }_{\mathcal{A},\mathcal{B}}}{min}\{\sum _{a\in \mathcal{A}}\mathsf{d}(a,{\pi }_{\mathcal{A},\mathcal{B}}(a))\}\end{array}$$

For the purpose of measuring approximation quality, we say that an algorithm is an $(ϵ,\delta )$-algorithm for computing a quantity of value Q if the value $Q^{\prime }$ returned by the algorithm satisfies $Pr[|Q-Q^{\prime }|<ϵQ]\ge 1-\delta$.

The basic approach of McGregor and Stubbs in [37] is to define two vectors $\mathbf{x},\mathbf{y}\in {\mathbb{R}}^{|E|}$ corresponding to the set $\mathcal{A}$ and $\mathcal{B}$. We then estimate ${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})$ by posing it as a ${\ell }_1$-regression problem using the vectors $\mathbf{x},\mathbf{y}$ and a set of other vectors defined by the structure of the underlying graph. The idea is take some random projections of these vectors to a smaller dimensional space and then perform ${\ell }_1$-regression on these projections to save space and time. The following result by Kane et al. [38] is crucial to the analysis of this approach (the notation ${Pr}_{M\sim \nu }$ is the standard notation for denoting that the entries of M are drawn from the distribution $\nu$):

$(🟉)$ There exists a distribution (“q-dimensional sketch”) $\nu$ over linear maps from ${\mathbb{R}}^n\mapsto {\mathbb{R}}^q$ where $q=O({\epsilon }^{-2}lognlog{\delta }^{-1})$ and a “post-processing” function $f:{\mathbb{R}}^q\mapsto \mathbb{R}$ such that for any $\mathbf{x}\in {\mathbb{R}}^n$ with polynomially-bounded entries, it holds that

$$\underset{M\sim \nu }{Pr}\left[{| \Vert \mathbf{x}\Vert }_1-f(M\mathbf{x})|\le \epsilon {\Vert \mathbf{x}\Vert }_1\right]\ge 1-\delta$$

To understand how the above result relates to the calculation of ${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})$, first consider the case when the given instance of ${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})$ is one dimensional, i.e., let $G=(V,E)$ be a path with n nodes $V=\{1,\dots ,n\}$ and $n-1$ edges $E=\{e_1,\dots ,e_{n-1}\}$ where $e_i=\{i,i+1\}$, let $A,B\subseteq V$, and let $\mathsf{d}(i,j)={\mathrm{dist}}_G(i,j)$ for all $i,j\in V$. Then we can associate computation of ${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})$ to a norm estimation problem in the following manner. Assume that we have vectors $\mathbf{x}=(x_1,\dots ,x_{n-1})\in {\mathbb{R}}^{n-1}$ and $\mathbf{y}=(y_1,\dots ,y_{n-1})\in {\mathbb{R}}^{n-1}$ such that for all $i\in \{0,1,n-1\}$ the following assertions hold: $x_i=|\{a\in \mathcal{A}|i\ge a\}|$ and $y_i=|\{b\in \mathcal{B}|i\ge b\}|$. Then, it can be shown that ${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})={\Vert \mathbf{x}-\mathbf{y}\Vert }_1$ and thus we can use the result of Kane et al. [38] as stated in $(🟉)$ directly.

As a second illustration of the above point, suppose that the graph G in the previous example is now a cycle of n nodes $V=\{1,\dots ,n\}$ and n edges $E=\{e_1,\dots ,e_n\}$ where $e_i=\{i,i+1\}$ for $i\in \{1,\dots ,n-1\}$ and $e_n=\{n,1\}$. Suppose that we simply ignore the last edge $e_n$ so that the graph becomes a path and we can apply the previous approach. However, this omission of $e_n$ changes the distance between the nodes $i\in \mathcal{A}$ and $j\in \mathcal{B}$ from $\mathsf{d}(i,j)=min\left\{|i-j|,|i-n|+1+|1-j|,|i-1|+1+|n-j|\right\}$ to a new distance ${\mathsf{d}}^{\prime }(i,j)=|i-j|$. To resolve this issue, we make a sequence of guesses for the number of pairs of nodes that will be joined using the edge $e_n$. More precisely, for $\lambda \in \{-k,-k+1,\dots ,k-1,k\}$ let ${\mathcal{C}}_{\lambda }$ be the multi-set consisting of $\lambda$ copies of “1” if $\lambda >0$ and $|\lambda |$ copies of “n” if $\lambda <0$. Then, one can show that

$${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})\le |\lambda |+{\mathrm{E}\mathrm{MD}}_{{\mathsf{d}}^{\prime }}(\mathcal{A}\uplus {\mathcal{C}}_{\lambda },\mathcal{B}\uplus {\mathcal{C}}_{-\lambda })$$

with equality for some $\lambda \in \{-k,-k+1,\dots ,k-1,k\}$, where ⊎ denotes the union for multi-sets. Thus, we can use the result in $(🟉)$ in the following manner. First define two vectors $\mathbf{x}=(x_1,\dots ,x_n)\in {\mathbb{R}}^n$ and $\mathbf{y}=(y_1,\dots ,y_n)\in {\mathbb{R}}^n$ where $x_i=|\{a\in \mathcal{A}|i\ge a\}|$ and $y_i=|\{b\in \mathcal{B}|i\ge b\}|$ for $i\in \{1,\dots ,n-1\}$, and $x_n=y_n=0$. Let $\mathbf{z}=\mathbf{x}-\mathbf{y}$ and $\mathbf{c}=(1,\dots ,1)\in {\mathbb{R}}^n$. Then, it follows that

$${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})=\underset{\lambda \in \{-k,-k+1,\dots ,k-1,k\}}{min}\left\{{\Vert \mathbf{z}+\lambda \mathbf{c}\Vert }_1\right\}$$

Define the function $f:\mathbb{R}\mapsto \mathbb{R}$ as $f(\lambda )={\Vert \mathbf{z}+\lambda \mathbf{c}\Vert }_1$; clearly ${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})={min}_{\lambda \in \{-k,-k+1,\dots ,k-1,k\}}\left\{f(\lambda )\right\}$. For a specific $\lambda \in \{-k,-k+1,\dots ,k-1,k\}$, we can use $(🟉)$ to find an approximation $\widetilde{f_{\lambda }}$ of $f_{\lambda }$ using a $O({\epsilon }^{-2}lognlog(k{\delta }^{-1}))$-dimensional sketch of $\mathbf{z}$ such that $Pr\left[|\widetilde{f_{\lambda }}-f(\lambda )|>\epsilon f(\lambda )]\right]<\frac{\delta }{2k+1}$. Iterating the process $2k+1$ times and using the union bound for probabilities, we get

$$\begin{array}{c}Pr\left[\forall \lambda \in \{-k,\dots ,k\}:|\widetilde{f_{\lambda }}-f(\lambda )|\le \epsilon f(\lambda )\right]\ge 1-\sum _{\lambda =-k}^{k}Pr\left[|\widetilde{f_{\lambda }}-f(\lambda )|>\epsilon f(\lambda )]\right]\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} >1-(2k+1)\times \frac{\delta }{2k+1}=1-\delta \end{array}$$

It is possible to design a more careful approach that iterates only $O(logk)$ times instead of $2k+1$ times. The ideas behind this approach as described above can be extended to trees with some non-trivial effort.

Finally the approach can indeed be generalized to the case when G is an arbitrary graph (which applies to computing Ric$(u,v)$) in the following manner. The basic idea to calculate ${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})$ for an arbitrary graph G is to reduce it in an approximate sense to that of computing Emd for a tree. Let $T=(V,E_T)$ be an arbitrary spanning tree of G, and let $F=E\backslash E_T$. The tree T defines a natural tree metric ${\mathsf{d}}^{\prime }$ where ${\mathsf{d}}^{\prime }(a,b)$ is the length of the shortest path between a and b in T for all $a,b\in V$. One can then express ${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})$ in terms of ${\mathrm{E}\mathrm{MD}}_{{\mathsf{d}}^{\prime }}({\mathcal{A}}^{\prime },{\mathcal{B}}^{\prime })$ for some ${\mathcal{A}}^{\prime }\supseteq \mathcal{A}$ and ${\mathcal{B}}^{\prime }\supseteq \mathcal{B}$ in the following manner. For $f=(u,v)\in F$ and ${\lambda }_f\in \{-k,-k+1,\dots ,k-1,k\}$, let ${\mathcal{C}}_{{\lambda }_f}^f$ be the multi-set consisting of ${\lambda }_f$ copies “u” if ${\lambda }_f>0$ and $|{\lambda }_f|$ copies of “v” if ${\lambda }_f<0$. Then the following bound holds:

$$\begin{array}{c}{\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})\le \sum _{f\in F}|{\lambda }_f|+{\mathrm{E}\mathrm{MD}}_{{\mathsf{d}}^{\prime }}\left(\mathcal{A}\uplus \sum _{f\in F}{\mathcal{C}}_{{\lambda }_f}^f,\mathcal{B}\uplus \sum _{f\in F}{\mathcal{C}}_{-{\lambda }_f}^f\right)\end{array}$$

The above inequality leads to the following approach. Fix an arbitrary node $r\in V$ as the root of the spanning tree T, and let ${\mathcal{P}}_T(u,v)$ denote the set of edges in the unique path in T between nodes u and v. Define the two vectors $\mathbf{x},\mathbf{y}\in {\mathbb{R}}^{|E|}$ as follows ($x_e$ and $y_e$ denote the component of $\mathbf{x}$ and $\mathbf{y}$, respectively, indexed by the edge $e\in E$):

$$\begin{array}{c}{x}_e=\left\{\begin{array}{cc}|\{a\in \mathcal{A}|e\in {\mathcal{P}}_T(a,r)\}|,\hfill & \mathrm{if}e\in E_T\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.y_e=\left\{\begin{array}{cc}|\{b\in \mathcal{B}|e\in {\mathcal{P}}_T(b,r)\}|,\hfill & \mathrm{if}e\in E_T\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.\end{array}$$

and let $\mathbf{z}=\mathbf{x}-\mathbf{y}$. For each $f=(u,v)\in F$, define a vector ${\mathbf{c}}^f\in {\mathbb{R}}^{|E|}$ where the component ${\mathbf{c}}_e^f$ of ${\mathbf{c}}^f$ indexed by the edge $e\in E$ is given by:

$$\begin{array}{c}{\mathbf{c}}_e^f=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}e\in {\mathcal{P}}_T(u,r)\backslash {\mathcal{P}}_T(v,r)\hfill \\ -1,\hfill & \mathrm{if}e\in {\mathcal{P}}_T(v,r)\backslash {\mathcal{P}}_T(u,r)\hfill \\ 1,\hfill & \mathrm{if}e=f\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.\end{array}$$

This leads to the following optimization problem:

$${\mathrm{E}\mathrm{MD}}_{\mathsf{d}}(\mathcal{A},\mathcal{B})=\underset{\forall f\in F:{\lambda }_f\in \{-k,-k+1,\dots ,k-1,k\}}{min}\Vert \mathbf{z}+\sum _{f\in F}{\lambda }_f{\mathbf{c}}^f{\Vert }_1$$

The above optimization problem can be solved using several approaches, e.g., using a recursive regression algorithm that exploits the convexity of f or using some recent results on robust regression via sub-space embeddings [39,40].

5. Discussion

In this paper we have reviewed some computational aspects of the Ollivier–Ricci curvature for networks, and shown a few simple computational bounds. As already mentioned in Section 1, there are other notions of network curvature that is also used by researchers and therefore this review should not be viewed as championing the Ollivier–Ricci curvature over other curvatures. We hope that this review will motivate further research on the exciting interplay between notions of curvatures from network and non-network domains. Some applications of network curvatures for real-world networks appear in references such as [11,13,15,16,18].

We conclude our article by mentioning an interesting application of the Ollivier–Ricci curvature for Markov chains for graph coloring and other problems (recise technical descriptions of these results are beyond the scope of this introductory review). The probability distributions on nodes used to compute Emd in the Ollivier–Ricci curvature can be naturally associated with a Markov process on the given graph (as a very simplified illustration, one can use a “normalized version” of Emd$(V_{u,v},{\mathbb{P}}_u,{\mathbb{P}}_v)$ as the probability of transition between the states corresponding to nodes u and v). Such associations have a long history in the Markov chain literature under various names such as path coupling [41] and the values of Ric$(u,v)$’s have been used (explicitly or implicitly) to prove useful properties of the Markov chain, such as fast convergence to its stationary distribution, in many settings such as graph colouring [41] and sampling of paths with constraints [42].