Hypergraph clustering using Ricci curvature: an edge transport perspective
Authors: Olympio Hacquard
Venue: Accepted by TMLR ()

Abstract: In this paper, we introduce a novel method for extending Ricci flow to hypergraphs by defining probability measures on the edges and transporting them on the line expansion. This approach yields a new weighting on the edges, which proves particularly effective for community detection. We extensively compare this method with a similar notion of Ricci flow defined on the clique expansion, demonstrating its enhanced sensitivity to the hypergraph structure, especially in the presence of large hyperedges. The two methods are complementary and together form a powerful and highly interpretable framework for community detection in hypergraphs.

Published in Transactions on Machine Learning Research (10/2025)
Hypergraph clustering using Ricci curvature: an edge trans- port perspective
Olympio Hacquard
hacquard. hacquard. Soopuaattllmmpi..kkkkkttttoo.ooo
Kyoto University Institute for Aduanced Study
Kyoto University, Kyoto 606-8501, Japan
Reviewed on OpenReview: https: openreview. net/ farum?? id= HMRDU8MXqV
Abstract
In this paper, we introduce novel method for extending Ricci flow to hypergraphs by defining probability measures the edges and transporting them the line expansion. This approach yields a new weighting on the edges, which proves particularly effective for community detection. We extensively compare this method with a similar notion of Ricci flow defined on the clique expansion, demonstrating its enhanced sensitivity to the hypergraph structure, especially
the presence of large hyperedges. The two methods are complementary and together form a powerful and highly interpretable framework for community detection in hypergraphs.
1 Introduction
Hypergraphs are gencralizations of graphs extending the concept of edges to encompass relationships in- volving any number of vertices rather than being restricted to pairs. Hypergraphs provide a more faithful data representation than graphs as many real-life interactions occur at a group level rather than at a binary one. Examples include social interactions, simultaneous participation at an event, co-authorship, mutual evolutionary traits, spatial proximity or molecular interactions. These interactions are better encoded by hypergraphs instead of traditional graphs, see Davis 1941] 0; Dotson et al. (2022) Konstantinova and Sko-
robogatov (2001); Torres et al. (0021;; Klamt et al. 22099 We refer to Berge 1984 and Bretto (2013) for comprehensive overview of hypergraph theory.
Recently, machine learning tasks on hypergraphs have encountered growing success, in particular for clas- sification (Feng et al. 2019), regression [Lu et al. 2021), anomaly detection (Lec et al. 2022) or embedding (Zhang et al., 2019 Antelmi el al. 20233) The present article focuses on the clustering problem or commu- nity detection, i.e. recovering labels on the nodes in a fully unsupervised setting from a single hypergraph
instance. Several approaches have been taken to tackle this problem such emboddings using neural net-
works (Zhang et al. 2021; Lee and Shin 2023 random walks-based embeddings (Hayashi et al. 22200 Huang et al. 2019) followed by a clustering in the Fuclidean space. Some methods developed in Kumar et al. (2020):
Kamiñski et al. (2024) aim at maximizing hypergraph-moouulaityy functions that measure the strength of a clustering. Finally, let us mention the work of Eyubov et al. (0023) that finds a partition in linear time by streaming all the nodes one by one.
The present work investigates generalizations of Ricei flow based clustering on hypergraphs. Ollivier-Riee curvature, introduced by Ollivier (007)) for general metric spaces and later specifically tailored to graphs LLn et al. 2011), defines distance graph edges that quantifies local curvature using optimal transport theory. Edges within strongly connected communities have positive curvature while edges bridging two communities are negatively curved. Ricci curvature can be turned into a flow dynamic in order to further stress out this community structure and take some more global graph properties into account. Alternative notions of curvature for graph processing are also present in Forman (2003): Sreejith et al. (2016); Tyer et al. (2024); Tian al. (2025). Ricci curvature on graphs has been used derive thcoretical bounds on the spectrum of the graph Laplacian by Lin and Yau (2010) and Bauer al. (201)) For applied purposes, it

---

Published in Transactions on Machine Learning Research (10/2025)
has been used for data exploration Ni et al 2015 representation learning Zhang al. 2023 topological data analysis (Carriere and Blumberg, 2020; Hacquard and Lebovici 2024), and in particular clustering (Ni et al. 2019) ; relying on the property of the Ricci flow to place emphasis on the community structure.
There has been a few attempts to generalize Ollivier-Ricet curvature to hypergraphs, in particular by Coupette et al. (2022). The authors introduce a notion of curvature using random walks on the nodes. As pointed out by CChitra and Raphael (2019), in most practical cases, considering a random walk on the hypergraph is equivalent to random walk on its clique expansion (a graph representation where each hy- peredge is replaced by weighted clique). Doing so is common way to circumvent the complex hypergraph structure by replacing it with a graph with similar structure. However, as noted in Chitra and Raphael (2019), this reduction can result in significant information loss, as distinct hypergraphs may share identical clique graphs (Hein et al.) 2013). In addition, replacing a single hyperedge between nodes implies adding up to (*) connections between nodes which can be computationally prohibitive in a network with mutual interactions between many agents. Extensions of Ricci curvature on directed hypergraphs have also been proposed by Eidi and Jost. (2020).
The main contribution of this work aims at defining a notion of Ricci curvature hypergraphs where we consider probability distributions on the edges instead than on the nodes. This approach leverages the line expansion of the hypergraph, which is a graph representation where nodes correspond to hyperedges, and edges reflect hyperedges intersections. The line expansion is a common way to represent a hypergraph for learning purposes, see Bandyopadhyay et al. (2020); Yang et al. (2022). In addition, it has been demonstrated in Kirkland (2018) that almost all the hypergraph information is retained by the joint knowledge of both its clique and line expansions. The current work puts particular focus on clustering. We perform thorough experimental study synthetic and real data comparing the approach where transport measures on the edges to the more standard approach where we transport measures on the nodes. More precisely, this notion of edge transport should be favored when we have large number of small communities, when the edges between communitics have a larger cardinality than the ones within communitics, and more generally for hypergraphs with very large hyperedges as this approach is much more efficient computationally.
The work organized follows: Section 2 introduuess the foundational concepts of hypergraph theory and Ollivier-Ricci curvature on graphs. Section X presents two different possible expansions of Ricci curvature for hypergraphs: the standard one where we transport measures the nodes, and the main contribution of this paper where we transport measures on the edges. We also compare the two approaches theoretically on a synthetic example. Section ! provides a detailed baseline of experiments on synthetic data and on real data where we compare both methods to state-of-the-ar clustering algorithms on hypergraphs, along with a computational analysis of both methods.
2 Model
This section presents the main concepts related to hypergraph analysis and the hypergraph partitioning problem. We also investigate standard methods to replace hypergraphs by traditional graphs and the loss of information it implies.
2.1 Hypergraphs and associated graphs
Hypergraphs, definitions Undirected hypergraphs, sometimes referred to as hypernetworks or 2-modes networks, consist of a set of nodes V and a set of hyperedges E. Extending the concept of graphs where edges link two distinct nodes, hyperedges are defined as non-empty sets of nodes of arbitrary size. For a hyperedge e (u....., ug), its cardinality le is referred to as its size. A hypergraph in which all hyperedges have the same size is called a k uniffoorm hyperrraph. Notably, graphs are 2 -uniform hypergraphs. We further define the star of vertex u V as the set of hyperedges that include St(w) (c E Elu c).
Clique expansion Given a hypergraph H with node set V = (VI...., v,)) and edge set E (ei, Cm): its incidence matriz I E (0, (),1)=xx ax is defined as L, rectangular matrix makes further analysis of hypergraphs much more complicated than that of graphs,
v, E e, and otherwise. This representation
2

---

