1

Curvature of Hypergraphs via Multi-Marginal Optimal Transport
Shahab Asoodeh1, Tingran Gao2 , and James Evans3

arXiv:1803.08584v1 [cs.IT] 22 Mar 2018

Abstract
We introduce a novel definition of curvature for hypergraphs, a natural generalization of graphs, by introducing a multimarginal optimal transport problem for a naturally defined random walk on the hypergraph. This curvature, termed coarse scalar
curvature, generalizes a recent definition of Ricci curvature for Markov chains on metric spaces by Ollivier [Journal of Functional
Analysis 256 (2009) 810-864], and is related to the scalar curvature when the hypergraph arises naturally from a Riemannian
manifold. We investigate basic properties of the coarse scalar curvature and obtain several bounds. Empirical experiments indicate
that coarse scalar curvatures are capable of detecting “bridges” across connected components in hypergraphs, suggesting it is an
appropriate generalization of curvature on simple graphs.

I. I NTRODUCTION
Complex systems or datasets are often modeled as weighted simple graphs in network science problems. While edges in these
simple graphs qualitatively characterize similarity or adjacency relations among entities represented by the graph vertices, the
edge weights are frequently used to quantify the nature of the interactions between pairs of nodes. Simple yet powerful as these
simple graph models are, many recent work reported the importance of understanding higher-order interactions among more
than a pair of nodes, rendering simple graphs insufficient as a natural model for capturing the network structure information in
these practices. Applications of this type include spatial network [1], image tagging [2], image retrieval [3], cellular networks
[4], and co-authorship network [5], to name just a few. Hypergraphs have been proposed as a replacement to tackle this
difficulty.
Roughly speaking, a hypergraph H = (V, E) consists of a finite set V of vertices and a set of hyperedges E ⊆ 2V –
just as edges in a simple graph that can be identified with vertex pairs, hyperedge E ∈ E are subsets of V . The ubiquitous
influence in modeling complex networks fostered numerous recent developments in the theory and algorithms of hypergraphs,
including extensive studies of the spectral and algebraic properties such as hypergraph Laplacian [6], hypergraph partitioning
[7], Cheeger’s inequality for hypergraph [8], and spectrum of hypergraphs [9].
Among many tools developed for better understanding the geometry of graphs, the graph Ricci curvature [10]–[14] has
attracted an increasing amount of interest in the past years. In his original work [10], Ollivier defined coarse Ricci curvature
for metric measure spaces, including simple graphs and Markov chains as special cases. In a nutshell, the coarse Ricci curvature
summarizes the behavior of shortest paths with close-by starting points and parallel initial directions: two such paths tend to
get closer to each other in a metric space of positive Ricci curvature, and further if the space is negatively curved. On simple
graphs, this notion of Ricci curvature has found applications ranging from bounding the chromatic number [15] and analyzing
the Internet topology [16] to measuring the stability in financial networks [17], brain structural connectivity [18], and similarity
of networks [19].
This paper proposes a novel definition of curvature for hypergraphs by generalizing Ollivier’s coarse Ricci curvature through
a multi-marginal optimal transport framework (see e.g. [20]–[22]). Analogous to coarse Ricci curvatures, our definition of
hypergraph curvature is grounded upon differential geometric intuitions, and reduces to the graph Ricci curvature when the
hypergraph is a simple graph. While the coarse Ricci curvature is defined for pairs of points, which are naturally identified with
edges in simple graphs, we need to adjust the construction to account for ≥ 3 vertices joined by a hyperedge simultaneously;
consequently, the geometric information captured in our definition is a summary of a small neighborhood enclosing all the
end nodes of a hyperedge, as opposed to the directional information revealed by the Ricci curvature. In fact, our construction
corresponds to the scalar curvature of Riemannian manifolds under appropriate manifold assumptions analogous to the manifold
Ricci curvature example in [10].
The rest of the paper is structured as follows. We list a few useful notation in Section II-A. After a brief review of coarse
Ricci curvature in Section II-B, we define coarse scalar curvature in Section II-C. Based on this definition, we then propose
our notion of hypergraph curvature and investigate its properties in Section II-D. We derive a closed form for the curvature
of complete uniform hypergraphs in Section III and a general lower bound for hyperpaths in Section IV. In Section V, we
provide a detailed consistency result for the definition of coarse scalar curvature in a Riemannian manifold setting. Finally, we
conclude the paper in Section VI.
1 Computation

Institute and Institute of Genomics and System Biology, The University of Chicago, Chicago, IL 60637 shahab@uchicago.edu
of Statistics, The University of Chicago, Chicago, IL 60637 tingrangao@galton.uchicago.edu
3 Computation Institute and Department of Sociology, The University of Chicago, Chicago, IL 60637 jevans@uchicago.edu
2 Department

2

II. H YPERGRAPH C URVATURE VIA M ULTI -M ARGINAL O PTIMAL T RANSPORT
A. Notations
P
PFor each vertex i of a hypergraph H = (V, E), we use di := E∈E 1{i∈E} to denote the degree of vertex i and d(E) :=
r∈V 1{r∈E} to denote the cardinality of hyperedge E ∈ E. Similar to graph, we use N (i) for the neighbors of vertex i, i.e.,
N (i) = {j ∈ V : ∃E ∈ E, (i, j) ∈ E}. For a pair of vertices i and j of a hypergraph, d(i, j) denotes the shortest distance, i.e.,
d(i, j) = r if there exist r interesting hyperedges E1 , . . . , Er , such that i ∈ E1 , j ∈ Er , and Ek ∩ Ek+1 6= ∅ for 1 ≤ k ≤ r − 1.
We will always denote M for a d-dimensional Riemannian manifold. We use expx (·) : Tx M → M to denote the exponential
map. For any x ∈ M and v ∈ Tx M with kvk = 1, we denote Ricx (v, v) for the Ricci curvature at x ∈ M in the direction of
v ∈ Tx M , defined as
d
1 X
hR (v, ei ) v, ei i
(1)
Ricx (v, v) =
d − 1 i=2
where v, e2 , · · · , ed constitutes an orthonormal basis for Tx M , and R is the Riemannian curvature tensor. We will often write
Ric (v, v) for Ricx (v, v) when the point x is fixed throughout the discussion. Averaging out Ricx (v, v) for v ranging in an
orthonormal basis of Tx M gives rise to the scalar curvature at x ∈ M :
d

