On the relation between graph Ricci curvature and community structure

1.   Introduction

The connection between curvature and topology is a fundamental question in Riemannian geometry. Notable examples include the Gauss-Bonnet theorem, which relates the curvature of a surface to its Euler characteristic, and Myer's theorem, which bounds the diameter of a manifold in terms of its curvature (see ^[15] for more details). Remarkably, successful definitions of curvature have been extended to graphs (Forman ^[8], Ollivier ^[20], Lin ^[16], Devriendt ^[4]), generalizing the curvature notions on Riemannian manifolds and establishing analogous connections between curvature and topology.

A crucial topological question in the study of complex networks is their community structure (see ^[9,10] for a survey on community detection). This involves clustering nodes such that many edges connect nodes within the same cluster, while few edges connect nodes between different clusters. These clusters, referred to as communities, are defined based on the application at hand. This task is significant across various fields including computer science ^[13,14], biology ^[5,22,25], chemistry^[21], logistics ^[12,19], where graphs are commonly used to model real-world systems. Consequently, numerous methods based on diverse theories are available, such as partitioning algorithms and spectral methods (^[9] contains a survey of commonly used algorithms).

A recent approach to community detection draws inspiration from the geometric notion of curvature. In this paper, we employ the Ollivier-Ricci curvature (ORC), originally defined by Ollivier ^[20] using optimal transport theory. The essential idea is to compare the distance $d(x, y)$ between two vertices $x$ and $y$ to the distance between the neighbors of $x$ and $y$ (defined in terms of optimal transport). If the latter distance is smaller, the edge is positively curved; if greater, it is negatively curved. For instance, in Figure 1, the edge $(0, 6)$ is one where the neighbors of 0 are further from the neighbors of 6 than 0 is from 6, and would be negatively curved, whereas the edge $(4, 3)$ would be positively curved because the neighbors of 3 and those of 4 largely overlap. Negatively curved edges act as "bottlenecks," indicating that to move from the neighbors of $x$ to those of $y$, one must pass through the edge $xy$. This concept is applied to rewire graph neural networks in ^[28]. It has also been used to study the the robustness of neural networks in ^[26].

Studies such as ^[18,24] have observed that edges with positive ORC typically exist between nodes within the same community, whereas edges with negative ORC often connect nodes from different communities. This observation has been turned into a computational algorithm for community detection. ^[24] achieves this by sequentially deleting negatively curved edges, while ^[18] employs "Ricci flow with surgery" to elongate or contract edges based on their curvature, then removes the longest edges. These curvature-based methods have been shown to perform competitively against other industry-standard techniques.

In addition to experimental and theoretical results on graph Ricci curvature and community detection algorithms, there have been a number of papers in the sciences in recent years that have used such algorithms to reveal interesting structures and relationships. One such is ^[23], where authors have reported that ORC-based methods identify communities in protein complexes than other algorithms. Forman and Ollivier Ricci curvatures have been shown to predict protein-ligand affinity in ^[31,32], highlighting their potential in drug discovery. Another is ^[6], where graph Ricci curvatures have been used to characterize atypical connectivity in the brains of people diagnosed with autism spectrum and other neurodevelopmental disorders. Graph Ricci curvature methods have also been shown to be effective at identifying phase transitions in time-varying complex networks ^[33].

A variant of ORC known as the dynamical ORC has been used in ^[11] to reveal community structures at varying scales of resolution. Mixed membership, where a node is allowed to belong to multiple communities has been studied in ^[27,29] (note that these papers use flow-based approaches similar to ^[18]). Other curvature notions that are not based on optimal transport have also been used to attack the problem of community detection. One of the popular definitions is that of Forman ^[8]. Though not equivalent to Ollivier's notion, it has the advantage of being computationally efficient, and its flow version has been used for community detection in ^[30]. The shortcomings of Forman's definition have been partially mitigated by modifying its definition (while retaining computational efficiency): One such is the augmented Forman-Ricci curvature, which has also been shown to be effective at community detection in ^[7].

From a theoretical point of view, ORC has been linked to other deep properties of graphs. Besides the work of Ollivier himself, one of the earliest theoretical analyses of ORC is ^[16], which relates several geometrical and spectral properties of a graph to its ORC. Its relation to the heat flow on graphs has been studied in ^[17]. The spectrum of the Laplacian is also intimately connected to ORC, and this is shown in ^[1]. Analyses regarding geometric properties of ORC such as flatness, rigidity have been studied in ^[2,3]. In spite of the great theoretical interest in ORC and its relation to other properties of graphs, and a great practical interest in its application to community detection, there has not been a substantial amount of literature in the theoretical relation between ORC and community structure.