Published in Transactions on Machine Learning Research (10/2025)
13
14
(a) H1
(b) H2
(c) H3
(d) H4
VL
12
1
19
14 19
(e) C(Hi)
(f) C(H2)
(g) C(Hs)
(h) C(H.)
e
e
(i) L(H))
(i) L(H2)
(k) L(Ha)
() L(Ha)
Figure 1: Examples of hypergraphs H, with their clique C(H.) and line L(H,) expansions. H1, H2 and H3 share the same clique but have different line expansions.
which can be described by their adjacency matrix. A commonly used simplification of hypergraphs is the clique erpansion, where each edge is replaced by a clique. More precisely, the clique expansion C(H) of the hypergraph H is the graph with node set V and with an edge (x.y) if there exists a hyperedge E E such that y E e. The clique expansion provides a convenient simplification of hypergraphs by grouping nodes belonging the same edge. However, there share the same clique expansion, see Figure ] We refer to Hein et al. (2013) for a more thorough analysis of differences between hypergraphs and their clique expansion. Notably, according to Chitra and Raphael (2019) and Hayashi et al. (2020), unless the nodes are assigned edge-dependenl weighting, standard notions of random walks and Laplacians on the hypergraphs can be expressed on a reweighted clique expansion. This mothods, such as clustering, on hyporgraphs often incurs the
certain loss of information since multiple hypergraphs
implics that directly applying Laplacian-base information loss inherent in their clique expansions. We note that the adjacency matrix Ac of the clique graph can be derived from the incidence matrix via Aç = = - Dy where D2 the diagonal node-degree matrix, with entries de = EE Lig.
Line expansion Another graph associated with H is the line graph L(H). Each edge in H now corresponds to a node in L(H). Thus, L(H) has node set (ei...., en) and we have an edge (et,et) in L(H) if the corresponding hyperedges intersect in H, i.e e, * 0. Similarly to the clique expansion, many hypergraphs share the same line expansion, see Figure [ However, joint knowledge of both the line and clique expansions seems to capture most of the structural information of the hypergraph. Indeed in Figure [ hypergraphs H1, H2 and H3 all share the same clique expansion while having different line expansions (they even have different node sets). Similarly to the clique graph, the adjacency matrix Ar, of the line graph can be derived from the incidence malrix via Ar. I'I D. where D. is the diagonal matrix of edge-lengthss hs, with entries & leel. Let us define the dual hypergraph H (E*, V*) as the hypergraph obtained by swapping the edge and node sets, i.c. E* = (et...., e,,) and V = (oi,... ) where uz = {eelu; E ey}. We can casily observe, see Zhou et al. (022)). that the clique expansion is the line graph of the dual hypergraph: C(H) L(H)).
Gram mates We can wonder the joint knowledge of both the clique graph and the line graph allows to reconstruct the hypergraph. The answer negative, as there exists pairs of distinct (-1 matrices (A, B) such that AAT BB" and AT B" Such matrices are called Gram mates, and we refer to Kim and Kirkland 2022 for proof of this result and thorough analysis of families of matrices that generate Gram
3

---

Published in Transactions on Machine Learning Research (10/2025)
(2018) that if uniformly pick mates. However, it has been demonstrated in Corollary 1.1.1 of Kirkland two x n 0-1 matrices, the probability that they are Gram mates decays exponentially as (m, -> co. Thus, for practical applications, the information loss from replacing a hypergraph with its clique and line expansions together is negligible. This representation also simplifics hypergraph analysis significantly.
Clustering We consider hypergraphs where nodes are associated with discrete labels {1...., K}, repre- senting communities clusters. Intuitively, such hypergraphs exhibit a community structure, with denser connections between nodes sharing the same label compared to those with different labels. We assume fully unsupervised setting, where try to infer the labels (up to permuuatioon) simply via the hypergraph structure. This generalization of the graph partitioning problem has been studied extensively, and we refer to Çatalyürek et al. (2023) for a survey of different approaches to tackle this problem. A popular mothod to determine the quality of a partitioning is given by modularity maximization, initially defined by Newman (2006). We recall its definition in the graph case. For a graph G= = (V, F) and partitioning (C1,...,C4 of V into subsets, we define the modularity function Q as:
(G(CC) E
[o,(C.)) vol(V)
Q(C) Σ
where (CiC;) is the number of edges in the subgraph of G induced by a node set C₁ and vol(A) Eves deg(v) the volume of any subset A of nodes. Up to renormalization, the modularity function computes the difference between the number of edges uncut by the partitioning and the expected number of edges the same partitioning would yield in the Chung-Lu random graph model introduced in Chung and Lu (2006). Maximizing Q over every partitioning yields partitions that minimize cuts within communities, aligning with the underlying structure. There have been several works generalizing modularity for hyper- graphs, notably Kumar et al. (2020) and Kamiński et al. (2024), by generalizing the Chung-Lu random model to hypergraphs, and allowing different weights to hyperedges different sizes. Modularity also serves as ground truth-free measure of the quality of a given clustering.
2.2 Ricci curvature and flows on graphs
This paper addresses the clustering problem using an extension of Ollivior Ricci curvature to hypergraphs. This method extends prior works on Ollivier Rivvirr-Ricii curvature, initially defined in Ollivier (2007) on metric spaces, and extended to the case of graphs Lin et al. (2011). In Ni et al. (2019), the Ricci curvature is turned into discrete flow such that edges between communities are heavily curved. They directly derive a clustering algorithm. We start by recalling the key concepts of their method in the case of graphs.
Discrete Ricci curvature Let G = (V, E) be a weighted graph with weight function w : E + Rzo- In what follows, the function w is set to be a dissimilarity measure between nodes. Let d denote the shortest path distance between nodes induced by weights w. We adopt the framework introduced in Ni et al. (019 for each node F, we define probability measure uouP over x and its neighbors given by:
a La exp(-d(z,g)))
yf= if E N(x), otherwise,
(y)
(1)
where where.V(x) Nxx)) denotes the set of neighbors of x. Here, C= EyEnNN(a) to ensure that ve-P is a probability measure. The parameters a E (0, 1] and respectively denote the amount of mass retained at x and how much we want to penalize far neighbors. When not required or clear from context, we will drop the superscript and simply write 1ー
y)") ) a normalization constant
The discrete Ricci curvature is function defined on the edges of the graph such that for edge (x,
4

---

Published in Transactions on Machine Learning Research (10/2025)
G
R
C
< 0
R >>>> 0
Figure Saivier-RRiel curvature on graph with a clear two-commuiities structure.
x(r,y) = 1 W Wwns By) d(x, v)
where Wi is the 1-Wasserstein distance between probability measures for the cost function d, see Santambrogio 2015 More precisely, a discrete transport plan T between the measures Vs and By is an application VE V + [0, I] such that Evev v',,") va (u) and Ewev T("',) = my(v). The 1- I-Wasserstein distance corresponds to the total cost of moving v Vy with the optimal transport plan for a cost function d, Le.
wy),, = inf
Σ W.EV
T(u, v)d(u, e) transport plan between Va and By
The sign of k provides information on the density of connections. Indeed, two nodes x and belonging to the same community will typically share many neighbors, hence transporting v, to My has a smaller cost than moving x to y and therefore induces a positive curvature. Conversely, nodes belonging communities do share many neighbors, such that moving Ve to By requires traveling through the edge (z, y) bridging the two communities. This in turn corresponds to negative curvature. We refer to Figure 2 for concrete example: when transporting Mr, to Uny and Vu; to Muys most of the mass remains on the nodes such that measures are transported at low cost. In the extreme case where a = 1/5, all the mass remains and ni(;,, 0y) x(u; u,) = 1. When transporting Ve, to Vn,, all the U;'s must be transported to u,'s through the edge (u1, v1) such that the total transport cost is larger than d(u1, 01) and therefore s(uu, U1) <
different
Trimming edges of low curvature typically removes spurious connections between densely connected areas. Consequently, we can obtain new graph where each connected component corresponds to a different community. We note that Ricci curvature can theoretically be computed for any pair of nodes in the graph. However, for our purposes, only need to compute it for adjacent nodes.
Discrete Ricci flow and community detection To amplify the impact of heavily negatively curved edges and incorporate more global graph structure, turn Ricci curvature into discrete flow that modifies the graph weights. We recall that the edge weights are dissinilarities, and a high weight corresponds to a high distance between nodes. The initial weight between and y is (0()) (x,,v) w(x,v). We iteratively update the weights with:
w0+1 x1-xxxxxxx)) w (x,0).
(2)
where (()) is the Ricci curvature computed with the distance induced by the weights w(t) The updated weights after the I-th iteration are referred to as the Rioci flow. This flow dynamic strecches edges of low curvature, making more and more costly to transport measures between communities. The complete clustering algorithm is described by Algorithm and simply trims edges with a high Ricci flow. The choice of the number of flow iterations N is mostly heuristic, we refer to Ni et al. (2019) and the corresponding python library GraphRicciCurvatuun for some guidelines. The threshold at which to trim the weights
5

---

Published in Transactions on Machine Learning Research (10/2025)
Input: Graph G = (V, E), Number of iterations N, Threshold Output: Clustering labels Y
for i 1 to N do
Update the weights using Equation end
Trim all edges with a weight larger than to create new graph G Compute connected components C₁ II... for i to [ do
III..III, II of G
Set Y, j if U E Cj;
end
Algorithm 1: Ricci flow algorithm.
is a crucial parameter and can also be taken as the one that maximizes the modularity function defined in Section 2.1 which evaluates clustering quality without ground truth labels.
This approach ensures that comer-community connections are down-weighted while preserving intra- community coherence. This enables robust and interprctable method for clustering. Indeed, the method relies direct computations of the Silvierr-Ricii curvature which is strongly associated to intrinsic com- munity partitioning of the graph, see Figure 2 We defer an extended comparison of the interpretability of Ricci-based clustering as opposed to neural network embeddings to Section 4.2
3
Two complementary notions of Ricci curvature on hypergraphs
Extending Ricci curvature to hypergraphs presents two main challenges:
Ricci curvature is traditionally defined for pairs of nodes and needs be extended to hyperedges.
Computing transport distances between measures defined on the nodes of hypergraph typically relies on the clique expansion (see Section 2.1 and Hayashi et al. (2020)). As consequence, this approach introduces loss of structural information, as clique expansions fail capture certain higher-order interactions.
The first challenge is straightforward to treat, for instance by laking the average or the maximum of all pairwise curvatures of nodes in a hyperedge (as in Coupette et al. (2022)). ). We will discuss different possi- bilitios Section 3.1 The second challenge constitutes the main contribution this paper and will further be developed Section 3.2 where we explore a method to transport hyperedges.
Note that we restrict our analysis the Ollivier-Riie Ricci curvature, Another notion, the Forman- Carman-Ricci curvature Forman 2003). has been extended the case of hypergraphs in Leal et al. (2021). We refer to Samal et al. (018)) for detailed comparison of these two curvature types in the graph case.
3.1 Nodes transport on the clique graph
Clique graph transport Let H be a hypergraph with nodes V = (V1,..., ea) and edges E = (ci,..., Cm). To compute the Ricci curvature between two nodes a and we can still define measures V, and Vy on æ and y and their neighbors following Equation [ as the definition of neighbor unchanged. We first propose replace the hypergraph with clique expansion. Two possibilities are considered obtain a clique graph from a hypergraph. For the sake of clarity, we assume the hypergraph to be unweighted. Let Ac (si)) be the adjaceney matrix of the clique expansion of H.
(i) The first option is consider a simple unweighted clique graph expansion where
1 if there exists e H such that (v,, Uz) C e, otherwise.
aij

---