Scal (x) =

1X
Ricx (zi , zi )
d i=1

(2)

where z1 , · · · , zd constitutes an orthonormal basis for Tx M . Equivalently, the scalar curvature can be obtained from averaging
out the Ricci curvature over the unit sphere in the tangent plane, i.e. (c.f. [23, Exercise 4.9])
Z
1
Ricx (v, v) dSd−1 (v)
(3)
Scal (x) =
ωd−1 Sd−1 (0)
where Sd−1 (0) is the unit sphere in Tx M and ωd−1 is the volume of the standard (d − 1)-dimensional sphere in Rd .
For any set A ∈ Rn , we let P (A) denote the set of all probability measures defined on A.
B. Graph Ricci Curvature
Given a graph G = (V, E) and a pair of vertices x, y ∈ V , Ollivier [10] defined the curvature of edge (x, y) ∈ E as
κ(x, y) := 1 −

W (mx , my )
,
d(x, y)

(4)

where d(x, y) is the shortest distance from x to y, mi is the uniform random walk starting at i ∈ V , and W (mx , my ) is the
Wasserstein distance between mx and my given by
X
W (mx , my ) :=
inf
d(r, s)π(r, s),
(5)
π∈Π(mx ,my )

(r,s)∈V 2

where Π(mx , my ) is the set of all joint distributions having mx and my as marginals (i.e., the set of all couplings of mx and
my ). He then showed that positive curvature is equivalent to the contraction of the random walk under Wasserstein’s distance
which in turn leads to the existence of a unique stationary distribution.
To justify that (4) is a valid discrete version of Ricci curvature, Ollivier argued as follows. In a d-dimensional Riemannian
manifold (M, dM ), consider the random walk (c.f. Definition 1) dmεx for each x ∈ M and ε > 0 given by
dmεx (s) :=

1B(x,ε) (s)
dvol(s),
vol(B(x, ε))

(6)

where B (x, ε) = {z ∈ M | dM (x, z) < ε} is the metric ball with radius ε centered at x and 1{x∈A} is the indicator function
of set A. It is then shown [10, Example 7] that for sufficiently small δ = dM (x, y) > 0

W1 mεx , mεy
ε2 Ric(v, v)
1−
=
+ O(ε3 + ε2 δ),
(7)
dM (x, y)
2(n + 2)

where v ∈ Tx M is a unit tangent vector at x such that expx (δv) = y and where W1 mεx , mεy is the L1 -Wasserstein distance
between mεx and mεy
Z

ε
ε
inf
dM (x, y) dπ (x, y) .
(8)
W1 mx , my :=
π∈Π(mεx ,mεy ) M×M

In Riemannian geometry, Ricci curvature Ricx (v, v) is, up to a scaling factor, the average of the sectional curvatures of all
two-dimensional subspaces of Tx M passing through v [23, §4] and hence, it measures the coupling of the random walks. In
this context, if the curvature of a point in a manifold is zero, it is locally on a Euclidean space, positive if it is locally on an
sphere and negative if it locally on a hyperbolic space.

3

C. Coarse Scalar Curvature for Metric Spaces
We begin our construction of coarse scalar curvature by defining random walks on a metric space, which was used in [10]
to define coarse Ricci curvatures.
Definition 1 ( [10] Definition 1). Let (M, dM ) be a Polish metric space equipped with its Borel σ-algebra. A random walk
m on M is a family of probability measures {mx | x ∈ M } satisfying
• The map x 7→ mx is measurable;
• Each mx has finite first moment.
Definition 2 (Coarse Scalar Curvature). For a collection of n points Xn := {x1 , · · · , xn } in a metric space (M, dM ) with
random walk m := {mx | x ∈ M }, define the coarse scalar curvature for Xn by
κ ({Xn }) := 1 −

W1 (Xn )
,
c(x1 , . . . , xn )

(9)

where W1 (Xn ) is the minimum of the multi-marginal optimal transport problem
Z
W1 (Xn ) := inf
c (ξ1 , · · · , ξn ) dπ (ξ1 , · · · , ξn ) ,
π∈Π(Xn )

with

M×···×M

n
o
Π (Xn ) := Π (m1 , · · · , mn ) = π ∈ P (M × · · · × M ) | (Projk )# π = mxk , ∀1 ≤ k ≤ n ,

with (A)# π being the push-forward of measure π under mapping A and
c (ξ1 , · · · , ξn ) := inf

z∈M

n
X

dM (ξi , z) .

(10)

i=1

It must be mentioned that the multi-marginal optimal transport problem is first studied in Gangbo and Świȩch [22] where
they showed the necessary conditions for the existence and uniqueness of the optimizer when c(ξ1 , · · · , ξn ) is the sum of
pairwise ℓ2 distances. The coarse scalar curvature is closely tied to the multi-marginal optimal transport problem among n ≥ 2
probability measures mx1 , · · · , mxn , which is a direct generalization of the pairwise Wasserstein distance between measures.
We will make frequent use of the following well-known facts in the theory of multi-marginal optimal transport problems (see
e.g. [20]–[22], [24], [25] and the references therein):
Proposition 1 (Multi-marginal and barycenter [20]). The minimum of the multi-marginal optimal transport problem is equal
to the minimum of the Wasserstein barycenter problem, i.e.
W1 (Xn ) =

