Lower Ricci Curvature for Efficient Community Detection
Authors: Yun Jin Park
Didong Li
Venue: Accepted by TMLR ()

Abstract: This study introduces the Lower Ricci Curvature (LRC), a novel, scalable, and scale-free discrete curvature designed to enhance community detection in networks. Addressing the computational challenges posed by existing curvature-based methods, LRC offers a streamlined approach with linear computational complexity, which makes it well suited for large-scale network analysis. We further develop an LRC-based preprocessing method that effectively augments popular community detection algorithms. Through applications on multiple real-world datasets, including the NCAA football league network, the DBLP collaboration network, the Amazon product co-purchasing network, and the YouTube social network, we demonstrate the efficacy of our method in significantly improving the performance of various community detection algorithms.

Published in Transactions on Machine Learning Research (03/2025)
Lower Ricci Curvature for Efficient Community Detection
Yun Jin Park
wiimpark@hunc.coo eduu
Department of Biostatistics The University of North Carolina at Chagel Hill
Didong Li
didongli@unc.cm edu
Deportment Biostatistics The University of North Carolina at Chapel Hill
Reviewed on OpenReview: Attps: // openreview. net/ por/formm? id- EotuRII'M.
Abstract
This study introduces the Lower Ricci Curvature (LRC), a novel, scalable, and scale-free discrete curvature designed to enhance community detection in networks. Addressing the computational challenges posed by existing curvature-based methods, LRC offers a stream- lined approach with linear computational complexity, which makes it well suited for large- scale network analysis. We further develop an LRC-based preprocessing method that effec- tively augments popular community detection algorithms. Through applications on multiple real-world datasets, including the NCAA football league network, the DBLP collaboration network, the Amazon product co-purchasing network, and the YouTube social network, we demonstrate the efficacy our method in significantly improving the performance various community detection algorithms.
1 Introduction
In the modern era, the ubiquity of networks in various domains, from biological pathways (Koutrouli al. 2020) and social networks (Ji et al.) 2022) to technological and cosmic networks (De Regt et al., 2018): has fostered significant interest in the study of complex systems. These networks, characterized by nodes representing entities and edges denoting interactions, provide framework for understanding the intricate relationships and dynamics within these systems. Graph theory, applied to these network representations, has emerged as a vital tool for dissccting and intorpreting the structural and functional intricacies these interconnected systems (West et al. 2001
Community detection one of the most important aspects in the analysis of complex networks (Dey al. 2022). In these networks, communities represent subgroups of nodes (such as individuals, biological entities, devices) that are more densely interconnected among themselves than with the rest of the network. The identification of these communities can yield invaluable insights into the structure and dynamics of the system being studied. For instance, in social networks, communities can represent groups of people with shared interests or connections, revealing patterns social interactions and relationships (Bakhthemmat & Izadi 2021 In biological networks, such as those representing metabolic or protein-protein interaction pathways, community detcction can help identify functional modules clusters of interacting molocules, crucial for understanding biological processes and disease mechanisms (Tripathi al. 2019). Similarly, in technological networks, such as the internet or telecommunications networks, communities might consist of densely interconnected nodes or hubs that are critical for network functionality and resilience (Zhang et al. 2022 By discerning these communities, we can gain deeper understanding of not only the individual elements within the network, but also the overarching principles that govern their interact ions and collective behavior.
Community detection methods have evolved significantly address the diverse and complex structures of modern networks. Hierarchical Clustering (Fortunato) 2010 Hastie et al.) 2009). for instance, has been

---

Published in Transactions on Machine Learning Research (03/2025)
instrumental in identifying nested community structures by iteratively merging dividing groups based their similarity. The Girvan-Newman algorithm (Nwmman 2004 2006), notable for its edge-betweenness centrality approach, has contributed substantially to understanding modularity within networks. Similarly, Label Propagation algorithms (Raghavan et al.) 2007); recognized for their simplicity and speod, have been effective in detecting community structures large networks by allowing nodes to adopt the majority label of their neighbors. The Walktrap algorithm (Pons Latapy, (005) has gained recognition for its approach of using random walks to identify communities, based on the idea that short random walks tend to stay within the same community. This method is particularly adept at capturing the local community structure in large networks. The Leiden algorithm (Traag et al.) 2019), an improvement over the well-known Louvain method (Blondel et al. 2008), offers enhanced accuracy and resolution in detecting communities. It addresses some of the limitations of previous methods by refining the community boundaries and ensuring a more balanced distribution of community sizes. These methods, each with their unique approaches and strengths, have collectively advanced our understanding of network structures, contributing to fields ranging from sociological studies to biological network analysis.
A recent and significant development in network analysis is the discovery of correlation between discrete curvature and community detection (Sia et al. 2019), which underscored the potential of using curvature- based methods to enhance our understanding and identification of communities within complex networks. Network curvature, particularly discrete curvature, has emerged as a powerful tool in the realm of graph theory and network analysis. The concept, rooted in geometric analysis, involves adapting the notion of Ricci curvature (Ricci & Levi-Civita, 1900 Do Carmo & Flaherty Francis 1992), traditionally applied to smooth manifolds, to discrete networks. This adaptation has led to the development of various discrete curvature mcasures, cach offering unique insights into network properties.
which has been instrumental in studying transport efficiency and robustness in networks. It provides a measure of how the network deviates from a geometrically flat structure, offering insights into network connectivity and resilience. hno significant variant is the Forman Ricci Curvature (FRC, Forman (2003)) ), adapted from Riemannian geometry, which has been applied to analyze the shape and topological features of networks, proving useful in understanding the underlying structure of complex systems. The Balanced Forman Curva- ture (BFC, Topping et al. (2021)). refined version of the FRC, has been particularly effective in identifying bottleneck structures and critical connections within networks. This form of curvature is beneficial in ap- plications where understanding the flow or distribution within a network is crucial. These curvature-based approaches have opened new avenues in network analysis, offering a geometric perspective to complement traditional topological and ssatistical methods.
One of the key forms of discrete curvature is the Ollivier-Rie Ricci Curvature (ORC, Ollivier 2007
(a)
(b)
0.4
Ollivier Riccl Curvature
0.2
0.0
20-
0.0
0.4
Figure 1: (a) A toy simulated network with two communitios, with edges colored by ORC. (b) The histogram
of ORC, suggesting its potential in community detection.
2

---

Published in Transactions on Machine Learning Research (03/2025)
Although discrete curvature has found various applications in network analysis, such understanding in- ternet topology (Ni et al. 2015), differentiating cancer networks (Sandhu et al. 2015 and addressing oversquashing and oversmoothing problems in graph neural networks (Nguyen et al. 2023). ; its specific use in community detection remains relatively underexplored. Figure ! shows a toy network with two communi- ties. In this network, the edges connecting different communit lend have lower ORC values than those within community. This observation shows the potential of network curvatures in community detection. In relation to this observation, Sia et al. (2019) proposed to iteratively remove the edge with the smallest ORC and recalculating all edge ORCs until the network becomes disconnected, with each connected component identified a community. Similarly, Fesser et al. (2023) proposed another iterative algorithm to remove edges with augmented FRC above a threshold, until no edge curvature exceeds that threshold.
However, these approaches have several major drawbacks. First, the computational cost calculating ORC and augmented FRC of a single edge is high, scaled as O(n²) for ORC and O(n²) for augmented FRC, where n represents the number of nodes. This makes it prohibitively expensive for large scale such as the DBLP co-authorship network (n 317, 080); the Amazon product co-purchasing network (n 334, 863), and the YouTube social network (n 1, 134, 890, Yang & Leskovec (2012)). Second, the iterative nature of the algorithm introduces significant extra time inefficiencies. In the worst-casc scenario, up to O(m) itcrations might be required. Third, the methods, despite their innovative approach, can sometimes be too restrictive and may underperform compared to popular methods such as the Leiden algorithm.
To effectively tackle the challenges in community detection within large-scale networks, our study introduces novel curvature measure, the Lower Ricci Curvature (LRC), LRC is specifically designed for efficient computation, with linear computational complexity of O(n). This significantly reduces the computational burden compared to traditional curvature measures, making it highly suitable for large networks. In addition to its computational efficiency, we provide some theoretical analysis of LRC, particularly its connection to the Cheeger constant, a well-established concept in graph theory (Mohar 1989 which helps in understanding how LRC relates to the division of a network into communitics.
Building on the theoretical foundation of LRC, we have developed a preprocessing algorithm that utilizes LRC to improve existing community detection methods. This algorithm is designed to be suitable for a wide range of applications, due to its adaptability to different network structures and sizes and its compatibility with various community delection methods. We applied it to networks of diverse sizes, including both small- scale networks (NCAA football league network) and large-scale networks with mixed membership (the DBLP coauthorship network, the Amazon product co-purchasing network, and the YouTube social network). The results from these studies consistently demonstrate that our preprocessing step, based on the Lower Ricci Curvature, not only enhances the efficiency but also improves the accuracy of various established community detection methods.
Proofs, simulation results, and additional experimental details are provided in the Appendix.
2 Background
2.1 Community detection
Community detection in network analysis is essential for unraveling the intricate structures of networks. Communities are typically defined as subgroups of nodes with denser internal connections compared their external connections (Radicchi et al., 2004).. Understanding these communitics is vital reveal the underlying structural characteristics of networks and to classify nodes based on their interrelations (Fottunato & Hrie 2016).
While the Introduction briefly mentions various community detection algorithms, this subsection aims to delve deeper inlo their specific functionalities and contributions. The Girvan-Newman algorithm leverages edge betweenness centrality and hierarchical clustering to identify community structures (Newman & Girvan 2004). The Leiden algorithm, evolving from the Louvain method, focuses on optimizing enhancing the resolution and accuracy of detected communities (Blondel al., 2008 Traag et al. 2019). Other notable methods include Label Propagation, which relies on the diffusion of information (Raghavan
modularity, thereby
3

---

Published in Transactions on Machine Learning Research (03/2025)
et a..
2007 and Walktrap, which uses random walks to discern community structures (Pons & Latapy
2005
ego-based community detection (Egoo Leskovec & Meauley (2012), ) K-clique (Palla et al. 2005), Speaker- Listener Label Propagation Algorithm (SLPA, A.P.A.p Xie
Additionally, algorithms such as the Angel (Rossetti. 2020
jtt al. [2011] contribute diverse perspectives and techniques to community detection. Each of these methods brings unique strengths the analysis of network structures, addressing different aspects and challenges in identifying community patterns.
To evaluate the performance of these algorithms, criteria such as the Adjusted Rand Index (ART) and the Adjusted Mutual Information (AMI) are commonly used. ARI evaluates the agreement in node pair assignments between clustering results, offering a quantitative assessment of similarity (Rand 1971). AMI measures the similarity between different community detection results on the same dataset, providing insights into the amount of shared information (Vinh et al.) 2009). In our study, we utilize these criteria gange the improvements in community detection algorithins performance when incorporating our newly proposed LRC-based preprocessing step.
2.2 Discrete curvatures
Curvature, fundamental concept in mathematics, describes how curve deviates from straight line surface from being flat (Boothby 1986). In Riemannian geomelry, curvatures such Ricci curvature, provide insights into the unique geometry properties of different spaces, including volume changes along geodesics (Do Carmo & Flaherty Francis 1992). Historically, generalizing this concept to discrete objects, such as networks, presented a significant challenge. A pivotal moment in this endeavor came with the work of Forman (Forman 2003). who innovatively adapted curvature concepts to the discrete realm. This milestone opened the door for further exploration and application of curvatures in discrete spaces, including networks.
For presentational simplicity, in this paper, focus nodes and E is a set of edges, but the framework can be generalized to weighted graph in straightforward manner. Let (ij) be an edge connecting node i and node j, we denote the degree of i, i.c., the number of edges of node i, by ni, the number of shared neighbors of i,j, i.e., the number of triangles based on (ij), by my.. Under this framework, the Forman Ricci Curvature, or FRC, defined as follows:
unweighted graph G E); where V is set of
Definition 1 (Forman Ricci Curvature (FRC)) The FRC of edge (ij) is defined as
FRC(I)) 4 -4; n4 14:-10 nj 3na--
FRC evaluates the "structural support' an edge by presenting higher values to edges with more shared neighbors and lower-degrec endpoints, since they are more 'intogral' the network's structure. The com- pulational cost, for calculating FRCs for single edge is O(n). Following Forman's groundbreaking work Forman 2003), there has been surge of studies exploring and applying FRC, to various network structures. For example, Sreejith et al. (2016a) extends FRC from undirected to directed networks, and [Sreeith et al. 2016bb extends FRC to complex networks and explains its connection to continuous Ricci curvature.
However, its unbounded and scale-dependent nature, as well as its skewness toward negative values in various networks pose interpretational challenges (Sreejith et al. 2016b).. To address these issues, an improved version known as the Balanced Forman Curvature (BFC, Topping et al. (2021) was proposed:
Definition 2 (Balanced Forman Curvature (BFC)) The BFC of edge (ij) is defined as
2 + -2+2 BFC(i))
nij max(n;,
Nij + min(n,,n))
85, + 85,i
n4 n
"max max(n;, ny))'
where S1,j is the number of neighbors of node forming 4-cycle based at the edge (ij) without diagonals inside, 7max the maximal numbee of 4- 4-cycles based at edge (ij) traversing common node (see Topping
et al. 2021) for more delails).
4

---

Published in Transactions on Machine Learning Research (03/2025)
BFC rescales the contribution of shared neighbors and node degrees, making it bounded within the range [-2, 2]. This modification ensures that the curvature captures essential topological features, such as bottle- necks, more consistently. With this feature, BFC has been applied to identify the bottleneck structure in graphs, particularly for addressing the over-squashing phenomenon in graph ncural networks. However, its computational complexity of O(n²), limits its application to large-scale networks, mainly due to computa- tionally intensive terms $i,j and Thaxx which involves counting the number of squares based at nodes and under certain constraints (Topping et al. 2021).
Moreover, Ollivier made significant contributions by defining the Ricci curvature for networks through opti- mal transport and differential equations OOllivier 2007
Definition 3 (Ollivier-Ricci Curvature (ORC)) The ORC of edge (ij) is defined as
W1 (m,
ORC(
d(i,j)
where W1 is Wasserstein-1 distance, my is local probability measures at node i, defined as
(k(k) = n, (ik) E
(1)
0, (ik) $
and d)i,j) is the length of shortest path from node i to node j, also known as the gruph distance.
ORC quantifies the change in probability distributions across the neighborhoods of two nodes connected by edge. A larger ORC value indicates stronger cohesion between the two neighborhoods, while smaller or negative value suggests a bridge-like connection. This curvature has sparked wide array of follow- up research, further enriching the field of network analysis with these novel curvature based insights. For example, Lin & Yau (2010): Lin et al. (2011); Erbar & Maas (2012) : Bauer et al. (2013) have provided deep mathematical insights into the properties and implications of ORC in the context of graph theory and network geometry. [Tillos & Weber (2023) showed its connection to continuous Ricci curvature using random geometric graph sampled from a manifold. Notably, [Sia al. (2019) utilized ORC for community detection, itcratively removing the edge with the smallest ORC. However, its computational cost (O(n²) poses significant challenges, especially for iterative algorithms.
2.3 Stochastic Block Model (SBM)
To illustrate network curvatures in a simplified context, we consider the Stochastic Block Model (SBM) in this manuscript, basic yet versatile model used in network analysis (Holland et al. 1983). SBM is renowned for its ability to mimic community structures within networks. In this model, nodes are partitioned into K distinct communities, and connections between nodes are probabllisticall determined based on their community memberships.
Each node is assigned a community label 2; E (I....,K', KK, indicating its community membership. The block matrix B, K K symmetric matrix, a critical component of the SBM, dictating the probability of edge formation between nodes from communities. Specifically, Bu represents the probability of an edge existing between nodes from community & and community I. In SBM, the probability of an edge existing between any two nodes i and j follows a Bernoulli distribution, and is independent of other edges, as reflected in the adjacency matrix A E R
P(A:; = 1) = B
While a basic SBM might appear too simplistic for complex real-world data, its extensions, such as hi- crarchical SBM and mixed membership SBM, offer more nuanced representations. These models cater scenarios involving hierarchical community structures (Peixoto 2014) or nodes with memberships in multiple groups (Airoldi et al. 2008).
5

---

Published in Transactions on Machine Learning Research (03/2025)
3 Lower Ricci Curvature (LRC)
In this section, we introduce novel discrete curvature, the Lower Ricci Curvature (LRC), notably for its high performance in community detection and low computational complexity of O(z). We delve into the intuition behind defining LRC, and how these factors contribute to its computational efficiency and efficacy in community detection.
The LRC of edge (if) is defined as:
LRC(ij) 2 2 74 ng
Taj
Rij
2 2
max(n4; ng)
min min(n;, m3)"
Several key observations about LRC can be made. Firstly, the computation of LRC(i)) requires O(n), similar to FRC. Secondly, LRC is always within the range of [-2, 2), aligning with the bounds of BFC. Third, LRC is consistently less than or equal to BFC, with the difference, denoted as A(j)), defined as
84 + 8338
((ij)
BFC(i)) TRC((j) 0.
Vimx max (14, n))
In fact, BFC is further upper bounded by ORC (Topping et al. 2021 loading to the following proposition, which underlines why we term it lower Ricci curvalure.
Proposition For any edge (ij),
LRC(I)) S BFC( S ORC(i)).
This proposition motivales our first rationale for defining LRC. The computational bottleneck of BFC the term A, which requires O(n²) time. However, this leads two pertinent questions. First, is LRC effective in differentiating edges within and between communities? Second, does the term A significantly contribute to community detection, or is there a notable difference in A for edges within the same community versus those between different communities?
To further investigate these questions, we utilize an SBM-gencrated network as a toy example. Figure 2 presents a network with n = 60 nodes, divided evenly into two communities. Edges within communties have a higher probability of 0.8, while edges between communities are set at a lower probability of 0.05. The edges are color-coded based on their LRCs: higher LRCs are marked in yellow, while lower LRCs are marked in purple. This visual representation helps highlight that edges bridging different communtiies tend to have smaller LRC values compared to those within the same community. This example shows that LRC achieves computational efficiency by omitting the computationally expensive term A without sacrificing its ability to detect community structures.
The direct link between LRC and ORC less straightforward, which guides the second intuition behind the definition of LRC. The primary computational challenge in calculating ORC lies the Wasserstein-1 distance, also known the earth moving distance (Villani et al. 2009). A natural approach is to approximate this distance bound it from below, above, both. To effectively bound ORC, it is necessary to bound the Wasserstein distance, which involves complex calculations of the total cost of certain candidate transports (see Jost & Liu 2014 for more details). The bounds are established as follows:
2 n nj
2 Raj
nij S ORC(i)) max max(n,, ng} min(n,,
Thi
max maax(n;,n) (n)
Notably, the lower bound is preciscly the LRC, which connects back to Proposition 1 While it is technically leasible to use the upper bound to define a curvature, it has some drawback. First, the upper bound is always positive, which conflicts with the intuition that Ricci curvature can be positive (sphere), negative (hyperbolic space), or zero (hyperplanc). reflecting different gcometric propertics. Second, some theoretical support, as shown in the Corollary below, does not apply to this upper bound. Third, has some linitations distinguishing between different network structures. For example, if there is only one edge connecting

---

Published in Transactions on Machine Learning Research (03/2025)
(a)
(b)
(c)
120
140
WINE A CORVILERS
0.5
Lower- Ricci Curvature
100
120
0.0
100-
80
0.5
-1.0
40
40-
0.05
0.06
0.07
0.08
0.09
Figure 2: (a) A SBM-generated network with K = 2, B&g- 0.8, Ba 0.05 for k # with edges colored by LRC. (b) The histogram of LRC, suggesting its potential in community detection. (c) The histogram of A for within and across community edges, indicating that A may not significantly contribute to community detection.
two fully connected communities, then max[m..ng 0, which is same as any edge in a straight-line graph. Hence, we focus on the lower bound, i.e,, LRC.
As direct corollary of these inequalities, the following corollary establishes link between the bound of LRC and the diameter of the network, defined diam(G) suPi.eev d(i,j), where d represents the graph distance. This is also related to the Cheeger constant (Chung 1997.. measure indicative of the presence of communtty structure in the network.
Corollary 1 If there enists a > O such that LRC(ij) 2 a for any (ij) E E, then
1. (G
A 2 lig 2 q; where x first non-zero eigenvalue of the normalized graph Laplacian, also known 2
as the spectral gap, and he is the Cheeger constant.
The interpretation of this corollary is that a larger value a, suggests graph structure more akin a fully connected graph, hence a smaller diameter. Similarly, larger a correlates with higher Cheeger constant, indicating a more interconnected network with less pronounced separability into distinct community structures.
We conclude this section with Table to compare four curvatures: FRC, BFC, ORC, and LRC. The compu- tational complexity is the cost of calculating the curvatures for each edge. Scale-free means the curvature is independent of the network size characterized by n and m. Scale-free propertics are particularly important in the network analysis, as they ensure the applicability and consistency of curvature measures across networks of different sizes. This quality preferable it allows for meaningful comparisons (Sandhu al. 2015)) and generalizations across various network structures, from small-scale large-scale networks, without being biased by their size. FRC is not scale-free because its values grow unbounded in large networks due to its definition.
Among These curvatures, LRC stands out for its linear computational complexity and scale-free property, making versatile and efficient choice for network analysis. This blend of computational efficiency and scale-free nature makes LRC an idcal candidate for analyzing networks various contexts. While this paper primarily focuses on the practical applications of LRC, some discussion on its theoretical aspects, including concentration of ma and phase transitions in SBM, can be found in Appendix B and Appendix C.1

---

Published in Transactions on Machine Learning Research (03/2025)
Table 1: Comparison of four curvatures.
Curvature
Computational Complexity
Scale-Free
FRC
((n)
No
BFC
O(n")
Yes
ORC
O(n")
Yes
LRC
((n)
Yes
4 LRC-based preprocessing
As observed in Figure 2(b), the presence of community structures in networks often results in bimodal distribution of LRC values. This typically manifests itself as two distinct modes in the histogram of LRCs: a smaller mode corresponding to across-commmnty edges and a larger mode representing within-community edges. This observation underpins our proposed preprocessing step for community delection: removing edges with small LRC values below a specific threshold. This approach aims retain more atthn--commuity edges, thereby making the community structure more pronounced. The threshold determined by fitting Gaussian mixture model (GMM, Reynolds et al. (2009) to the histogram of LRCs, as outlined in the following algorithm.
Algorithm 1: LRC-based preprocessing algorithm for community detection
Input: Raw network data: G G= EV,
Output: Preprocessed network data. G' (V)
Calculate the LRC for all edges;
Fit Gaussian mixture model with two mixing component to LRCs, obtaining the estimate
Mx) Th ((;; M1, of) + 72 #2, oι), where f4 < μ22
Find the local minimum 3 = inf p(x);
Remove all edges with LRCs smaller than 3: E' = ((1) E E: LRC(1J) 2 $}
The workflow of our proposed method is illustrated in Figure discussod.
based on the network example previously
(b)
132
1.25
GHINE
1.50
Curenure
0.50
Figure 3: (a) A SBM-generated network with K = 2, B&g- = 0.8, Bu = 0.05 for k & L, with edges colored by LRC. (b) The histogram of LRC, with each bar colored by LRC. (c) The threshold 3 (the dotted vertical line) estimated by GMM. GMM1 the mixing component with a large mcan μ2, GMM2 is the mixing component with smaller mean in- (d) The processed network, exhibiting a more discernible community structure.
This toy example illustrates how our preprocessing step expected enhance the performance of existing community detection methods by clarifying the underlying community structures.

---

Published in Transactions on Machine Learning Research (03/2025)
Following the description of the underlying community structures, it is crucial to highlight the efficiency and scalability of the LRC--ased preprocessing method. The calculation of LRC itself requires O(n) time, and the subsequent edge removal step is a one-time, non-iterative process, This is in stark contrast to competitor methods that rely on iterative processes (Jost & Liu 2014 Sia et al. 2019), which can significantly increase computational time, especially for large networks that are increasingly common in various domains.
Crucially, this increase in efficiency does not compromise the accuracy of community detection. In the Ap- pendix, we provide the result of simulation study using SBM-generated networks to evaluate the effectiveness of LRC on community detection. In the following section, present empirical evidence showing how LRC-based preprocessing not only maintains, but often enhances the effectiveness of popular community de- tection algorithms,, even in complex network scenarios. This demonstrales the dual benefit of our approach: it streamlines computation while enriching the depth of network analysis.
While LRC preprocessing may seem similar to a denoising method (Yu et al. 2021 it not intended treat low-curvalure edges (e.g., bridges) as noise. Instead, these edges are considered meaningful structural features whose removal can enhance community detection. See the Appendix D for detailed discussion the distinction from denoising approaches.
5 Application
In this section, we evaluated the impact of our proposed LRC preprocessing method the performance of various community detection algorithms using four real-world datasets with known community structures. We begin our analysis with smaller network, the NCAA Football League Network, to demonstrate the impact of our preprocessing method in a more controlled setting. To this end, we compared the Adjusted Rand Index (ARI) and Adjusted Mutual Information (AMI) scores before and after applying our prepro- cessing technique with LRC, utilizing four representative community detection models: Label Propagation, Leiden, Girvan-Newman, and Walktrap. These models were chosen for their effectiveness and widespread use in community detection, noted in the cxisting litcrature (Fortunato & Hric 2016). In addition to the LRC-based preprocessing method, we also applied the preprocessing algorithı using BFC and FRC to further demonstrate the performance of curvature-basel preprocessing in broader framework. We did not include ORC in these experiments, due to its high computational complexity.
After evaluating the NCAA Football League Network, we extend our analysis to three larger-scale networks. These networks pose additional challenges, particularly in terms of computational efficiency. Moreover, they often exhibit mixed membership, where nodes can belong to multiple communities, diverging from the unique community structures seen in smaller and simpler networks like the NCAA dataset.
Given these differences, we shift our focus to algorithms better suited for these conditions. For larger net- works, we use Angel, Ego, K-clique, and Speaker-Listent Label Propagation Algorithm (SLPA). These replacements are due to the suitability of these algorithms in handling large-scale networks and their ca- pability to address mixed membership scenarios. In addition, since BFC requires a significant amount of computational time with a large memory size for calculating curvatures in large networks, we applied only FRC and LRC preprocessing on the three following networks.
Furthermore, since the ARI and AMI scores are less effective for evaluating community detection in networks with mixed memberships, we utilize the F1 score to evaluate community detection results. This is well- established metric in such scenarios because it combines the precision and recall of the delected communities to provide a balanced measure of a method's accuracy and is particularly useful in networks where a node can be part multiple communities (Hollocou et al. 2018
5.1 NCAA Football League Network
The NCAA Football League Network is a graph representing the NCAA Division I football game schedule in the year 2000 (Girvan & Newman 2002). There are a total of 115 nodes, each representing college football teams, and 613 edges, corresponding the regular season games played between these teams. Each node in the network is assigned to one of the 12 ground-truth conference groups Since teams tend to play more
9

---

Published in Transactions on Machine Learning Research (03/2025)
frequently within their own conference groups, each conference in the network clearly exhibits community structure. below rllustrates the performance improvement of various community detection algorithms through the application of our preprocessing method.
Table 2: Community detection algorithms evaluation for NCAA Football League network
Algorithms Leiden
Scores
Label Propagation
Walktrap
ARI: before
0.75
0.81
0.84
0.82
ARI: after BFC
0.90
0.90
0.84
0.90
ARI: after FRC
0.90
0.90
0.83
0.90
ARI: after LRC
0.90
0.90
0.84
0.90
AMI: before
0.83
0.86
0.87
0.86
AMI: after BFC
0.90
0.90
0.88
0.90
AMI: after FRC
0.90
0.90
0.87
0.90
AMI: after LRC
0.90
0.90
0.88
0.90
Complexity
((m)
O(nm)
((n"))
O(n)
The results clearly show an improvement in both ARI and AMI scores after applying our preprocessing method based on network curvatures, across all four community detection algorithms. Comparing the three curvalures, LRC-based processing achieved similar AMI and ARI compared to BFC and FRC-based pre- processing. Notably, the Label Propagation algorithm, which initially had the lowest ARI (0.75) and AMI (0.83), significantly improved to both 0.90, respectively, after preprocessing. This enhancement elevates it to one of the top-performing algorithms in this context. In fact, after preprocessing, all algorithms exhibit very similar scores, suggesting that our preprocessing method regardless of the type of curval ure simplifies the community detection problem by making the community structures more distinct and evident. This homogenization performance implics that, with effective preprocessing, the choice of community detoc- tion algorithm becomes less critical, as the clarified network structure facilitates more accurate community detection across different methods.
Importantly, the inclusion of computational complexity in our analysis (as shown in the last row of the table) provides further insight into the selection of an optimal algorithm. Algorithms such as Label Propagation and Walktrap, with their lower computational complexities of ((m) and O(n) respectively, become attractive options. This highlights another significant advantage of our preprocessing method it not only improves the accuracy of community detection, but also enhances overall efficiency by enabling the use faster algorithms without compromising on performance.
5.2 DBLP Collaboration Network
The DBLP Collaboration Network is graph that shows coauthorship relationships in the computer science bibliography between multiple researchers (Yang & Leskovee 2012). The network comprises 317,080 nodes representing researchers and 1,049,860 866 edges indicating a collaborative paper. The results, as shown in the table below, demonstrate that the LRC preprocessing method aids in detecting community structures more complex networks.
For methods in Table the traditional Big O notation for computational complexity not consistently available in the literature. Instead, we focus the actual runtime of each algorithm, providing more practical measure of efficiency in real-world applications. The 'Time: before' represents the runtime (in seconds) of each communily detection algorithm when applied directly to the raw network data, while 'Time: after" encompasses the total time, which includes calculating the curvature, identifying the threshold, removing odges basod on this threshold, and rerunning the same community detoction algorithm on the processed network. This approach ensures a fair comparison, as it accounts for all steps involved in our preprocessing method. It. important to note that do not claim method to be faster than the
10

---

Published in Transactions on Machine Learning Research (03/2025)
Table Community detection algorithms evaluation for DBLP network
Algorithms
Scores
Angel
Ego
K-clique
ST.PA
F1: before
0.284
0.317
0.276
0.211
Fl: after FRC
0.385
0.311
0.383
0.334
Fl: after LRC
0.452
0.386
0.420
0.371
Time: before
260.17
831.87
40.50
1024.12
Time: after FRC
168.03
122.03
85.03
549.03
Time: after LRC
180.39
184.88
111.60
2349.36
approach without preprocessing. Instead, the table shows that the preprocessing step has a minimal impact on the total computational time, given its linear complexity.
Table 3 reveals a notable improvement in the F1 scores for each algorithm after integrating our preprocessing method to DBLP collaboration network. Although preprocessing with FRC tends to increase the accuracy of community detection, preprocessing with LRC shows more significant improvement overall. Furthermore, this improvement in performance does not come at the cost of reduced efficiency; in fact, the Angel algorithm remonstrates increased processing speed post-preproeessing even with these additional preprocessing steps, highlighting the efficiency of our method complex network environments.
5.3 Amazon Product Co-purchasing Network
This network represents the co-purchasing patterns of products on Amazon Yang & Leskovec 2012). The nodes symbolize products, and the edges indicate co-purchasos by Amazon customers. The network includes 334,863 nodes and 925,872 edges. As with the previous datasets, the application of the LRC preprocessing method significantly enhanced the results of various community detection algorithms, illustrated in the table below.
Table Community detection algorithms evaluation for the Amazon network
Algorithms
Scores
Angel
Ego
K-clique
SLPA
Fl: before 0.368
0.371
0.387
0.345
F1: after FRC
0.375
0.374
0.394
0.351
Fl: after LRC
0.463
0.444
0.482
0.483
Time: before 159.52
1000.85
42.40
2380.61
Time: after FRC
160.59
112.59
67.59
810.59
Tine: after LRC
139.61
629.56
85.73
3911.19
In line with the results of the DBLP collaboration network, our method utilizing LRC significantly improved the performance of each community detection algorithm.
5.4 Tube Social Network
This datasct represents the social network on YouTube (Mislove et al. 2007), where nodes symbolize users, and edges indicate subscription between YouTube users. The network includes the total number of 1,134,890 nodes and 2,987, 624 edges. The results show that the implementatio atinnn of the LRC preprocessing method greatly improved the results of multiple community detection algorithms in line with prior datasets.
Table showcases the effectiveness of our preprocessing method using LRC in the YouTube social network. While the performance boost is apparent across all algorithms, the Ego and SLPA algorithms stand out for
11

---

Published in Transactions on Machine Learning Research (03/2025)
Table 5: Community detection algorithms evaluation for the YouTube network
Algorithms
Scores
Angel
Ego
K-clique
STPA
F1: before
0.063
0.223
0.066
0.093
Fl: after FRC
0.086
0.238
0.091
0.124
Fl: after LRC
0.282
0.445
0.216
0.429
Time: before 972.74
143.09
9029.98
117.23
Time: after FRC
392.30
131.30
1895.71
1974.30
Time: after LRC
67.84
129.63
131.75
218.29
their marked improvements in F1 scores. This result diverges slightly from other large networks, as K-clique is not the fastest method here. Nevertheless, our method consistently enhances the overall performance of community detection, particularly benefiting faster analysis methods.
In conchusion, curvature-aased preprocessing algorithm consistently improves community detection results on real-world datasets. In particular, our LRC preprocessing method demonstrates its strength on large complex networks. Across all three large networks analyzed DBLP, Amazon, and YouTube our LRC preprocessing method consistently enables at least community detection algorithm to achieve the best near-best performance scores, while maintaining impressive efficiency with runtimes under 200 seconds. For instance, the Angel algorithm for the DBLP network, K-clique for the Amazon network, and Ego for the YouTube network each emerged as lop performers in their respective datasets. This is particularly noteworthy given the substantial size of these networks. Such results underscore the exceptional effectiveness and efficiency of our LRC preprocessing approach in handling complex, large-scale network data, making it a highly valuable tool in the field of network analysis. Moreover, the LRC preprocessing could be applied any community detection algorithm. In particular, fast community detection methods, such as Wang et al. (2020), can be combined with LRC preprocessing for efficient and effective community detections.
6 Discussion and future work
In this work, we have focused on network curvature and its applications in community detection. Our key contribution is the proposal of the Lower Ricci Curvature (LRC), a scalable and scale-free discrete curvature designed specifically for network analysis. Alongside this, we have developed an LRC-based preprocessing method that has shown potential in enhancing the performance of established community detection methods. This assertion is backed by multiple real-world applications, including analyses of large-scale networks such Amazon, DBLP, and YouTube. Moreover, the LRC framework is adaptable and can be straightforwardly extended to weighted networks. Looking forward, several promising directions for extending this research are evident.
Extension to directed graphs: Extending LRC to directed graphs opens up numerous possibilities for analysis various fields. Directed graphs are crucial in representing asymmetric relationships, such as citation networks academia, where the dircctionality citations plays a significant role (Newman 2001) or in web link structures where the direction of links implies flow of information (Kleinberg al. 1999). Adapting LRC to account for the directionality in such networks can provide more nuanced insights into their structural and community dynamics.
Hypergraphs, which involve higher-order interactions beyond pairwise con- nections, present an exciting frontier. For instance, in collaborative environments like multi-author scientific publications (Taramasco al. 2010) or gene co-cxpression [Tran] 2012), interactions are inherently multi- dimensional. Extending LRC to hypergraphs could yield a deeper understanding of these complex relational structures and the underlying community formations.
Application to hypergraphs:
12

---

Published in Transactions on Machine Learning Research (03/2025)
Deeper theoretical investigation of LRC: A systematic study of network curvature's thcoretical prop- erties under different models, including but not limited to SBM, is an important direction for future work. Based on the theoretical insights, exploring alternative curvature definitions and analyzing their effective- ness under different model settings, could further improve the performance curvature- based methods in community detection.
7
Acknowledgments
YJP was supported by NIH grant T32 CA106209; DL was supported by NIH grants P30 ES010126, Ro1 HL149683, R01 HL173044, RO1 LM014407, R56 LM013784, UM1 TR004406.
References
Emmanuel Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1-88 86, 2018.
Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall. Exact recovery in the stochastic block model, 2014. URL btttpp:://axxv..rr//bbbss
3267
Edo M Airoldi, David Blei, Stephen Fienberg, and Eric Xing, Mixed membership stochastic block models. Advances in neural information processing systems, 21, 2008.
Ali Bakhthemmat and Mohammad Izadi. Communities detection for advertising by futuristic greedy method with clustering approach. Big Dala, 9(1):22 40, 2021.
Frank Bauer, Bobo Hua, Jürgen Jost, and Shiping Liu. Generalized Ricci curvature and the geometry of graphs. Actes des rencontres du CIRM, 3(1):69-77) 78, 2013.
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Ftienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008, 2008.
William M Boothby. An introduction to differentiable manifolds and Riemannion geometry. Academic press, 1986.
Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Robin De Regt, Stepan Apunevych, Christian Von Ferber, Yu Holovatch, and Bohdan Novosyadlyj. Network analysis the cosmos galaxy field. Monthly Notices of the Royal Astronomical Society, 477(4):4738 4748, 2018.
Asim K Dey, Yahui Tian, and Yulia R Gel. Community detection in complex networks: From statistical foundations to data science applications. Wiley Interdisciplinary Reviews: Computational Statistics, 14 (2)e11566 2022.
Manfredo Perdigao Do Carmo and Flaherty Francis. Riemannian geometry, volume 6. Springer, 1992.
Matthias Erbar and Jan Maas. Ricci curvature of finite Markov chains via convexity of the entropy. Archive for Rational Mechanics and Analysis, 106:997-1038, 2012.
Lukas Fesser, Sergio Serrano de Haro Iváñez, Karel Devriendt, Melanie Weber, and Renaud Lambiotte. Augmentations of Forman's 's Ricci curvature and their applications in community detection. orXiv preprint arXiv:2306.00 064 74, 2023.
Forman. Bochner's method for cell complexes and combinatorial Rieci curvature. Discrele & Computational Geometry, 29:323-379 374, 2003.
Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5):75 1774, 2010.
13

---

Published in Transactions on Machine Learning Research (03/2025)
Santo Fortunato and Darko Hric. Community detection in networks: A user guide. Physics reports, 659: 1-44, 2016.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national acodemy of sciences, (0(12):78217722) 2002.
Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic block models: First steps. Social networks, 5(2):109 137, 1983.
Alexandre Hollocou, Thomas Bonald, and Marc Lelarge. Multiple local community detection. ACM SIG- METRICS Performance Evaluation Review, 45(3):76 83, 2018.
Pengsheng Ji, Jiashun Jin, Zheng Tracy Ke, and Wanshan Li. Co-citation and co-authorship networks of statisticians, Journel of Business & Economic Statistics, 40(2):469-45) 485, 2022.
Jürgen Jost and Shiping Liu. Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs. Discrete & Computational Geometry, (2):3000 322, 2014.
Jon M Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. The web as a graph: Measurements, models, and methods. In Computing and Combinatorics: 5th Annual International Conference, COCOON'99 Tokyo, Japan, July 26 28, 1999 Proceedings 5, pp. 1 1-17. Springer, 1999.
Mikaela Koutrouli, Evangelos Karatzas, David Paez- teez-ospino, and Georgios A Pavlopoulos. A guide to conquer the biological network era using graph theory. Frontiers in bioengineering and biotechnology, 8:34, 2020.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. Advances in neural information processing systems, 25, 2012.
Yong Lin and Shing- Shing-Tung Yau. Ricci curvature and eigenvalue estimate on locally finite graphs. Mathematical research lellers, 17(2):343 356, 2010.
Yong Lin, Linyuan Lu, and Shing- Tung Yau. Ricci curvature of graphs. Tohoku Mathematical Journal, Second Series, (4):6600 (/)6660-627, 2011.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang, Learn- ing to drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM international conference on web search and data mining, pp. 779 787, 2021.
Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. Mea- surement and Analysis of Online Social Networks. In Proceedings of the 5th ACM/Usende Internet Mea- surement Conference (IMC'07), San Diego, CA, October 2007.
Bojan Mohar. Isoperimetric numbers of graphs. Journal of combinatorial theory, Series B, 47 1989.
Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency threshokds for the planted bisection model. Tn Proceedings of the serty-seventh annual ACM symposium on Theory of computing, pp. 69 75, 2015.
Mark EJ Newman. The structure of scientific collaboration networks. Proceedings of the national academy of sciences, 98(2):404-409, 2001.
Mark EJ Newman. Fast algorithm for detecting community structure in networks. Physical review E, 69(6): 066133, 2004.
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):8577-8588 2006.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113, 2004.
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using Ollivier-Ricci curvature. In International Conference on Machine Learning, pp. 25956-2555 25979. PMLR, 2023.
Chien-Chun Ni, Yu- Yao Lin, Jie Gao, Xianfeng David Gu, and Emil Saucan. Ricci curvature of the internet topology. In 2015 IEEE conference on computer communications (INFOCOM), pp- 2758-22 7768- IEEE, 2015.
Yann Ollivier. Ricci curvature of metric spaces. Comples Rendus Molhemalique, 345(11):643 646, 2007.
Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Viesek. Uncovering the overlapping community struc- ture of complex networks in nature and society, nature, 435(7043):814 818-818 2005.
Tiago P Peixoto. Hicrarchical block structures and high-rcsolution model selection in large networks. Physical Review X, 4(1)00110 2014.
Pascal Pons and Matthieu Latapy. Computing communities in large networks using random walks. In Com- puter and Information Sciences-ISCIS 2005: 20th International Symposium, Istanbul, Turkey, October 26-28, 2005. Proceedings 20, pp. 284 293. Springer, 2005.
Filippo Radicchi, Claudio Castellano, Foderico Cecconi, Vittorio Loreto, and Domenico Parisi. Defining and identifying communities in networks. Proceedings of the national academy of sciences, 101(9):2688-666) 2004.
Usha Nandini Raghavan, Rćka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3):036106, 2007.
William M Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, 66(336):846 850, 1971.
Douglas Reynolds et al. Gaussian mixture models. Encyclopedia of biometrics, (6596666))3 2009.
MMG Ricci and Tullio Levi-Civita. Méthodes de calcul différenticl absolu et leurs applications. Mathema- lische Annalen, 54(1-2):125 201, 1900.
Giulio Rossetti. Angel: efficient, and effective, node-centric community discovery static and dynamic networks. Applied Network Science, 5(1):26, 2020.
Giulio Rossetti, Letizia Milli, and Rémy Cazabet. Cdlib: python library to extract, compare and evaluate communities from complex networks. Applied Network Science, 4(1):1-26, 2019.
Romeil Sandhu, Tryphon Georgion, Ed Reznik, Liangiia Zhu, Ivan Kolesov, Yasin Senbabaoglı, and Allen Tannenbaum. Graph curvature for differentiating cancer networks. Scientific reports, 5(1):12323, 2015.
Jayson Sia, Edmond Jonekheere, and Paul Bogdan. Ollivie-RRicci curvaturo-based method to community detection in complex networks. Scientific reports, 9(1):9800, 2019.
RP Sreejith, Jürgen Jost, Emil Saucan, and Areejit Samal. Forman curvature for directed networks. arXiv preprint arXiv:1605.0 04662, 2016a.
RP Sreejith, Karthikeyan Mohanraj, Jürgen Jost, Emil Saucan, and Areejit Samal. Forman curvature for complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2016(6):063206 2016b.
Carla Taramasco, Jean- Cointet, and Camille Roth. Academic team formation evolving hyper- graphs. Sciendomelrics, 85(3):721-74)) 2010.
15

---

Published in Transactions on Machine Learning Research (03/2025)
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. ar preprinl arXiv:2111.14522 2021.
Vincent A Traag, Ludo Waltman, and Nees Jan Van Eck. From Louvain to Leiden: guaranteeing well- connected communities. Scientific reports, 9(1):5233, 2019.
Loc Tran. Hypergraph and protein function prediction with gene expression data. orXiv preprint arXi::1222.00 2012.
Nicolas Garcia Trillos and Melanic Weber. Continuum limits of ollivier's ricci curvature on data clouds: pointwise consistency and global lower bounds. arXiv preprint Xiiu:2307.02375 2023.
Beethika Tripathi, Srinivasan Parthasarathy, Himanshu Sinha, Karthik Raman, and Balaraman Ravindran.
Adapting community detection algorithms for disease module identification in heterogeneous biological networks. Frontiers in genetics, 10:164, 2019.
Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information thcoretic measures for clusterings compar- ison: is a correction for chance necessary? In Proceedings of the 26th annual international conference on machine learning, pp.
2009.
Peng Wang, Zirui Zhou, and Anthony Man-Cho So. A nearly-linear time algorithm for exact community recovery in stochastic block model. In International Conference on Machine Learning, pp. 10126-10133 PMLR, 2020.
Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.
Jierui Xie, Boleslaw K Szymanski, and Xiaoming Liu. Sipa: Uncovering overlapping communities in social networks via speaker-listener interaction dynamic process. In 2011 iece 11th international conference dala mining workshops, pp. 344 349. IEEE, 2011.
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Dala Semanlics, pp. 1 1-8, 2012.
Jiating Yu, Jiacheng Leng, and Ling- Yun Wu. Network refinement: unified framework for enhancing signal or removing noise of networks. arXiv preprint arXiv:21000 109.09119,,,.1111111111111111111 2021.
Shuzhuang Zhang, Yaning Zhang, Min Zhou, and Lizhi Peng. Community detection based on similarities of communication behavior in ip networks. Journal of Ambient Intelligence and Humanized Compuling, (3):1451-1461, 2022.
Appendix
A Proof of Proposition and Corollary 1
LRC BFC directly follows from definition, as BFC -FC-LRC- = 2.0. 0. The inequality BFC < ORC is derived
from Theorem in 'Topping al. (2021). Corollary [ is direct consequence of Proposition combined
with Corollary 3 and Proposition from Topping et al. 2022
Concentration for ni under SBM B
In this section, we aim to compute the probability of all within-commuiity ni values greater than all across-community ni values in simple case of an SBM with two communities, each of size n:
min Ewiihin
within ni
max Eacross
BCTOSS
16

---

Published in Transactions on Machine Learning Research (03/2025)
We first calculate the expected values of ny separately for within-community and across-community edges. For nodes i,j in the same communily:
m within] (n - -2)p + =np2
For nodes j.j in different communities:
E El across] = 2(n 1)p122.
Using Chernoff bounds,
e ElInn
Pr (mg within < (1 - (1))))[[n () S exp
2
Applying the union bound, we have
enInn prithin
Pr (V(i,)) within ni
within 2 (1 c) mn withhul) 2 1 4n cxp
2
Similarly, for across-community edges, using Chernoff bounds,
2 2n acaoos
Pr (1) across
acrooss) S exp (1 ([+e)B
3
Using the union bound,
e
across sj
Pr (v(i,)) E across, nij
across < (1 + E) (e 2 4n² exp
To ensure perfect recovery, we set to ensure non-overlap between within-community and across-community bounds:
(1 E) (iiitiiiinn > (1+ in peross]
Substitute the expectations:
()(( - 2)r + np3) > (1 + c2( 1)p1P2).
Solving for e:
(n - 2)pp + np3 2(n 1)P1P2 <<
(n 2) + nr2 + 2(n 1)p122
To create safety margin, we sel:
(n 2)p np3 2nn 1 1)p1P2
nn 2)p + np + 2(n 1)pı22
Substitute this into the union bounds. For withinncommmnity edges:
within (1 E)nnntthinn) 4n² exp (- 2((n ([ 2)p + npz))
Pr (3(r,)) within, my
For across-community edges:
22 - 1)p1p2)
Pr (3(i,)) across, nij acTOsS
> + e) arTross) < 4n² exp
The total failure probability is:
Pr(Failure) S 4n exp ( ((n - 2)p + npp)
22(2n 1)p1P22
+ 4n2 exp
2
3
17

---

Published in Transactions on Machine Learning Research (03/2025)
in-2)p +ori++ngn +np -2( 12 into both terms:
Substitute c = 2 (n-2)p; 2)p mp: +2 P)
(1 2)př + np3 - 2(n 1)p1p2)
Pr([ailure) S 4n² exp
((n - 2)pp / + nD²)
[[((n 2)pp + mp3 + 2(n 1)p1p2)
(nn (- (n-2)ppf (T 12 ((n - 2)r mp3 2(n 1)p1p2)
+ npp - 2(n 1)p)p2))
(2(n - 1ippps)
+4n² exp
As - 20, both terms decay exponentially, ensuring:
Pr(Failure) -> 0.
However, these calculations are specific to ny and do not fully extend to LRC, which involves additional dependencies on n, and nj. Rigorous analysis of LRC under SBM requires further investigation, as it introduces additional complexity. A systematic study of network curvature's theoretical properties under different models, including but not limited to SBM, is left as future work.
C
Simulation
C.1 Phase transition
As measure of the performance of LRC preprocessing method, we conducted experiments lesting recovery performance near exact recovery threshold. Phase transition in recovery performance has been widely used as a metric to evaluate the performance numerous community detection algorithms (Abbel 2018). Exact recovery threshold indicates thcoretical conditions for SBM models where recovery of true community mem- bership with probability - o(1) is possible. The theorem for exact recovery in symmetric SBM (SSBM) is as follows.
Theorem Abbe et al. 2014; Mossel et al. 2015) Exact recovery in SSBM( a log logg) is solvable and efficiently if Va vbl= > /2 and unsolvable if Va vbl < 22.
n n
In the above theorem, SSBM(n, a logn blogg) denotes a symmetric SBM with total n nodes where a logn a is cothin-commmnity connection probability and 6 blng is across-community connection probability. For the experiment, we chose n = 100, ranging from O to 30 with increments 1, and b ranging from 0 to 10 with increments 1. For each combination of a and b, we generated 100 SSBMs and computed the mean AMI or mean ARI. The theoretical exact recovery boundary, Va - vb = v2 is plotted in red for each plot for better comparison. For community detection algorithms, we chose spectral clustering and Leiden algorithms as representatives. The resulting heatmaps of ARI and AMI are provided in Figure 4 and Figure 5 Clearly, LRC preprocessing method improves the performance of both spectral clustering and Leiden algorithm, but still respect the theoretical recovery boundary.
solrre UKC Preprocesiing
All After JRC Prepocess
AP Before LAC Preprccesiing
AMI After LRC Propocessiro
35
Figure 4: Phase transition in spectral clustering.
18

---

Published in Transactions on Machine Learning Research (03/2025)
bufore UBC Preprscessingg
ARl Aftr JCC Treprocas
AM Sefore LSC Progesseaiing
Afte UBC Proprocessing
8
13-
30
3-
12
Figure 5: Phase transition in Leiden algorithm.
C.2 Three additional scores
To access the effectiveness of LRC in community detection, we conducted simulations using SBM-generated networks. For a pair of edge probability within the community p1 and edge probability across the community p2 (with p2 < pi), we generate 100 replicates of the graph, each with n 100 nodes. We evaluated three distinct scores, motivated by our proposed preprocessing method, to compare the performance of LRC against three other existing curvatures. The results are visually represented through heat maps, with the x-axis representing Pl, the y-axis representing P2, and the color indicating the score.
Proportion of Perfect Separation (PPS). The first score we considered is the Proportion of Perfect Separation. For each graph replicate, we calculated the minimum curvature value among within-community edges and the maximum curvature value among across-community edges. A situation where the min- imum within-community curvature exceeds the maximum acrosscommmuitty curvature indicates perfect separation of within and across community edges. This implies that our preprocessing would remove all across-community edges while retaining all within-community odges, cnabling effective community detection by any reasonable method processi.....g. Mathematically, PPS is the proportion of networks satislying inf (.)) IRC(ij)= 2 SuP(s)eE,,, LRC(ij). The score ranges between 0 and 1, with higher values indicating better performance.
The diagonal heat maps in Figure 6 depict the extent of separation between within-communite and across- community curvature distributions. A redder hue indicates a higher degree of separation. These maps suggest that all the four curvatures, including LRC, effectively differentiate community structures across a variety of P1, P2 pairs. The off-diagonal heat maps in the lower triangle compare the performance of each curvature with others (red for superior performance, blue for inferior), with a raw scale of 1]. The upper triangle heat maps also compare curvature performances, but with normalized ranges to amplify differences. Overall, LRC shows comparable performance in PPS compared to other curvatures.
Average within-community Edge Removal Ratio (AER) The second score, AER, provides softer evaluation compared to PPS. While PPS focuses on perfect scparation, AER quantifics the extent to which within-community edges might be incorrectly removed when aiming to eliminate all across-community edges. This score particularly insightful, as accounts for the potential drawback of our preprocessing method in mistakenly removing valuable communico connections.
Mathematically, AER is defined the ratio of the number of wilhin-community edges, whose LRC values are smaller than the maximum LRC value of across-community edges, to the total number of within-commmiity edges. In formula terms, AER is given by the proportion
AER (()) ( E, 2j LRC(U)) < Si LRCIEE
K(() E E, = 2
A score of indicates ideal performance (no within-communie community edges are incorrectly removed), aligning with PPS of 1. Conversely, an AER of 1 implies the extreme scenario where all edges are erroneously removed.
19

---

Published in Transactions on Machine Learning Research (03/2025)
5.5
122
0001
-622
-656
-10
2.46
1.2
8
8.30
6.48
623
-003
--2
LAC 15C
OSC TRC
TRC
FSC. DTC
130
6.50
1.25
-656
-6.56
-6.5
-8.95
-3.00
-100
-3.00
-02
2.50
3.00
1.00
1.00
LAC
3.75
Figure 6: Comparison heat map for PPS.
Figure 7 presents the heat map of AER scores, organized similarly to the PPS heat map. The diagonal panels show the AER score for each curvature, while the off off-iiaonal panels compare the performance of different curvatures using the AER score. A visualization these heat maps can provide insights into how effectively each curvature avoids the unintended removal of within-community edges, which is crucial for maintaining the integrity of the community structure during preprocessing.
Average overlapping percentiles AOP, The third score, AOP, is designed to quantify the extent of overlap between the curvature distributions of within-community and across-communigg edges in a more symmetric manner. This score captures the degree to which these two distributions intermingle, providing curvature in distinguishing community structures.
a muanced view of the effectiveness
Mathematically, AOP is calculated as follows: For each replicate graph, we determine the percentile of the minimum wit within--ommuiity LRC value within the distribution of across-community LRR values. We then
20

---

Published in Transactions on Machine Learning Research (03/2025)
5.5
UAC-
100
13
1.0
-622
-12
-656
-66
-05
2.66
0.2
3.30
1.48
623
-44
-E6
LAC 15C
OSC TRC
TRC
FSC. DTC
0.0
0.75
0.8
3.0
6.50
8.5
1.25
3.3
-6.6
-6.56
-6.6
-3.00
-1000
-3.00
2.50
3.00
1.00
1.0
LAC
3.75
-2.00
EX:3
Figure 7: Comparison heat map for AER
calculate one minus the percentile of the maximum across- across-comminn community LRC value within the distribution of within-community LRC values. The AOP score is the sum of these two quantities. Formally, it can be expressed as:
AOP PintaneR, (LLCC()): (1)) E, 233) +1 11111amppae Papranne.etts ((LCC())) (17) E E, 273)
where P.A is the a-th percentile of set A.
In the ideal scenario where there is no overlap, the first percentile would be (indicating the minimum within- community LRC is at the highest end of the ccross-communt distribution), and the second percentile would also be 0 (indicating the maximum across-commnity LRC is at the lowest end of the within-commmity distribution), resulting in an AOP score of Conversely, in the worst-case scenario where there complete overlap, the AOP score becomes O. Figure displays the heat map visualization of AOP scores, arranged
21

---

Published in Transactions on Machine Learning Research (03/2025)
1.5
BTC
1.5
1.8
110
0.0
-42
2523 0233 323338
253 0333
1.00
23
422
4.35
-05
-328
9335
-158
933593355
UKC
0.22
-0.0
-0.8
160
.22
LIC BFC
O4C BFC
SFC
6.6
6.25
005
+0.00
101
22 2022
-1.0
-30
Figure 8: Comparison heat map for AOP.
similarly to the previous scores. The diagonal panels show the AOP for each curvature, while the off-diagonal panels compare different curvatures using the AOP measure. This visualization aids in understanding the extent which each curvature can differentiate community structures by evaluating the overlapping of curvature distributions.
In summarizing the evaluations conducted using PPS, AER, and AOP, observe that the four curvatures LRC, FRC, BFC, and ORC exhibit comparable performance in community detection. None of the curvatures consistently outperforms the others across all metrics and all pairs of Pi, P2, indicating a balanced landscape of effectiveness.
However, when considering computational efficiency, LRC and FRC emerge as the fastest, both offering O(n) complexity. The crucial difference is that FRC is not scale-free, but LRC boasts this advantageous property, making it particularly suitable for analyzing large-scale networks where scalability is key. This distinction
22

---

Published in Transactions on Machine Learning Research (03/2025)
positions LRC an ideal candidate for proposed preprocessing method. Nevertheless, it is important to note that if specific scenarios requirements strongly favor other curvatures, our preprocessing approach remains adaptable and can be effectively applied in a broader context.
D Comparison with network denoising algorithms
Network denoising is a process that aims to remove erroneous noisy edges to reveal its underlying struc- ture et al.) 2021 Yu et al. 2021). However, the LRC preprocessing step is not intended to treat bridges (odges with low curvature) as noise. Instead, we are identifying edges that has informative signals that, when removed, improve the performance of community detection by making community structures more distinct. To compare denoising method with our preprocessing method, we implemented the NR method by Yu al. (2021) and applied it to the NCAA football network dataset. The results are included in the Table We observe that the AMI and ARI scores after NR denoising lower than those obtained without any preprocessing for all four community delection methods considered. This suggests that while NR is general-purpose denoising method, our LRC-based preprocessing is specifically tailored to enhance community detection performance.
Table 6: Community detection algorithms evaluation for NCAA Football League network
Algorithms
Scores
Label Propagation
Leiden
Walktrap
ARI: before
0.75
0.81
0.84
0.82
ARI: after LRC
0.90
0.90
0.84
0.90
ARI: after NR
0.40
0.47
0.00
0.57
AMI: before
0.83
0.86
0.87
0.86
AMI: after LRC
0.90
0.90
0.88
0.90
AMI: after NR
0.73
0.67
0.01
0.76
E Additional experimental details
E.1 Hyperparameters for community detection
All algorithms implemented in this paper are from Python package CDlib (Rossetti al. hyperparameters are as follows:
2019). The
1. NCAA Football League network
Label Propagation: NA.
Leiden:
Initial membership None, weights= None.
Girvan-Newman: Level = 10.
Walktrap: NA.
DBLP collaboration network
Angel: Threshold = 0.5, minimum community size 3.
Ego-networks: Level 1.
K-clique: K 3.
SLPA: 20,r 0.1.
3. Amazon product co- co-purchasing network
Angel: Threshold 0.5, minimum community size 3.
23