A basic question regarding this relationship is the following: It is observed that a single edge connecting two disjoint communities will have negative curvature, whereas a complete graph formed by adding all possible intercommunity edges will have positively curved edges (this is discussed in Section 2). Therefore, the critical question is: What is the maximum number of intercommunity edges such that we can guarantee each one is negatively curved? More broadly, when examining two particular communities in a graph, what can we infer about the curvature of intercommunity edges? This paper aims to address this question quantitatively, as provided by the main theorem.

In all of the following, it is assumed that the graph $\mathcal{G}$ is undirected and all edges have weight 1.

Theorem 1.1. Suppose $\mathcal{G}$ is a graph comprised of several communities. Let $C_i, C_j$ be distinguished communities in $\mathcal{G}$ whose sizes are $m$ and $n$, where $m \ge n$ (without loss of generality). Let $k$ be the total number of edges that are either intercommunity edges between $C_i$ and $C_j$, or from any other community to $C_i$ or $C_j$.

Then, if

we have $\kappa(e) \leq 0$ for every intercommunity edge $e$ between $C_i$ and $C_j$.

In particular, if $k \le \min_l|C_l|-1$ where $C_l$ are the various communities, the same conclusion holds.

We have the following when the community sizes are all the same:

Corollary 1.2. Let $\mathcal{G}$ be a graph as in previous theorem. Suppose in addition that all communities have the same size $n$. Then if $k \le n-1$, we have $\kappa(e) \leq 0$ for every intercommunity edge $e$ between $C_1$ and $C_2$.

In the case where the graph only has two communities, we have the following:

Corollary 1.3. Suppose $\mathcal{G}$ is a graph comprised of only two communities $C_1, C_2$ whose sizes are $m$ and $n$, where $m \ge n$ (without loss of generality). Let $k$ be the total number of intercommunity edges between $C_1$ and $C_2$.

Then, if

we have $\kappa(e) \leq 0$ for every intercommunity edge $e$ between $C_1$ and $C_2$.

If $m = n$, the same conclusion holds for $k \le n-1$.

The paper is organized as follows: In Section 2, we do a quick review of optimal transport as it pertains to graphs, define the Ollivier-Ricci curvature of an edge of a graph, and give some examples. In Section 3, we give a key example that simultaneously motivates the claims in the paper and highlights the computational techniques used to prove the main theorem. In Section 4, we provide a proof of the main theorem and the corollaries. In Section 5, we show that the bound prescribed in the theorem is sharp, but at the same time we show experimental results that show that we have a lot of latitude even if we go beyond the theoretical limit prescribed in the theorem.

2.   Preliminaries

2.1.   Definitions

Let $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ be a graph:

(1) A community $C$ of $\mathcal{G}$ is a maximal complete subgraph of $\mathcal{G}$ (in the sense that $C$ is not contained in any bigger complete subgraph of $\mathcal{G}$, potentially including $\mathcal{G}$).

(2) An edge whose endpoints lie in different communities is called an intercommmunity edge.

(3) An edge whose endpoints both lie inside the same community is called an intracommunity edge.

We remark that this is definition of community is only one of several possible definitions, but this simplifies our mathematical analysis.

2.2.   Optimal transportation on graphs

Let $\mu, \nu$ be probability measures on a graph, and let the vertices be enumerated $1, \ldots, n$. A transference plan $\pi = (\pi_{ij})$ is an $n \times n$ matrix with nonnegative entries such that $\sum_j \pi_{ij} = \mu(i)$, and $\sum_i \pi_{ij} = \nu(j)$. More concisely, $\pi$ is a joint probability distribution on $\mathcal{V} \times \mathcal{V}$ whose marginals are $\mu$ and $\nu$. We define $\Pi$ to be the set of all transference plans between $\mu$ and $\nu$.