inf

ν∈P(M)

n
X

W1 (mxi , ν)

(11)

i=1

where the L1 -Wasserstein distance W1 (m, ν) for any m, ν ∈ P (M ) is defined in (8).
The minimization problem in (11) is called Wasserstein barycenter of Xn .
Proposition 2 (Duality [25]).
W1 (Xn ) =

sup

n Z
X

(f1 ,··· ,fn )∈F i=1

fi (ξ) dmxi (ξ)

(12)

M

where the supremum is taken over
n
o
n
X
fi (ξi ) ≤ c (ξ1 , · · · , ξn ) .
F := (f1 , · · · , fn ) fi ∈ L1 (M, mxi ) ∀1 ≤ i ≤ |ex | ,
i=1

We postpone the justification of our nomenclature of “scalar curvature” in Section V, under an appropriate manifold setting.
Briefly speaking, at least when the hypergraph arises from a Riemannian manifold in a natural geometric construction, the
coarse scalar curvature (9) is asymptotically lower bounded by the scalar curvature of the Riemannian manifold.

4

D. Hypergraph Curvature
Let a hypergraph H = (V, E) with V = {1, 2, . . . , N } and a hyperedge E = {1, 2, . . . , n} be given. Inspired by coarse
scalar curvature, we wish to define the curvature for each hyperedge E of H. To this goal, we first need to define random
walk over hypergraphs. It is natural to define the (uniform) random walk started at vertex i ∈ V on H as the following: for
each j ∈ V
X
1
1
,
(13)
mi (j) =
di d(E) − 1
E∈E:(i,j)∈E

and hence we associate E with n probability measures
mi ∈ P(V ), 1 ≤ i ≤ n. Replacing Xn with {1, 2, . . . , n} in
P
Definition 2 and defining c(x1 , . . . , xn ) = minz∈V ni=1 d(xi , z), we can define a multi-marginal optimal transport problem
associated with E ∈ E as
X
W (E) :=
min
c(xn )π(xn ),
(14)
π∈Π(m1 ,m2 ,...,mn )

xn ∈V n

n

where x = (x1 , x2 , . . . , xn ). It is worth mentioning that c(1, 2, . . . , n) = n − 1 as {1, 2, . . . , n} is a hyperedge. In general,
c(x1 , . . . , xn ) ≥ n − 1 for distinct x1 , . . . , xn .
Definition 3 (Hypergraph Curvature). The curvature of a hyperedge E = {1, 2, . . . , n} ∈ E is defined as
W (E)
.
n−1
Note that if xi ∈
/ N (i), then π(x1 , . . . , xi , . . . , xn ) = 0 for all π ∈ Π(m1 , . . . , mn ). Hence, we have either c(x1 , . . . , xn ) ≤
3(n − 1) or π(x1 , . . . , xn ) = 0 for all π ∈ Π(m1 , . . . , mn ). This then demonstrates that, similar to graph curvature, −2 ≤
κ(E) ≤ 1.
Specializing Propositions 1 and 2 to the hypergraph setting, we now provide two equivalent formulations for hypergraph
curvature.
Barycenter: Although the minimization problem in (14) is a linear program, its complexity is exponential in N . However, it
turns out [26] that Wasserstein barycenter problem (11) can be solved quite efficiently. The equivalence between barycenter
problem and multi-marginal optimal transport problem justifies to define the Wasserstein barycenter of hyperedge E as
κ(E) := 1 −

bar(E) :=

inf

ν∈P(V )

Following mutatis mutandis Proposition 1, we have

n
X

W (mi , ν).

(15)

i=1

bar(E)
.
(16)
n−1
The term P
barycenter makes sense by recalling that for the Euclidean space the barycenter of points {xi }ni=1 is given by
n
arg minx i=1 kxi − xk2 . Consequently, bar(E) is the barycenter of points {mi }ni=1 in the Wasserstein space (i.e., a
metric space with Wasserstein distance).
Duality Following mutatis mutandis Proposition 2, we can write the following dual formula for W (E)
κ(E) = 1 −

κ(E) = 1 −

n
X
1
Emi [fi (X)],
sup
n − 1 (f1 ,...,fn )∈K i=1

(17)

where Eν [·] is the expectation operator with respect to measure ν and K is the set of all integrable real-valued functions
on V such that for any vector (x1 , . . . , xn ) ∈ V n
n
X

fk (xk ) ≤ c(x1 , . . . , xn ).

(18)

k=1

After defining hypergraph curvature, a natural question is whether or not this definition reduces to graph Ricci curvature (4) if
the hypergraph is indeed a simple graph, i.e., the cardinality of each hyperedge is two. We answer this question in affirmative by
invoking the barycenter interpretation. If H is in fact a graph and E is a hyperedge (i.e., n = 2 and thus E = {1, 2}), then bar(E)
equals either m1 or m2 , because for any ν ∈ P(V ) the triangle inequality implies W (m1 , ν) + W (m2 , ν) ≥ W (m1 , m2 ).
Thus, hypergraph curvature coincides with (4).
It is a well-known fact that Ollivier-Ricci curvature of edge (x, y) depends heavily on the number of common neighbors of
x and y. Specifically, if N (x) ∩ N (y) = ∅, then κ(x, y) ≤ 0 (see e.g., [14]). We now prove a similar result for hypergraphs.
Theorem 1. For any hyperedge E with cardinality m, we have
X |N (υ) ∩ N (ϑ) ∩ F |
.
W (E) ≥ 1 − min
υ,ϑ∈E
(d(F ) − 1)dυ
F ∈E