---

Published in Transactions on Machine Learning Research (03/2025)
Ego-networks: Level 1. K-clique: K- 3.
t 20, 0.1.
4. YouTube social network
Angel Threshold = 0.5, minimum community size 3.
Ego-networks Level = 1.
K-clique K
SLPA 20, 0.1.
E.2
Code and data availability
All codes can be found in https://githhb.. httttprr//gttthh...ooo/rrayuuy/p com////rrkyjjjui//oooriiiiccorrr
The lour real datasets used in this paper can be downloaded in the following websites:
NCAA Football League network: htttps//uebsites. umiuhmmihhh.mm... www.:..........cc..... /ataeacaa/mmme/ under "Ameri- can College football". The graph provided in the Graph Modeling Language (.gml) format.
2. DBLP collaboration network: sttp:://snap.staaforrrs wdw/data/coaaooeo DBLP html This graph is represented as NetworkX objects, provided by the CDlib Python package.
3. Amazon product co-purchasing network: attps:///anap.stanfort edu/dataaccommmmzoo html This graph is represented as NetworkX objects, provided by the CDlib Python package.
YouTube social network: https://saap.stanfor..oo hotii///ddddaaaaooommaaaa Youtube hhtmll This graph is represented as NetworkX objects, provided by the CDlib Python package.
24