Closeness between two probability distributions can be measured via the 1-Wasserstein distance (or earthmover's distance) which is defined as follows:

where $d(i, j)$ is the graph distance between vertices $i, j$.

Proposition 2.1. Under the metric $W$ defined above, the set of all probability measures on $\mathcal{V}$ is a metric space.

Note that computing $W$ amounts to solving a linear programming problem. Therefore, by duality, we have an equivalent formulation for $W$ via a maximization problem. To present this formulation, we first define a $1$-Lipschitz function to be a function $f$ such that $|f(x)-f(y)| \le d(x, y).$ On (combinatorial) graphs, this is equivalent to insisting that the values of $f$ on adjacent nodes do not differ by more than $1.$

Proposition 2.2. Let $\mathcal{F}$ be the set of $1$-Lipschitz functions on $G$. Then,

A function $f$ that achieves this supremum is called a Kantorovich potential.

2.3.   The Ollivier-Ricci curvature

Ollivier ^[20] defined Ricci curvatures on general Markov chains on metric spaces, with random walks as the building blocks. The following is a simplified exposition for graphs. A random walk is a family of probability distributions $\{m_x\}_{x \in \mathcal{G}}$. For any $\alpha \in [0, 1]$, the $\alpha$-lazy random walk is one where the probability measures at each node are given by

Finally, the $\alpha$-Ollivier-Ricci curvature of an edge $e = (xy)$ is defined as

We deal with combinatorial graphs in this paper, and therefore, all edges have length $1$. Thus the formula reduces to

Example 1. The intuition behind the Ollivier-Ricci curvature is captured by the following examples:

a. An edge of the lattice $\mathbf{Z}^n$ has curvature $\kappa = 0$. So does an edge of the cycle $C_n$ for $n \ge 6$.

b. An edge of the complete graph $K_n$ has curvature $\kappa = \frac{n(1-\alpha)}{n-1} > 0$.

c. Imagine a 'dumbbell' graph comprised of two communities of size $m, n$, joined by a single intercommunity edge. This edge has curvature $\kappa = 2(1-\alpha)\left(\frac{1}{m}+\frac{1}{n}-1\right)$, which is negative for all $m, n \ge 3$.

Remark 1. The claims in the above example can be proved by following the general strategy described here.

(1) To establish an upper bound on the curvature, we need a lower bound on $W(m_x, m_y)$. This uses (2.2) and requires prescribing an explicit potential function.

(2) To establish a lower bound on the curvature, we need an upper bound on $W(m_x, m_y)$. This uses (2.1) and requires prescribing an explicit transference plan.

(3) If we can show that the curvature is bounded above and below by the same constant $C$, then the curvature equals $C$.

We will apply this strategy to an important nontrivial example in the next section.

3.   A zero-curvature example

To see what motivates the claims of this paper, we start with the case that the two communities have the same size $n \ge 3$. Consider the number of intercommunity edges below which it is guaranteed that every intercommunity edge is nonpositively curved. We show an explicit construction which suggests that this number can be no more than $n-1$. A proof of the sufficiency of this claim is given by the main theorem of this paper. Sharpness is given by Proposition 5.1.

Theorem 3.1. For communities of size $(n, n)$, there is a configuration of $n-1$ edges between the communities such that each intercommunity edge has zero curvature.

Proof. We give an explicit construction. Let $A, B$ be a complete graph on the vertices $\{a_0, \ldots, a_{n-1}\}, \{b_0, \ldots, b_{n-1}\}$ respectively. Add inter-community edges $a_ib_i, i = 0, \ldots, n-2$ (see Figure 2 for an illustration). We claim that every edge $a_i b_i$ has zero curvature. Indeed by symmetry, we only need to show it for one of them, say $a_0 b_0$.

To get an upper bound on the curvature, we obtain a lower bound on $W(m_{a_0}, m_{b_0})$. We use $f$ as defined in Table 1. Applying the Eq (2.2), an explicit calculation shows that $W(m_{a_0}, m_{b_0}) \ge 1$, which implies $\kappa(a_0 b_0) \le 0$.

To get a lower bound on curvature, we obtain an upper bound on $W(m_{a_0}, m_{b_0})$. We use the following transference plan:

together with $\pi_{a_0 a_0} = \pi_{b_0 b_0} = \frac{1-\alpha}{n}$ and $0$ between any other pair of vertices not specified previously. Note that the associated distances are

Applying Eq (2.1), it follows that $W(m_{a_0}, m_{b_0}) \le 1$ and hence $\kappa(a_0 b_0) \ge 0$. Thus we conclude that

□

Remark 2. The configuration in the previous example is not unique. Indeed, it can be shown using the same technique that the intercommunity edges in Figure 3 have curvature 0.

4.   Proof of main theorem

Let $\mathcal{G}$ be graph, and $C_1, C_2$ be two communities in $\mathcal{G}$. Suppose $e = xy \in \mathcal{E}$, $x \in C_1, y \in C_2$. We obtain an upper bound on $\kappa(e)$ by getting a lower bound on $W(m_x, m_y)$. To do so, we need a potential function. The key step is to partition the graph into several subsets on which $f$ will be constant. We define $C_3 = G - C_1 -C_2$, which could be a union of several communities.

We partition $C_1$ into five subsets $\{x\}, A, B, C, J$, $C_2$ into $\{y\}, D, E, F, K$ and define the subsets $C_3$ in $G, H, I$ in the following way:

● $B = \{z \in C_1-x : yz\in \mathcal{E}\}$,

● $D = \{w \in C_2-y : xw\in \mathcal{E}\}$,

● $C = \{z \in C_1-x-B : zw\in \mathcal{E} \, \text{ for some } w\in C_2\}$,

● $E = \{w \in C_2-y-D : zw\in \mathcal{E} \, \text{ for some } z\in C_1\}$,

● $J = \{z \in C_1-x-B-C : \exists v\in C_3\text{ such that } zv \in \mathcal{E}\}$,

● $K = \{w \in C_2-y-D-E : \exists v\in C_3 \text{ such that } wv \in \mathcal{E}\}$,

● $A = C_1-x-B-C-J$,

● $F = C_2-y-D-E-K$,

● $G = \{v \in \mathcal{G}-C_1-C_2:\, xv, yv\in \mathcal{E}\}$,

● $H = \{v \in \mathcal{G}-C_1-C_2-G:\, xv\in \mathcal{E}\}$,

● $I = \{v \in \mathcal{G}-C_1-C_2-G:\, yv\in \mathcal{E}\}$.

This configuration, along with the values of the function $f$ are illustrated in Figure 4. The number shown inside each "node" (or subset of $\mathcal{G}$ to be precise) is the value of the function $f$. Note that we have not added all possible edges: For instance, there could be edges $C$ and $D$, between $J$ and $H$, and so on. The important thing is that $A, J$ do not have neighbours in $C_2$, and $F, K$ do not have neighbours in $C_1$. This ensures that the function in Table 2 is 1-Lipschitz.

In Table 2 we depict the measures $m_x, m_y$ together with the value of $f$. We let $\beta := 1-\alpha$.

In the following we abuse notation by conflating $S$ with its cardinality $|S|$ where $S$ could be any of the sets $A, \ldots, K$. Let $W = W(m_x, m_y)$. Using (2.2) we have the following bound:

We also have the following constraint equations from counting nodes and edges:

Equations (4.1) and (4.2) together give

Note that the lack of symmetry between $x$ and $y$ in the above expression is due to the lack of symmetry in the way we defined $f$.

Let $k_1$ be the number of intercommunity edges between $C_1$ and $C_2$, and $k_2$ be the number of edges from $C_1$ or $C_2$ to the rest of $\mathcal{G}$. Then,

Defining $k = k_1+k_2$, we have

which, together with the constraint Eq (4.2), yields

and

The plan is to get $W \ge 1$ (which would imply our goal of $\kappa(xy) \le 0$). From (4.3), it is sufficient to find the optimal $k$ such that

which reduces to

When $m = n$, it is trivial to see that the above equation is true precisely when $k \le n-1$. When $m > n$, we have

Since $d_x \ge n$ and $d_x + d_y \le n+m+k-1$, a sufficient condition for the above to be true is

which results in the quadratic inequality

Theorem 1.1 now follows directly from this.

Proof of Corollary 1. By letting $m = n$, we get

□

Proof of Corollary 2. In the proof of main theorem, we may assume that $G, H, L, I, M = \emptyset$. Consequently, $J, K = \emptyset$ as well, and $k_2 = 0$, and the claim follows immediately. □

5.   Empirical results

In the previous section, we gave theoretical bounds on the number of intercommunity edges that guarantee the negativity of curvatures. This bound is sharp due to the following proposition:

Proposition 5.1. For communities of size $(n, n)$, there is a configuration of $n$ edges between the communities such that each intercommunity edge has positive curvature.

Proof. Consider the product graph of the complete graph $K_n$ with the graph consisting of only two points joined by an edge. See Figure 5 for an illustration with $n = 4$.

We can show that edge $a_0 b_0$ (and hence every intercommunity edge) has positive curvature. The distributions $m_{a_0}, m_{b_0}$ are shown in Table 3.

Consider the transference plan defined by $\pi_{a_0a_0} = \pi_{b_0b_0} = \frac{1-\alpha}{n}$,

This plan has a cost of

which is an upper bound on $W(m_{a_0}, m_{b_0})$, and hence

□

Even though it is theoretically possible for all edges to be positively curved when we have $k = n$ intercommunity edges, the point of the remainder of this section is to share experimental findings that indicate how unlikely such a situation is. For the sake of simplicity, we generate two-community graphs with randomly chosen intercommunity edges and observe the empirical proportion of nonpositively curved edges.

Figure 6 shows the result of one such experiment. Here, we choose the community sizes $|C_1| = |C_2| = 128$. We experiment with $k = 128,256,384,512$ intercommunity edges. For each $k$, we generate 100 graphs where $k$ intercommunity edges are chosen at random. In each of those random graphs, we compute the proportion $p^k_{\le 0}$ of nonpositively curved edges. Finally, we plot $p^k_{\le 0}$ versus its frequency of occurrence.

One notices in Figure 6 that for $k = 128,256$, almost all edges were negatively curved in every one of the 100 randomly generated graphs. When $k = 384$, most of the edges are negatively curved. But when $k = 512$, the proportion of negatively curved edges is small.

In fact, we find something similar for different sizes. In Figure 7, we examine community sizes $n = 16, 32, 64,128,256,512$. And for each $n$, we generate graphs with number of intercommunity edges $k = n, \; 2n, \; 3n, \; 4n$ and empirically find the proportion of intercommunity edges that have nonpositive curvature. For each choice of $(n, k)$, we generate $100$ graphs at random. We plot the empirical proportion of nonpositive edges with error bars one standard deviation wide (over the 100 runs.) What we find is that for $n \ge 32$, even when we have $2n$ intercommunity edges, almost all of them are negatively curved. When $n = 512$, even when $k = 4n$ we have almost all edges negatively curved.

6.   Conclusions

In this paper, we have examined the relation between curvature and community structure from a theoretical point of view. In particular, we have sought to understand how the sizes of communities and the number of intercommunity edges affects the curvature of those intercommunity edges. More specifically, we have given sufficient conditions for intercommunity edges to be negatively curved. In addition, we show these requirements are sharp, in the sense that there are counterexamples as soon as we cross the cutoff. We have achieved this by exploiting two equivalent definitions of the Wasserstein distance between probability distributions, which give us concrete computational tools for proving curvature estimates.

In the experimental section of the paper, we explored how likely it is to find positively curved edges when the number of intercommunity edges $k$ exceeds the theoretical bound. We found that as the community sizes become large, $k$ can get much larger than the theoretical bound while most of the intercommunity edges have negative curvature. A likely explanation for this is in the estimate (4.3). Here we see that the Wasserstein distance is large when the "unmatched" sections $A, F$ are large and the node degrees $d_x, d_y$ are small. When we randomly sample intercommunity edges from the list of all possible intercommunity edges, we are less likely to sample an edge configuration where degrees are very large and the unmatched sections are very small, at least when the number of intercommunity edges is very small.

We believe that this analysis raises several interesting questions. For instance, it would be very interesting to study the curvature of intracommunity edges and obtain criteria that ensure that they are positively curved. In effect, this would provide a theoretical underpinning for curvature-based community detection via edge deletion. Another interesting direction is the analysis of curvature distribution as a function of the number of intercommunity edges. For instance, for a fixed $k$, let $I$ be a random sample of $k$ intercommunity edges from the list of all possible ones. Now we can generate a graph with $I$ as the set of intercommunity edges. Let $\kappa_{max}(I)$ be the maximum curvature among edges in $I$, which we may regard as a random variable. What is the probability distribution of $\kappa_{max}$? How is it affected by $k$? Another interesting question is one that concerns "surgery", or edge deletion. How does the deletion of a subset of edges of a graph affect the curvature of the remaining edges? Questions of this nature provide ideal circumstances for the synthesis of tools from differential geometry, graph theory, statistics, and programming.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The work of authors SR and VM was partially supported by the US Army Research Office Grant No W911NF2110094. The work of TB was supported through grant DMS-2105026 of the National Science Foundation.

Conflict of interest

The authors declare no conflicts of interest.