5

Proof. Let again E be denoted by {1, 2, . . . , n}. The proof relies on the dual formula of W (E). In order to make use of (17),
we need to find a set of functions {fj }nj=1 that satisfy the constraint (18). Fix two vertices υ and ϑ in E. Set fi ≡ 0 for
i ∈ E\{ϑ, υ} and suppose
fυ (r) + fϑ (s) ≤ d(r, s),
(19)
for all pairs of vertices (r, s). Then we have for any vector (x1 , . . . , xn ) ∈ V n
n
X

fi (xi ) =

fυ (xυ ) + fϑ (xϑ )

i=1

≤

d(xυ , xϑ ) = min [d(xυ , z) + d(xϑ , z)]

≤

c(x1 , . . . , xn ).

z∈V

Hence, the constraints fi ≡ 0 for i ∈ E\{ϑ, υ} and (19) are sufficient to satisfy (18).
Letting Cυ,ϑ denote the set of real-valued functions satisfying (19), we can write
X
X
fυ (r)mυ (r) +
W (E) ≥
sup
fϑ (r)mϑ (r)
fυ ,fϑ ∈Cυ,ϑ r∈V

=

sup

X

f ∈A r∈V

r∈V

f (r) [mυ (r) − mϑ (r)] ,

where the last equality is due to [27, Theorem 1.14] and A is the set of all real-valued 1-Lipschitz functions f on V , that is
A := {f : V → R : |f (r) − f (s)| ≤ d(r, s)}.
Now consider the following function
f (r) =