Published in Transactions on Machine Learning Research (10/2025)
(t
St(y)
Sea) n (.8e)))
66
(a) Stars of x and
(b) Corresponding line graph
Figure 3: Edge-Rieci transport between nodes x and A measure on St(x) is transported onto measure on St(y) via the line graph.
(ii) The second option is proposed by Zhou al. (022)) and relies on Jaccard index weighting. Recall that for two finite sets U and V, the Jaccard index J(U, junv| is a measure of similarity between [tov|
sets U and V. Let H (V*, E*) be the dual hypergraph as defined in 2.1 We remark that for two nodes vi and fjj, Ogy = 0 if and only if juğ nu3l 0. The weight of two adjacent nodes in the clique graph is given by 1/J(er, uz). The Jaccard index is inverted to provide dissimilarity weighting.
A discussion the relative performance of these two weightings can be found in Section 4.3
A Aggregating pairwise curvatures After computing the Ricci flow w (e) for every pair adjacent nodes in the clique graph of H, the Ricci weight of a given hyperedge E is obtained by aggregating all pairwise flows between nodes of e:
(e)
[Ag Eo
Agg
(v..)))
where Agg is aggregation function. Experimentally, found that aggregating using the marimum of all pairwise curvatures systematically yielded the best clustering performance.
The clustering pipeline given by Algorithm [ then operates similarly by trimming all hyperedges with a Ricci flow larger than some threshold. The optimal threshold can be found by either maximizing the modularity of the clique graph, or a corresponding notion of hypergmahh modularity, see Kamiński et al. (2024).
3.2 Edges transport on the line graph
As discussed in 2.1 replacing hypergraph by its clique graph induces substantial loss of information. To address this, we propose novel notion of Ricci curvature specific to hypergraphs. Instead of transporting measures defined on the nodes of hypergraph, we transport measures defined on its edges. The motivation is that two nodes from different communities should be contained sets hyperedges that typically do not intersect much.
Edge-Ricci curvature The proposed mothod also computes pairwise curvature and then extends it to hyperedges using an aggregation step similar to the one previously defined. We first describe the Ricci curvature computation for a hypergraph H = (V, F) with initial dissimilarity weights d -> Ry0- Let æ and y be two adjacent nodes in the hypergraph. We define simple probability measures pa and by on their stars St(z) and St(y):
die if E St(x) px(e) {
(3)
otherwise,
where C E d(e) is normalization constant ensure that dı a probability measure. The definition of By is analogous. Similarly to the measures vs defined the nodes, the measures He could

---

Published in Transactions on Machine Learning Research (10/2025)
be adapted to include hyperparameters and p. However, preliminary experiments wide variety of settings suggested that it had close to no effect on the resulting curvature.
The distance dæ between two edges e and f is defined using the line graph: (e, (en))(" , where L(G) is the line graph of H, see Figure 3 Note that similarly to the clique graph, there are several ways the line graph can be weighted (for instance using Jaccard weights between hyperedges). This aspect will be discussed in more details in Section 4.3 Similarly to the graph case, we can then define an optimal transport plan and corresponding 1- 1-Wasserstein distance W using the distance dæ between the two mcasures pa and My. The edge-Rice Ricci eurvature Kg between two adjacent nodes and y is therefore defined as
W (Ma, Mly
(g( =
max (ES(())(St())
d(e)
Pairs of nodes in different communities tend to have very different stars, which implies in turn a low curvature. Conversoly, the two nodes x and y belong to the same community, the mcasures fe and By can be transported onto each other with a low cost, resulting a curvalure close to 1. We remark that even in the case of 2-uniform hypergraph, this definition not equivalent the usual curvature on graphs from Section 2.2 In addition, we lose the interpretability observed in Figure 2 concerning the sign of the curvature. Note that although it is inspired by the notion of curvature developed by Ollivier (2007). edge-Ricci curvature cannot be directly connected to Ollivier's 's original definition of curvature in metric spaces. As such, deriving theoretical results for this curvature seems currently out of reach.
As edge-Riee Ricci curvature uses both the clique and the line expansions, it allows to be more sensitive to the hypergraph information than node-Ricci curvature which crases information by considering the clique. For mastrenghtsy have different edge-Ricci curvature
example, we can observe that pairs of nodes in Figure | while every pair has the same node-Ricci curvature. However, general theoretical analysis of the differences between Ricei and edge-Ricct curvatures remains out of reach. In Section 3.3 differences on toy example and illustrate the strengths of each notion.
investigate these
Edge-Ricei flow Similarly the graph case, the curvature then turned into a discrete flow. We start with an initial edge weighting 3 = d. At the I-th iteration, the weights are updated according to the following three steps:
(1) (i) Compute the Ricci curvature Kg for every pair of adjacent nodes in the weighted hypergraph.
(ii) For every hyperedge e, aggregate all pairwise curvatures with an aggregation function Agg to define the curvature of the hyperedge, similarly to Section 3.1
(c)
(c)
Agg E.
(i (v. v;))
(iii) For every hyperedge e, update the edge weights using the Ricci flow dynamic:
@ (+1) (e) = (1-xx (e) W (e). WE
Similarly to the graph case this procedure is iterated N times, and hyperedges with weight larger than given threshold are trimmed. The resulting connected components form the assigned node communities. In (raditional Ricci flow with = O, negatively curved edges gradually gain weight, increasing the cost. of moving probability measures through them. Here, we take a dual perspective: edges with low curvature are assigned increasing mass, making them progressively more expensive transport. The line graph, however, remains unchanged, such that distances between edges are unaffocted by the flow process. We refer to Tian et al. (025)) for another example of method using the line graph for community detection.
8

---

Published in Transactions on Machine Learning Research (10/2025)
3.3 A toy clustering example
We start by comparing the node-Ricci flow from Section 3.1 with the edge-Ricei flow from Section 3.2 in a synthetic example where transport maps and curvatures can be computed explicitly. We adopt a very similar setting to the of Ni et al. (2019) where we consider family of hypergraphs H(a, b) where a, b 2 3 are integers. Consider b complete graphs CI,...,Cy Cs distinct vertices. For each complete graph C₁, take particular vertex vi (called gateway vertex) and consider the hyperedge of size b, (e1.... 1%) connecting all gateway vertices across the communities. This hypergraph exhibits a clear community structure where each C, forms a distinct community, and there is a single hyperedge connecting all the communities together. Figure provides a visual representation.
The case of the node-Ricei flow for an unweighted clique expansion has been treated explicitly in Ni el al. 22119) for measures defined by Equation with the clique expansion, the Ricci flow at the 1-th iteration can only take three possible values: wX,, for edges between two galeway nodes, "N22 for edges between a galeway node and another node from its community, and wN,3 for edges belween two non-galeway nodes from the same community. They further demonst.rate that if a > b, WN.3 = (2) 0 and that there exists À >> y and constants c2 such that = a o(X) and "x12 02 o(2') as algorithm properly identifies the communities Ci...., Co.
and p 0. They observe that by symmetry, in
+e
This implics that the Ricci flow-based trimming
We derive similar result for specific measures μ. Equation is slightly modified such that the transported mcasures are now defined, for two nodes x and y as:
0
fayeee if Si(a) and e $ Styy)
(x(e)
d(c)
(4)
otherwise,
where C is a normalization constant. In practice, this choice of measure yields results extremely similar to the ones defined by Equation 3 It simply discards edges shared between x and y, which would typically not play big role in deriving the transport plan. This choice simply ensures much simpler expression for the Ricci flow to facilitate the delivery of the following proposition:
Proposition 1 We keep the same notation above and consider the adge-Ricci flow with measures defined by Equation 4 and aggregation Agg with the marimam function. At the 1-th iteration, the Ricci flow con only take three possible values: W for the edge of size b connecting all gateway nodes, w w/22 for binary edges between a gateway node and another node from its commanitty, and w for binary edges between two non-gateway nodes from the same communityy. Under these cireumstances, we have that for all 1 0:
(1)
w N11 2,
())
44(a-2)wu) (-1)
E [1,2],
N22 2+(a 2+(a-2)wx
4-11
w N.3
1.
The proof is deferred to Appendix A Proposition D implies that the edge-Ricci flow also identify the community structure with an edge cut-off parameter between 1 and 2. We notice that in this case, the explicit expression of the Ricei flow, although much simpler than in the node-Ricci case, does not have an exponential decay to for the intra-community edges. This implies that the cut-off parameter might be more delicate to tune in practice. However, note that Proposition Toolds for any values of a and b, contrary to the result of Ni et al. (2019) which only holds for b. This implies that in practice, edge-Rice Ricci allows for better detection of many small communities.
9

---

Published in Transactions on Machine Learning Research (10/2025)
Figure 4: Example of hypergraph (a, b) with a = 6 and = 4. The gateway nodes are represented in blue. 4 Experiments
To evaluate the practical effectiveness of Ricci flow for hypergraph clustering, we conducted a range of experiments on synthetic and real data. We opted for a Jaccard type weighting for the clique graph and the line graph. Curvatures of hyperedges are computed by aggregating curvatures of pairs of nodes using the maximum function. For node-Ricct flow, we have used the python library GraphRicci with parameters p = 1 and a = 0.5 for the measures )zev defined on the nodes. We refer to Section 4.3 for a discussion about the choice of default values for the hyperparameters. The clustering accuracy measured using the Normolized Mutual Information score (NMI). The implementations of edge-Ricci and node- Ricci flows for hypergraphs are available at https://g/ thub. com/AAroaiiccc1///iccc... curvvccci_vvvv_.ee HG and are directly adapted from the GraphRicciCurvaturx library.
4.1 Hypergraphs stochastic block models
We first evaluate method on synthetic set-up to highlight differences between edge-Ricci and node- Ricci flows. We consider a hypergraph stochastic block model inspired by Kim et al. (018)) We consider hypergraph with nodes and & communities. We give ourselves two size parameters 8in and Sout- We generate Nin hyperedges of size 8in by uniformly sampling 8in nodes of the same communily for each community. We generate Nout hyperedges of size Sout by first sampling one node from each community at random, and drawing the Sout remaining nodes uniformly from N. In the graph case where 8in = Sout = 2, this is a form of stochastic block model, see Abbe (2018). This is a simple model where untraccommunity edges can be interpreted signal and inter-community edges noise. In the hypergraph case, as soon 8in 2 3, inter-community edges also regrouping nodes of the same community together and cannot simply be interpreted as pure noise.
We try to reconstruct the communities using edge-Ricci and node-Ricei flows clustering algorithms. We consider randomly generated hypergraphs of = 100 nodes, k = 2 equal-sized communities and compare the performances of the two methods for various values of sin and Sout- We fix the value of N,, and measure the evolution of the clustering accuracy for a growing number Nout of 'noisy" hyperedges. We compute N = 20 flow iterations for each method and take the thresholding parameter 7* that maximizes the NMT. We average over 5 random hypergraph generations and report the corresponding NMI in Figure 5 We remark that node- Ricci flow seems to perform comparatively better than edges-flow when the size of intra-commn nntra-community edges Sin is large and the size of inter-community edges 8out is small and conversely. These differences can be simply understood heuristically: when contaminating a hypergraph by adding a hyperedge size s, the clique graph will have up to s(s - 11//2 new edges while the line graph will only have a single new additional node. This accounts for an improved robustness of edges-flow to large hyperedges contamination, as it mostly relies on shortest-path computations the lino-graph.
4.2
Real data
We further compare the clustering performance nodes and edges-flow with state-of-the-art graph and hypergraph clustering methods.
Methodology and data We evaluate our method on the datasets presented in Table S.1 A detailed description of the datasets can be found in Section B Data and code to reproduce the experiments are
10

---

Published in Transactions on Machine Learning Research (10/2025)
250 intra-edges
250 intra-edges
250 intra-edges
Nodecconrport 1-1 Exges
1801
Rodes transpat, p Fdgee torrpoot
Kumber of Lutwouummanty stigos
Kumbow of Lrcsiiun mumily udgis
Nkanoa LocaansttETu scdgee
(a) Sin 2, Sout 2
(b) 8in 2, Bout 4
(c) Sin 2, Sout 6
200 intra-edges
200 intra-edges
200 intra-edges
Ddyo buansert
-Ape humsott
Kumber of cross-community edges
Kumber of cross-corrmuntly edges
Number crose-commuriiyy edges
Sin 3, Sorct 2
Sin 3, Sout 4
(f) Sin 3, Sout
125 intra-edges
125 intra-edges
125 intra-edges
1301
04
bage Conncortt
bages carspott
533e5 taangott
Rumber of coow-cammmnity veiges
Kumber of tronseentt muniifi adges
Namber of cromaceammmrrlll ndges
Sin 4, Sout 2
(h) Sin 4, Sout 4
ii) Sin Sout
75 intra-edges
75 intra-edges
75 intra-edges
M
Modes canppott P Falys Inessur
transpors Pager "Worppot
Rumbor of Luoa-curmmani stigus
Rumbor of Lrcaeiu munily sdgpe
Nandla Lronensmmeurriy sddie
(i) 8in 5, Sout 2
(k) 8in 5. Sout 4
(1) Sin 5, Sout
Figure 5: Hypergraph stochastic block model reconstruction using hypergraph notions of Ricci flow.
11

---

Published in Transactions on Machine Learning Research (10/2025)
Dataset
Cora-C
Cora-A
Citeseer
Pubmed
Zoo
Mushroom
NTU2012
Node2Vec
39.1
16.0
24.5
23.1
11.5
1.6
78.3
DGT
54.8
45.2
40.1
30.4
13.0
OOM
79.6
GRACE
44.4
37.9
33.3
16.7
7.3
OOM
74.6
8 SH-HHGR
51.0
45.4
27.7
90.9
18.6
82.7
TriCL
54.5
49.8
44.1
30.0
91.2
3.8
83.2
Modularity
45.0
33.4
33.8
25.0
77.7
43.4 4
74.5
N-Ricci
45.8
39.4
38.8
27.8
96.2
OOT
76.3
E-Ricci
43.3
39.1
38.3
22.7
100.0
42.3
77.6
Table 1: NMI clustering accuracy on real datasets.
available http://hwwwb.commooooaaccccaaaaa cerrcci__ur__i_eee HG
We adopt the same benchmark study in Lee and Shin (2023). For each dataset, we iterate Ricci flows N 20 times. The edge-cutting threshold
is taken as the one that maximizes the hypergraph modularity, computed with the hypernetx python package.
Quantitative results We report the NMI of our method in Table where we compare ourselves with graph and hypergraph partitioning hate-of-theeatt methods. Node2vec (Grover and Leskovec 2016 DGI Veličković et al.) 2018) and GRACE (Zhu et al. 2020) embed the hypergraph's clique expansion in a Euclidean space using various neural networks architectures. S²-HHGR from Zhang et al. (2021) and TriCL from Lee and Shin 2022) directly embed the hypergraphs using a neural network architecture. Communtties are then detected using a k-means algorithm. Note that for TriCL and 8 -H-HHGR, additional node-feature information is usod improve the prediction, while Ricci flow methods rely only on the hypergraph structural information. All scores for these methods are reported from Lee and Shin (2023).
We also report. the score
obtained by the modularity maximization algorithm from Kamiñiki et al. 20021 OOM indicates out- of-memory еrror on 24GB GPU (reported from Lee and Shin (2023))
OOT indicates that the results
could not be obtained within 72 hours on single 8-core laptop with Intel(R) Core(TM) 15-8300H CPU @ 2.30GHz processor unit.
Ricci-based clustering methods provide an overall fair accuracy, with a better performance than simple graph vectorization methods, while managing be as competitive as saat--ofthheart neural network- based hypergraph embeddings on few datasets. In particular, we achieve perfect clustering the Zoo dataset using edge-Ricei flow. This dataset stands out for having very few nodes and edges and demonstrates the ability of Ricci-based methods to capture fine structural information small graphs. We assert that a significant advantage of our method is its high level of explainability, particularly when compared to methods based on neural network embeddings. Specifically, Ricci flow facilitates clustering on graphs with several notable properties:
It is grounded in established theoretical works on metric spaces, see Ollivier 2007 and benefits from convergence results when applied on random geometric graphs, as shown in Van Der Hoorn et al. (2021).
The method is computable in closed-form on simple examples as demonstrated Ni et al. 20199
and further claborated in Soction 3.
is strongly associated with the intuitive notion of a community on graph, by assigning a sub- stantial weight. edges across communities, see Figure 2
The method relies on explicit and transparent computations and is fully deterministic.
However, it is to be noted that when exlended to hypergraphs, some of these points fail to be as com- pelling, notably the theoretical guarantees and the interpretability of the sign of the curvature from Figure g Nevertheless, our method's explicit computation of a flow process, which draws a strong analogy well-ostablished geometric counterpart, offers greater interpretability compared to neural network ap- proaches. The latter often involves many parameters, making their interpretation challenging.
12

---

Published in Transactions on Machine Learning Research (10/2025)
4.3 Hyperparameter discussion
Both notions of Ricci curvature on hypergraphs depend on moderate number of hyperparameters. Some of them can significantly influence the final performance. In this section, we review all the hyperparameters, conduct a sensitivity analysis, and provide guidelines for tuning.
The number of flow iterations N This parameter is inherited from Ricci flow on graphs. The effect of this parameter has been examined in Scction 4.1 of the Supplementary Material of Ni et al. (2019). The authors experimentally illustrate the convergence of the edge weights as N lend to inlinity. Therefore, choosing a large N therefore has detrimental impact aside from increasing the running time. In the associated code, the authors observe convergence for N between 20 and 50. This guideline still holds in our case, and we did also observe a stabilization of the Ricci flow weights for N larger than 20.
Parameters a and p for DaP These paramcters are used to define the mcasures in Equation 1 These parameters are directly inherited from Ricci flow on graphs. The impact of the parameter p has been studied in Section 4.2 of the Supplementary Material of et al. (2019). We nevertheless decide to review the impact of this parameter in Figure S..2 where we observe that in some cases, there is a drop of performance for p 0 while p 1 and p 2 show similar performance. Additionally, we decide to investigate the role of the parameter a in some critical cases, see S.3 This study has not been conducted in loc. cit. where the authors advocate for default choice of a = 0.5. Although it is challenging to provide specific guidelines, extreme values of the parameter a can lead to serious instabilities. As a result, taking a close to 0.5 is a safe choice.
Aggregation and graph weightings Both methods compute a Ricci-curvature between pairs of adjacent nodes which is in turn aggregated at the hyperedge level, as suggested in Coupette et al. (2022) We have explored two choices: taking the maximun and the arithmetic average.
In addition, the transport costs depend on the initial clique graph and line graph weightings discussed in Section 3.1 We compare between unweighted graphs and Jaccard weightings. We have studied the joint We make the following
impact of these two parameters and report the results in Figures S.4 and S.5 observation:
For mode-Rice flow, the clique graph weighting has little to no impact, while using the maximum of the pairwise curvature for the hyperedge curvature consistently yields better results.
For edge-Ricei flow, we observe a very important difference between these parameters. In short, the combination Jaccard-maximunn is the most competitive when Sin Sout and Uniform-average is the most competitive when 8in > Sout- The other two combinations always yield an intermediate accuracy. This implies that an intersection-sensitee impact in the case of large hyperedges between communities. Nevertheless, we observe in Figure S.6 that edge- Ricci flow with any combination of parameters is always outperformed by a mode-Rices flow with a maximum aggregation function in the case where 8in > Sout, as already observed in Section 1. Therefore, we always recommend using the Jaccard-maxinum parameter combination for the Ricei flow to fully leverage its potential in the case of large inter-community hyperedges.
line graph weighting has strong positive
Joint study of every hyperparameter on a real dataset In the previous paragraphs, we considered critical cases where a change in parameters could have dramatic impact. We now study the robustness of the two types of transport applied to real dataset. In Tables S.2 and S.3 we examine the joint effect of every parameter except a and on the dataset NTU2012. We observe that for this real dataset, the choice of weighting has almost no impact on the final accuracy. However, using the maximum function for Agg provides a much better accuracy than the average. Finally, We observe modest improvement by considering p= over p 0.
Both notions of Ricci flow simply operates a community-consitive rewoighting of the edges, oquivalent to a hierarchical clustering of the nodes. The cut-off parameter 7 enables access to particular clustering, making it crucial parameter when comparing to ground-truth labels. To chose
Threshold parameter
13

---

Published in Transactions on Machine Learning Research (10/2025)
Nodes Rucc fow Edges-Ricd
Time (s)
K
Figure 6: Computation times of Rieci curvature for both methods K-uniform hypergraph with 1000 nodes and 300 edges as function of K.
the value of T, we compare the one that maximizes the hypergraph modularity TH, the one that maximizes the graph modularity on the clique expansion To and the one giving the clustering with the highest NMI, i.e. closest to the ground-truth one r². We report these results in Tables S.4 and S.5 We observe that using ти gives results relatively close from the optimal ones using T" and better accuracy than using TC- In particular, on the Zoo dataset, ти = for both notions of transport, while To gives extremely poor results. This additional experiment aligns with the findings of Kamiñski et al. (2021) and Lee and Shin (2023) advocating for using iyperiraph-speecfiic tools when available, rather than reducing to the clique expansion.
Finally, note that there is not necessarily single best value for the parameter т. Indeed, modifying the optimal t provide clusters coarser finer than the ground-truth, which can be appealing in some applications.
4.4 Computational aspects
Comparison between the two types of transport We observe in Table ] that node-Ricei flow failed to provide results for the Mushroom dataset in a reasonable time. Even after 72 hours, not a single Ricci-flow iteration was completed, despite this dataset containing relatively small number of hyperedges (see Table S.1.. To better understand this limitation, further investigate the computational complexity of both methods.
Computing the Ricci curvature of all edges in a hypergraph H = (V, E)) requires solving |E] optimal transport problems where is the edge set of the clique expansion C(H). In practice, the optimal transport costs between two measures with at most n points are computed using the Sinkhorn algorithm from [Sinkhorn] (1974), which provides an e-approximation at cost O(n2/e?) according to Lin et al. (2019). This implics
worst-case complexities of order O (EE) max( for node-Rieee and O || x zev max) for W
zev
edge-Ricci. In turn, large hyperedges have a stronger impact on the node-Ricci complexity.
To justify these theoretical claims, we consider a K-uniform hypergraph with 1000 nodes and 300 edges of length K drawn uniformly at random. We report. the computational times in seconds for single Ricci-flow interation in Figure G Computations are carried out for unweighted clique and line expansions and are averaged over five different hypergraph initializations. We observe that the computational cost of nodes- Ricci curvature indeed blows up for hyperrapphs with large hyperedges due to the inflated neighborhood size [V()). Edge-Ricci flow demonstrates much slower growth in computational time, remaining efficient even for hypergraphs with large hyperedges. Computations are executed on a single 8-core laptop with a Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz processor unit. These computations explain why only edge-Ricci could produce results in a reasonable time on the Mushroom dataset. Although this dataset has relatively few hyperedges, the hyperedges are exceptionally large, inducing severe computational challenges for node-Ricci flow.
Comparison on real data We now compare the two notions of Ricci flow the modularity--ased clustering. As they involve solving many optimal transport problems, flow-based methods appear to be
14

---

Published in Transactions on Machine Learning Research (10/2025)
Dataset
Cora-C
Pubmed
NTU2012
Zoo
Modularily 150.1
298
40.1
0.9
N-Rieci
7890
48.8
7.4
E-Ricci 296
31500
40.5
17.7
Table 2:
Computational time on real data (in seconds)
quite costly in practice. We report computational times for N 20 flow iterations in Table 2 For datasets which typically have nodes with large stars (especially citation datascts), the computational performance of RiceiRiccii can be vattavantsgeous in some cases when compared to modularity node-Ricci. The times from Table together with the quantitative results from Table indicate that Ricci-flow based methods are more suited to dealing with rather small hypergraphs to extract fine information on them.
4.5 upap-up, comparison of Node-Ricci and Edge-Ricci flows
Based the findings from Sections 3.3 and node-Ricci and edge-Ricci flows complementary approaches for competilive hypergraph clustering. Indeed, as the first one primarily leverages the clique expansion and the second one the line expansion information, taken together, they capture most of the information of the hypergraph. More precisely, edge-Ricci is preferable to node-Ricci whenever:
There are many small communities.
The intma-community edges are typically smaller than inter-community edges.
The hypergraph has very large hyperedges, inducing prohibitive computations on the clique graph.
When dealing with real data with no structural priori the communities, both methods tend perform comparatively, Section 4.2 However, they can have sensibly different computational costs making preferable over the other depending on the structure of the hypergraph, in particular the number of hyper- edges and their size. We note that alternating between itcrations of node-Rice flow and edge- Ricci flow did not provide any substantial quantilative benefit.
Conclusion
We have developed two methods to extend Ricci flow to hypergraphs. The first method, node-Ricci flow, applics standard Ricci flow on the clique expansion and further aggregates it to hyperedges. The sccond method, RiceiRicci flow, is the main contribution of this article and constitutes an original approach to transporting edges using the line expansion. Both methods define new weights on the hyperedges, which can then be simply turned into a partitioning algorithm. Each method has its own advantages depending on the specific characteristics of the hypergraph.
A natural extension of this work would be to consider co-optimal transport of both nodes and edges, discussed in Tiitouan et al. (2020); Chowdhury et al. (2024). Additionally, the notion of discrete Ricci flow has more practical uses beyond graph partitioning. For instance, it can be used as method to preprocess hypergraphs by generating new weights that better highlight underlying community structures, as seen in Khodaci ct al. (2024). Finally, several notions of curvature have been developed for graph, as explored in Iyer et. al. (2024b; Cushing et al. (2022). Further exlending these notions to hypergraph data constitutes a potential research direction.
References
Abbe, E. (2018). Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18117)):1-86.
Antelmi, A., Cordasco, G., Polato, M., Scarano, V., Spagmuolo, C., and Yang, D. (2023). survey on hypergraph representation learning. ACM Computing Surveys, 36(1):1-38.
15

---

Published in Transactions on Machine Learning Research (10/2025)
Bandyopadhyay, S., Das, K., and Murty, M. N. (2020). Hypergraph attention isomorphism network by learning line graph expansion. In 2020 TEEE International Conference on Big Data (Big Dala), pages 669 678. IEEE.
Bauer, F., Jost, J., and Liu, S. (2011). Ollivier-rieci curvature and the spectrum of the normalized graph laplace operator. arXiv preprint arXi::1105.380..
Berge, C. (1984). Hypergraphs: combinatorics of fonite sets, volume 45, Elsevier.
Bretto, A. (2013). Hypergraph theory. An introduction. Mothematical Engineering. Cham: Springer, 1.
Carriere, M. and Blumberg, A. (2020). Multiparameter persistence image for topological machine learning. Advances in Newral Information Processing Systems, 33:22432 22444.
Çatalyürek, U., Devine, K., Faraj, M., Gottesbüren, L.., Heuer, T., Meyerhenke, H.,, Sanders, P., Schlag, S., Schulz, C., Scomaier, D., et al. (2023). More recent advances in (hyper) graph partitioning. ACM Compuling Surveys, 55 (5(1))11-38 38.
Chitra, U. and Raphael, B. (2019). Random walks on hypergraphs with edge-dependent vertex weights. In International conference on machine learning, pages 1172 1181. PMLR.
Chowdhury, S., Needham, T., Semrad, E., Wang, B., and Zhou, Y. (2024). Hypergraph co-optimal transport: Metric and categorical properties. Journal of Applied and Computational Topology, 8(5):1171-133 -1230.
Chung, F. R. and Lu, L. (2006). Compler graphs and networks. Number 107. American Mathematical Soc.
Coupette, C., Dalleiger, S., and Rieck, B. (2022). Ollivier-ricci curvature for hypergraphs: A unified frame- work. arXiv preprint orXiv:2210.120.
Cushing, D., Kamtue, S., Liu, S., and Peyerimhoff, N. (2022). Bakry-émery curvature on graphs as an cigenvalue problem. Calculus of Variations and Partial Differential Equations, (2):662
Davis, G. (1941). Gardner, Deep South.
Dotson, G. A., Chen, C., Lindsly, S., Cicalo, A., Dilworth, S., Ryan, C., Jeyarajan, S., Meixner, W., Stansbury, C., Pickard, J., et al. (2022). Deciphering multi-way interactions in the human genome. Nature Communications,, 13(1):5498.
Eidi, M. and Jost, J. (2020). Ollivier ricci curvature of directed hypergraphs. Scientific Reports, 10(1):12466.
Eyubov, K., Faraj, M. F., and Schulz, C. (2023). Freight: Fast streaming hypergraph partitioning. arXiv preprint ar 2xXiv:2002.000
Feng, Y., You, H., Zhang, Z., Ji, R., and Gao, Y. (2019). Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3558-3565.
Forman (2003). Bochner's method for cell complexes and combinatorial ricci curvature. Discrete & Compu- tational Geometry,
Grover, A. and Leskovec, (2016). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864.
Hacquard, O. and Lebovici, V. (2024). Euler characteristic tools for topological data analysis. Journal of Machine Learning Research, 25(24)):1-39.
Hayashi, K., Aksoy, S. G., Park, C. H., and Park, H. (2020). Hypergraph random walks, laplacians, and clus- tering. In Proceedings of the 29th acm international conference on information & knowledge managemend, pages 495-504.
Hein, M., Setzer, S., Jost, L., and Rangapuram, (2013). The total variation on hypergraphs--eerming hypergraphs revisited. Advances in Neural Information Processing Systems, 26.
16