Reviews:
[{"review_id": "9BxILNXFpO", "reviewer": "Reviewer_GeSG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1.) The proposed notion of ``curvature'' is more efficiently computable than previously introduced notions.\n\n2.) The proposed notion of curvature is related to graph structural properties, such as the Laplacian spectral gap, that are associated with cut sizes in graphs.\n\n3.) For several example datasets, either running time, accuracy, or both are improved by the use of LRC.\n\nWeaknesses:\n\n1.) The theoretical analysis seems to be a little trivial.  Furthermore, it misses some low-hanging fruit: it is very easy to give a high-probability asymptotic expression for the lower Ricci curvature of edges in the stochastic block model, under the regime that is covered by experiments.  This can be used to show that with probability $1-o(1)$, ground-truth community memberships can be recovered exactly.  I feel that this direction should be pursued for completeness.  The crux of the analysis is to first calculate the expected value of $n_{i,j}$ and $n_i$, then show that these are both well-concentrated around their expected values (using a Chernoff bound).  A union bound then allows one to conclude that with probability $1-o(1)$, $n_{i,j}$ and $n_i$ are uniformly close to their expectations (more specifically, $n_{i,j} = \\mathbb{E}[n_{i,j}]\\cdot (1 + o(1))$ and $n_i = \\mathbb{E}[n_i] \\cdot (1 + o(1))$), for all vertices $i, j$.  The remainder of the analysis plugs these approximations into the definition of the LRC and then simplifies. \n\n2.) The experiments on stochastic block models do not cover challenging cases of community detection near the exact recovery threshold.  See https://www.jmlr.org/papers/volume18/16-480/16-480.pdf and surrounding works for details.  Indeed, away from this threshold, rather trivial community detection algorithms recover ground-truth community memberships with probability $1-o(1)$.  I feel that the authors should cite this and surrounding work and should additionally perform experiments using SBMs with parameters near the exact recovery threshold.\n\n3.) It would be useful to see experiments using alternative definitions of curvature -- for example, the authors mention $\\frac{n_{i,j}}{\\max \\{n_i,n_j\\}}$.  The reason that I think this would be useful is that one can use this alternative notion to perform exact community recovery in the SBM in the regime that the authors have empirically analyzed.  Thus, I fear that the proposed curvature notion is rather arbitrary.\n\n4.) Essentially, calculation of LRCs can itself be viewed as the basis of a community detection algorithm that partitions edges into between-community and within-community subsets, with an implicit confidence measure.  The preprocessing step simply discards the low-confidence edges.  One could view this as a denoising procedure (which is not really necessary in the SBM case for the parameter regime that the authors study).  If this is the case, then I feel that there may be some relevant work to which the authors should compare (e.g., https://www.sciencedirect.com/science/article/abs/pii/S0378437123002364).\n\n5.) It seems like the wall clock running time results for some datasets are not very good.  For instance, the running times in Table 4 seem to indicate that for three out of the four considered algorithms, the use of LRC significantly increased running time compared to the use of FRC and even, in two cases, compared to no preprocessing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a measure of ``curvature'' on graphs that is less computationally intensive than previously used notions of curvature.  It then uses this in a preprocessing algorithm to improve the accuracy of existing community detection methods.  Experiments are performed on stochastic block models as well as various real networks with known ground-truth communities.  Connections are drawn to other graph structural parameters, such as the Laplacian spectral gap and the diameter.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.) I feel that addressing weaknesses 1-4 is important for strengthening the paper.  However, a faithful reading of the acceptance criteria for this journal leads me to conclude that I cannot justify rejection the basis of these weaknesses.\n\nRegarding weakness 5, I am not really certain that it can be fixed, but perhaps the authors can comment on it.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ityOHEe40A", "reviewer": "Reviewer_N1VX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I am quite positive about this work: the problem being studied is quite important as meaningful graph curvature measures are known to not scale well, the text is very well written and very clear, and the numerical experiments are convincing. I just have a few questions/remarks that I would like the authors to address (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this article, the authors propose a new type of measure for quantifying the curvature in networks, called the Lower Ricci curvature (LRC). Compared to other measures of curvatures, such as the Ollivier-Ricci curvature (ORC), the Forman-Ricci curvature (FRC), or its balanced version (BFC), the LRC enjoy several good properties: it captures well curvature information in the context of community detection (as demonstrated by its theoretical links with the diameter, Cheeger constant, and graph Laplacian spectrum), while being much faster to compute than its competitors (as its complexity is linear in the number of graph nodes and edges), making it highly scalable. Empirical evidence is demonstrated on large networks, where it is shown that an LRC-based edge pruning strategy results in significant improvements for most community detection methods, while keeping a small running time.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "---I would have appreciated a more intuitive description of the formulas associated to the FRC, BFC, ORC and LRC. Otherwise, the equations provided in the various definitions are a bit cryptic.\n\n---In terms of baselines in the experiment, why not compare against the non-iterative preprocessing versions of the FRC, BFC and/or ORC? As far as I understand, Algorithm 1 could be used with any of the other curvature measures in a non-iterative way, making them more scalable. This could maybe allow to even include ORC in the baselines for the various experiments. Alternatively, would an iterative version of Algorithm 1 with LRC perform even better?\n\n---I am a bit puzzled about some of the results presented in Table 5. Do the authors have an explanation for the huge increase in running time when using SLPA after FRC preprocessing? Also, given that the running times of K-clique are exactly the same after FRC and LRC preprocessings, I would have expected that the simplified networks are the same, resulting in the same F1 scores as well. However the F1 scores are different. Any idea of what is happening? \n\nTypos:\n\n---definition of $\\Delta(i,j)$ above Proposition 1: I think $s_i$ and $s_j$ should be $s_{i,j}$ and $s_{j,i}$ to be consistent with Definition 2.\n\n---appendix A: \"$\\Delta\\geq .$\" ---> $0$ is missing.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8wD5K7W3aB", "reviewer": "Reviewer_tfRj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This submission will be of interest to some in the TMLR audience. The paper with written with care and it is easy to follow the points the authors make. All the claims seem supported, modulo some details I address below.\n\nThe paper should better address (i) why these notions of discrete curvature are analogs of the continuous notion and (ii) why discrete curvature is useful in community detection. Currently, these points are rushed over or left implicit. (Such a discussion doesn't need to be very formal.)\n\nI don't understand what is meant by the claim that LRC is \"scale-free,\" which is an issue as this is one of the central claimed contributions.\n\nI found the submission's discussion of computation to be lacking. Here are a few comments.\n1. How is the graph presented? \n1. I believe algorithms based on fast matrix multiplication, such as that of Itai & Rodeh, allow us to compute all-pairs FRC in time faster than $O(mn)$ when the graph is dense. It's worth mentioning these, especially around statements like \"the computational cost for calculating FRC...\", which might be better phrased as \"in our setting, the best-known algorithm...\".\n1. There are $\\tilde{O}(n)$ algorithms for community detection in SBMs under certain parameter regimes, e.g. [1]. I would like to see a brief discussion on this line of work and whether or not it's relevant.\n1. I don't understand why we switch from big-Oh notation in Table 2 to clock time in Table 3. The sentence containing \"due to the complex nature of the community detection... computational complexity is not reported here.\" did not clarify things.\n \n[1] Wang, Peng, Zirui Zhou, and Anthony Man-Cho So. \"A nearly-linear time algorithm for exact community recovery in stochastic block model.\" International Conference on Machine Learning. PMLR, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission proposes a new notion of \"discrete curvature\" for graphs, called *Lower Ricci Curvature* (LRC), with the goal of improving community detection algorithms. There are a few other methods given by prior work. This one aims to keep the best aspects of all of them, as it is computationally lightweight and, perhaps, easier to interpret.\n\nIn the main body of the submission, we get an overview of prior work, a definition and discussion on the new curvature notion, and experiments. There are some examples on toy models. The main experiments evaluate LRC as a pre-processing step: if one computes LRC for every edge and then removes edges with low values, does it improve the downstream performance of existing algorithms for community detection?", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Once these changes are made I will happily recommend acceptance. Items 3, 4, and 5 are small edits.\n1. If \"scale-free\" means something precise, include a definition and prove that LRC satisfies it. If it does not have a precise definition, please point out that you use it informally and spend some more time discussing what it means. \n1. Address my previous comments on computation and other algorithms.\n1. Typo before Def 1, it should say \"FRC.\"\n1. Top of p5, Ollivier's happened simultaneously with what?\n1. The plots, like Figs 1 and 2, would be easier to read with bigger text.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I thank the authors for addressing the comments from all three reviewers and revising their paper accordingly. Despite the lack of thorough theoretical analysis and justification, this work does demonstrate merits of the proposed approach to improving existing community detection algorithms, at least empirically. With the revisions, all reviewers are supportive of acceptance of this paper for publication in TMLR.
Decision: Accept (poster)