(

2, if r ∈ N (υ)\N (ϑ),
1, otherwise.

Clearly, f ∈ A and therefore,
W (E)

≥

X

f (r) [mυ (r) − mϑ (r)]

r∈V

=

X

2

mυ (r) +

=

mυ (r) − 1

r∈N (υ)∩N (ϑ)

r∈N (υ)\N (ϑ)

=

X

1 − mυ (N (υ) ∩ N (ϑ))
X |N (υ) ∩ N (ϑ) ∩ F |
.
1−
(d(F ) − 1)dυ
F ∈E

In light of this theorem, we have

X |N (υ) ∩ N (ϑ) ∩ F |
.
υ,ϑ∈E
(d(F ) − 1)dυ

κ(E) ≤ min

(20)

F ∈E

If H happens to be a simple graph, then for every edge E = (υ, ϑ), we have mυ (N (υ) ∩ N (ϑ)) =
of triangles supported on edge E. Hence, the bound (20) implies
κ(υ, ϑ) ≤

∆
,
max{dυ , dϑ }

∆
dυ ,

where ∆ is the number

(21)

which appears in [14, Theorem 4].
Remark 1 (Curvature as a projection of Boltzmann). Cuturi [26] introduced an entropic regularized version of Wasserstein
distance between two measures as
X
π(r, s)d(r, s) − εH(π)
Wε (µ, ν) :=
inf
π∈Π(µ,ν)

=

ε

inf

(r,s)∈V ×V

π∈Π(µ,ν)

D(πkKε ) − ε log Z(ε),

(22)

where ε > 0 is the regularization parameter, H(·) denotes the Shannon entropy function, Kε is the Boltzmann distribution
P
−d(x,y)/ε
and Z(ε) := (x,y)∈V ×V e−d(x,y)/ε . It follows that W (µ, ν) = limε↓0 Wε (µ, ν) [?]. As
defined as Kε (x, y) := e Z(ε)
mentioned in [26], despite the theoretically-guaranteed convergence, the procedure cannot work beyond a graph-dependent
value ε0 beyond which some entries of Kε are represented as zeroes in memory. Since H(·) is a strictly concave function, the

6

optimization problem in (22) has a unique solution π ∗ which corresponds to the projection of Kε onto Π(µ, ν). Following this
spirit, we can define the entropic regularized Wasserstein barycenter problem as
:=

Wε (E)

=
n

inf

ν∈P(V )

n
X

Wε (mi , ν)

i=1


ε inf D PkKε⊗n − nε log Z(ε)
P∈C

where C := {π1 ⊗ π2 ⊗ · · · ⊗ πn ∈ P (V × V ) : πi 1 = mi , and ∃η ∈ P(V ) s.t. πiT 1 = η}. Hence, Wε (E) is the
unique projection of Kε⊗n onto C. Assuming ε is sufficiently small, it follows that W (m1 , . . . , mn ) is an approximation of
this projection.
III. C OMPLETE UNIFORM

HYPERGRAPHS

Graph Ricci curvature turns out to have a simple formula for complete graphs KN . In particular, it is shown [14] that
−2
κ(x, y) = N
N −1 for any edges (x, y) in KN . In this section, we show that complete uniform hypergraphs with N vertices have
the same curvature as KN .
n
Definition 4. A hypergraph HN
= (V, E) is called complete n-uniform for n ≤ |V | = N if E = [V ]n , where [V ]n is the
collection of all n-subsets of V .

−1
2
n
Notice that HN
= KN . Recall that V = {1, 2, . . . , N }. It follows that in HN
, we have d(j) = N
n−1 , j ∈ V and d(E) = n

−2
for each E ∈ E. Furthermore, any pair of (i, j) ∈ E is contained in N
n−2 many hyperedges. Therefore, according to (13),
n
the random walk started at j ∈ V of HN is

mj (r) =

1{r6=j}
N −1

∀r ∈ V.

(23)

n
Lemma 1. For every hyperedge E of HN
, we have

W (E) =

n−1
.
N −1

In particular,

N −2
.
N −1
In light of this lemma, the curvature of complete n-uniform hypergraphs is independent of n. This is, in fact, a result of the
normalization in Definition 3.
κ(E) =

n
Proof. Again let E = {1, 2, . . . , n}. Notice that for HM
, we have d(r, s) = 1 for any distinct pair of vertices r, s ∈ V . Thus,
we can write for a measure ν ∈ P(V )
n
X

W (m1 , ν) =

i=1

=

min

π (1) ∈Π(m1 ,ν)

min

π (1) ∈Π(m1 ,ν)
n

=

N X
N
X

d(r, s)π (1) (r, s) + · · · +

r=1 s=1
N
X

"

1−

π

(1)

#

(r, r) + · · · +

r=1

1X
kmi − νk,
2 i=1

min

π (n) ∈Π(mn ,ν)

min

π (n) ∈Π(mn ,ν)

"

N X
N
X
r=1 s=1
N
X

1−

π

d(r, s)π (n) (r, s)
(n)

1
n

Pn

i=1

mi . Recalling that mi (r) =

1{r6=i}
N −1 ,

we obtain

W (E) =

n−1
.
N −1

(r, r)

r=1

where the last equality follows from [27, Exercise 1.17] and for two vectors a and b, ka − bk :=
obtain
n
n
1X
1X
bar(E) = inf
kmi − νk =
kmi − m̄k,
ν∈P(V ) 2
2 i=1
i=1
where m̄ =

#

P

i

|a(i) − b(i)|. Thus, we

7

Fig. 1. A hyperpath with 42 vertices and 7 hyperedges. For the green hyperdge, we have m = 10 and β = 7. Note that, unlike path graph,
hyperpath might have cycles.

IV. E XAMPLES
In this section, we focus on the computation of hypergraph curvature in two examples to illustrate the differences and
similarities with the graph curvature. The first example is a natural generalization of infinite path Pn ; a simple graph that has
n vertices with n − 2 vertices of degree 2 and the other two of degree one.
Example 1. It is shown [28] that Pn is one of the few graphs (among graphs with girth at least 5) with constant zero curvature.
We now demonstrate in the following theorem that a similar statement does not hold for the hyperpath; a hypergraph whose
vertices have degree at most 2. For the ease of presentation, we assume that any two intersecting hyperedges have exactly one
common vertex; see Fig. 2.
Theorem 2. For any hyperedge E of a hyperpath described above, we have
W (E) ≤ β

3n − 4
2n − 3
+ (n − β − 1)
,
2(n − 1)
2(n − 1)

where n := d(E) ≥ 3 and β := |{v ∈ E : ∄R ∈ E, v ∈ R}| < n. In particular, the curvature of hyperedge E is bounded
from below by
−(n − β − 2)
κ(E) ≥
.
2(n − 1)
Proof Sketch. The proof relies on the simple observation that for the hyperedge E = {1, 2, . . . , n}, we have W (E) ≤
P
n
i=1 W (mi , ν) for any probability measure ν ∈ P(V ). In particular,
W (E) ≤

n
X

W (mi , m1 ).

(24)

i=2

Assuming that {1, 2, . . . , n − β} are vertices in E that are shared with other hyperedges and {n − β + 1, . . . , n} are isolated
vertices inside E, we can employ a tedious (yet standard) linear-programming argument to show that
W (m1 , mj ) =
and
W (m1 , mk ) =

3n − 4
,
2(n − 1)

2n − 3
,
2(n − 1)

∀j ∈ {2, . . . , n − β},

(25)

∀k ∈ {n − β + 1, . . . , n}.

(26)

Plugging (25) and (26) into (24), we obtain the result.
In light of this result, we have κ(E) > 0 if only one vertex of E is shared, i.e., β > n − 2. In other words, the leaves of a
hyperpath have positive curvature which is different from graph curvature in that in simple graphs (with girth at least 5) each
edge connecting to a leaf has zero curvature, see [28, Theorem 3.3].
Example 2. As a toy example, consider the hypergraph H = (V, E) with V = {1, 2, . . . , 13} and E = {E1 , E2 , E3 , E4 },
where E1 = {1, 2, 3}, E2 = {2, 4, . . . , 7}, E3 = {6, . . . , 11}, and E4 = {7, 11, 12, 13}, as illustrated in Fig. 2. Using (13),
we can compute the probability measures associated to each hyperedge. For instance, the random walk started at vertex 2 is
µ2 = [0.25, 0, 0.25, 0.125, 0.125, 0.125, 0.125, 0, . . ., 0]. Since there are only 13 vertices, we can solve the optimization problem
(14) (as a linear program) for each hyperedge. Solving this optimization problem, we obtain W (E1 ) = 1, W (E2 ) = 2.38,
W (E3 ) = 2.08, and W (E4 ) = 1.45. Consequently, it follows that κ(E1 ) = 0.5, κ(E2 ) = 0.4, κ(E3 ) = 0.58, and κ(E4 ) = 0.52.
Informally speaking, the hyperedge with the lowest curvature is the bridge connecting two components of hypergraphs. This
is similar to the intuition of graph Ricci curvature, as experimentally observed in [29], that edges with negative curvature are
locally shortcuts of two component of graph.

8

4

E2 5
2

3
E1

8
6
7

11
13 12

1

9 E3
10

E4

Fig. 2. The hypergraph studied in Example 2.

V. C OARSE S CALAR C URVATURE

IN A

R IEMANNIAN M ANIFOLD S ETTING

In this section, we establish a consistency result for the definition of coarse scalar curvature (9) under a Riemannian manifold
setting. We will assume the hypergraphs of interest stem from a natural geometric model encoding adjacency relations among
discrete points randomly sampled from a Riemannian manifold.
Definition 5 (ε-Neighborhood Hypergraphs). Let (M, dM ) be a complete metric space. For any ε > 0, an ε-neighborhood
hypergraph H = (V, E) supported on M consists of the following data:
• A finite set of vertices V = {vi ∈ M, 1 ≤ i ≤ N };
• A set of hyperedges E, where each E ∈ E is a subset of V satisfying
diam (E) := sup dM (u, v) < 2ε;
u,v∈E

Every subset U of vertices with diam (U ) < 2ε corresponds to a hyperedge EU ∈ E.
We will denote |E| for the number of vertices joined by hyperedge E; |V | and |E| will be used to denote the number of vertices
and hyperedges in H, respectively.
•

The definition of ε-neighborhood hypergraphs assumes that the spatial proximity of the vertices is faithfully reflected in the
connectivity: the diameter of every hyperedge — understood as a discrete subset E ⊂ V — is bounded from above by 2ε.
In the rest of this section, we will assume M is an orientable d-dimensional complete Riemannian manifold with finite
volume, and the distance function dM : M × M → [0, ∞) is induced from the Riemannian length structure. As often
encountered in the manifold learning setup (see e.g. [30] and [31]), we assume the vertices of H are sampled i.i.d. uniformly
on M with respect to the standard volume measure dvol/vol (M ). Our goal in this section is to establish conditions under
which the coarse scalar curvature (9) converges to the scalar curvature on M in the limit |V | → ∞ and ε → 0. We begin
our discussion by summarizing some geometric and statistical properties of the Riemannian medians that we will need in the
following two lemmas.
Lemma 2. Let M be an orientable d-dimensional complete Riemannian manifold with
• Finite volume vol (M ) < ∞;
• Finite, positive injectivity radius 0 < Inj (M ) < ∞;
• Uniformly bounded sectional curvature Kx (u, v) < D for D ∈ R and all x ∈ M , u, v ∈ Tx M .
Assume U = {x1 , · · · , xn } is a finite discrete subset of M contained in a geodesic ball B (x, ε) of sufficiently small radius
ε > 0 satisfying
n
o
(
min D−1/2 π/4, Inj (M ) /2
if D > 0
2ε <
(27)
Inj (M ) /2
otherwise
and U is not totally contained in any geodesic on M . Then there exists a unique x̄ ∈ M minimizing the moment function
M ∋ z 7→

n
X

dM (z, xi ) ∈ [0, ∞) ,

i=1

and x̄ lies in the smallest closed, geodesically convex subset of B (x, ε) containing U .
Proof. The bound on ε and the assumption that U is not totally contained in any geodesic on M together ensures the uniqueness
of x̄, according to [32, Theorem 3.1]; the existence can be found e.g. in [33] or [34]. The last assertion about the location of
x̄ is a consequence of [32, Proposition 2.4].
The minimizer x̄ is known as the Riemannian median. Note that the diameter bound 2ε only depends on the injectivity
radius when the Riemannian manifold has negative sectional curvatures; this is of particular interest to us since many real
world networks demonstrate “negatively curved” behaviors, see e.g., [29], [35], [36].

9

∞

Lemma 3. Assume M , ε > 0 satisfy the same assumptions as in Lemma 2. Let {Xn }n=1 be a sequence of i.i.d. random points
uniformly distributed in a geodesic ball B (x, ε) of radius ε > 0 centering at x ∈ M , and denote µn for the Riemannian
median of X1 , · · · , Xn for all n ∈ N. Then µn → x̄ a.s. as n → ∞, where x̄ is the unique Riemannian median of the uniform
distribution on B (x, ε).
Proof. The existence and uniqueness of µn and x̄ follows from Lemma 2; note here that x̄ need not coincide with x in
general, by the characterization of Riemannian medians established in [32, Proposition 2.1 and Theorem 2.2]. The almost sure
convergence has been established in [34, Corollary 4.1].
We now turn to investigating the coarse scalar curvature of hypergraphs generated from a geometric probabilistic model:
saturated ε-neighborhood hypergraphs supported on a Riemannian manifold M , with vertices uniformly distributed on M . We
consider the same random walk on the Riemannian manifold M as in [10], namely, the one given in (6): for any x ∈ M and
ε > 0,
1B(x,ε)
dmεx :=
dvol,
(28)
vol(B(x, ε))
which is essentially the standard volume measure on M restricted and renormalized on B (x, ε). For simplicity of statement,
let us denote x̂E for the Riemannian median — when it exists and is unique — of the vertices connected by a hyperedge E
in a saturated hypergraph G = (V, E).
∞

Theorem 3. Let M , ε > 0 be as assumed in Lemma 2. Let {vi }i=1 be a sequence of i.i.d. random points sampled uniformly
on M with respect to the standard Riemannian volume measure. For any N ∈ N, let VN := {vi }N
i=1 and HN = (VN , EN ) be
an ε-neighborhood hypergraph supported on M . If there exists a hyperedge EN ∈ EN for each Hn such that
• EN $ EN +1 for all sufficiently large N ∈ N
• there exists x̄ ∈ M such that x̂EN → x̄ as n → ∞
• EN ⊂ B (x̄, ε) for all sufficiently large N ∈ N
then the coarse scalar curvature of hyperedge EN satisfies, for all sufficiently small ε > 0,
lim sup κ (EN ) ≥
N →∞


ε2
Scal (x̄) + O ε3 .
2 (d + 2)

(29)

Proof. Since curvature is a local quantity, we may assume without loss of generality that M is connected and even compact. Let
ε > 0 be sufficiently small such that the geodesic ball B (x̄, ε) is geodesically convex neighborhood of x̄ (c.f. [23, Proposition
4.2]). To ease notations, write ℓN := |EN | and denote x1 , · · · , xℓN ∈ VN for the vertices of HN connected by the hyperedge
EN ∈ E. By Proposition 1 and the definition of Riemannian median, we have
Z
dvol (y)
W1 (my , mx̄ )
P ℓN
vol (B (x̄, ε))
W1 (mxi , mx̄ ) ℓN →∞ B(x̄,ε)
W1 (EN )
(30)
−−−−→ Z
≤ Pi=1
ℓ
N
dvol (y)
c (x1 , · · · , xℓn )
i=1 dM (xi , x̂EN )
dM (y, x̄)
vol (B (x̄, ε))
B(x̄,ε)

where the limit follows from the law of large number and the Lipschitz continuity of the function (see e.g. [32, §2])
Z
dM (x, y) dvol (y) .
x 7→
B(x,ε)

We know from [10, Example 7] that, for any y ∈ B (x̄, ε),



ε2
Ric (vx̄,y , vx̄,y ) + O ε3 dM (x̄, y)
W1 (my , mx̄ ) = 1 −
2 (d + 2)

where vx̄,y is a unit tangent vector in Tx̄ M such that

expx̄ (dM (x̄, y) vx̄,y ) = y.
It follows that
Z

ε2
W1 (my , mx̄ ) dvol (y) =
dM (x̄, y) dvol (y) −
2 (d + 2)
B(x̄,ε)
B(x̄,ε)
!
Z
Z

+ O ε3

dM (x̄, y) dvol (y)

B(x̄,ε)

Z

Ric (vx̄,y , vx̄,y ) dM (x̄, y) dvol (y)
B(x̄,ε)

10

which, when plugged back into (30), gives

ε2
W1 (EN )
≤ 1 + O ε3 −
lim sup
2 (d + 2)
N →∞ c (x1 , · · · , xℓN )

dvol (y)
Ric (vx̄,y , vx̄,y ) dM (x̄, y)
vol
(B (x̄, ε))
B(x̄,ε)
Z
.
dvol (y)
dM (x̄, y)
vol (B (x̄, ε))
B(x̄,ε)

Z

A straightforward calculation using geodesic normal coordinates reveals


Z

Scal (x)
d
ε2
dvolM (y)
=ε
−
+ O ε3
dM (x, y)
vol (B (x, ε))
d+1
3 (d + 1) (d + 2) (d + 3)
B(x,ε)

(31)

(32)

and
Z

#
!
"
2

dvolM (y)
|Scal (x)|
ε2
Scal (x)
2
3
Ric (vx,y , vx,y ) dM (x, y)
(33)
=ε
+
− kR (x)k +O ε
vol (B (x, ε))
d+1
3 (d + 2) (d + 3)
d+1
B(x,ε)
Pd
2
where kR (x)k = i=1 |Ric (ei , ei )| for an arbitrary orthonormal basis e1 , · · · , ed of Tx̄ M . Plugging (32) and (33) back into
(31) to conclude that

W1 (EN )
ε2
lim sup
(34)
≤1−
Scal (x̄) + O ε3 .
2 (d + 2)
ℓN →∞ c (x1 , · · · , xℓN )
Theorem 3 indicates that coarse scalar curvature asymptotically upper bounds the scalar curvature of the Riemannian manifold,
when the hypergraph is constructed from uniformly sampling the manifold in a natural way. This justifies the nomenclature
of "scalar curvature" in our definition. We conjecture that coarse scalar curvature also asymptotically lower bounds the scalar
curvature in the same setting, but will have to leave that for future work.
VI. C ONCLUSION

AND FUTURE WORK

In this paper, we propose a novel definition of curvature for hypergraphs by generalizing coarse Ricci curvature to coarse
scalar curvature through multi-marginal optimal transport. Our definition is shown to be consistent with graph curvature in
that (i) it reduces to graph curvature if the hypergraph of interest is indeed a simple graph, and (ii) it shares several properties
with graph curvature. In particular, it is experimentally observed that, analogous to graph curvature, hypergraph curvature
can be used to determine the bridge between components in the network. We are currently computing hypergraph curvature
in real-world hypergraph networks (in particular co-authorship or cellular networks) to observe this centrality property of
hypergraph curvature. We are also applying hypergraph curvature to characterize dynamic effects in large dynamic network
(in particular, financial network). Intuitively, hypergraph curvature provides a computational method for detecting changes in
dynamic networks, characterizing fast evolving network components, as well as identifying stable network region. On the
theoretical side, we are interested in gaining better understandings of our hypergraph curvature with deeper insights from
differential geometry.
R EFERENCES
[1] E. Demir, C. Aykanat, and B. B. Cambazoglu, “Clustering spatial networks for aggregate query processing: A hypergraph approach,” Information
Systems, vol. 33, no. 1, pp. 1–17, 2008. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S030643790700021X
[2] A. Chasapi, C. Kotropoulos, and K. Pliakos, “Adaptive algorithms for hypergraph learning,” in IEEE Int. Conf. Acoustics, Speech and Signal Processing
(ICASSP), March 2016, pp. 1179–1183.
[3] Y. Fang and Y. Zheng, “Metric learning based on attribute hypergraph,” in IEEE Int. Conf. Image Processing (ICIP), Sept 2017, pp. 3440–3444.
[4] S. Klamt, H. U-U, and F. Theis, “Hypergraphs and Cellular Networks,” PLoS Comput Biol, vol. 5, no. 5, p. e1000385, May 2009.
[5] P. Ji and J. Jin, “Coauthorship and citation networks for statisticians,” The Annals of Applied Statistics, vol. 10, no. 4, pp. 1779–1812, 12 2016.
[6] T.-H. H. Chan, Z. G. Tang, and C. Zhang, “Spectral Properties of Laplacian and Stochastic Diffusion Process for Edge Expansion in Hypergraphs,”
[Preprint] arXiv:1510.01520v1, 2017.
[7] R. Shaydulin, J. Chen, and I. Safro, “Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning,” [Preprint] arXiv:1710.06552v2, 2017.
[8] A. Louis, “Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms,” [Preprint] arXiv:1408.2425v2, 2016.
[9] A. Banerjee, “On the spectrum of hypergraphs,” [Preprint] arXiv:1711.09356v2, 2017.
[10] Y. Ollivier, “Ricci curvature of Markov chains on metric spaces,” Journal of Functional Analysis, vol. 256, no. 3, pp. 810–864, 2009.
[11] Y. Lin, L. Lu, and S.-T. Yau, “Ricci Curvature of Graphs,” Tohoku Mathematical Journal, vol. 63, no. 4, pp. 605–627, 2011.
[12] E. Saucan, A. Samal, M. Weber, and J. Jost, “Discrete curvatures and network analysis,” Max Planck Institute for Mathematics in the Sciences,
Preprint, 2017. [Online]. Available: http://www.mis.mpg.de/de/publications/preprints/2017/prepr2017-34.html
[13] F. Bauer, J. Jost, and S. Liu, “Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator,” Mathematical Research Letters,
vol. 19, pp. 1185–1205, 11 2012.
[14] J. Jost and S. Liu, “Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs,” Discrete and Computational Geometry,
vol. 51, no. 2, pp. 300–322, Mar 2014.
[15] H. J. Cho and S. H. Paeng, “Ollivier’s Ricci curvature and the coloring of graphs,” European Journal of Combinatorics, vol. 34, no. 5, pp. 916–922,
2013.

11

[16] C. C. Ni, Y. Y. Lin, J. Gao, X. D. Gu, and E. Saucan, “Ricci curvature of the Internet topology,” in IEEE Conference on Computer Communications
(INFOCOM), April 2015, pp. 2758–2766.
[17] R. Sandhu, T. Georgiou, and A. Tannenbaum, “Ricci curvature: An economic indicator for market fragility and systemic risk,” Science Advances, vol. 2,
no. 5, 2016.
[18] H. Farooq, Y. Chen, T. Georgiou, A. Tannenbaum, and C. Lenglet, “Network Curvature as a Hallmark of Brain Structural Connectivity,” bioRxiv, 2017.
[19] R. Sandhu, T. Georgiou, E. Reznik, L. Zhu, I. Kolesov, Y. Senbabaoglu, and A. Tannenbaum, “Graph curvature for differentiating cancer networks,”
Scientific Reports, vol. 5, 7 2015.
[20] G. Carlier and I. Ekeland, “Matching for Teams,” Economic Theory, vol. 42, no. 2, pp. 397–418, 2010.
[21] Y. H. Kim and Pass, B., “Multi-marginal Optimal Transport on Riemannian Manifolds,” American Journal of Mathematics, vol. 137, no. 4, pp. 1045–1060,
2017.
[22] W. Gangbo and A. Świȩch, “Optimal maps for the multidimensional Monge-Kantorovich problem,” Communications on Pure and Applied Mathematics,
vol. 51, no. 1, pp. 23–45, 1998.
[23] M. P. Do Carmo, Riemannian Geometry. Springer, 1992.
[24] M. Agueh and G. Carlier, “Barycenters in the Wasserstein Space,” SIAM Journal on Mathematical Analysis, vol. 43, no. 2, pp. 904–924, 2011.
[25] H. G. Kellerer, “Duality Theorems for Marginal Problems,” Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, vol. 67, no. 4, pp. 399–432,
1984.
[26] M. Cuturi, “Sinkhorn Distances: Lightspeed Computation of Optimal Transport,” in Advances in Neural Information Processing Systems, 2013, pp.
2292–2300.
[27] C. Villani, Topics in Optimal Transportation. American Mathematical Society, 2003.
[28] B. B. Bhattacharya and S. Mukherjee, “Exact and asymptotic results on coarse ricci curvature of graphs,” Discrete Mathematics, vol. 338, no. 1, pp. 23
– 42, 2015.
[29] C.-C. Ni, Y.-Y. Lin, J. Gao, X. D. Gu, and E. Saucan, “Ricci Curvature of the Internet Topology,” ArXiv e-prints, Jan 2015. [Online]. Available:
arXiv:1501.04138v1
[30] M. Belkin and P. Niyogi, “Laplacian Eigenmaps for Dimensionality Reduction and Data Representation,” Neural Comput., vol. 15, no. 6, pp.
1373–1396, Jun. 2003. [Online]. Available: http://dx.doi.org/10.1162/089976603321780317
[31] R. R. Coifman and S. Lafon, “Diffusion Maps,” Applied and Computational Harmonic Analysis, vol. 21, no. 1, pp. 5–30, 2006, special Issue: Diffusion
Maps and Wavelets. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1063520306000546
[32] L. Yang, “Riemannian Median and its Estimation,” LMS Journal of Computation and Mathematics, vol. 13, pp. 461–479, 2010.
[33] P. T. Fletcher, S. Venkatasubramanian, and S. Joshi, “The Geometric Median on Riemannian Manifolds with Application to Robust Atlas Estimation,”
NeuroImage, vol. 45, no. 1, pp. S143–S152, 2009.
[34] M. Arnaudon, F. Barbaresco, and L. Yang, “Medians and Means in Riemannian Geometry: Existence, Uniqueness and Computation,” in Matrix Information
Geometry. Springer, 2013, pp. 169–197.
[35] O. Narayan and I. Saniee, “Large-scale curvature of networks,” Phys. Rev. E, vol. 84, p. 066108, Dec. 2011.
[36] R. Albert, B. DasGupta, and N. Mobasheri, “Topological implications of negative curvature for biological and social networks,” Phys. Rev. E, vol. 89,
p. 032811, Mar 2014.