---

Published in Transactions on Machine Learning Research (10/2025)
Huang, J., Chen, C., Ye, F., Wu, J., Zheng, Z., and Ling, G. (2019). Hyper2vec: Biased random walk for hyper-network embedding. In Database Systems for A Advanced Applications: DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Chiang Mai, Thoiland, April 22 25, 2019, Proceedings 24, pages 277.277. Springer.
Iyer, R., Wang, Y., Wang, W., and Sun, Y. (2024). Non-cuclidean mixture model for social network embed- ding. Advances in Neural Information Processing Systems, 4444-114488
Kamiñikki, B., Misiorek, P., Pralat, P., and Théberge, F. (2024). Modularity based community detection in hypergraphs. Journal of Complex Nelworks, 12(5))enae041.
Kamiński, B., Pratat, P., and Théberge, F. (2021). Community detection algorithm using hypergraph mod- ularity. In Complex Networks & Their Applications IX: Volume 1, Proceedings of the Ninth International Conference on Complez Networks and Their Applications COMPLEX NETWORKS 2020, pages 152-163. Springer.
Khodaei, M., Bidabad, B., Shiri, M. E., Sedaghat, M. K., and Amirifard, H. (2024). Classification of alzheimer's disease using ricci flow-based spherical parameterization and machine learning techniques. Signal, Image and Video Processing, 18(10):6529 6545.
Kim, C., Bandeira, A. S., and Goemans, M. X. (2018). Stochastic block model for hypergraphs: Statistical limits and a semidefinite programming approach. arxiv preprint arXiv:1807.028: 02884.
Kim, S. and Kirkland, S. (2022). Gram mates, sign changes in singular values, and isomorphism. Linear Algebra and its Applications, 644:108-148.
Kirkland, S. (2018). Two-mode networks exhibiting data loss. Journal of Complex Networks, 6(2):297 316.
Klamt, S., Haus, U.-U., and Theis, F. (2009). Hypergraphs and cellular networks. PLoS computational biology, 5(5):c10
Konstantinova, E. V. and Skorobogatov, V. A. (2001). Application of hypergraph theory in chemistry. Discrete Mathematics, 235(1-3):365-383
Kumar, T., Vaidyanathan, S., Ananthapadmannban, H., Parthasarathy, S., and Ravindran, B. (2020). A new measure of modularity in hypergraphs: Theoretical insights and implications for effective clustering. In Complez Networks and Their Applications VIlI: Volume Proceedings of the Eighth International Conference Complez Networks and Their Applications COMPLEX NETWORKS 2019 8, pages 286- 297. Springer.
Leal, W., Restrepo, G., Stadler, P. F., and Jost, J. (2021). Forman ricci curvature for hypergraphs. Advances in Complex Systems, 24(01):2150033.
Lee, D. and Shin, K. (2023). I'm me, we're us, and i'm us: Tri-directional contrastive learning on hypergraphs. Proceedings of the AAAT Conference on Artificial Intelligence, volume 37, pages 1456-8464.
Lee, G., Choe, M., and Shin, K. (2022). Hashnwalk: Hash and random walk based anomaly detection in hyperedge streams. arXiv preprint arxi::2204 13882.
Lin, T., Ho, N., and Jordan, M. (2019). On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. In International Conference on Machine Learning, pages 3982 3991. PMLR.
Lin, Y., Lu, L., and Yau, S.T. (2011). Ricci curvature of graphs. Tohoku Mathematical Journal, Second Series, 63(4):605-625
Lin, Y. and Yau, S.-T. (2010). Ricci curvature and eigenvalue estimate on locally finite graphs. Mathematical research letters, 17(2):343-355 356.
Liu, X., Feng, H., Wu, J., and Xia, K. (2021). Persistent spectral hypergraph based machine learning (psh-ml) for protein-ligand binding affinity prediction. Briefings in Bioinformatics, 22
17

---

Published in Transactions on Machine Learning Research (10/2025)
Newman, M. E. (2006). Modularity and community structure in networks. Proceedings of the national acndemy of sciences, 103((3))8577-8888 8582.
Ni, C.-C., Lin, Y.-Y., Gao, J., Gu, X. D., and Saucan, E. (2015). Ricci curvature of the internet topology. In 2015 IEEE conference computer comamanications (INFOCOM), pages 2758 2766. IEEE.
Ni, C.-.,, Lin, Y.Y.,, Luo, F., and Gao, J. (2019). Community detection on networks with ricci flow. Scientific reports, 9(1):9984.
Ollivier, Y. (2007). Ricci curvature of metric spaces. Comples Rendus Mathematique, 345(11):643 646.
Samal, A., Sreejith, R., Gu, J., Liu, S., Saucan, E., and Jost, (2018). Comparative analysis of two discretizations of ricci curvature for complex networks. Scientifie reports, 8(1):8650.
Santambrogio, (2015). Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-63):944
Sinkhorn, R. (1974). Diagonal equivalence to matrices with prescribed row and column sums. ii. Proceedings of the American Mathematical Sociely, 45(2):195-199
Sreejith, R.,, Mohanraj, K., Jost, J., Saucan, E., and Samal, A. (2016). Forman curvature for complex networks. Journal of Statistical Mechanics: Theory and Eaperiment, 2016(6):063206.
Tian, Y., Lubberts, Z., and Weber, M. (2025). Curvature-based clustering on graphs. Journal of Machine Learning Research, 26(52):1-65 67.
Titouan, V., Redko, I., Flamary, R., and Courty, N. (2020). Co-optimal transport. Advances in neural information processing systems, 33:17559-
Torres, L., Blevins, A. S., Bassett, D., and Eliassi-Rad, T. (2021). The why, how, and when of representations for complex systems. SIAM Review, 6333):435-485.
Van Der Hoorn, P., Cunningham, W. J., Lippner, G., Trugenberger, C., and Krioukov, D. (2021). Ollivier- ricci curvature convergence random geometric graphs. Physical Review Research, 3(1):01321
Veličković, P., Fedus, W., Hamilton, W. L., Liò, P., Bengio, Y., and Hjelm, R. D. (2018). Deep graph infomax. arx preprint ar arxiv:1800 1809.10341.
Yang, C., Wang, R., Yao, S., and Abdelzaher, T. (2022). Semi-supervised hypergraph node classification on hypergraph line expansion. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 2352 2361.
Zhang, J., Gao, M., Yu, J., Guo, L., Li, J., and Yin, H. (2021). Double-scale self-superviser hypergraph learn- ing for group recommendation. In Proceedings of the 30th ACM international conference on information knowledge management, pages 2557-2567.
Zhang, R., Zou, Y., and Ma, J. (2019). Hyper-sagnn: a self-attention based graph neural network for hypergraphs. arXie preprint
Zhang, X., Song. D., and Tao, D. (2023). Ricci curvaturo-based graph sparsification for continual graph representation ion learning. IEEE Trunsactions on Neural Networks and Learning Systems.
Zhou, Y., Rathore, A., Purvine, E.,, and Wang, B. (2022). Topological simplifications of hypergraphs. IEEE Transactions on Visualization and Computer Graphics, (9())3200 3225.
Zhu, Y., Xu, Y., Yu, F., Liu, Q Wu, S., and Wang, L. (2020). Deep graph contrastive representation learning. arXio preprint arXiv:2006, 04131.
18

---

Published in Transactions on Machine Learning Research (10/2025)
A
Proof of Proposition
We start by computing "X Let x and y be two non-gateway nodes from the same clique (x, y: u1,..., (0 ua-2).
We have that Si(ar) (x, ((,,,)).. mi).... (x, (a-2)) and Sl(y) (xr (y, (1y,,,).... (y, ua-2)) Each (x, u.) is adjacent to (y, u,) and at distance two from the others (v, Ug)pmi? The optimal way to transport the uniform probability measure on St(æ) \ (2,y) y) to the uniform probability measure on St(y) \ (z,y) is therefore to transport each (z, u,) to (v, ug), which are at a distance from each other. Each edge has weight 1/(a - 2) and there is a - 2 of them, (I) hence a total cost of 1. Hence by induction, since Wyy33 1, we have that W/,33
(!) 1 for all I.
For (()) let a and y be two distinct gateway-nodes, connected by the large hyperedge Es. We have St(x:) \ Eg = {(z uz)..... (z,, ua-1)} and St(y) \ E, {(y. oj)..... va-1)). (x.,)))) Each (I,u,) u,) is at distance at least 2 from a vy). Therefore, an optimal way to transport the uniform probability measure on St(x)) Es to the uniform probability measure on St(y) \ E, is to transport each (z, u,) to a corresponding us) via Es, such that the distance is exactly 2. This corresponds to path of length 2 on the line graph. Each edge has weight 1/(a-1) -1) and there is a - 1 of them, hence total cost of 2. As the cost is the same for each pair of nodes in Eg, the flow of Eb, is equal to that of any (1) pair (x, Es. We therefore have that WN,3 = 2 for all 1 2 1.
For (1)
WN.2. let be a gateway node and y and non-gateway node from the same clique We have St(x)) \ (xx, = {Es, (zz, uz),..., .,. (x, ua-2)} and St(y) \ (z,z)
(ar U. ",,,,,,.,--21.
[1y, u1)...., (v, ())))- We represent the line graph restricted to Sl(x) U St(w) (x. y) in Figure
S.1 We write the mass of each edge according to Equation where we write d; = w Mi to simplify
((-1)
the notation. We have just demonstrated that d1 = and d3 = 1. From Figure [S.1] it is clear than an optimal transport plan between f& and By transports the mass on each (x, uq) to (y, ux)- These edges are adjacent in the line graph. These (a ( 2) edges therefore occupy fraction of the total cost of (a-2)dg___
dg 2+(a-2)dg The mass 2-(a-2)dz on Eg is equally transported to each (y, u.) through the corresponding u;). Each (y. u,) is at a distance 2 from Es, see Figure S.1 This implics cost of 24(a-2)dy for transporting the mass at Eg. In the end, the total cost of transporting Pe to By is 4+ (2)d)2))2 This implies that
2dg
(+(a-2)d;
(1) + (a - 2) (1-1) 2x22 2 + (a 2) N
N
(1-1)*
We can easily prove by induction on / that for every L, WN E [1.
(1)
B Description of the datasets
The experiments from Section 4.2 have been conducted on these hypergraph datasets:
Co-citation datasets Cora-C, Citeseer and Pubmed where nodes represent research papers, edges papers co-citing these papers and the communities correspond to similar research thematic.
The dataset Cora-A has a similar structure but is a co-authorship dataset, where hyperedges repre- sent authors.
In the dataset Zoo, nodes are animals, edges represent mutual traits, and communtiiss are types of animals (mammal, fish...).
In the dataset Mushroom, nodes are mushroom samples, edges represent mutual traits, and there are two communities: edible and poisonous.
In the dataset NTU2012, nodes correspond to 3D objects, edges to proximity using image- processing features, and communities are the type of object.
19

---

Published in Transactions on Machine Learning Research (10/2025)
(x, u1)*
(y/ u1)"
(x, uz)*
u2))
E
(2+(a-2)d
(2r, Un-2)
(y. 2
de
dy+(a-2)d
(a (a-2)ds
Figure S.1: Restriction of the line graph to compute the flow between a gateway and a non-gateway node in
Proposition I
We refer to Table S.1 for quantitative description of each dataset.
Dataset
Cora-C
Cora-A A
Citeseer
Pubmed
Zoo
Mushroom
NTU2012
Nodes
1431
2388
1458
38/10
101
8121
2012
4 Hyperedges 1579
1072
1079
7963
43
298
2012
Avg. hyperedge size
3.0
4.3
3.2
4.4
39.9
136.3
5.0
Avg. node degree
3.3
1.9
2.4
9.0
17.0
5.0
5.0
f Communitics
7
3
2
Table S.1: Basic statistics of hypergraph data used in the experiments.
C Impact of the hyperparameters
Unless specified otherwise, we report the NMI in the synthetic set-up of Section 4.1 Results are averaged over 5 random hypergraph generation and comparison with the ground-truth is realized for the optimal cut-off parameter T²
Mcasure parameter p. In Figure S.2 we report the NMI for three values p 0, 1,2 for the nodes transport, compared with the edge transport. We set Agg to be the maximum function and consider a uniform weighting of the clique graph. We p= 0, while p = and 2 display similar performances.
that in some cases, there is clear drop of accuracy for
we report the NMI for a few specific critical values of 8in, Sout, Nin, Nout- These results are obtained for = for the node transport. We set Agg to be the maximum function and consider a uniform weighting of the clique graph. We can see that these critical cases, the parameter a can play a very big impact. It is difficult to provide any generic guideline, but extreme values of to provoke instabilities some cases.
Measure parameter a. In Figure S.3
Aggregation and clique graph weighting In Figure S.4 report the NMI in the synthetic set-up of Section 4.1 where we simultancously compare the effect of the clique graph weighting and the curvature aggregation at the hyperedge level. We compare the four possible combinations, where the clique graph can have either a Jaccard or a uniform weighting, and Agg can either the maximum or the arithmetic average. We do not notice any significant difference between the two types of clique graph weightings. However, we observe that using the maximum pairwise curvature instead of the average yields similar to much better results and should therefore always be preferred.
20

---

Published in Transactions on Machine Learning Research (10/2025)
14
10-
Sin 2, Sout
(b) Sin Sout
(c) 8in Sout
2014
(d) 8in
2, Sout
(e) 8in
3, Sout
(f) 8in 4, Sout 5
Figure S.2: Study on the impact of the paramcter p to cluster hypergraph stochastic block models.
(a) 8in 3, Sout
(b) 8in
3, Sout
(c) 8im
3, Sout
Figure S.3: Study on the impact of the parameter a to cluster hypergraph stochastic block models
1.0
(8) 8in 2, Bout
(b) 8in 3, Bout
(c) Bin = 5, Bout
Figure S.4: Study on the impact of the clique graph weighting and the aggregation function to cluster hypergraph stochastic block models with node-Ricci flow
21

---

Published in Transactions on Machine Learning Research (10/2025)
Aggregation and line graph weighting In Figure S.5 we report the NMI in the synthetic set-up of Section 4.1 where we simultaneously compare the effect of the line graph weighting and the curvature aggregation at the hyperedge level. We compare the four possible combinations, where the line graph can have either a Jaccard or a uniform weighting, and Agg can be either the maximum or the arithmetic average. The differences can be very signíficative, in particular between the combinations Jaccard-maximum and Uniform-average. Overall, we observe that the former provides a much better clustering accuracy whenever Sin S Sout while the latter is better when Sin > Sout- However, we observe in Figure [S.6] that in this case, edge-Ricci flow with any parameter still underperforms compared to node-Rieci flow, which is particularly adapted to dealing with the situation of large intra-community hyperedges and small inter- community hyperedges. We consider a node-Ricci flow with parameters Jaccard-maximum. As a result, we claim that the parameter combination Uniform-average for edge-flo should never be preferred as it will always be beaten by either the mexeamdd edge-flow or by the node-Ricci flow.
Ryprape UD of
syper 1iM,, onger
The
(a) Sin 2, Sout 4
(b) 8in 4, Sout 2
(c) Siy Nout 4
Figure S.5: Study on the impact of the line graph weighting and the aggregation function to cluster hyper- graph stochastic block models with adge--Rice flow
14
(a) Sin 2, Sout 4
(b) 8in 4, Bout 2
(c) Sin 5, Bout 3
Figure S.6: Comparison of seccard-maximun and Uniform-average edge-Ricci flow with node-Ricci flow.
Joint study of every hyperparameter on a real datasct. We study the impact of all paramoters except a and T for the clustering task on the dataset NTU2012. The clustering accuracies are reported for the optimal r* Results are reported in Tables S.2 and S.3 We can see that in this real data case, The choice of the weights for the clique graph and the line graph has a negligible impact. For both types of Ricci flow, considering the maximum curvature over the average one has tremendous impact. In addition, we can observe an improvement by considering p = 1 over p = 0. For p 2, numerical instabilities prevented the code from compiling.
Threshold parameter 7 We now try to assess the estimation of the 7* parameter providing the highest clustering accuracy. We compare the NMI obtained by trimming edges with a flow greater than 7* with the NMI obtained with Ta and Te. We report the results for the clustering of the datasets NTU2012 and Zoo in Tables S.4 and S.5 Based the previous findings, considered a Jaccard weighting, a hyperedge
22

---

Published in Transactions on Machine Learning Research (10/2025)
Aggregation
Clique graph weights
p
NMI
Max
Jaccard
79.7
Max
Uniform
79.7
Average
Jaccard
0
69.1
Average
Uniform
69.1
Max
Jaccard
82.1
Max
Uniform
82.5
Average
Jaccard
69.1
Average
Uniform
69.1
Table S.2: Node-Ricci flow clustering of the NTU2012 dataset for various sets of hyperparameters
Aggregation
Clique graph weights
NMI
Max
Jaccard
80.2
Max
Uniform
80.2
Average
Jaccard
69.1
Average
Uniform
69.1
Table S.3: Edge-Ricci flow clustering of the NTU2012 dataset for various sets of hyperparameters
aggregation with the max function, and for the nodes transport. On the NTU2012 dataset, observe better performance using the hypergraph notion of modularity over the clique graph modularity. The loss of accuracy for Edge-Ricei flow is milder than for Node-Ricel flow when using an approximate T parameter. For the Zoo dataset, we observe a very strong difference between the two notions of modularity, as considering the hypergraph modularity yiclds the optimal clustering, while the modularity on the clique graph gives extremely poor results. This has to be paralleled with the results from Table 1 where methods relying only the clique graph expansion provided very unsatisfactory results.
Type of flow
r²
TC
Nodes
82.1
76.3
72.3
Edges
80.2
77.6
75.2
Table S.4: NMI for various choices of r on the NTU2012 dataset.
Type of flow
r*
Nodes
96.2
96.2
18.3
Edges
100
100
18.3
Table S.5: NMI for various choices of on the Zoo dataset
23


Reviews:
[{"review_id": "1ChAxwoOqA", "reviewer": "Reviewer_Afr5", "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\n- The paper is written in a clear manner. The explicit example computing edge-Ricci curvature is nice.\n\n- Conclusions drawn from experiments, and explicit examples, distinguishing between node and edge-Ricci curvature are nice. The submission includes an experiment using Ricci flow to recover communities from a hypergraph analogue of the stochastic block mode. Results seem to suggest that node-Ricci performs better when the size of intra-community hyperedges are larger than the size of inter-community edges. A number of other experiments are included to study sensitivity of Ricci flow to hyperparameters.\n\n- Work which defines different notions of (hyper)graph-theoretic curvature and provides a substantial number of explicit examples, and experiments would be of great interest theoretically. Understanding what Markov processes defined over graphs in which clustering via Ollivier-Ricci curvature admits approximation algorithms with provable worst-case guarantees is a difficult question. There is some hope that these techniques can yield qualitatively different algorithms whose approximation guarantees match state-of-the-art for partitioning problems like sparsest cut. The definitions of node-Ricci and edge-Ricci are novel contributions towards this direction.\n\nWeaknesses \n\nThere does not seem to be a strong reason to prefer partitioning via Ricci flow over other baseline methods.\n\n- The submission’s claim that Ricci flow is highly explainable does not seem to be supported by clear evidence. There are no experiments targeting explainability. Further, from a theoretical perspective, I think it is still up to debate whether current notions of discrete Ricci curvature *always* capture cluster structure of graphs. As an example: it is known that bounded degree expanders with non-negative Ollivier-Ricci curvature do not exist [2]. Mixing time bounds implied by positive Ollivier-Ricci curvature then do not immediately apply. Yet, the standard random walk rapidly mixes on expanders. If one were to take a uniformly sampled $d$-regular graph (for $d = O(1)$), then in some sense, Ollivier-Ricci curvature would be sensitive to the fact that neighborhoods are ``locally tree-like’’. On the other hand, $G$ is w.h.p. an expander; it is well-connected so the entire graph could be treated as a single cluster.\n\n- It is not clear to what extent current theoretical results concerning Ollivier-Ricci curvature for Markov processes over metric spaces apply to edge-Ricci curvature because the two definitions seem qualitatively different. The quantity which needs to be defined in Ollivier-Ricci curvature,\n\n  $$\n  1 - \\frac{W(\\mathfrak{m}^{\\epsilon}\\_{x}, \\mathfrak{m}^{\\epsilon}\\_{y})}{\\rho(x, y)}\n  $$\n\n  considers Wasserstein distance to scale as the metric distance. This is also the case for the definition of Ricci curvature in [1]. On the other hand, edge-Ricci curvature is defined so that Wasserstein distance scales as the diameter of the hyperedge,\n\n  $$\n  \\kappa_{\\mathcal{E}}(u, v) = 1 - \\frac{W(\\mu\\_{u}, \\mu\\_{v})}{\\max_{e \\in \\partial u \\cap \\partial v} w_{e}}\n  $$\n\n  The additional aggregation step used to define curvature for the hyperedges themselves make it difficult to ascertain if theoretical results apply.\n\n- Performance on clustering real world data seems a bit weak relative to other baseline methods. I think this is important to note, though it is not one of my primary concerns.\n\nFinally, The discussion regarding clique and line expansion seems to suggest two items: \n\n- edge-Ricci curvature captures hyperedge structure that is lost when node-Ricci curvature gets defined as the Ollivier-Ricci curvature associated with the clique expansion of the hypergraph\n\n- edge-Ricci curvature and node-Ricci curvature are complementary in that it might give a complete description of hyperedge structure: “taken together, they capture most of the information of the hypergraph” (section 4.5)\n\nThere does not seem to be comprehensive enough study of what structure is actually captured, let alone what structure means, by these two notions of curvature to make such a broad claim.\n\n[1] Ni, Chien-Chun, Yu-Yao Lin, Feng Luo, and Jie Gao. \"Community detection on networks with Ricci flow.\" Scientific reports 9, no. 1 (2019): 9984.\n\n[2] Salez, Justin. \"Sparse expanders have negative curvature.\" Geometric and Functional Analysis 32, no. 6 (2022): 1486-1513.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "The present submission studies hypergraph partitioning methods based on discrete Ricci curvature. Its primary contributions are:\n\n- A new notion of Ricci-Ollivier curvature for hypergraphs, which the authors call *edge-Ricci curvature*. This is given by the Wasserstein distance between two measures supported over hyperedges.\n- A generalization of a preexisting notion of Ricci-Ollivier curvature for graphs [1] to the hypergraph setting, which they call *node-Ricci curvature*. This is given by the Wasserstein distance between two measures supported over vertices.\n- A number of experimental results which illustrate certain cases where partitioning using their notions of curvature may be preferable over preexisting methods.\n\nTo explain their notion of curvature, we briefly describe Ollivier’s formulation of Ricci curvature. In [2] (Example 7), Ollivier notes the following connection between Ricci curvature and Wasserstein distance.\n\nLet $(X, \\rho)$ be a complete, $N$-dimensional Riemannian manifold and fix a constant $\\epsilon > 0$. For every $x \\in X$, define the measure \n\n$$ \n\\mathfrak{m}^{\\epsilon}_{x}(A) \n= \\frac{\\textup{vol}(A \\cap B(x, \\epsilon)}{\\textup{vol}(B(x, \\epsilon))}\n\\qquad\\qquad\n\\forall \\\\, A \\textup{ measurable w.r.t. vol}(\\cdot)\n$$\n\nwhere $\\textup{vol}(\\cdot)$ is the standard Riemannian volume, and $B(x, \\epsilon)$ is the geodesic ball of radius $\\epsilon$ centered at $x$. Think of this as the following random walk process: starting from $x$, jump to a uniformly random point $y$ within geodesic distance at most $\\epsilon$. Then\n\n$$\n1 - \\frac{W(\\mathfrak{m}^{\\epsilon}\\_{x}, \\mathfrak{m}^{\\epsilon}\\_{y})}{\\rho(x, y)} \n= \\frac{\\epsilon^2}{2 (N + 2)} \\cdot \\Big(  \\textup{Ric}(v, v)  + O(\\epsilon) + O\\big( \\rho(x, y) \\big) \\Big)\n$$\n\nwhere $v$ is a unit tangent from $x$ to $y$, $\\textup{Ric}(v, v)$ is the contraction of the Ricci curvature tensor with $v$, and $W(\\mathfrak{m}\\_{x}, \\mathfrak{m}\\_{x})$ is the Wasserstein distance associated with using $\\rho(x, y)$ as the cost function. \n\nThe key insight is that the left-hand side is fully specified so long as one has a metric space where each point is associated with a measure. Consequently, one can bootstrap this identity for a definition of curvature that is purely measure-metric theoretic so that it applies to discrete (e.g. graph-theoretic) settings.\n\nThe authors define a notion of Ricci curvature for hypergraphs called **edge-Ricci curvature**. Let $G = (V, E, \\mathbf{w})$ be a weighted hypergraph, so that $E \\subseteq V$ are hyperedges with non-negative weights $w_{e} > 0$. For every vertex $v \\in V$, let $\\mu_{v}(e)$ be the distribution where the probability of $e$ is proportional to $w_{e}$ only if $e$ is adjacent to $v$, and zero otherwise. That is,\n\n$$\n\\mu_{v}(e) = \\begin{cases}\n& w_{e} / Z\n& & \\textup{if } e \\in \\partial v \\\\\\\\\n& 0 \n& & \\textup{otherwise}\n\\end{cases}\n\\qquad\\qquad\n\\forall \\\\, v \\in V\n$$\n\nwhere $\\partial v \\subseteq E$ is the set of hyperedges adjacent to $v$, and $Z$ is a normalization factor. The edge-Ricci curvature *between two adjacent nodes* $u, v \\in V$ is then \n\n$$\n\\kappa_{\\mathcal{E}}(u, v) = 1 - \\frac{W(\\mu\\_{u}, \\mu\\_{v})}{\\max_{e \\in \\partial u \\cap \\partial v} w_{e}}\n$$\n\nand the edge-Ricci curvature for a _hyperedge_ $e \\in E$ is \n\n$$\n\\kappa_{\\mathcal{E}}(e) = \\textup{Agg}\\_{u, v \\in e} \\Big( \\kappa\\_{\\mathcal{E}}(u, v) \\Big)\n$$\n\nHere, $\\textup{Agg}$ is a manner of aggregating the curvature between pairs of vertices in the same hyperedge, for example by averaging. \n\nThe authors use this notion of curvature to partition hypergraphs in the following manner. Consider the diffusion process, which they call **edge-Ricci flow**:\n\n$$\nw^{(t+1)}\\_{e} = \\Big( 1 - \\kappa^{(t)}\\_{\\mathcal{E}}(e) \\Big) \\cdot w^{(t)}\\_{e}\n$$\n\nwhere $w^{(0)}\\_{e} = w\\_{e}$ and $\\kappa^{(t)}\\_{\\mathcal{E}}(e)$ is the edge-Ricci curvature computed using $w^{(t)}\\_{e}$ as hyperedge weights. After running edge-Ricci flow for a fixed number of steps, remove all edges whose weights are above a prefixed threshold $\\tau$, then output all disconnected components as clusters. \n\nThe intuition for this matches that of Riemannian manifolds: regions with negative Ricci curvature locally expand “outwards”, whereas regions with positive curvature concentrate “inwards”. If one wanted to parsimoniously separate a hypergraph, then it seems reasonable to remove hyperedges with negative curvature.\n\n[1] Ni, Chien-Chun, Yu-Yao Lin, Feng Luo, and Jie Gao. \"Community detection on networks with Ricci flow.\" Scientific reports 9, no. 1 (2019): 9984.\n\n[2] Ollivier, Yann. \"Ricci curvature of Markov chains on metric spaces.\" Journal of Functional Analysis 256, no. 3 (2009): 810-864.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical items\n\n- Can you provide more evidence that clustering using these definitions of Ricci curvature is theoretically grounded? For example, what’s the choice of metric space and Markov process so that the definition of Ollivier-Ricci curvature in [3] recovers node and edge-Ricci curvature? It need not exactly recover the definitions in this submission, something similar enough to would be greatly helpful.\n\n- Can you clarify what hyperedge structure is captured by edge-Ricci curvature for which defining curvature w.r.t. the clique expansion erases? For example, can you compute out that node curvature is substantially different from $\\kappa\\_{\\mathcal{E}}(u, v)$ for pairs of vertices $u, v$ in graphs (a) and (b) from figure 1?\n\n- There are fairly performant solvers for optimal transport [2, 4]. This is also the primary computational bottleneck when computing different notions of discrete curvature. Do you know how wall-clock time required to partition via Ricci flow compares to the baseline methods you considered in section 4.2? Some experiments in this domain would be nice.\n\nSmaller items \n\n- Can you clarify what the sample procedure for your version of the stochastic block model in section 4.1 is? The submission’s description seems to parameterize the model differently than [1]\n- Why is the distance $d_{H}$ introduced right before edge-Ricci curvature is defined? Was this supposed to be included in the definition somehow? Additionally, why not write $d_{L(G)}$ instead of $d_{LG}$ since it is already introduced that $L(G)$ denotes the line graph associated with $G$.\n\nNits\n\n- “unless the nodes are assined” (pg. 3) -> assigned\n- Should the sum in the sentence “More precisely, a discrete transport plan $T$...” (pg. 5) be a sum in $T$ and not $A$?\n- “Table S.1” (pg. 13) incorrectly links to figure S.1 on pg. 19\n- In section 4.3, “The number of flow iterations $N$” can you report the epsilon used for convergence?\n- Can you place error bars for the plots reported in figure 5?\n- $\\mathbf{C}(H)$ is used to denote the clique expansion (pg. 3) but $\\mathbf{C}$ is used to denote the collection of clusters for $H$ (pg. 4)\n- The definition of the modularity score (pg. 4) uses capital $K$ as the number of clusters, whereas elsewhere in the paper, lowercase $k$ is used to denote the number of clusters (section 4.1).\n- Equation 1 (pg. 4) uses $d$ to denote the shortest path distance between vertices. Then, $d$ is used to denote the weight of hyperedges when defining edge-Ricci curvature (pg. 7). Maybe this is by design, but it seems a bit weird.\n\n[1] Kim, Chiheon, Afonso S. Bandeira, and Michel X. Goemans. \"Stochastic block model for hypergraphs: Statistical limits and a semidefinite programming approach.\" arXiv:1807.02884 (2018).\n\n[2] Lin, Tianyi, Nhat Ho, and Michael I. Jordan. \"On the efficiency of entropic regularized algorithms for optimal transport.\" Journal of Machine Learning Research 23, no. 137 (2022): 1-42.\n\n[3] Ollivier, Yann. \"Ricci curvature of Markov chains on metric spaces.\" Journal of Functional Analysis 256, no. 3 (2009): 810-864.\n\n[4] Tupitsa, Nazarii, Pavel Dvurechensky, Darina Dvinskikh, and Alexander Gasnikov. \"Numerical methods for large-scale optimal transport.\" arXiv:2210.11368 (2022).", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sZn1w46bRr", "reviewer": "Reviewer_o3BN", "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- Experiments are extensive, highlighting the strengths and weaknesses of node-based and edge-based Ricci flows for hypergraph clustering.  In addition, ablation on the various hyperparameters properly justifies the design choices made for the models.\n- The writing is fairly easy to follow overall (aside from some details describing the methodology, see below). In particular, the authors identify and make clear in which settings one should use the Node vs. Edge-Ricci flows.\n\n__Weaknesses:__\n- Some details of the Edge-Ricci curvature can be explained better (see __Requested Changes__ below).\n- The quality of the figures can be improved. For example, the labels in most of the figures are too small to see without zooming in. In Figure 5, it would also be more useful if the ranges of the y-axis are fixed (e.g. fix between 0.2 and 1.1).", "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": "The paper aims to define a notion of Ricci curvature and the corresponding Ollivier-Ricci flow for hypergraphs, with applications to node clustering. For this purpose, the authors introduce Ricci curvature based on the clique graph of the hypergraph, in addition to a novel _Edge-Ricci curvature_, which directly parallels the definition of the usual Ricci curvature, except that it is defined using probability measures defined on the hyperedges. Experiments on synthetic and real data show the ability of the two notions of Ricci curvatures and the corresponding Ricci flows to successfully carry out clustering, achieving competitive results to state-of-the-art algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The authors make a point that one of the Edge-Ricci curvature is that there is no need to tune the hyperparameters $\\alpha, p$ that appear in the discrete Ricci curvature. However, I am confused why we couldn't also introduce these hyperparameters in the definition of the Edge-Ricci curvature in the first place.\n- When introducing the definition of the Ricci curvature, I would suggest making it explicit that the Wasserstein distance used here is for $p=1$ to avoid confusion.\n- In the definition of the Edge-Ricci curvature, how are the dissimilarity weights $d$ chosen? Does the Jaccard index give this? I would ask the authors to be more explicit about this.\n- It would be useful to have a brief sentence explaining how the Wasserstein distance $W(\\mu_x, \\mu_y)$ is defined for edge measures. From the context, I expect this is just given by replacing the distance $d(u, v)$ with the distance $d_H(e, f)$, but again,In the df I would suggest being more explicit.\n- For the Edge-Ricci curvature $\\kappa_{\\mathcal{E}}(x, y)$, how is this defined when $St(x) \\cap St(y) = \\varnothing$? What value do we take for the denominator in $\\frac{W(\\mu\\_x, \\mu\\_y)}{\\max\\_{e \\in St(x) \\cap St(y)} d(e)}$?", "broader_impact_concerns": "There are no immediate ethical concerns as far as I can see.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cYHdEkLB31", "reviewer": "Reviewer_sY6W", "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\nGood discussion of the limitations of reducing hypergraphs to graphs, particularly the clique expansion\n\nIllustrations of clique and line expansions are helpful\n\nThe discussion of the threshold parameter and \\tau_H being more useful than \\tau_C is an interesting finding\n\nWeaknesses\n\nMethod seems like a relatively minor variant on existing methods essentially just using the line expansion rather than clique expansion\n\nBaseline results are “as reported in other papers.” Rerunning the experiments would be better in an ideal world to ensure consistent experimental set up although I understand this is not always possible", "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 novel hypergraph clustering mechanism. It constructs a Ricci flow on the hyperedges. This essentially corresponds to looking at the Ricci Curvature on the line expansion and then running standard methods. \n\nNumerical methods are not particularly strong, as the proposed method is out performed on a majority of data sets. Moreover, the method is somewhat limited in its novelty since it essentially substitutes the line expansion in place of the clique expansion.\n\nNevertheless, I do deem this an approach that is interesting and worth exploring and the proposed method does seem to be advantageous in certain settings. Therefore,  in the context of the stated goals of TMLR, I will lean toward acceptance after the requested edits are made.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Page 5: “It instantly appears that trimming edges of low curvature”… please add more detail\n\nPage 6: “The first solution …. “ please rephrase this sentence for clarity. It is not clear what you mean you are solving\n\nThe claim that the model achieves “overall competitive accuracy” seems like a bit of an oversell. Please amend your language. It does perform well in certain settings, but it is far from the top on the vast majority of data sets.\n\nAppendix A – Add more details to the proof. How do we know that those transport plans are optimal?\n\nMinor\n\nPage 1: The phrase “metric spaces and later adapted to graphs” seems strange since graphs are metric spaces. Please clarify\n\nPage 3: “assined”\n\n\nPlease address the following questions\n\nPage 3: “can be expressed on a reweighted clique expansion” should this be “can’t?”\n\nPage 8: “binary graphs” does this refer to 2-regular graphs? \n\nPage 9: What is the intuition behind this synthetic cluster model? Are there settings where it is realistic?\n\nPage 10: In the hypergraph SBM, is there a single fixed s_in and s_out? If so, does this present a significant limitation? Can the model be made more flexible?\n\nPage 10: Is the take away from the discussion of SBM that edge-based is better in noisy settings and that node-based is better in low-noise settings? Please be more explicit on this", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)