Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework
Authors: Corinna Coupette
Sebastian Dalleiger
Bastian Rieck
Venue: ICLR 2023 poster (2023)
Keywords: curvature
hypergraphs
graphs
Wasserstein distance
topological data analysis
random walks
probability measure

Abstract: Bridging geometry and topology, curvature is a powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, the Ollivier-Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept in ideas from probability theory and optimal transport. We develop Orchid, a flexible framework generalizing Ollivier-Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments on synthetic and real-world hypergraphs from different domains, we demonstrate that Orchid curvatures are both scalable and useful to perform a variety of hypergraph tasks in practice.

Published as a conference paper at ICLR 2023
OLLIVIER-RICCI CURVATURE FOR HYPERGRAPHS: A UNIFIED FRAMEWORK
Corinna Coupette', Sebastian Dalleiger': Bastian Rieck 3,4
I Max Planck Institute for Informatics
2CISPA Helmholtz Center for Information Security
BAIDOS Lab, Institute of AT for Health, Helmholtz Munich *Technical University of Munich (TUM)
ABSTRACT
Bridging geometry and topology, curvature is powerful and expressive invariant. While the utility of curvature has been theoretically and empirically confirmed in the context of manifolds and graphs, its generalization to the emerging domain of hypergraphs has remained largely unexplored. On graphs, the Ollivier-Riae Ricci curvature measures differences between random walks via Wasserstein distances, thus grounding a geometric concept ideas from probability theory and optimal transport. We develop ORCHID, flexible framework generalizing Ollivier-Riie Ricci curvature to hypergraphs, and prove that the resulting curvatures have favorable theoretical properties. Through extensive experiments synthetic and real-world hypergraphs from different domains, we demonstrate that ORCHID curvatures are both scalable and useful to perform variety of hypergraph tasks in practice.
INTRODUCTION
Hypergraphs generalize graphs by allowing any number of nodes to participate in an edge. They enable us faithfully represent complex relations, such as co-authorship of scientific papers, multi- lateral interactions between chemicals, or group conversations, which cannot be adequately captured by graphs. While hypergraphs are more expressive than graphs and other relational objects like sim- plicial complexes, they are harder to amalyze both theoretically and empirically, and many concepts that have proven useful for understanding graphs have yet to be transferred to the hypergraph setting.
Curvature has established itself as powerful characteristic of Riemannian manifolds, as it permits the description global properties through local measurements by harmonizing ideas from geome- try and topology. For graphs. graph curvature measures to what extent the neighborhood of an edge deviates from certain idealized model spaces, such as cliques, grids, or trees. It has proven helpful, for example, in assessing differences between real-world networks (Samal al., 2018), identifying bottlenecks in real-world networks (Gosztolai & Arnaudon, 2021), and alleviating oversquashing in graph neural networks (Topping et al., 2022). One prominent notion of graph curvature Ollivier- Ricci curvature (ORC), ORC compares random walks based at specific nodes, revealing differences in the information diffusion behavior in the graph. As the sizes of edges and edge intersections can vary in hypergraphs, there are many ways to generalize ORC to hypergraphs. While some notions of hypergraph ORC have been previously studied in isolation (e.g., Asoodeh et al., 2018; Eidi Jost, 2020; Leal et al., 2020), unified framework for their definition and computation is still lacking.
Contributions. We introduce ORCHID, a unified framework for Ollivier-Ricei curvature on hy- pergraphs. ORCHID integrates and generalizes existing approaches to hypergraph ORC. Our work the first to identify the individual building blocks shared by all notions of hypergraph ORC, and to perform rigorous theoretical and empirical analysis of the resulting curvature formulations. We develop hypergraph ORC notions that are aligned with our geometric intuition while still efficient to compute, and demonstrate the utility of these notions in practice through extensive experiments.

---

Published as a conference paper at ICLR 2023
Structure. After providing the necessary background on graphs and hypergraphs and recalling the definition of OOlivier- Ricci curvature for graphs in Section 2. we introduce ORCHID, our framework for hypergraph ORC, and analyze the theoretical properties of ORCHID curvatures in Section 3. We assess the empirical properties and practical urility of ORCHID curvatures through extensive experiments in Section 4, and diseuss limitations and potential extensions of ORCHID well as directions for future work in Section 5. Further materials are provided in Appendices A.I to A.5.
2 PRELIMINARIES
Graphs and Hypergraphs A simple graph G = (V, E) is a tuple containing n nodes (ver- tices) V = fui...., ) and m edges E fei....,, em
with e, E (2) for all i E [m]] Here, for a set S and a positive integer & S |S), (x) denotes the set of all k-element subsets of S, and for x E IN with 0 & I. [x] = {i NN S x). In multi- graphs, edges can occur multiple times, and hence, F = (ei,..., Cm is an indexed family of sets, with E (k) for all i E [m]] Generalizing simple graphs, a simple hypergraph H- = (V, E) is a tuple containing n nodes V and m hyperedges E C \ (. i.e. in contrast to edges, hyperedges can have any cardinality r E [n]. In a multi-
hypergraph, E = (EI..... : Cm) is an indexed family of sets, with e, S V for all i E [m]] We assume that all our hypergraphs are multi-hypergraphs, and we drop the prefix hyper from hypergraph and hyperedge where it is clear from context.
We denote the degree of node i, i.e., the number of edges containing i, by deg(i) = le F e e}), write ~ j if is adjacent to j (i.e., there exists E E' such that {i S e). and use (i) (e()) for the neighborhood of i (e), i.e., the set of nodes adjacent to (edges intersecting edge e). While (tg
[.((i) in simple graphs and deg(i) 2 [i) in multigraphs, these relations do not generally hold for hypergraphs. Two nodes + j are connected in H if there is a sequence of nodes i = "2,....... 1, Uh- = such that i ~ u for all E [A.. Every such sequence is path in H. whose length is the cardinality of the set of edges used in the adjacency relation. We refer to the length of shortest path connecting nodes j the distance between them, denoted as a(ii,).. We assume that all (hyper)graphs are connected, i.c., there exists a path between all pairs of nodes. This turns H into a metric space (H, d) with diameter diam (H) = max ((i, j) j E V).
(Hyper)graphs in which all nodes have the same degree k (deg(i) = k for all E V) are called k-regular. Three properties of hypergraphs that distinguish them from graphs give rise additional (ir)regularities First, hyperedges can vary in cardinality, and hypergraph in which all hyperedges have the same cardinality (lel = r for all e E E) is called r-umiform. Second, hyperedge inter- sections can have cardinality greater than 1, and we call hypergraph s-intersecting if all nonempty edge intersections have the same cardinality s (e f せ 0 + Ien fl = s for all f E E). Third, nodes can cooccur in any number of hyperedges; we call hypergraph c-cooccurrent if each node cooccurs e times with any of its neighbors (i ~6~ + He E É' {t,j} S e]l = e for all i, E V). Using this terminology, simple graphs are 2-uniform, 1-intersecting, 1-cooceurrent hypergraphs.
Given a hypergraph H = E), the unweighted clique expansion of H is G = (V, E.) with E = {[i.}} {ř.j] } C e for some E}, where two nodes are adjacent in G if and only if they are adjacent in H. The weighted clique expansion of H is G endowed with a weighting function w: F. - N. where w<e) Ie E F {i.j} C {) for each e E F i.e., edge (i,j) is weighted by how often and cooccur in edges from H. Both of these transformations are lossy, i.c., we cannot uniquely reconstruct // from Go. The unweighted star expansion of I is the bipartite graph G' (V', E') with V = VÜE and E' = {fi, e} E V,e E E, E c). and we can uniquely reconstruct H from G' if we know which of its parts corresponds the original node set of H.
Ollivier-Rieci Curvature for Graphs Ollivier-Rice curvature (ORC) extends the notion of Ricci curvature, defined for Riemannian manifolds, to metric spaces equipped with a probability measure or, equivalently, random walk (Ollivier, 2007: 2009). On graphs, which are metric spaces with the shortest-pal path distance d(., -), the ORC x a pair of nodes {i,j} } is defined as
x(i.j) = d(i,j) W1 and hence, x(i,j) = 1 Wi if)
(I)
where H4 is a probability measure associated with node i that depends measurably on and has finite first moment, and W, is the Wasserstein distance of order 1, which captures the amount of
2

---

Published as a conference paper at ICLR 2023
work needed to transport the probability mass from 14, H4j in optimal coupling. The use of the shortest-patte distance is necessary to ensure that ORC is also well-defined for pairs of non non-adjacent nodes. This definition to tangent vectors of manifold. A common strategy to measure curvature at node i is to average over the curvatures of all edges incident with (Banerjee, 2021; Jost & Liu, 2014), i.e.,
edges pairs of nodes alludes to the fact that Ricci curvature is associated
<(i)
k(i,j)
(ig(t)
(t,))EE
A popular probability measure that easily generalizes weighted graphs and multigraphs is
(
(1
(3)
deg(i)
otherwise
where a serves as a smoothing parameter (Lin et al., 2011). With this definition, stacking the probability measures yields the transition matrix of c-lazy random walk.
THEORY
Having introduced the concept of hypergraphs and the definition of Ollivier-Rice curvature (ORC) for graphs, we now develop our framework for ORC on hypergraphs, called ORCHID (Ollivier- Ricci Curvature for Hypergraphs In Data). We focus our exposition on undirected, unweighted multi-hypergraphs, but ORCHID straightforwardly generalizes other hypergraph variants.
3.1 OLLIVIER-RIEE CURVATURES FOR HYPERGRAPHS (ORCHID CURVATURES)
As mentioned in Section 2, hypergraphs differ from graphs in that edges can have any cardinality, and consequently, edges can intersect in more than node, and nodes can co-occur in more than one edge. When generalizing ORC as defined in Section 2 to hypergraphs, these peculiarities be- come relevant in two places: (1) in the generalization of the measure μi for nodes, and (2) in the generalization of the distance metric W₁. Construing the distance metric as function aggregating R, we can rewrite Eq. (1) for pairs of nodes (i, as
measures (AGG), with AGG: V-
<(i,j) = AGs(M4.
(4)
d(i.j)
which facilitates its generalization; will also s(e) for (hyper)edges shorthand notation
for Eq. (4). When defining probability measures and Agc functions on hypergraphs, we would like
retain as much flexibility as possible while also ensuring the following conditions:
Mathematical generalization. For graphs, AgG simplifies the original ORC on graphs. II. Permutation invariance. AGG(e) = (e)) for edges e and all node index permutations a. III. Scalability: The probability measures and Ase functions should be efficiently computable.
Beyond these properties, we would also like to have the following interpretability features to ascer- tain that hypergraph curvature measure is conceptual generalization of ORC:
A. Probabilistic intuition. The probability measures assigned nodes should correspond semantically sensible random walk on the hypergraph.
B. Optimal transport intuition. The generalization of the distance metric (Agg) should have semantically sensible interpretation in terms of optimal transport.
C. Geometric intuition. Edges in hypercliques should have positive curvature, edges in hypergrids should have curvature zero, and edges in hypertrees should have negative curvature.
We now specify probability measures and AGS functions for which the conditions above hold.

---

Published as a conference paper at ICLR 2023
A
B
(a) Node 0 and neighhorhood
(b) Equal- Nodal- Random Walk (RN)
D
E
B
(c) Equul--Egge Random Walk (EE)
(d) Weighted -ddgss Random Walk (W2)
Figure I: ORCHID'S 's probability measures are based on random walks, depicted for the neighborhood of node Arrows outgoing from the same node or edge are traversed with uniform probability.
Probability Measures (n). In graphs, the most natural probability measures are induced by the o-lazy random walk given in Eq. (3): With probability a, we stay at the current node i, and with probability (1-a)/deg(t) we move to of its neighbors. There of this formulation to hypergraphs that all retain this probabilistic intuition, thus fulfilling the re- quirement of Feature A. These extensions, illustrated in Fig. differ only in how they distribute the (1 a1) probability mass in Eq. (3) from node to the nodes in i's neighborhood. Given hypergraph H, for and with ~ j, first, we could define
least three direct extensions
p p (f)= [N(1)
(5)
by which we pick a neighbor j of node uniformly at random. We call this the equal-nodes random walk (EN), which is random walk on the unweighted clique expansion of H. Second, could set
p ( = (1 - a) deg(i) - (e el =
Σ
(6)
(2( -1-1 24-11
which first picks an edge e 3 with |e| 2 2, then picks node E e (1), both uniformly at random. We call this the equal-edges random walk (EE), which is two-step random walk the unweighted star expansion H. starting at node E V, and non-backtracking in the second step. It underlies the curvatures studied by Asoodeh et al. (2018) and Banerjee (2021). Third, could define
E( e -1 (1 a)) fe E E [i. S etl
-² = -
Σ (2 131
(7)
((fl-
first picking an edge incident with i with probability proportional to its cardinality, then picking node j E e {i} uniformly at random. We call this the weighted-edges random walk (WE); a two-step random walk from a node i E V on specific directed weighted star expansion of H whose second step banbbccttrckingg....... or equivalently, random walk on weighted clique expansion of H.
Similarity Measures (Acg). In the original formulation of ORC, i.e., Eq. (1), when determining the curvature of an edge [i.j], the Wasserstein distance Wi is used to aggregate the probability measures of i and j. There hypergraphs that retain an optimal transport intuition, as required by Feature B. Leveraging that an edge V is simply set of nodes, the easiest extension is to leave the aggregation function
at least three different extensions of this aggregation scheme to
4

---

Published as a conference paper at ICLR 2023
unchanged. We continue determining the curvature for pairs of nodes, and account for the edges in H only in the definition of our probability measure. this case, we could derive a curvature for an edge as the average over all curvatures of node pairs contained in Le.. we could define AGG as
(G) = |e[[e|| -1
2
Σ (ui (aj]Ce
(8)
This is equivalent to computing the curvature of based on the average over all W1 distances of probability measures associated with nodes contained e:
(e) == AGGA(e) = [e|(Te]
2
Σ (i.i)ee
Wi(ki
2
Σ (b.))ee
k(t,)).
(9)
|e[(|e|- - 1)
Intuitively, this definition assesses the mean amount of work needed to transport the probability mass from one node in to another node in e. Alternatively, and still keeping with the intuition from optimal transport, we can define AGG as
AGG (c)
1 C
Σ IEE
Wi (44,P)) and consequently, (c(c) = (c)
(10)
where ji denotes the Wasserstein barycenter of the probability measures of nodes contained in e, and the denominator generalizes the original d(i, Asoodeh et al. (2018) use this aggregation function. Intuitively, AGG, is proportional to the minimum amount of work needed to transport all probability mass from the probability measures of the nodes to one place, with the caveat that this place need not correspond to node in the underlying hypergraph. Finally, we can capture the maximum amount of work needed to transport all probability mass from one node in to another node in e as
AG) = max Wi Hg) {i,j} Ce}, and consequently, Ky(e) = 1 AGGM(E) (11)
Independent of the choice of Ase, the curvature at a node can be defined as the mean of all curvatures of meaningful directions containing i, i.e.,
Σ m(i.)),
(12)
[N(1)
JEN(()
it can be derived the mean of all curvatures of edges containing i.e.,
1 Σ x(e)
(13)
dig(i)
Finally, since H is connected, we can define the curvature of an arbitrary subset of nodes C V as
AGG(s)
<(s) = 1
(14)
d(s)
where AGG be any of our aggregation functions, and d(s) max(d(i,j) (i.j) S s) refers to the extent of the subset s. Note that for s E E, d(s) = 1, and thus, Eq. (14) is consistent with our previous definitions of hyperedge curvatures.
3.2 PROPERTIES OF ORCIID CURVATURES
Having introduced our probability measures (μ) and aggregation functions (A&g), we now ana- lyze their properties and the properties of the resulting curvatures. All proofs are deferred to Ap- pendix A.I. First, we note that f EN n² and μ are equivalent for certain hypergraph classes, and all aggregation functions coincide for graphs.
Lemma 1. For graphs and r-uniform, k-regular, c-cooccurrent hypergraphs, yN p1 ME
Lemma 2. For graphs. i.e., 2-uniform hypergraphs, we have Assz(e) = AGGa(e) = AGGu(E) for all edges F..
5

---

Published as a conference paper at ICLR 2023
Taken together, Lemma 1 and Lemma imply that for graphs, ORCHID simplifies to ORC, gardless of the choice of probability measure and aggregation function. This fulfills Condition Moreover, all aggregation functions permutation-invarte Condition II. Concerning Condition III, Ka and Ky exhibit better scalability than Ka, as Wasserstein barycenters are harder compute than individual distances (Cuturi & Doucet, 2014). Another rea- son to prefer Ką and Ky over Kş is the existence of upper and lower bounds that are easy to calculate. To this end, let dmii (H) = min v) u j E VJ be the smallest nonzero distance in H, and let Il-l1 refer to the L1 norm of a vector. We then obtain the following bounds for KA and Ke.
by construction, thus satisfying
Theorem 3. For any probability measure and C(e) = 2/1e[(ee)-1), the curvature Ky (e) of an edge e E E is bounded by
- -idim (H)
E (WJ)
11m 1ou-Myll Myll1 S <xa(e) S 1 dmin (H)C(e) Σ (W))
114--all
(15)
Theorem 4. For any probability measure μ4, the curvature (eg(e) of an edge E is bounded by
diam H) max
I| Mill S mx(e) S -min (H) max
l|ss - M5l1 (ij)Ce
(16)
Directly from our definitions, we further obtain the following relationships between Ka, Ka, and fxs and between ORCHID curvatures on hypergraphs and ORC on their unweighted clique expansions.
Corollary 5. Given a hypergraph = (V, E). Ka(e) I (x(c) and kg(e) S Ke(c) for all E E.
(V, E) and its unweighted clique expansion G (V, (V.E)). for {i,5} E E", the ORC x(i.j) in G equals its ORCHID curvature k(i.j) of direction {i.}} S H with yPM, and the ORC K(i) of i E V in G equals ORCHID curvature NN (i) in with p
Corollary 6. Given a hypergraph
Corollary clarifics that the equal-nodes random walk establishes the connection between ORCHiD and ORC graphs. Moreover, ORCHID curvatures capture relations between global properties and local measurements, similar to the Bonnet-Myers theorem in Riemannian geometry (Myers, 1941).
Theorem 7. Given a subset of nodes C V and an arbitrary probability measure p., let ô, denote Dirac measure at node i, and let J(ss) Wi (ōi, uu) denote the jump probability pú. If all curvatures based on i are strictly positive, i.e., k(()) 2 K for all S V. and (ii) Wi WL(g, M5) S
AGG(s) for {i,j] argmax(d(s)). then
d(s) S J(1) +
(17)
x(s)
Note that condition (ii) of Theorem 7 is always satisfied by AGGy Finally, in Appendix A.I, we generalize the concepts of cliques, grids, and trees (prototypical positively curved, flat, and nega- tively curved graphs) to hypergraphs, and we prove the following lemmas to ensure that ORCHID curvatures respect geometrie intuition, required by Feature C.
Theorem (Hyperclique curvature). For an edge e in a hyperclique H (V, on nodes with edges F. (*) for some r S n, with a
<(e) =
i.e., lim <(e) = independent of
Theorem (Hypergrid curvature). For an edge e in a r-uniform, k-regular hypergrid, with a = O, x(e) 0, independent of and k.
Theorem 10 (Hypertree curvature). For an edge in r-uniform, k-regular, 1-intersecting hyper- free,
with a = 0, x((e) = 1 (3((k- -1)
k + (r 1)1e ) Le. lim s(() = -2, independent of k0000

---

Published as a conference paper at ICLR 2023
Table 1: Hypergraphs used in ORCHID experiments cover several domains and orders of magnitude. and m are node and edge counts, "/m is the aspect ratio, e is the number of filled cells in the node- to-edge incidence matrix, i/nm is the density, and N the number of hypergraphs in a collection.
(a) Individual Hypergraphs
Nodes
Edges
72
m
7/m
4/nm
aps-a
Authors
APS Papers
505 827
688 707
0.7345
2,800 373
0.000007
dblp
Authors
DBLP Papers
3 108 658
6011 388
0.5171
19411 479
0.000001
ndc-ai
Active Ingr.
NDC Drugs
7090
131 450
0.0539
224 084
0.000240
ndc-pe
Pharm. Classes
NDC Drugs
166
70 101
0.0180
273 088
0.003084
(b) Hypergraph Collections
Nodes
Edges
Graphs
N
(*/m)
(4/mm) max
aps-av
Authors
APS Papers
Journals
19
4. 4.698182
0.005216
aps-cv
APS Cited P.
APS Citing P.
Journals
19
1.396552
0.028430
dbip-v
Authors
DBLP Papers
(Groups of) Venues
1 193
5.599424
0.002443
mus
Frequencies
Chords
Music Pieces
994
1.454545
0,375000
stex
Tags
Questions
StackExchange Sites
355
1,233449
0.121528
sha Characters
Stage Groups
Shakespeare's Plays
37
0.554054
0.304688
syn-c
Hypergraph Configuration Models
250
0.5
0.005
syn-r
Rénés-Rényi Random Hypergraph Models
250
0.5
0.005
syn-s
Hypergaph Stochastic Block Models
250
0.5
0.005
EXPERIMENTS
Having established in Section 3 that ORCHID curvatures have our desired theoretical properties, and finding that they strictly generalize both ORC graphs and existing definitions of hypergraph ORC, we now seek to ascertain that they are also meaningful in practice. We ask the following questions:
Q1 Parametrization. How do our choices of a, μl and Age impact ORCHID curvatures?
Q2 Hypergraph exploration. How can ORCHID curvatures help us in exploring hypergraphs?
Q3 Hypergraph learning. How can ORCHID curvatures help us in hypergraph learning tasks?
To address these questions, we experiment with data from different domains, spanning several or- ders of magnitude. We investigate four individual real-world hypergraphs in which edges represent co-authorship (aps-a, dbip) and FDA-registered drugs (ndc-ai, ndc-pc), six collections of real- world hypergraphs in which edges represent questions on Stack Exchange Sites (stex), co-authorship by venues (aps-av, dblp-v), co-citation by venues (aps-cv), chords in music pieces (mus), and character cooceurrence on stage Shakespeare's 's plays (sha), as well as three collections of synthetic hyper- graphs based on different generative models (syn-c, syn-r, syn-s), for a total of 4 321 hypergraphs. We summarize their basic properties in Table I, and give more details on their statistics, semantics, and provenance in Appendix A.3. We implement ORCHID in Julia and Python. Our experiments run on AMD EPYC 7702 CPUs with up to 256 cores. We discuss our implementation and results in more detail in Appendices A.4 and A.5, and make all our code, data, and results publicly available!
Q1 Parametrization. To understand how choices of a, μt, and AGG impact ORCHID curva- tures, we first compute the pairwise mutual information between ORCHID edge curvatures with 36 different parametrizations. As illustrated in Fig. 2, while changing a for the same combination of μu and AGG has similar effects across hypergraphs, there is no uniform pattern in the relationships between different combinations μ and AgG. This underscores the fact that the various notions of ORCHID curvature are not redundant but rather emphasize distinct aspects of hypergraph structure. For fine-grained view of the differences between parametrizations, we inspect the distributions of
http:://ddi..or/110.52///////// 7624573
7

---

Published as a conference paper at ICLR 2023
14
EN AE WE A
EN A EE MEEA A WE A
A WEMWEA
EN BE MEE A
(a) (5.10) syn-c
(b) 2-community syn-s
(c) ndc-ai
(d) nde-pe
Figure 2: ORCHID curvature notions are non-redundant. We show the Min-Max-Normalized Mu- tual Information (NMI) between ORCHID edge curvatures with 36 different parametrizations, using probability measures f (EN), f (EE), or f (WE), aggregations AG Gy (M) or A (A), and {0.0, 0.1, 0.2, 0.3, 0.4, 0.5} (ordered - 1), for two synthetic and two real-world hypergraphs.
4601
50
Languages
4602.
Chineslis
Religions
4605
4604.
pituracce Moseaaaeeeaaae
4606-
4037
4608
Mislam's y
*amiing
46
10
Sto-Chissp
miini
4612
4615
adtradanity
4801
4013
(a) kPCA (directional curvature) (b) kPCA (edge neighborhood
(c) MMD (cardinality vs. curvature)
Figure 3: Curvatures carry more information than other local features. We show a 2-dimensional
embedding of graphs from the stex collection based on kPCA, using RBF kernel with curvature distributions computed using a = 0.1, n= and AGG, (3a) or edge neighborhood size distributions (3b) as input features. We see that only curvatures yield meaningful and discriminative grouping. Corroborating this finding, we also depict conferroni-ajjuste p-values of testing for significant differences in feature distributions-iie. p-values multiplied by the number h of hypothesis tests, as Bonferroni (1936) correction requires S a/h for some desired Type I-error rate a using MMD on distributions of edge curvatures computed with the same parameters as for (3a) (upper triangle) or edge cardinality (lower triangle), for the subset of the dbip-v collection corresponding to top conferences grouped by areas of research (3c).
our four curvature types, (i) edge curvature k(e), (ii) edge-averaged node curvature x xi), (iii) di- rectional curvature k(i, for all {i.}} S e E, and (iv) direction-averaged node curvature xN (i), for each of our 36 parametrizations. By construction, directional curvature and direction- node curvature do not vary with the choice of AGG, and Ki lower-bounds K2 for edge curvatures and edge-averaged node curvatures. However, the differences between fix and KA vary across graphs, while consistently, the larger a, the more concentrated our curvature distributions (Appendix A.5).
Q2 Hypergraph Exploration. To explore individual graphs, we perform case studies on graphs from the aps-cv collection, leveraging that most nodes in these graphs also occur as edges. We scru- tinize the relationships between node and edge curvatures, other local node and edge statistics, and article metadata. We observe that curvature values span a considerable range even for articles with otherwise comparable statistics, but the curvature distributions of influential papers appear to differ systematically from those of less influential papers (Appendix A.5). Exploring graph collections, we run kernel PCA (kPCA) (Schölkopf et al., 1997) with radial basis function kernel (RBF kernel) and curvatures or other local features known to be powerful baselines (Cai & Wang, 2018), e.g., node degrees and neighborhood sizes, as inputs to jointly embed graphs from a collection. We statistically bootstrap the maximum mean discrepancy (MMD) (Gretton et al., 2006) test the null hypothesis that the feature distributions of two graphs are equal. As shown in Fig. 3, ORCHID curvatures result in more interpretable embeddings and more discriminative tests than other local features.
8

---

Published as a conference paper at ICLR 2023
Table ORCHID curvatures lead to better clusterings than other local features. We show (CC,) for collection clusterings computed using RBF or exp. Wasserstein kernels with edge curvatures, edge neighborhood sizes, edge-averaged node curvatures, or node neighborhood sizes as inputs.
RBF x<())
Wk(e)
(V()) (W())
W(ee)
RBF x)F
W,e(1)
RBF (V(())
dblp-v 0.2151
0.1908
0.3309
0.2358
0.2273
0.0445
0.0910
0.1285
mus
0.1955
0.1758
0.2609
0.2723
0.2062
0.1606
0.2774
0.2458
stex 0.2651
0.2877
0.3018
0,2950
0.2393
0.2577
0,3067
0.2689
sha
0.5984
0.6390
0.6716
0.6597
0.5021
0.6526
0.6236
0.6641
Q3 Hypergraph Learning. To explore the utility of curvatures for learning on individual hyper- graphs, we perform spectral clustering using either curvatures or other local node features. To evaluate the resulting node clusterings, we leverage that nodes in the aps-cv collection correspond to APS papers, for which consistently know the titles. Hence, even in the absence of meaningful ground truth, we can still check the sensibility of a clustering by statistically analyzing the titles grouped together using tools from natural language processing. We find that node clusterings based on curvatures correspond to thematically more coherent groupings (Appendix A.5). For learning on hypergraph collections, we spectrally cluster the collection using RBF or exponential Wasserstein kernel matrices, exp( W(pz, (2)),, on node and edge curvatures or other local features (Plaen al., 2020). Lacking ground-truth labels, we evaluate the clustering quality in an unsupervised manner, using what we call the Wasserstein Clustering Coefficient (WCC). This measure compares averaged intra-cluster Wasserstein distances averaged inter-cluster Wasserstein distances, such that a lower WCC corresponds to higher-qualit, clustering. Given e clusters X' = (XI..... X.} of hypergraphs H represented by their feature distributions XHs. we define
WCC(X) = 1 (xx))x with w(X) = ((2) Enzyex Whee, w(X,Y) (IXIIT)) " W(X,, Xy)
ExEx ((X
As illustrated in Table 2, when evaluated using WCC with directional curvature distributions as X.
i.e, WCC.(i.)) ORCHID curvatures consistently yield better clusterings than other local features.
5 DISCUSSION AND CONCLUSION
We introduced ORCHID, the first unified framework for AllivierRRicel curvature on hypergraphs that integrates and generalizes existing approaches to hypergraph ORC. ORCHID disentangles the com- mon building blocks of all notions of hypergraph ORC, yielding curvature notions that are provably aligned with our geometric intuition. We performed a rigorous theoretical and empirical analysis of ORCHID curvatures, demonstrating their practical utility and scalability through extensive exper- iments, covering both hypergraph exploration and hypergraph learning. While our work paves the way toward future work seeking to leverage the power of Ollivier-Riccl curvature for hypergraphs in hypergraph learning algorithms, it still has some limitations to be addressed. First, ORC on graphs is defined for any probability measure, but we only consider measures corresponding to single step of a random walk. Future work could thus hamess higher-order random walks or alternative proba- bility measures, and consider analyzing relationships between such probability measures and other structural hypergraph properties. Second, hyperedge intersections can vary in cardinality, but this variation is not currently reflected in our probability measures. One could thus integrate ORCHID with the s-walk framework proposed by Aksoy et al. (2020), or define persistent ORCHID curvatures based on hypergraph filtrations, extending work on persistent ORC for graphs (Wee & Xia, 2021b). Third, like the original ORC, ORCHID curvatures are static, but many hypergraphs are inherently dy- namic, suggesting need to develop dynamic curvature notions. Fourth, despite its comprehensive scope, our study only scratches the surface regarding the theoretical and empirical analysis of OR- CHIDD curvatures, and we believe that there are many more connections between ORCHID curvatures and other hypergraph descriptors to be uncovered, and many additional use cases to be explored. For instance, ORCHID generalizes ORC, but not Forman- Rerman-Ricci curvature (FRC), and we believe that a framework for FRC could help uncover new relations between combinatorial curvature notions and hypergraph structure. Finally, we imagine that incorporating hypergraph curvature into models as an additional inductive bias could prove useful in hypergraph learning more broadly.

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
Our main contribution is ORCHID, a unified mathematical framework yielding theoretically sound hypergraph descriptors that are also practically useful for hypergraph exploration and hypergraph learning. As such, ORCHID comes with the caveats applicable to hypergraph exploration and hyper- graph learning methods more generally. Most importantly, it should be used with caution on data related to people, and its results should not be decontextualized. We adhered to these principles in our experiments, and selected our datasets accordingly.
REPRODUCIBILITY STATEMENT
To facilitate reproducibility, we provide more details on our data, implementation, and results in more detail in Appendices A.3 to A.5, and make all our code, data, and results publicly available at htpps//db..ogg/0.5588//eeeoooo 7624573.
REFERENCES
Tomoya Akamatsu. A new transport distance and its associated ricci curvature of hypergraphs. Analysis and Geometry in Metric Spaces, 10(1):90-108, 2022.
Sinan G. Aksoy, Cliff Joslyn, Carlos Ortiz Marrero, Brenda Praggastis, and Emilie Purvine. Hyper- network science via high-order hypergraph walks. EPJ Data Science, 9(1):16, 2020.
Iya Amburg, Nate Veldt, and Austin Benson. Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of the Web Conference 2020, pp. 706-717, 2020.
Shahab Asoodeh, Tingran Gao, and James Evans. Curvature of hypergraphs via multi-marginal optimal transport. In IEEE Conference on Decision and Control (CDC), pp. 1180-1185, 2018.
Lu Bai, Peng Ren, and Edwin R Hancock. A hypergraph kernel from isomorphism tests. In Inter- national Conference on Pattern Recognition (ICPR), pp. 3880-3885, 2014.
Dominique Bakry and Michel Émery. Diffusions hypercontractives. Séminaire de probabilités de Strasbourg, 19:177-206, 1985.
Anirban Banerjee. On the spectrum of hypergraphs. Linear Algebra and its Applications, 614: 82-110, 2021.
Bauer, Chung, Y Lin, and Liu. Curvature aspects of graphs. Proceedings of the American Mathematical Society, (45(5):2033-2442 2017.
Isabelle Bloch and Alain Bretto. Mathematical morphology on hypergraphs, application to similarity and positive kernel. Computer Vision and Image Understanding, 117(4):342-355 3544, 2013.
Carlo Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del Istituto Superiore di Scienze Economiche Commericiali di Firenze, 8:3-62 62, 1936.
David P. Bourne, David Cushing. Shiping Liu, Florentin Münch, and Norbert Peyerimhoff. Ollivier- Ricci idleness functions of graphs. SIAM Journal Discrete Mathematics, 32(2): (022):448-1444 2018.
Chen Cai and Yusu Wang. A simple yet effective baseline for non-attributed graph classification. arXiv: 1.03508, 2018.
Corinna Coupette, Jilles Vreeken, and Bastian Rieck. All the world's (hyper)graph: A data drama. arXiv:2206.08225, 2022.
Mihai Cucuringu, Peter Davies. Aldo Glielmo, and Hemant Tyagi. SPONGE: A generalized eigen- problem for clustering signed networks. Kamalika Chaudhuri and Masashi Sugiyama (eds.), ). In- fernational Conference Artificial Intelligence and Statistics (AISTATS), pp. 1088-1098, 2019.
10

---

Published as a conference paper at ICLR 2023
Marco Cuturi and Arnad Doucet. Fast computation of wasserstein barycenters. In Eric P. Xing and Tony Jebara (eds.), International Conference on Machine Learning (ICML), volume 32, pp. 685-693, 2014.
Manh Tuan Do, Se-eun Yoon, Bryan Hooi, and Kijung Shin. Structural patterns and generative models of real-world hypergraphs. In Proceedings of the 26th ACM SIGKDD International Con- ference on Knowledge Discovery & Data Mining (KDD), pp. 176-186, 2020.
Marzieh Eidi and Jürgen Jost. Ollivier-Rice Ricci curvature of directed hypergraphs. Scientific Reports, 10(1):1-14, 2020.
Robin Forman. Bochner's method for cell complexes and combinatorial Ricci curvature. Discrete and Compulational Geometry, 29(3):323-374, 2003.
Tingran Gao, Shahab Asoodeh, Huang, and James Evans. Wasserstein soft label propagation hypergraphs: Algorithm and generalization error bounds. In AAAI Conference Artificial Intelligence, pp.
2019.
Alison L. Gibbs and Francis Edward Su. On choosing and bounding probability metrics. Interna- tional Statistical Review, 70(3):41-435, 2002.
Adam Gosztolai and Alexis Amnadoon Unfolding the multiscale structure of networks with dy- namical Ollivier-Riiei curvature. Nature Communications, 12(1):4561, 2021. doi: 10.1038/
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola. A kernel method for the two-sample-problem. Advances in Neural Information Processing Systems, 19, 2006.
Jing Huang and Jie Yang. UniGNN: a unified framework for graph and hypergraph neural networks. In Proceedings of the 30th International Joint Conference Artificial Intelligence (IJCAI), pp- 2563-2569, 2021.
Masahiro Ikeda, Yu Kitabeppu, Yuuki Takai, and Takato Uehara. Coarse Ricci curvature of hyper- graphs and its generalization. arXiv:2102.0048 2021.
Jürgen Jost and Shiping Liu. Ollivier's Ricci curvature, local clustering and survature-dimensee inequalities on graphs. Discrete & Computational Geometry, 51()):000-322, 2014.
Mark Kempton, Gabor Lippner, and Florentin Münch. Large scale Ricci curvature on graphs. Cal- culus of Variations and Partial Differential Equations, 59(5) 2020.
Wilmer Leal, Marzich Eidi, and Jürgen Jost. Curvature- analysis of directed hypernetworks. Complex Networks, pp. 10-12, 2019.
Wilmer Leal, Marzieh Fidi, and Jürgen Jost. Ricei curvature of random and empirical directed hypemnetorrs.. Applied Network Science, 5(1 5(1):65, 2020.
Wilmer Leal, Guillermo Restrepo, Peter Stadler, and Jürgen Jost. Forman-Ricc curvature for 2021.
hypergraphs. Advances in Complex Systems, (-11))22155000:112100000000
Geon Lee and Kijung Shin. THyMe+: Temporal hypergraph motifs and fast algorithms for exact counting. In IEEE International Conference on Data Mining (ICDM), pp. 310-319, 2021.
Geon Lee, Jihoon Ko, and Kijung Shin. Hypergraph motifs: concepts, algorithms, and discoveries.
Proceedings of the VLDB Endowment, 13(12):2256 22659, 2020.
Yong Lin, Linyuan Lu, and Shing- Tung Yau. Ricci curvature of graphs. Tohoku Mathematical Journal, Second Series, 63(4)6605-627, 2011.
Shiping Liu, Florentin Münch, Norbert Peyerimhoff, and Christian Rose. Distance bounds for graphs with some negative Bakry-Emery curvature. Analysis and Geometry in Metric Spaces, 7(1):1-14, 2019.
11

---

Published as a conference paper at ICLR 2023
Peter Macgregor and He Sun. Finding bipartite components in hypergraphs. Advances in Neural Information Processing Systems, 34, 2021.
Alessio Martino and Antonello Rizzi. (Hyper)graph kernels over simplicial complexes. Entropy, 22 (10):1155, 2020.
Florentin Münch and Christian Rose. Spectrally positive Bakry-Emery Ricci curvature on graphs. Journal de Mathématiques Pures et Appliquées, 143:334-344 2020.
Kevin A. Murgas, Emil Saucan, and Romeil Sandhu. Hypergraph geometry reflects higher-order dynamics in protein interaction networks. Scientific Reports, 12(1 ):20879, 2022.
Sumner Byron Myers. Riemannian manifolds with positive mean curvature. Duke Mathematical
Journal, 8(2):401-444, 1941.
Yann Ollivier. Ricci curvature of metric spaces. Comptes Rendus Mathematique,345(10 345(11):643-644) 2007.
Yann Ollivier. Ricci curvature of markov chains metric spaces. Journal of Functional Analysis, 256(3):810-888) 110-864,2200 2009.
Henri De Plaen, Michael Fanuel, and Johan A. K. Suykens. Wasserstein exponential kernels. IEEE International Joint Conference on Neural Networks (IJCNN), 2020.
Indrava Roy, Sudharsan Vijayaraghavan, Sarath Jyotsna Ramaia, and Areejit Samal. Forman forman-Ricci curvature and persistent homology of unweighted complex networks. Chaos, Solitons & Fractals, 140: 10260, 2020.
Areejit Samal, RP Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost. Comparative analysis of two discretizations of Ricci curvature for complex networks. Scientific Reports, 8(1): 1-16, 2018
Emil Saucan and Melanie Weber. Forman's Ricci curvature From networks to hypernetworks. In Luca Maria Aiello, Chantal Cherifi, Hocine Cherifi, Renaud Lambiotte, Pietro Lió, and Luis M. Rocha (eds.), International Conference on Complex Networks and their Applications, volume 812, pp. 706-717, 2018
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Kernel principal component anal- ysis. Artificial Neural Networks (ICANN), pp. 583-588, 1997.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In Interna- tional Conference on Learning Representations (ICLR), 2022.
Nate Veldt, Anthony Wirth, and David F. Gleich. Parameterized correlation clustering in hyper- graphs and bipartite graphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 1868-18766 2020.
Gabriel Wachman and Roni Khardon. Learning from interpretations: a rooted kernel for ordered hypergraphs. In International Conference on Machine Learning (ICML), pp. 943-950, 2007.
Melanie Weber, Emil Saucan, and Jürgen Jost. Characterizing complex networks with Forman- Ricci curvature and associated geometric flows. Journal of Complex Networks, 544):5275550, 2017. doi: 10. 1093/commet/cnw000..
Junjie Wee and Kelin Xia. Forman persistent Ricci curvature (FPRC)-based machine learning mod- els for protein-ligand binding affinity prediction. Briefings in Bioinformatics, 22(6), 2021a.
Junjie Wee and Kelin Xia. Ollivier persistent Ricci curvature-based machine learning for the protein- ligand binding affinity prediction. Journal of Chemical Information and Modeling, 611) 1626, 2021b.
Yasharth Yaday, Areejit Samal, and Emil Saucan. poset-based approach to curvature of hyper- graphs. Symmetry, 14(2):420, 2022.
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. Advances in Neural Information Processing Systems, 19, 2006.
12

---

Published as a conference paper at ICLR 2023
A APPENDIX
In this Appendix, we include the following materials.
A.1 Deferred Proofs.
All proofs for Section 3, along with supporting definitions, lemmas and corollaries.
A.2 Related Work.
Discussion related work treating hypergraph curvatures, graph curvatures, or hypergraph analysis.
A.3 Dataset Details.
Further information on the provenance, semantics, and statistics of our datasets.
A.4 Implementation Details.
Details on our implementation, including proofs showing the correctness of performance shortcuts.
A.5 Further Results.
Display and discussion of results not included in the main paper.
A.1 DEFERRED PROOFS
Lemma 1.
For graphs and r-uniform, k-regular, c-cooccurrent hypergraphs, yr p. =1
Proof. For notational simplicity, w.l.o.g., we assume that a = 0. In an r-uniform, k-regular, c- cooceurrent hypergraph H (V. E). each node has degree & and [r-1]k neighbors, and each edge has cardinality r. Hence, for nodes i E V with ~ j.
F (J) [N(0)
1 B (j)
c. r-1
(r - 1)h
dog(i)
c
c k(r 1))
He E
[1,j)
Cell
11 (j)
Σ(1-1)
Graphs 2-uniform and 1-cooceurrent (but not generally regular), and hence, IW(it) deg(()) (i).
Using this to simplify the probability measure expressions, the claim follows.
Lemma 2. For graphs, i.e., 2-uniform hypergraphs, we have AGGa(e) AGGz(e) = AGGu(e) for all edges E F.
Proof. Given probability distributions μ1, U2....... Pas their Wasserstein barycenter defined as the distribution ı that minimizes f(z)
> ii=1 Wi (T, p.). Since |el 2, we minimize W, (ū. P1) + Wi (ūz p2). The Wasserstein distance is metric, so it satisfies the triangle inequality. Thus, Wi (M1 (12) (a, [4) Wi (ū, (22) for all choices of j. Hence, is minimized by either J4
or u2. Evaluating both cases yields AGGa(E) = AGGn(e). and observing that AGGx(e) = Wi pg)
for {i by definition, the claim follows.
Theorem 3. For any probability measure and C(e) == 2/1e1(el-1), the curvature Ka. (e) of an edge e E E is bounded by
- (H)
Σ 1155-151 S (x(e) < dmia (H)((e) Hij}Ce
Σ 1l4 Mylh
(15)
(W
Proof. We bound each of the summands in the curvature calculation. Given probability measures Ms. Pj. result by Gibbs & Su (2002, Theorem 4) states that
dmin (H) drv (p::))))) S W1 Pb)) S diam(H) (Tv(P:
(18)
where drv refers to the total variation distance. The intuition behind this bound is that the total vari- ation distance represents specific type of transport plan between the two probability measures; the factors arising from the minimum (maximum) distance a space indicate the minimum (maximum) distance that realizes this transport plan. Since all our measures are defined over finite space, have (Ty(H:; (4;)) = 1/2| μ4 - My I| The claim follows by considering that pairwise distances are being subtracted to calculate curvature measure.
n
13

---

Published as a conference paper at ICLR 2023
Theorem 4. For any probability measure μ.. the curvature kz(le) of edge E is bounded by
1 - diam
max (B
ll; -3yll S kx(e) 1 - dmmn max {iotCe
|s - Myll
(16)
Proof. For GG Eq. (18) applies for a single pairwise distance only. We thus only obtain a single bound based on the maximum total variation distance between two probability measures.
L
Theorem 7. Given subset of nodes V and arbitrary probability measure p. let ö; denote a Dirac measure at node i, and let J(4s) == (r uu)) denote the jump probability of p4. (i) all
curvatures based on yr are strictly positive, i.e,, k(s) 2 K > 0 for all C V, and (ii) Wi (14, (5))))) S
ABG(8) {i,j} = (ogmax(d(s)) then
d(s) S J(1) + J()
(17)
x(s)
Proof. Let {i.}} = argmax(d(s)) as required in the theorem. We then have following chain of (in)equalities:
d(s) = d(i,j) (6,, 6,) Wi Wi(m,, + Wi
(19)
Rearranging Eq. (14), we have (1 - -(s)) d(s) = AGE(s). According to our assumptions, (1 S AGG(s) (1 x(s)) d(i. j). Inserting this into Eq. (19) yields
d(i,j) J(ps) + J(4) (1 d(i,))
(20)
d(i,j) - (1 (1=+(s)) d(i, - J(ms) + J(4))
(21)
d(i,j) J(i) J(i)
(22)
n(())
where the last step is only valid since x(ss) 2 K > 0 by assumption.
Definition 11 (Hypercliques, hypergrids, hypertrees). A simple, connected hypergraph H (V, V) is
a hyperclique if E ( for some r S [V..
hypergrid if H is an r-uniform hypergraph for which there exists lattice L = (V,EL) EL)
S.I. E (e (Y) corresponds path of length in T.J. and
a hypertree if there exists a tree T = (V, ET) s.t. each edge E Er induces a subtree in T.
Corollary 12. Cliques are hypercliques, grids are hypergrids, and trees are hypertrees.
Corollary 13. If H E) is a hypercllquee, a hypergrid, or an r-uniform, k-regular, 1- intersecting hypertree, for i.j V, the sets S, f Eliii e) and S, {e E j e) are isomorphic, ie., there exists :N(1) (i) + N()) U (i} such that ((p(() x E eE Sy.
For hypercliques, hypergrids, and hypertrees with certain regularities, AGGa and AG) constants.
Lemma 14 (Hypercliques, hypergrids, hypertrees). If = (V is a hyperclique, a hypergrid, or an r-uniform, ke-reuular, 1 1-intersecting hypertree, have AGsx(e) AGGu(e) = W, (1(,),))) for W E R, e E E, and j E V with i j.
Proof. By Corollary 13, we have w = Wi (4)) = (1p for i.j.p. E V with q. Hence AGGu(e) w. and (G)x(e) |e[le--] Ensise Wi(pi,19)) =
i and
[1] 2 w w, for e E.
Corollary 15. H = EV,E) is a hyperclique, a hypergrid, or an r-uniform, k-regular, 1- intersecting hypertree, (G) AGGx(e).
14

---

Published as a conference paper at ICLR 2023
Using Lemma 14, now prove that under AGGa and AGGa. hypereliques are positively curved, hypergrids are flat, and hypertrees are negatively curved, as desired.
Theorem (Hyperclique curvature). For an edge e in a hyperclique H = (V, E) on nodes with edges E = (7) for some r 5 n, with a = 0,
n(E) = 72
ie, lim <<e) =1, 1, independent of 10
Proof. A hyperclique is r-uniform, (n - 1) regular, and (r 2)-cocccu,,nnt, so f4. p μ4 for each node E V by Lemma Thus, considering p each node V has n neighbors to which it distributes its probability mass equally, and we have W1(1,19)) | for i.j E with i i~ j. The claim now follows from Lemma 14.
Theorem 9 (Hypergrid curvature). For an edge e in r-uniform, k-regular hypergrid, with 0, x(e) 0. independent of and k.
Proof. By Corollary 13, the phic, and due to the symmetries in the hypergrid. the isomorphism p: (i) + NG) ( minimizing the cost ExEN()U(( d (z, (p(x)) corresponds to the coupling minimizing Wi (i The cost of & equals the minimum cost of an isomorphism in H's underlying lattice L. between the inclusive (r 1o-hop neighborhoods of two nodes adjacent in I, which is [W(i) U (+)]- Hence, and all choices μ. and the claim then
- {e
i e} and Sj- E e} are isomor-
(14, (4)) (+)
[H) 1 for i, E V with
follows from Lemma 14.
Theorem 10 (Hypertree curvature). For an edge r-uniform, k-regular, 1-intersecting hyper- tree,
with a 0, x(e)) = 1 33kk + (r - 1yk
i.e. lim x(e) = 22 independent of k+000
k
Proof. An r-uniform, k-regular, 1-intersecting hypertree is 1-cooccurrent, so we have μu = 1u " for each node i E V by Lemma 1. Each node i E V has (r -1)k neighbors, such that 14th distributes fraction アল-Tバæ of the probability mass to each of i's neighbors. Nodes i, E V with i ~ share (r 2) neighbors (those the unique edge satisfying {i,j} Ce). and the probability mass allocated by μr to j can be matched with the probability mass allocated by μj to i at cost 1. Because H is hypertree, the remaining probability mass, (r -r- 1) - 1)/ 1((((r- 1)k) = (A- 1)/k, needs to be transported from the neighborhood of to the neighborhood of j at cost Hence,
1
k
Wi W1 M4y
+ +3-
(r 1)k
k
for i,j E V with ~ j. Again, the claim follows from Lemma 14.
15

---

Published as a conference paper at ICLR 2023
A.2 RELATED WORK
Hypergraph Curvature Most closely related to our work is the literature on hypergraph curva- tures. Much of this literature focuses defining notions of ORC and Forman-Ricei Curvature (FRC) specifically for directed hypergraphs and studying some of their mathematical and empiri- cal properties (c.g.. Leal et al.. 2019; 2020; 2021: Saucan & Weber, 2018). Notably, the directed hypergraph ORC introduced by Eidi & Jost (2020) is an instantiation of our framework with μ and AG Curvature notions for undirected hypergraphs are comparatively less explored, and es- pecially the literature generalizing ORC is almost entirely theoretical. The generalization of ORC proposed by Asoodeh et al. (2018) and the equivalent measure used by Banerjee (2021) are instan- tiations of our framework using 1 and AGGs. Akamatsu (2022) propose (a, h)-ORC using cost functions based on structured optimal transport, and Ikeda et al. (2021) define X-coarse Ricci cur- vature using a X-nonlinear Kantorovich difference based on a submodular hypergraph Laplacian as a generalization of ORC as introduced by Lin et al. (2011). Both of these works define curvature exclusively for pairs of nodes, rather than for hyperedges. Beyond ORC, Yadav et al. (2022) study FRC for undirected hypergraphs defined via poset representations, and Murgas et al. (2022) explore hypergraphs constructed from protein-protett interactions using a different notion of FRC based on the Hodge Laplacian. To the best of our knowledge, with ORCHID, we are the first to introduce a flexible framework generalizing ORC to hypergraphs, and to demonstrate the utility of hypergraph ORC in practice.
Graph Curvature. Beyond the Ollivier-Rice concepts, there are also curvature concepts based on the contractivity of operators (Bakry & Émery, 1985), which could be considered a "spiritall precursor" to Ollivier's work. This perspective has been used to provide predominantly spectral perspective on curvature (Liu et al., 2019; Münch & Rose, 2020), whereas ORC can foremost be seen probabilistic concept. Recently, Kempton et al. (2020) defined a hybrid between Ollivier and Bakry-Emery curvature on graphs. A more combinatorial perspective is assumed by FRC, which is motivated by defining equivalent formulations of curvature on structured spaces, such as CW complexes or simplicial complexes. Originally described by Forman (2003), FRC has since been improved in the context of explaining the learning behavior of graph neural networks (Topping et al., 2022), with other recent work focusing on fusing it with topological graph properties (Roy et al., 2020). ORC was first developed for general Markov chains (Ollivier, 2007: 2009), but has quickly been adopted characterize graphs (Jost& & Liu, 2014) and networks (Weber et al., 2017). With numerous follow-up publications elucidating the relationship between structural properties of a graph and ORC (Bauer al., 2017: Samal et al., 2018), the initial concept has also been substantially updated (Bourne et al., 2018; Lin et al., 2011). As an emerging research direction, we identified the combination of ORC (and FRC) with concepts from computational topology, leading to an inherent multi-scale perspective on data. This has led to promising results for treating biomedical graph data (Wee& & Xia, 2021a;b).
Hypergraph Learning. Work tackling certain hypergraph learning tasks such as hypergraph clus- tering (Amburg et al., 2020; Veldt et al., 2020) has existed for many years (Wachman & Khardon, 2007: Zhou et al., 2006). Some approaches make use of intrinsic structural properties of hyper- graphs. leading to hypergraph neural network architectures (Huang & Yang, 2021) and message passing formulations (Gao al., 2019), whereas others focus on developing similarity measures, i... kernels (Bai et al., 2014; Bloch & Bretto, 2013; Martino & Rizzi, 2020). Methods from the rich literature on graph kernels can also be employed to address hypergraph learning tasks, namely, by transforming the hypergraph into graph, but most popular transformations are lossy and may drastically increase the size of the object under study, such that the practicality and utility of this approach is unclear.
Hypergraph Mining and Analysis. In recent years, there has been a renewed interest in hyper- graph mining and analysis. Notably, there is work developing new hypergraph descriptors (Aksoy et al., 2020), extending motif discovery to hypergraphs (Lee & Shin, 2021; Lee et al., 2020), solv- ing classic graph mining tasks in the hypergraph setting (Macgregor & Sun, 2021), or identifying patterns in real-world hypergraphs (Do et al., 2020). However, to the best of our knowledge, none of this work draws on curvature concepts solve the mining and analysis tasks of interest.
16

---

Published as a conference paper at ICLR 2023
A.3 DATASET DETAILS
At high level, our workflow to produce and work with the datasets used in our experiments (Sec- tion 4) was as follows:
1. Obtain raw data in a variety of different formats, e.g., JSON, or XMI..
2. Transform the raw data into hypergraph CSV that retains as much of the raw data semantics as possible. This CSV is guaranteed to contain one row per edge, one column with unique edge identifiers, and one column with the nodes contained each edge. It may also contain additional columns holding further metadata associated with individual edges. Column names may differ between datasets to reflect dataset semantics.
3. Provide unified loading interface to the datasets in Python.
4. Transform semantics-lade hypergraph CSV files into semantics- one-based integer edge lists and sparse matrices for curvature computations in Julia, compute curvatures in Julia, and store the results in JSON files.
5. Map results back to original dataset semantics in Python for further examination.
In the following, we give more details on the provenance, semantics, and statistics of our datasets. Unless if otherwise noted, we make our datasets publicly available with our online materials, along with the raw data and preprocessing code.
A.3.1 APS-A, APS-AV, APS-CV: AMERICAN PHYSICAL SOCIETY JOURNAL ARTICLES
The American Physical Society (APS), nonprofit organization working to advance the knowledge of physics, publishes several reviewed research journals. The APS makes two datasets based on its publications available to researchers: (i) an edge list containing (citing, cited) pairs of articles contained in its collection, and (ii) JSON dataset containing the metadata for each article in its collection. These datasets are updated on a yearly basis, and researchers can request access by filling out web form located https: : / jjournals aps org/ /ataaatsttsss We made data access request and were granted access to the 2021 versions of the APS datasets within two weeks.
From the APS datasets, derived the following hypergraphs and hypergraph collections:
aps-a: Each node corresponds to an author who published least one article in an APS journal. Each edge corresponds to an article in an APS journal, and it contains as nodes all authors of This hypergraph derived from the JSON data.
(ii) aps-av: aps-a, split up by journal, for total of 19 hypergraphs. For each journal j. the edge set of aps-a is restricted to articles from j, and the node set of aps-a a is restricted to nodes authoring at least one article from j.
(iii) aps-cv: We derive one hypergraph for each of the 19 journals represented in the edge list data. For each journal j. the edge set comprises articles from j citing at least one article in j. and the node set consists of articles in j cited by at least one article in j.
Access. Due the terms and conditions associated with data access, we cannot make the APS datasets or the hypergraphs derived from them publicly available, and researchers seeking to work with this data will have to request data access from APS directly outlined above. However, we make our preprocessing code publicly available, such that researchers who have obtained access to the APS datasets can easily reproduce our hypergraphs from the raw data.
Caveats. When doing our case studies on the aps-cv dataset, we observed that some DOIs present in the edge list had no associated metadata the ISON files provided by APS. This does not affect curvature computations, but it might constrain the interpretability of results, e.g., when inspect- ing node clustering results based on article categories present only in the metadata.
hhopp://dooi.or//10..222 12tm
17

---

Published as a conference paper at ICLR 2023
A.3.2 DBLP, DBLP-V: DBLP JOURNAL ARTICLES AND CONFERENCE PROCEEDINGS
The DBLP computer science library provides high-quality bibliographic information on computer science publications, All DBLP data is released under CCO license and freely available in one XML file that is updated regularly. We obtained the XML dump dated September 1, 2022 from https: dblp. org/ //x/m/////// release/ and preprocessed it into CSV file containing only en- tries corresponding to the AMI.tags article and inproceddi ngs, ngs, with one row per entry and the following columns:
key: unique identifier of the entry, egg. journals caaurnasscaam//e// Savagel 6c.
or
tag: XML tag associated with the entry, one (inproceedings, article).
crossref: cross-reference to venue, e.g., conf/iclr/200 Sometimes missing although a venue should be present.
author: semicolon separrted list of DBLP author names, e.g.. Keyulu Xu; Weihua Hu; Jure Leskovec Stefanie Jegelka. Sometimes missing (we discard entries without authors when loading the data).
year: entry publication year, e.g.. 2019.
title: entry title, e.g., How Powerful are Graph Neural Networks?.
publtype: if present, the type of publication, e.g., informal. Mostly missing.
journal: for article entries, the name of the publishing journal, e.g., Commun. ACM.
booktitle: for inproceedings entries, the name of the publishing venue, e.g., ICLR.
volume: present, the publication volume, e.g., 59.
number: if present, the publication number, e.g., 7.
pages: if present, the entry pages, e.g., 12-14.
mdaat: modification date, e.g., 2019-07-25.
This constitutes our individual hypergraph dblp, in which each edge represents a paper, and each node represents an author. From this hypergraph, we additionally derived the dblp-v hypergraph collection, which contains different subsets of dbip by venue group of venues. More precisely, we distinguish 193 hypergraphs as follows:
dbl holpp_.. p_ p_inproceedi ngs-aall partition of dblp into entries pub- lished in journals and entries published as part of proceedings.
db ablp_jourral--p
iii halp_jourrral--- (journal): one hypergraph per journal, for all journals with at least 000 articles in the DBLP dataset.
(iii) db 1 httplpppooeediegeeeeeeegeoeeeeep wwwpocceeeing---eeoene wwwiingsssvvvvnn (venue): : one hypergraph per venue (grouped by booktitle), for venues with at least 000 papers in the DBLP dataset.
(iv) db dblp__hh wtt_pppcceenn__ss__eee_e areearaareea atlaaaareaa_v_eeaaaaaa_aa_ (venues); one hypergraph per each of the FoR (field of research) areas 4601-4608, 461 1-4613 as used in the CORE ranking (4609 and 4610 were not present in the ranking), where each area represented by all conferences (grouped by booktitles le) with CORE rank A and A that have at least I 000 papers in the DBLP dataset. These areas and associated top conferences are as follows:
4601: Applied computing AIED, ICCS
4602: Artificial intelligence - AAAL, AAMAS, ACL, AISTATS, CADE, CIKM, COLING, COLT, CP, CogSci, EACL, EC, ECAL, EMNLP, GECCO, ICAPS, IJAAL IROS, KR, UAI
4603: Computer vision and multimedia computation AAAI, CVPR, ECAI, ICCV, ICME, IJCAI, IROS, WACV
4604: Cybersecurity and privacy AsiaCCS, CCS, CRYPTO. DSN
4605: Data management and data science CIKM, ECIR, EDBT, ICDAR, ICDE, ICDM, ISWC, KDD, MSR, PODS, RecSys, SDM, SIGIR, VLDB, WSDM, WWW
46066 Distributed computing and systems software ASPLOS, CCGRID, CLUSTER, CONCUR, DISC, DSN, HPCA, HPDC. ICCAD, ICDCS, ICNP, ICPP, ICS, ICWS, IN- FOCOM, IPDPS, IPSN, PODC, SC, SIGCOMM, SPAA, WWW
4607: Graphics, augmented reality and games ISMAR, SIGGRAPH, VR, VRST
18

---

Published as a conference paper at ICLR 2023
2
2
Number of Drugs
213
Number of Drugs
213
2
210
27
22
24.
2
21.
100
150
200
100
150
200
Number of Active Ingredients
Number of Pharmaceutical Classes
(a) nde-ai
(b) nde-pe
Figure 4: Edge cardinality distributions for hypergraphs derived from NDC data.
4608:
Human-centree computing - ASSETS, CHI, CSCW, ITICSE, IUI, SIGCSE, UIST
4611: Machine learning- AAAL, AISTATS, COLT, ECAL, ICDM, ICLR, ICML, IJCAL, KDD, NeurIPS, PPSN, WSDM
4612: Software engineering ASE, ASPLOS, CAV, ICSE, ICST, ISCA, ISSRE, MSR, OOPSLA, PLDI, POPL, RE, SIGMETRICS
4613: Theory of computation EC,, ESA, FOCS, ICALP, ICLP, ISAAC, ISSAC, KR, LICS,
MFCS, SODA, STACS, STOC, WG
Caveats. For about 0.1% of all records, XML parser failed, which originally resulted in "None" as one of the authors of all problematic records. We then redid the preprocessing (and all subsequent computations) excluding those records, but the records were still counted when de- termining the venues to include in dblp-v.
A.3.3 NDC-AI, NDC-PC: DRUGS APPROVED BY THE U.S. FOOD & DRUG ADMINISTRATION
The U.S. Food and Drug Administration (FDA) collects information on all drugs manufactured, prepared, propagated, compounded, or processed by registered drug establishments commercial distribution in the United States. The FDA maintains the National Drug Code (NDC) Directory, which is updated daily and contains the listed NDC numbers and all information submitted as part of drug listing. We downloaded the NDC data from ht https: / dwwnloowdd open fda. gov/ drug/ / /ndc/dde /erer/ruggneeee ndc- 000100000--000000 oo 10000001, json. zip on August 21, 2022, and transformed into CSV file, example record of which is shown in Table 3. From this CSV file, we derived two hypergraphs. In both hypergraphs, edges correspond to FDA-registered drugs. In ndc-ai, nodes correspond to the active ingredients used in these drugs, and ndc-pe, nodes correspond to the pharmaceutical classes assigned to these drugs. The edge cardinality distributions resulting from both semantics are shown Fig.
A.3.4 MUS: MUSIC PIECES
mus 12l1 an open-source Python library for computer-aided musicology that comes with corpus of public-domain music in symbolic notation. Using the music21 library, extracted collection of hypergraphs from the music2] corpus. In this collection, each hypergraph corresponds to music piece, each edge corresponds from the start of the piece, and each node corresponds to a sound frequency. Note that hypergraphs node-aligned, which distinguishes them from the hypergraphs in all other
chord sounding for specific duration at particular offset
in the collection collections. In Table 4, we show the cardinality decomposition of selected music hypergraphs that include the largest edges. There, we include edges of cardinality 0 for completeness (they correspond to pauses in the music), but they are discarded in our curvature computations.
Caveats. When constructing our hypergraph collection from the mus i c21 corpus, we excluded pieces that primarily monophonic. After exploring the corpus manually and evaluating the chord
19

---

Published as a conference paper at ICLR 2023
Table 3: Example record from the data underlying the ndc-ai and nde-pe hypergraphs.
Column Name
Record Value
product_ne nde
71930-020
active_ingredientss ingredients names active www_inncddinssssrreeeeeee
[ACETAMINOPHENN HYDROCODONE BITARTRATE]
[325 mg/1, 7.5 mg/1]
pharm_class marketing_catee category dea scshecueeeee finished packaging
[Opioid Agonist [EPC), Opioid Agonists [MoA]]
ANDA
CH
True
[[ [('package nde": '71930-020-12" "description': '100 TABLET in
BOTTLE (71930-020-12) 'marketing start date": '20180713". 'sample":
'description': '500 TABLET in False I paacaage nde": 71930-020-522'
BOTTLE (71930-020-52). 'marketing start date": '20180713', 'sample":
Falsc)]
dosage_fomn
TABLET
product_type spl id route product id
HUMAN PRESCRIPTION DRUG
[ORAL]
71930-020 005.555557-----00005444545111113 ANDA210211
opplication_numbe
labeler_name
Eywa Pharma Inc
generic_name
Hydrocodone Bitartrate and Acetaminophen
Trand_name
Hydrocodone Bitartrate and Acetaminophen
brand_ hand_nnme_hait
Hydrocodone Bitartrate and Acetaminophen
frand_name__a sufff_ listing expiration date marketing start date marketing end openfda
2022-12-31
2018-07-13
imamufacturer_namee ['Eywa Pharma Inc'), 'rxcui': ['856999',
'857002', '857005"1. 'spl_setid': [fcc22b90-8087-4455--0d6
911bd846ca96') 1, 'is ts__origina__acaant [TTrue]. 'upe': ['0371930011221,,
'037193002012'' '03719300191281,
'unii': ["NO70W386KK]
'32009TTL9D"I
statistics of individual pieces, decided to only music with the following prefixes (correspond- ing to names of composers or collections): bach, beethoven, chopin, haydn, handel, monteverdi, mozart, palestrina, schumann, schubert, verdi, joplin, trecento, weber. Some pieces are included in several editions (e.g., BWV 190.7, the chorale by Johann Sebastian Bach occupying the first two lines of Table 4, which included in both the original and instrumental version).
A.3.5 STEX: STACKEXCHANGE SITES
StackExchange is platform hosting Q&A communities also known sites. Each question is assigned at least one and at most five tags. In the second half August 2022, we used the StackEx- change API download all questions asked on all StackExchange sites listed the StackExchange data explorer (https: //aata. stackexchange com/), along with their associated tags and other metadata (including question titles and, for smaller sites, also question bodies). From our downloads, we created the stex hypergraph collection, in which each hypergraph corresponds to a StackExchange site, each edge corresponds to question asked on site, and each node corresponds to tag used at least once on site. Tables 5 to 11 list the basic statistics for each hypergraph from the stex collection.
Caveats. While our curvature computations uniformly include only questions asked no later than August 15, midnight GMT, the metadata associated with these questions stems from snapshots at different times in the second half August 2022. We also excluded s stackover math. stackexchangee com from our downloads because they could not be downloaded within one day due to API quota limitations, and ru. s stackoverflow com because was large but we would not have been able to interpret results.
com and
20

---

Published as a conference paper at ICLR 2023
Table 4: Selection of hypergraphs from the mus collection. the number of nodes, is the number of edges, and the columns labeled i for i 10.1..... 12] record the number of edges of cardinality in the hypergraph. Identifiers correspond to abbreviated musica identifiers and generally have the shape [composer]- (orkk <dentifier)((uffix) where stands for opus, stands movement, and inst stands for instrumental.
m
772
2
5
10
11
12
bach-bwy190.7-ins
38
233
0
60
56
72
bach-bwy190.7
38
233
1
0
0
4
25
60
56
72
6
0
bach-bwv248.25
23-2
35
155
1
0
12
45
90
0
bach-bwy248.42-4
38
386
3
11
42
147
106
54
14
0
heethoven-o133
88
5 140
236
565
828
1555
7788
168
42
21
5
0
0
beethoven-ol8noll-n
70 1979
28
295
165
472
761
244
beethoven-ol88ol
77 2669
13
338
438
678
1032
134
33
1
1
1
0
0
0
beethoven-ol8no4
81 4.700
95
465
674
977
1940
521
50
beethoven-oo99oll-mg
75 2338
27
80
231
338
1467
168
18
4
4
0
0
beethoven-o599o22m1
86 2338
60
127
398
427
1665
203
18
30
beethoven-o399no3-m4
81 399
19
381
529
734
1219
255
139
14
1
0
0
0
beethoven-o74
6492
112
440
922
448
2
288
538
119
monteverdi-madrigall..
35
480
1
9
40
194
151
76
4
1
0
0
0
caatmaann-claaao1170-0 17-m3
63
819
5
12
133
208
151
108
83
74
25
13
schumann-o41 -nn-ammnn--nnnn---
72 2410
51
130
208
592
919
366
117
18
2
0
A.3.6 SHA: SHAKESPEARE'S PLAYS
The sha collection is subset of the HYPERBARD dataset recently introduced by Coupette et al. (2022), based on the TEl-encoded XMI. files of Shakespeare's s plays provided by Folger Digital Texts. Here, each hypergraph represents one of Shakespeare's plays, which are categorized into three types: comedy, history, and tragedy. In each hypergraph representing play, nodes correspond named characters in the play, and edges correspond groups of characters simultaneously present on stage. These hypergraphs are documented extensively in the paper introducing the HYPERBARD dataset (Coupette et al., 2022).
A.3.7 SYN-C, SYN-R, SYN-S: SYNTHETIC HYPERGRAPHS
To generate synthetic hypergraphs, wrote hypergraph generators extending three well-known graph models to hypergraphs.
ii) For syn-c, we extended the configuration model, which, for undirected graphs, is specified by degree sequence. Our hypergraph configuration model is specified by node degree sequence and an edge cardinality sequence.
(ii) For syn-r, we extended the Erdös-Rényi random graph model, which, for undirected graphs, is specified by number of nodes and edge existence probability p. Our Erdós- Rényi random hypergraph model is specified by a number nodes n, number of edges m, and the probability p of
in any cell of the node-to-edge incidence matrix.
(iii) For syn-s, we extended the stochastic block model which, for undirected graphs, is specified by vector community sizes and e e affinity matrix specifying affiliation probabilities between communities. Our hypergraph stochastic block model is specified by vector of node community sizes, a vector of cg edge community sizes, and cv X Cg affinity matrix specifying affiliation probabilities between node communities and edge communities.
We used each of our generators to create 250 hypergraphs with identical node count n. edge count m, and density o/mm where is the number of filled cells in the node-to-edge incidence matrix.
Caveats. Our generators work by pairing node and edge indices, and duplicated (node, edge) index pairs are discarded to generate simple hypergraphs, which can lead to small deviations from the input specification in practice.
21

---

Published as a conference paper at ICLR 2023
Table Basic statistics of hypergraphs derived from StackExchange sites. n is the number of nodes, m is the number of edges, and columns labeled i E [5] count edges of cardinality i.
71
m
n/m
2
3
5
3dprinting
416
4902
0.084863
1 1003
1 167
367
649
266
3dprinting.mest
45
0.228426
85
38
academia
457
39 39.270
0.011637
6428
11 831
360
6
294
357
academia.mett
91
1237
0.073565
396
486
249
95
11
980
10204
0.096041
767
1 805
2696
2427
209
ai.meta
49
315 0.155556
100
132
67
11
5
alcohol
154
138
0.135325
415
406
229
56
32
alcohol.meta
28
94 0.297872
28
42
2
android
1 517
56403
0.026896
12890
18313
406
6996
3798
android.meta
103
996 0.103414
159
447
281
97
12
anime
528
12 122 0.126052
9510
2215
348
6
anime.meta
83
900 0.092222
234
384
215
56
11
apple
969
121
999 0.007943
15822
34777
372443
22
11
505
apple.meta
108
1452
0.074380
354
601
393
90
14
arduino
445
23616
0.018843
5838
7357
6027
2858
536
arduino.medt meta
50
255
0.196078
101
110
34
10
0
askubuntu
137
393
0.007977
68310
104.299
105
601
68
907
45919
astronomy
566
12773
0.044312
2781
3812
3884
1777
119
astronomy.meta
63
339
0.185841
115
93
76
43
12
aviation
1224
22701
0.045108
4294
793
6384
3231
1599
aviation.meta
73
752
0.097074
247
295
155
46
9
bicycles
548
18873
0.029036
4884
6267
4652
2097
973
bicycles.meta
74
442
0.167421
150
197
76
15
4
bioacoustics
354
287
1,233449
20
50
101
54
62
coacoustics.meta
36
49
0.734694
4
24
16
0
bioinformatics
490
4998
0.098039
922
1420
1335
782
539
bioinformatics.meta
29
112
0.258929
44
53
15
0
biology
745
27 348
0.027241
5487
8618
7093
742
2408
biology.meta
88
814
0.108108
280
331
145
44
14
bitcoin
936
28 882 0.032408
6677
8927
7 7432
3 766
0880
bitcoin.meta
58
434 0.133641
142
202
71
16
3
blender
371
98 724 0.003758
01
30
861
22 200
961
5337
blender.meta
69
716 0.096369
273
291
108
35
9
boardgames
1 1000
13 166 0.075953
9800
2779
500
75
12
boardgames.mett
75
659 0.113809
197
289
144
27
2
bricks
202
4220
0.047867
1391
1 669
805
266
89
bricks.meta
52
211
0.246445
45
95
51
17
buddhism
487
7956
0.061212
2381
2357
730
896
592
buddhism.mest
59
491 0.120163
104
252
94
30
11
cardano
285
248
0.126779
585
664
548
277
174
cardano.mett meta
24
43 0.558140
15
0
chemistry
370
41571
0.008900
9725
14 183
10
790
2070
chemistry.meta
90
1 1034
0.087041
250
441
243
88
12
chess
387
7 864
0.049212
1 1646
2682
2 2069
985
482
chess.meta
62
368 0.168478
102
183
72
2
chinese
166
10298
0.016120
4467
3438
1 1628
543
222
chinese.meta
60
349 0.171920
93
170
67
12
7
christianity
129
14955
0.075493
1739
3571
405
2967
2473
christianity.meta
110
1579
0.069664
593
589
285
88
24
civicrm
507
14324
0.035395
4639
150
3085
083
367
civicrm.meta
18
69
0.260870
43
18
6
0
codegolf
257
13228
0.019428
1360
4586
4379
2 106
797
codegolf.meta
128
2276
0.056239
559
848
549
245
75
codereview
111
76
105
0.014638
6300
20
23777
106
9.37
codereview.meta
133
1 1947
0.068310
190
615
688
345
109
22

---

Published as a conference paper at ICLR 2023
Basic statistics of hypergraphs derived from StackExchange sites (continued). n is the number of nodes, m is the number of edges, and columns labeled E [5] count edges of cardinality i.
Table 6:
T2
170
7/m
2
3
4
coffee
11 114
381
0.082549
492
524
260
78
27
coffee. moffee.meta meta
27
90 0.300000
45
30
13
2
communitybuilding
74
559 0.132379
148
219
112
55
25
communitybuidding.net
27
132 0.204545
36
24
4
computergraphics
259
600 0.071944
883
024
877
489
327
computergraphics.mett
34
150 0.226667
55
66
27
2
conlang
96
448 0.214286
109
204
91
32
12
conlang.mets
21
61 0.344262
16
34
7
4
cooking
834
25
877
0.032229
6 568
266
6344
2882
1017
cooking. meta
83
866 0.095843
241
410
178
34
craftems
523
13756
0.038020
3738
4912
3410
266
433
craftems.mett meta
20
50 0.400000
22
11
15
crafts
193
2039
0.094654
706
828
397
24
crafts.
49
184 0.266304
40
88
45
11
0
crypto
506
27 447
0.018436
6448
956
6600
283
700
crypto.meta
74
542 0.136531
139
237
127
27
12
cs
656
44
794
0.014645
624
14
332
14444
6336
2858
cs.meta
86
603 0.142620
90
247
185
68
13
cseducators
210
080 0.194444
297
378
252
116
37
cseducators.meta
29
146 0.198630
52
68
26
0
estheory
498
11 959 0.041642
1 653
3 384
3495
2
1375
cstheory.meta
80
608 0.131579
157
262
156
30
datascience
663
33 997 0.019502
4110
8228
305
6753
5801
datascience.mert
51
237 0.215190
80
97
38
dba
197
96 887 0.012355
15956
750
27
361
15610
7622
dba.meta
76
800 0.095000
280
334
140
38
devops
431
502
0.085771
1070
144
340
616
352
devops.meta
40
144 0.277778
45
63
31
5
diy
919
71
007 0.012942
19
347
22.799
173
399
3811
diy.meta
68
603 0.112769
227
233
118
21
drones
220
731 0.300958
114
240
193
115
69
drones.meta
28
62 0,451613
11
31
17
3
drupal
149
86
86283
0.001727
25
218
37
18
867
4.755
524
drupal.meta
75
1
1014
0.073964
361
432
186
35
dsp
509
24
850
0.020483
4460
6779
6565
488
2965
dsp.meta
48
307 0.156352
153
108
30
14
earthscience
424
6329
0.066993
1111
1778
1,698
1
099
648
carthscience.meta
54
321 0.168224
100
145
63
12
ebooks
180
466
0.122783
364
489
339
163
111
ebooks.meta
39
99 0.393939
31
37
23
6
economics
494
13
690
0.036085
3 4888
4426
160
1
1678
938
economics.meta
60
444 0.135135
241
151
40
7
electronics
2318
175731
0.013191
31 201
46423
46
974
29
107
22026
electronics.meta
107
685 0.063501
698
628
282
62
15
elementaryos
314
8 8471
0.037068
3 043
2910
669
619
230
elementaryos.me
29
107 0.271028
60
28
17
2
ell
533
99 970 0.005332
46 764
310
14
644
147
105
ell.meta
93
1224
0.075980
448
489
226
52
emacs
891
23939
0.037220
7561
9.77
4980
5590
437
emacs.metr
51
216 0.236111
34
112
59
engineering
468
13867
0.033749
3582
411
3315
1770
1079
engineering.meta
47
217
0.216590
71
87
45
english
984
125
848
0.007819
48
232
38
850
23
112
10
111
5543
english.mett
182
388
0.050711
224
1305
733
249
78
eosio
241
2
0.099505
766
766
533
245
112
23

---

Published as a conference paper at ICLR 2023
Basic statistics of hypergraphs derived from StackExchange sites (continued). n is the number of nodes, is the number of edges, and columns labeled E [5] count edges of cardinality i.
Table 7:
m7
7/m
2
3
4
5
eosio.meta
19
27
0.703704
6
14
4
2
1
168
1817
0.092460
310
665
568
230
44
es.stackoverflow
2960
479
0.016495
38
58
218
47
343
23
415
12449
esperanto
99
1592
0.062186
1050
422
16
8
esperanto. meta
20
84 0.238095
37
38
9
0
0
ethereum
891
46678
0.019088
8449
12
402
12.
687
5813
ethereum.meta
63
259 0.243243
98
71
59
26
5
expatriates
304
7 7182
0.042328
166
2 178
2 163
1,66
617
expatriates.mer
48
157
0.305732
41
72
expressionengine
603
12447
0.048445
3724
4239
2.901
150
433
expressionengine.nee
35
123 0.284553
59
49
15
0
fitness
402
9666
0.041585
2133
2
2664
2427
289
964
Rtness.mets
54
315 0.171429
126
123
2
freelancing
125
1946 0.064234
632
654
394
177
89
freelancing.men
132 0.250000
36
64
2
french
324
12413
0.026102
3368
126
2923
390
606
french.meta
73
290 0,251724
58
127
24
1
gamedev
1 096
54182
0.020228
7381
16 130
15 996
9433
5442
gamedev.meta
78
910 0.085714
300
430
148
27
5
gaming
5 883
983555
0.059814
72
20
20708
420
758
114
gaming.meta
177
4002
0.043575
478
1 1833
2119
425
87
gardening
526
16629
0.031631
3725
5.390
412
2997
295
gardening.meta
60
320
0.187500
95
157
49
17
2
genealogy
465
3572
0.130179
421
742
1037
902
470
genealogy.meta
56
485
0.115464
133
273
70
8
1
german
265
16022
0.016540
6003
5915
2914
927
263
german.meta
69
540
0.127778
177
224
107
30
2
gis
2 829
150
205
0.018834
868
36527
339
32
527
21
944
gis.meta
91
1 1016
0.089567
174
361
317
125
39
graphicdesign
612
320
0.017576
7542
10789
9 364
4
304
graphicdesign.mett
83
851
0.097532
253
338
187
58
15
ham
334
2.9
0.077692
927
287
1 199
610
276
ham.meta
45
156
0.288462
39
65
32
18
2
hardwarerecs
246
3945
0.062357
2011
366
823
378
177
hardwarerecs.men
42
255
0.164706
81
100
58
16
0
hermeneutics
422
12563
0.033591
2819
3720
3774
1772
178
hermeneutics.men
581
0.108434
256
212
22
7
hinduism
825
15771
0.052311
2.977
4.37
3976
876
1 985
hinduism.ment
827
0.107618
196
295
200
98
38
history
843
13784
0.061158
2071
3757
3
839
2436
681
history.meta
746
0.091153
340
265
107
31
3
homebrew
415
6 6113
0.067888
1393
1976
1593
803
348
homebrew.meta
50
172 0.290698
67
63
35
3
hsm
252
3 8988 0.064649
982
272
928
464
252
hsm.meta
32
146 0.219178
44
37
0
interpersonal
280
3890 0.071979
342
030
307
790
421
interpersonal.mett
76
825 0.092121
214
328
205
62
16
iot
241
2 203
0.114598
560
754
504
193
92
iot.meta
36
136 0.264706
30
74
27
0
148
022 0.144673
300
352
248
84
39
iota.meta
18
38 0.473684
10
20
8
0
islam
562
13792
0.040748
3018
990
3 557
1519
708
islam.meta
103
864 0.119213
240
358
206
47
13
italian
3,50
0.026184
196
1
636
206
76
italian.meta
27
151
0.178808
77
57
14
2
1
24

---

Published as a conference paper at ICLR 2023
Basic statistics of hypergraphs derived from StackExchange sites (continued). n is the number of nodes, is the number of edges, and columns labeled E [5] count edges of cardinality i.
Table 8:
π2
17
7/m
2
3
5
ja. meta.staccooerrflww
74
1 115
0.066368
193
386
306
204
26
sttakkoverlloww
145
785
0.039778
10077
10518
624
1946
620
japanese
354
26366
0.013427
9.325
8669
191
2020
960
japanese.mete
817 0.091799
270
351
147
43
6
joomla
374
7 190 0.052017
289
2221
2058
1072
550
joomla.meta
41
150 0.273333
81
46
19
0
judaism
264
36511
0.034620
3753
8
116
10854
842
5746
judaism.meta
147
1 1455
0.101031
108
576
489
222
60
korean
118
1716
0.068765
767
596
264
69
20
korean.mett
30
80 0.375000
38
28
8
1
languagelearning
216
287 0.167832
225
466
354
176
66
languagelearinng.mes
52
195 0.266667
31
103
48
12
1
latin
370
5 5400
0.068519
1223
603
1371
797
406
latin.meta
46
192 0,239583
34
80
49
25
4
938
23 649 0.039663
4483
7573
63229
381
883
law.meta
66
499 0.132265
117
216
120
36
10
lifehacks
140
2928 0.047814
1024
1052
595
190
67
lifehacks.met
59
268 0.220149
65
122
72
6
3
linguistics
605
10003
0.060482
1947
2836
2,566
627
003
linguistics.mett
59
363 0.162534
118
159
58
23
5
literature
2335
5 5614
0.415924
703
1 621
2449
830
211
literature.met
63
462
0.136364
56
292
99
15
0
magento
1811
110316
0.016416
15 598
28
805
32
20
123669
magento.mett
66
575 0.114783
251
227
17
2
martialarts
205
2199 0.093224
461
696
529
326
187
martialarts.mes
40
218 0.184486
66
97
0
math.meta
232
9 169 0.025303
1051
3485
2919
1312
402
matheducators
225
3360
0.066964
696
1118
903
435
208
matheducators.mee
57
255 0.223529
64
119
61
3
mathematica
705
85 069 0.008287
25
896
31
653
18
182
6.542
2796
mathematica.men meta
75
914 0.082057
416
341
130
25
2
mathoverflow.ne net
530
137 735
0.011108
20.88
37
763
38
643
24.
24
16351
mattermodeling
449
2422
0.185384
169
547
668
495
543
mattermodeling.meet
61
142
0.429577
25
41
29
37
10
mechanics
1 1430
25
0.056649
496
6245
7592
4673
2537
mechanics.men meta
52
387
0.134367
124
182
66
13
2
medicalsciences
1435
7 586
0.189164
1423
1970
1754
1261
178
medicalsciences..en
65
501 0.129741
171
191
102
27
10
meta.askubuntu
196
5 398 0.034398
1625
2308
1 257
397
111
meta
250
97
114
0.012871
4.599
25
289
34
23
9986
meta.maathoverlow.ne
133
1 1687
0.078838
272
601
504
229
81
meta.serverfault
139
2773 0.063967
767
799
463
119
25
meta.stackoverrlow
622
47 387
0.013126
297
15301
15
8233
2764
meta.superuser
207
5 000
0.041400
1010
1914
1474
510
92
monero
400
488
0.093349
193
1424
969
481
218
monero.meta
23
85 0.270588
40
26
19
0
money
1 002
36 187 0.027690
3788
8036
10:440
8450
5573
money.meta
67
672 0.099702
220
260
147
40
5
movies
4537
21 829 0.207843
4857
11430
4546
877
119
movies.meta
285
0.058366
302
519
391
music
516
23 424
0.022029
4754
7644
6370
3117
133
music.meta
992
0.081653
391
387
166
40
8
musicfans
237
2990
0.079264
200
169
465
111
36
musicfans.met
42
218
0.192661
62
95
18
5
mythology
303
1 1953
0.155146
484
723
439
215
92
25

---

Published as a conference paper at ICLR 2023
Basic statistics of hypergraphs derived from StackExchange sites (continued). n is the number of nodes, is the number of edges, and columns labeled E [5] count edges of cardinality i.
Table 9:
π
171
7/m
3
4
5
mythology.meta
35
162
0.216049
43
87
31
0
networkengineering
453
15
624
0.028994
2 2988
240
335
2
496
066
networkengineerringnmm
53
375
0.141333
192
115
48
17
opendata
302
590 0.050417
1362
2002
499
670
264
opendata.mete meta
26
180 0.144444
73
76
30
0
opensource
203
226 0.048036
845
1442
094
528
317
opensource.mett
53
225
0.235556
35
109
61
19
or
255
2 2865
0.089005
351
809
848
496
361
or.meta
44
114 0.385965
21
61
23
outdoors
555
5 908 0.093940
934
2017
1791
806
360
outdoors
52
512 0.101562
169
276
60
parenting
304
6 636 0.045811
182
2175
1 173
1 004
402
parenting.meta
61
473 0.128964
217
125
patents
2 102
488 0,479799
I 1421
1211
879
481
389
patents.meta
46
0.275449
69
34
pets
289
7 874 0.036703
781
2706
2,3
1 305
732
pets.meta
62
407 0.152334
194
112
15
philosophy
606
17915
0.033826
8
5.399
4.7
2
089
1450
philosophy.meta
61
793 0.076923
355
258
127
38
15
photo
156
25961
0.044528
3,55
6960
7 848
4936
222
photo.meta
107
1 1095 0.097717
289
500
239
60
7
physics
892
209
515 0.004257
21
914
42
808
53 150
45
705
45938
physics.meta
114
3228 0.035316
713
1085
872
403
155
pm
283
6198 0.045660
3779
1850
5592
870
507
pm.meta
64
315 0.203175
81
129
73
27
5
poker
2051
0.063871
763
6599
181
76
poker.meta
29
122 0.237705
74
30
15
3
0
politics
793
14
628
0.054211
294
022
663
3
062
5887
politics.meta
80
1
067
0.074977
249
436
259
103
20
portuguese
169
344
0.071946
703
898
509
174
65
portuguese.mett
35
137 0.255474
45
61
25
5
proofassistants
223
434 0.513825
80
175
116
42
21
proofassistants.meta
37
64 0.578125
11
26
18
2
psychology
401
7641
0,052480
1 632
2229
1971
1115
694
psychology.mett
62
557
0.111311
199
237
90
25
k..meta.stcckoverllww
140
9986
0.046885
703
081
775
362
65
pt.stackoverflow
2936
152
483
0.019255
28 143
50055
42
42386
21
287
10612
puzzling
209
24985
0.008365
6912
9471
5731
2020
851
puzzling.meta
98
1665
0.071795
351
582
309
26
quant
693
28.883
0.034167
3 322
5345
5392
356
2661
quant.meta
47
252
0.186508
95
115
37
3
quantumcomputting
306
7 823 0.039115
124
2585
2475
1 105
534
quantumcomputing.nee
50
187
0.267380
50
73
43
18
raspberrypi
598
35 872
0.016670
7901
11
152
9.351
765
603
raspberrypi.me
61
451 0.135255
213
169
58
retrocomputing
546
4976 0.109727
925
1694
3666
692
299
retrocomputing. meta
70
304 0.230263
30
188
56
27
reverseengineering
347
7554
0.039639
1878
2693
2122
249
762
reverseengineering.mo
37
150 0.246667
56
62
28
3
robotics
276
261
0.044082
528
1550
1 519
806
558
robotics.meta
39
159 0.245283
52
71
28
8
0
rpg
1447
46.355
0.026740
433
124
134
9.542
4963
rpg-meta
150
2627
0.057099
310
986
844
379
108
ru ww.meta.stackoverforr
242
4613
0.052460
445
1312
1574
979
303
390
909999
0.018572
12.76
5131
2331
840
411
26

---

Published as a conference paper at ICLR 2023
Table 10: Basic statisties of hypergraphs derived from StackExchange sites (continued), n is the number of nodes, is the number of edges, and columns labeled E [5] count edges of cardinality i.
771
7/m
1
2
3
4
rus.meta
30
214
0.140187
92
81
37
4
russian
166
4.5
0.036758
2407
1337
552
180
40
russian.meta
37
176
0.210227
80
61
25
7
salesforce
085
424
0.016748
22737
37977
33
635
19
220
123
salesforce.mett
79
795
0.099371
412
246
118
18
scicomp
346
10381
0.033330
1905
156
283
1 1566
871
seicomp.meta
48
215 0.223256
75
90
42
8
scifi
693
69 344
0.053256
17338
26498
17 146
6,584
1778
scifi.meta
149
3265 0.045636
506
160
889
266
44
security
2553
65817
0.019038
11 950
19
18 266
9 809
5993
security.mets
101
1224 0.089858
311
507
242
52
12
serverfault
3 864
344
0.012292
40967
83417
92 763
60
560
36
635
sharepoint
1222
99911
0.017235
16092
27312
28 073
17
305
129
sharepoint.meta
78
581 0.134251
206
233
127
14
sitecore
362
11:955
0.031768
106
4265
1611
342
sitecore.meta
24
202
0.118812
40
60
99
3
skeptics
682
10.00
0.063738
2,27
4165
2952
1
1042
314
skeptics.mett
100
1,529
0.065402
528
605
310
77
softwareengineerring
674
392 0.027267
8950
17773
17.80
10:52
6517
softwareengineering..etaa
165
2611
0.063194
421
1223
776
310
81
softwarerecs
962
792
0.044145
3090
6533
6199
3723
2247
softwarerecs.meta
85
654
O. 0.999969
86
297
189
66
16
sound
224
786
0.125077
122
2717
2330
1 624
993
sound.meta
42
160
0.262500
65
66
25
space
203
17:392
0.069170
1672
4012
4924
3712
3072
space.meta
74
682
108550
205
237
150
27
spanish
274
592
0.031890
2276
2722
140
1010
444
spanish.meta
84
498
0.168675
94
216
135
42
11
sports
261
5730
0.045550
926
2371
1637
609
187
sports.meta
57
350
0.162857
76
170
82
21
sqa
462
11242
0.041096
2263
3550
2881
1 705
143
sqa.meta
41
211 0.194313
115
71
17
7
stackapps
210
2756
0.076197
277
858
883
514
224
stats
572
196835
0.007986
19622
4796
979
57
502
41
443
30301
stats.meta
132
1685
0.078338
327
576
491
198
93
stellar
115
1493
0.077026
585
438
298
109
63
stellar.meta
19
31 0.612903
substrate
512
1814
0.282249
366
563
491
260
134
substrate.meta
40
44 0.909091
6
21
13
superuser
5676
480
854
0.011804
64 273
127
561
135
549
91
137
62
sustainability
234
2012
0.116302
431
713
536
235
97
sustainability.meta
37
151
0.245033
38
75
32
6
tex
2035
237
0.008559
60
247
84 998
59 476
23
747
995
tex.meta
163
2.77
0.071585
389
921
671
235
61
tezos
210
1288
0.114880
567
605
380
180
96
tezos.meta
18
32
0.562500
7
15
8
tor
218
5636
0.038680
1 1888
1817
147
464
320
tormeta
43
163 0.263804
57
76
25
travel
1916
040
0.042540
2985
8914
13 809
11 528
7
8004
travel.meta
99
1.79
0.071791
293
567
406
15
tridion
274
7334
0.037877
1471
2758
1915
818
272
tridion.meta
14
138
0.101449
93
39
6
ukrainian
124
2094
0.059217
664
873
404
127
26
ukrainian.met
33
104
0.317308
21
45
31
unix
2
220
644
0.012586
29 059
61 964
66
40
340
22
624
27

---

Published as a conference paper at ICLR 2023
Table 11:
Basic statisties of hypergraphs derived from StackExchange sites (continued). n is the number of nodes, m is the number of edges, and columns labeled E [5] count edges of cardinality i.
π2
m
n/m
2
3
4
5
unix.meta
1 118
1 668
0.070743
367
727
407
144
23
032
31 459
0.032805
660
9934
8 823
530
3.52
ux.meta
94
899 0.104561
273
358
199
54
15
vegetarianism
115
677 0.169867
85
233
205
106
vegetariamism.meta
41
133
0.308271
26
62
32
13
0
vi
421
12 558 0.033524
4.4
802
2,388
694
210
vi.meta
35
201
0.174129
63
105
30
0
video
327
8 661
0.037755
2705
2693
1 831
882
550
video.meta
41
200
0.205000
63
96
webapps
951
33 202 0.028643
14343
11
667
160
1435
597
webapps.mett
106
937 0.113127
97
447
311
76
webmasters
1 0778
36 840 0.029262
5772
10
197
10:531
286
454
webmasters.mett
70
649 0.107858
202
258
135
45
windowsphone
287
3440 0.083430
975
255
801
306
101
windowsphone.men meta
148 0.297297
64
woodworking
244
3739
0.065258
129
177
880
347
113
woodworking.me meta
34
142 0.239437
69
46
25
wordpress
702
112778
0.006225
27
669
37
039
28 491
13 228
6351
wordpress. meta
82
866
0.094688
381
330
118
30
7
workplace
498
30
0.016398
6371
9.325
8 103
4221
2349
workplace.meta meta
113
1 1229 0.061782
506
699
447
150
27
worldbuilding
675
348
0.019646
2958
284
10839
266
5010
worldbuilding. meta
120
2.02
0.059055
445
901
511
147
28
writing
391
11 699 0.033422
2456
869
3
555
762
writing.meta
88
789
0.111534
145
415
173
49
7
28

---

Published as a conference paper at ICLR 2023
A.4 IMPLEMENTATION DETAILS
To simplify the computation of Wasserstein distances between adjacent nodes, we leverage the fol- lowing fact about the relevant distances (i.e., transportation costs) between nodes.
Lemma 1. Given hypergraph H (V, E) and i, k. E V with ~ well μ (s(k) and p2(() (t) > 0, d(k, {) I 3.
Proof. By the triangle inequality and the definition of our probability measures, we have
d(ke L) d(k,)) + d(i,)) d(j,)) =3
Furthermore, we speed up the computation of Wasserstein distances by exploiting the following observation reduce each instance to its smallest equivalent instance.
Lemma 2. Given hypergraph H (V, E) and nodes i, E V with i ~ j. if ps(k) = My (k)(k) for some node k V, then Wi (14, (b) Wi (14 -11 k, where Ps k is defined as
0 =
M. (1)
(m: j jtk.
Proof. If = (k) = O, the claim holds trivially. Otherwise, p. (k) 0. In this casc, let C be an optimal coupling between μ4 and Mg. If the probability mass allocated to k by μ4 does not get moved at all C*, it contributes 0 to Wi (us (2), and we are done. Therefore, assume otherwise. Then there exist nodes p, and from to 9 in C By the triangle inequality, d(p, q) I d(p. k) - d(k, q). and as d(k, k) 0, the cost of moving that mass directly from p q and keeping all mass k cannot be larger than the cost of moving the mass from p to k and from to q. Hence, we can modify C* such that the mass allocated to k by μr does not get moved at all without increasing the coupling cost. Thus, there always exists an optimal coupling in which all mass at k remains at k and the claim follows. O
=
such that probability mass gets moved from p to
29

---

Published as a conference paper at ICLR 2023
A.5
FURTHER RESULTS
Here, we showcase further results to support and supplement the exposition in the main paper.
Q1 Parametrization. Expanding the discussion on ORCHID parametrizations, Fig. shows the distributions of edge curvatures and edge-averaged node curvatures for two hypergraphs from the dblp-v collection, representing top conferences in machine learning and theoretical computer sci- ence, respectively. The figure highlights once more the consistently concentrating effect of increas- ing a, and it elucidates the differential effects of moving from maximum aggregation (left parts of the split violins) to mean aggregation (right parts of the split violins), from almost shifts to large shifts in probability mass (compare, c.g., Fig. 5b, top right panel, with Fig. 5b, bottom left panel). Fig. 5 might convey the impression that, other parameters being equal, the distributions of curva- tures hased on y and f are more similar to each other than to j This does not hold in general, however, as demonstrated for ndc-pe in Fig. 6a, where node curvature distributions based f 4 are more similar to those based on μ than to the node curvature distributions based on μ²" Compar- ing Fig. 6a Fig. 6b (nde-ai), we further observe that rather similar distributions of edge curvature and directional curvature can be accompanied by rather different distributions of edge-avene aigeraae and averaged node curvatures, even for hypergraphs originating from the same domain. Fi- nally, when visualizing curvatures for hypergraphs in the same collection or across collections with related semantics (Fig. 7), we can identify several distinct prototypical shapes of curvature distribu- tions and relationships between curvatures based on different probability measures.
Q2 Hypergraph Exploration. Extending the discussion of individual hypergraph exploration in the main paper, we focus on case study of the citation hypergraph of the journal Physical Review (PRE), which regularly publishes, inter alia, interdisciplinary work on graphs and networks. In this hypergraph, which has 45 504 nodes and 52 574 edges, nodes represent PRE articles cited by at least one other PRE article, edges represent PRE articles citing at least one other PRE article, and each edge comprises the nodes j cited by the paper corresponding to Therefore, the edge curvature of (citing) paper i can be interpreted as an indicator of its breadth of content: The more positive the edge curvature, the stronger the general tendency of the papers jointly cited by paper to be cited together, suggesting that these papers are topically related. Similarly, the node curvature of a (cited) paper j can be interpreted as an indicator of its breadth of impact: The more negative the node curvature, the more diversely the paper has been cited in the literature.
With these interpretations in mind, we compute all curvatures for the PRE citation hypergraph, using 0.1, 12 and AGGa, We find that for all 54 articles with at least 100 citations (top articles), the edge-averaged node curvature is larger than the direction-averaged node curvature, which always negative, although only 36% of all PRE articles exhibit this feature combination. This matches the intuition that from highly cited articles, the literature should diverge in many different directions. At the same time, we observe that curvatures span considerable range, even among top articles. In Table 12, we record the top articles with extreme curvature values, and in Fig. 8, we display the pairwise relationships between curvature features and other local features for all PRE articles. In line with the interpretations sketched above, the top article with the largest node curvatures is a classic reference for community detection in the highly integrated field of network science, whereas the articles with the smallest node curvatures address topics relevant to a broader range of approaches collective phenomena in many-body systems (which are the focus of PRE).
30

---

Published as a conference paper at ICLR 2023
EEN
μ LE
u WE
Edge Curvature
1.0
0.5
0.0
0.5
2.0
0.0
0.1
0.2
0.3
0.4 0.5
0.0 0.1
0.2 0.3 0.4 0.5
0.0 0.1
0.2 0.3 0.4 0.5
WE Smoothing Parameter
Node Curvature (x²)
EN
F
0.5
0.0
1.0
1.5
2.0
0.0
0.1
0.2
0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
Smoothing Parameter a
(a) Top Conferences in Machine Learning
FN
μ F.F
u WE
Edge Curvature
1.0
0.5
0.0
0.5
0.0
0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
Smoothing Parameter
EN
EE
u WE
Node Curvature (x*)
1.0
0.0
1.0
115
2.0
0.0 0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5 Smoothing Parameter a
0.0 0.1 0.2 0.3 0.4 0.5
(b) Top Conferences Theoretical Computer Science
Figure 5: ORCHID curvatures are non-redundant. We show distributions ORCHiD edge curvatures (top) and edge-averaged node curvatures (bottom) using probability measures IN _ and se with smoothing o, for the aggregation functions AGGy (light blue) and AGG, (dark blue) on dblp-v hypergraphs representing top conferences in machine learning and in theoretical computer science.
31

---

Published as a conference paper at ICLR 2023
μ EN
p EE
WE
Edge Curvature
1.0
0.5
0.0
0.5
1.5
2.0
0.0
0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
Smoothing Parameter a
Node Curvature (x*)
# EN
# E
" WE
1.0
0.5
0.0
0.5
1.0
1.5
2.0
0.0
0.1 0.2
0.3
0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
Smoothing Parameter a
EN
1 EE
u WE
Direction Curvature
1.0
0.5
0.0
0.5
1.0
1.5
2.0
0.0
0.1
0.2
0.3 0.4 0.5
0.0 0.1
0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
Smoothing Parameter
Node Curvature (xeV)
H EN
1 EE
WE
1.0
0.5
0.0
0.5
2.0
0.0
0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5 Smoothing Parameter a
0.0 0.1 0.2 0.3 0.4 0.5
(a) nde-pe
Figure 6: Hypergraphs with similar distributions of one curvature type may differ their distribu- tions of other curvature types. We show ORCHID curvatures computed using AGG for all curvature types, probability measures, and a E {0.0, 0.1, 0.2, 0.3, 0.4, 0.53. (Figure continues on next page.)
32

---

Published as a conference paper at ICLR 2023
EN
EE
WE
Edge Curvature
1.0
0.5
0.0
-05
1.0
1.5
220
0.0 0.1 0.2
0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
Smoothing Parameter a
Node Curvature (x²)
U EN
F.
M WE
1.0
0.5
0.0
0.5
1.0
2.0
0.0
0.1
0.2
0.3 0.4 0.5
0.0 0.1
0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
Smoothing Parameter
Direction Curvature
EN
μ EE
p WE
1.0
0.5
0.0
0.5
1.0
1.5
2.0
0.0
0.1
0.2
0.3
0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5
Smoothing Parameter &
Node Curvature (x
EN
EE
μ WE
"
1.0
0.5
0.0
0.5
1.0
1.5
2.0
0.0
0.1
0.2 0.3 0.4 0.5
0.0 0.1 0.2 0.3 0.4 0.5 Smoothing Parameter
0.0 0.1 0.2 0.3 0.4 0.5
nde-ai
Figure 6: Hypergraphs with similar distributions of one curvature type may differ in their distribu- tions of other curvature types. We show ORCHID curvatures computed using AGG for all curvature types, probability measures, and a E {0.0, 0.1, 0.2, 0.3, 0.4, 0.5}. (Figure continued from previous page.)
33

---

Published as a conference paper at ICLR 2023
1.0-
Edge Curvature
0.5
0.0
0.5
1.0
1.5
-2.
PRXO
PR
PR-1
PRA
PRAB
PRApp
PRB
PRC
PRD
PRE
PRF
PRL
PRM
PRPER
PRR
PRST-AB
PRST-PERE
RMP
Node Curvature (x4)
1.0
0.5
0.0
0.5
-1.0
1.5
2.0
PRXQ
PR
PR-
PRA
FRAB
PRApp
PRB
PRC
PRD
PRE
PRF
PRI
PRM
PRPER
PRR
PRST-AB
PRST-PER
FREX
RMB
(a) aps-av
1.0
Edge Curvature
0.5
0.0
0.5
1.0
1.5
-2.0
PRXQ
PR
PR-1
PRA
PRAB
FRApp
PRB
PRC
PRD
PRE
PRF
PRL
PRM
PRPER
PER
PRST-AB
PRST-PER
PRX
RMP
Node Curvature (x²)
1.0
0.5-
0.0
0.5
-1.0-
1.5
-2.0
PRXQ
PR
PR-1
PRA
PRAB
PRApp
PRB
PRC
PRID
PRE
PRF
PRL
PRM
PRPER
PRR
PRST-AB
PRST- PERT
PRX
RMP
(b) aps-cv
Figure 7: ORCHID curvature distributions within the same collection and across semantically lated collections exhibit prototypical shapes, accompanied by varying types of relationships between probability measures. We show distributions of ORCHID edge curvatures (top) and edge-averaged node curvatures (bottom) computed using a = 0.1 and AG Gr, for μ (violet) and n (blue), for all hypergraphs in aps-av and aps-cv. Recall that the edges in aps-av and aps-cv as well as the nodes in aps-cv represent essentially the same set of APS papers, but in aps-av, they connect co-authors, and in aps-cv, they connect co-cited papers (edges) or are connected by citing papers (nodes).
34

---

Published as a conference paper at ICLR 2023
Table 12:
Top articles display varying relationships between different curvature values. We list the PRE articles that, out of all PRE articles cited at least 100 times, exhibit the most extreme curvature- related values.
DO1
x (8)
A(k(F))
K(e)
max (s).
10.1 J00//Moyseee.77..66661
04253366
Finding community structure in very large netwerks
min (()
10.1 100
-0,319638
-0.555431
0,235793
Scale invariant motion in internitent chaokic systems Exsended similanity
2 (3)
-0704152
0,465536
max (e())
10.1 100/PP/peee -0.131542
-0.68266
0.536724
0.038477
Determining the densily states for chasical statistical models: A randons walk algoritim produce a daat his- uugrum
(x(())
-0.015195
-0.191193
0.175697
0.156824
Ameephous systems athermal. quasistatic Topological defects and interactions in nemalic emul- sions
max x(c)
10.1 10.1089/PppNeev357.000
0.129557
-0.251633 1635
0.381192
0.610125
min ic(e)
10.1 R0.100//
-0.191094
-0.552908
0.361815
0.641665
Fox: Monte Carlo algorihhm for site bond percolation
Figure 8: Highly cited articles have distinct curvature distributions. Pairwise relationships between (left-to-right,, top-to-bottom) node neighborhood size, edge-averaged node curvature, direction- averaged node curvature, curvature delta, node expansion deg())//Ar()),, edge cardinality, edge neighborhood size, edge curvature, edge expansion == [ and (as an additional metadata feature) publication year, for all PRE articles cited at least once by another PRE article, colored by node degree (number of citations within PRE), where brighter colors signal larger node degrees.
35

---

Published as a conference paper at ICLR 2023
SPONGE-mwweigned--e Dtgprwiiiiii-----iieeafaii (0--iggeddddf-17
1.0
SPONGE sytsuneeighhee-
curvature- 100-dir cuncature_ negative-17
curvature 100-dir curvature_ppo _urature_positive-
rbfkome- adi-adi-oode curvature, edges11
tb 100 adj-ad/ curvature neighborfood-17
0.8
cbikernel- n00-no22 purvalure, edges-17
dbdkeree- 100- curvature, neighbothood-17
chikemel- (akemel-1000-oa 100---edde degree-17
rblkernel-110 node neighteshood, six-17
fbflemel-200mm degree-17
rilkernel 200 neightochoood six-17
0.6
zhfierne--S0-rohh degre-17
dskend- 50-nodd neighbodhood shx-17
tofkenel-TDDaa -TD-ad curvature 17
Mifeeml-STD-aff-oodd curvature neighboohood-1
rblkeme--11 aode curvature neighbothood::1
rbfierel--ST STD-node curvature edges=17
0.4
STDemo--TDDoodd degrne-17
rblkemel DD node neighboohooo. stze
spectral, dusster adjacency_ sog unweighted- signedadd-11
spectral, cluster, bno unweighted 10U signedad,-17
spectral closter Inplarinn-unveighhi
sigredad,-17
002
unweighted ad
wwssersteinkemme 100-9-17
waseersteenkemmelleee 20000----77777
wassersteinnkemeel STD-W-17
sorpiie sdge 17"
1?
sagharhooo 17
cervonte edger
modis ceraae nngghurfoote
17
aeaaahooo hood siseei
ii 21
21
21 peppoodle UIT paw zer soung leuzods
4 seeeeee cooproo
deeeeeeenn pos 3D
ero GUS cecie
tereemed 100-opot pe coooogoe
100 ponyfooum Sor peoooni
o01 pSiy powylpaum unpodda caum? popas
corronan dlt cun
-00---00---- relleeed 100--ood
nods
Balkemal tn sa
soom
papods
Figure 9: Node clusterings based on curvature features differ radically from clusterings based on other local features. We show the normalized mutual information (upper triangle) and the adjusted rand score (lower triangle) of node clusterings based on different method/feature combinations, computed on the citation hypergraph of PRB from the aps-cv collection, with curvatures computed using a 0.1, ME and AGGa-
Q3 Hypergraph Learning. Continuing the discussion of node clustering in hypergraphs abridged in the main paper, we again focus on the citation hypergraph corresponding articles from Physical Review E (PRE). We experiment with a variety of features, clustering methods, and combinations thereof, including both classic and recent clustering methods, such as SPONGE (Cucuringu al., 2019). We aim for 17 clusters, which is the number of "disciplines" present in the APS metadata (un- fortunately, disciplines are only assigned to more recent articles, and hence, cannot serve as ground truth). As depicted in Fig. 9, we find that clusterings generated using curvatures as features differ radically from clusterings generated using other local features. To evaluate the semantic sensibility of our clusterings in the absence of suitable ground truth, we leverage the metadata associated with PRE articles. In particular, we concatenate the titles of the articles grouped in each of our clusters into "documents", and consider the set of all clusters our "document collection", to then identify characteristic terms for each cluster using TF-IDF feature extraction. We observe that clusterings based ORCHID features tend be more thematically coherent than clusterings based on other local features. As illustrated Table 13, ORCHID features tend to separate paper titles well by topic (many frequently occurring terms associated with only very few clusters, and the terms grouped together characterize specific subfields of the physics of collective phenomena covered by PRE), whereas clusters based on non-ORCUID features are much less topically focused.
36

---

Published as a conference paper at ICLR 2023
Table 13: ORCHID features lead node clusterings that are semantically more coherent than node clusterings derived from other local features. For two clusterings of the PRE citation hypergraph from the aps-cv collection- one spectral clustering using the sign of directional curvatures as a feature (Table 13a), the other clustering using RBF kernel with node neighborhood size feature (Table 13 show the top terms, i.e., the terms associated with each cluster that have a TE-IDF score of at least 0.1, along with their TF-IDF scores and their occurrence frequency across all clusters, in tuples of shape (term, TD-IDF score, global occurrence frequency).
(a) Feature: sign of directional ORCHID curvatures
(smecric, 0.51, 13, (liquid, 0.39, 4), (erystals, 0.22, (antiferooletric, 0.21, 1) (crystal, 0.19, 2), (phase, 0.17, 4), (chiral, 0.17. 1), (co, 0.15, DJ (poper, 0U15, D.
1), (scissurs 0.15, (electric, 0.14, (phases, 0.14, (ray, 0.13, (eyelic, 0.13, Ospecies, 0,12, (Beld. 0.11. (games, 0.1.
tresetting, 0.76, 1), (stochastic, 0.322 trandoes, 0.24, (walks, 0.18, (diffission, 0.17, (brownian, 0.15, igrocessess, 0.11.
(nemaric, 0.66, 2), (liquid, 0.41, (erystal, 0.3, 2), (oolloodal,, 0.26, 1), (oollnids, 0.18, 1) Corystals 0.16, (portictes, 0.15, 13, (interaction, 0.14, 1)
(boltzmean, 0.75, 1), (lattioo, 0.51, D), (method,, 0.2, 13, (flos, 0.15, 1), (model, 0.11. 5)
(quantum, 0.58, 3), (bean, 0.38, 1), (ongine, 0.34, 1), (enginos, 0.37, 1), (offieseenyy 0.34, Ix (performiner, 0.21, 1), (power, 0.17, 1), (maximom, 0.17, 1), (otto, 0.12,
(comot, 0,12, D) (refiigenatoss 13
Igranular, 0.85, 2), (gas, 0.17, 1), (goses, 0.16, 1) (inelastic, 0.13, 1) (driven, 0.13,
(chimera, 0.7, 1) (states, 0.35, 1), (oscillators, 0.33, 1), Ecooplod 0,31, 2), (notworks, 0.2, 3), (nomlosilly, 0.13, 1), (chimeras, 0.12, 1), (ocupling. 0.1. [)]
idynamics, 0.19, 1). (model, 0.18, 5) (networks, 0.17, 30, (liquid, 0.16, 4), (diffusion, 0.13, 2), (phase, 0.13, 4), (quantum, 0.13, 3), (dimensional, 0.12, 1), (random, 0.12, 2), (foow, 0.11, 2), (systems, 0.11, 1) (plasma, 0.11, 1), (coupled, 0.1, 2), (ime, 1)
6dynamic, 0.41, 1) Gsing. 0.35, 2), (plase, 0,34, 4), Coscillatnn, 0.34, 1t (field, 0.32, 3), (transition, 0.24, 1), (kinetic, 0.2, 1), (model 0.2, 5), (migneric 0.15, D.
(eoneguilheium, 0313, (blume, 0,12, 1) (cope), 0.12, 1) (transirions, 6.11, T)
(biaxial. 0.53, 1), Inematic, 0.5, 2), (iquid, 0.29, 4), (crystals, 0.19, 4), (phases. 0.19, 2), (beni, 0.17, D) (phase, 0.16, 4), (molecules, 0,15, 1), (conc, 0.14, D. Isamulatoon 0.12. Imotecular, 1), (ontinemati,,
Imsesggencc, 1)
(gassive, 0.47, 1). (scaloe, 0,41, (anomalous. 0.39, 1), 0.29, 1X, (advected, 01.4, 1), (tufhulenee, 0.22, 1X (turhallnt, 8.18, 1), (advection, 0:15, TJ (loop. 0.12, 1), (onisotoppy B.11, (anisotropic, 0.11, (ennomalizzaion,
(vector, 0.11, 0.1,
Iquanrum, 0.51, 3), (decay, 0.45, (losctaniit,, 0.33, (ecbo, 0.33, (fidelity, 1), (chootic, 0.23, 31, (semiclassical 0.18, DJ dyypuuu,,, 0.13, (pecturtations, 0.11.
(ensimiir 0.69, 1), (eritical, D), (Borees, 0.27, (flms,, 0.13, 1), 0.13, (force, 0.13, 1), (fuiii, 0.12, (ftec, 0.11, (ising, 0.31, (Menmodyaanic, 0.1. D. (model, 0.1, 5)
(traftic, 1), (flow, 0.3, 2), (model, 0.13, 5), (car, 0.13, 1), dellooiing 0.11, 1)
trogue, 0.62, (schridinger, 0.34,
0.31, (wave, 2), (equation, 0.25, (nonlincar, 2), (solutions, 0.17, (soliton, 0.12, (solitoos,
(cooperation, (dilemma, 0.38, (prisonee, 0.34, (game, 0.25, (games, 0.24, 2), (evolutionary, 0.19, (networks, 0.18, 3y, (spatial, 0.17, 1), (social, 0.14, D) (public, 0,12, 1). (goods, 0,1. I)
Igranular, 0.59, 21, (chains, 0.36, 1), (chain, 0.52, 1), (propagation, 0.22, 1), (waves, 0.21, 2), (nonlinear, 0.2, 2), (solitury, 0.2, 1), (wave, 0.17, 21, (pulse, 0.15, 1), (erystals, 14,4, 4), (strongly. 0.12, l)
37

---

Published as a conference paper at ICLR 2023
(b) Feature: node neighborhood size
frolation,, 0.37, Fentroppy 0.34, 1), (diffiorences 0.34, 2t, (production, 0.34, 1), (theorem, 0.34, 1), (work, 0.31, 2), (flcctuttinn 0.29, 1), (noncquilibrium 0.37, (fice, 0.27, 5). (energy. 0.27, 3)
tmsodel, (125, 5). (phise, (1233, 5), (dimensional, 0.2, 3), (dynanics, 0.18. 6) (time, 0.17, 4), (networks, 0.16, duttice 0.15, 73, (systems, 0.15, 8). (gnanalar, 0.13, 6), (stochustic, 9.13, 23, trandoan 0.12, 61, (nnise, 0.12, 1), (lquid, 0.12, 4), (nonlineus, 0.12, 2), theld, 0.12, 2), (difiusion, 0.11, 4), (quanoum, 0.11, 4), (coupled, 0.11, 2), (transition, 0.11. 5), (boltzmann, (bblltuamm
O.1, 6)
(model, 0.28, 5) (networks, 0.25, 10), Cuattioe 0.22. 7), (bolumann, 0.21. 6), (equations, 0.19, 2), (stuchasiic, 0,15, 2), (dynamics, 0.14, 6), (transition, 0,13, 5),
femnchonization, 0,13, 3), (granuler, 0.13, 6), (time, 0.13, (ealle 0.13, 3), (glans, 0.13, 3). (syseems, 0.12, 8), (nundom, 0.12, 6). (dimensional, 0.12, 3), (phase. 0.12, 5), (diffusion, 0.11, (comples,
freactionn
(froc, (.1,5)
Imodel, 0.32, 5), (microstates, 0.25, (suxiliary, 0.27. (violating, 0.27, D) (counections, 0.24, (genense, 0.34, 1), (steady, 0.22, D) (collisions, 0.22, 13, (ising, 0.2, 11. (aggroact, 0.2, 2), (distibution, 0.2, (second, 3), (choos, 0,17, 1), (gases, 0.17. 2). (states. 0.17, 21, (graular, 0.15, 6), (networks. 0.13, 10)
(law, 0.2, D) Igeneralized, 0.2, 1), (arbitray, 0.2, 2), (equilibrium, 0.18, 21, (syachronizaiin, 0.18,
(equation, 0.22, 4), (fokker, 0.19. 1y iplanck, 0.19. 1), (hurd, 0.19, 21, (fractionll 0,17, D. odynamies. 0.16, 6), (observable, 0.13, 1), fevoluion, 0.12. D. (chur-
scteristiss 0.12, 1), Quusistatic, 0.12, 1). (comectionn 0.12, 1), (cohosion, 0.12, 1t. (puir. 0.12, (ncarly 0.12, 1), (ondered. 0.12, 1), (chamatteiizatioon 0.12, D.
(geasyyggooii 0.12, 1), (formulas, 0.12, 1). (themalization, 0.12, 1), (depinning, 0.12, 13, (thooeams 0.11, 1) (low, 0.11, 1), (amorphous, 6,11, 23, (intemiitinny. fcorrlation,
D) Gummed, 0.11, (prupelled. 0.11. 1), (oxllecative 0.11. 1), (interacting. 0.11, 1), fasymptotic, 0.11, Deteengeneitt. 8:11, 1). (6inglaritiss, 0.11. 1), (dense, 0.1, 23, (highty, 0.1. 1), (near, J. D)
D) Ohydrudynamics,
(oraalnchee 0.11, (othermal
21, (tumpport, 0.31, (solution.
(indlasic, 0.I. 1), (quantum, 0.1. 4), (Buid, 0.1, 2), (self, 0.1, 21, (shear, 0.1, 2), (theology, 0.1, 2), (Bow, 0.1, 3). O.1, 2). Olquids, 0.1. D), (grwwch 0.1, 1), (laws, D.I. D. Gppllicttion. 0.1. 1), (disundened, 0.1, 1) (walks,, 0.1,
teewwoks, 0.38, 10), (scientifc, 0.22. 1) (collaboration, 0.19, 1J, (path, 0.19. 1) 0.16, 1), (deasity, 0.14, 2), (diffusion, 0.14, 4), (bends, 0.12, 1), (theory, 0.12, 4). (gystems, 0.12, (gramula, 0.12, (mandon, 0.12, 6), (schools, 0.11, 1)
(attice, 0.27. 71, (nstworks, 0.26, 10), (boltummnn. 0,21. 61. (phase, 0,18, 5), (models, 0,16, DJ, (ttructure, 0,16, 21, (method., 0.16, 4), (interactions, 0.14, D) (eel,e,, 0,14, 0.13, (community.
3), (social, 0.12, (Free, 0.12. (dimensions, 0.12, 1), (scale, 0 3), (gramular, 0.11, 6), (random, 0.11, (systoms, 8), (motion, 0.1. 1), (graphs, 0.1, 2), (tramsition, 0.1, 5), (emulsions, 0.1. L)
(netwoeks, 0.24, 10), (glass, 0.17, 2), (transition, 0.17.5), (luticc 0.15, 7), (solutions, 0.14, 1), (systems, 0.14, S1, lequations, 0.13, 21, (lkEvy 0.13, Clarge,
13. (oxtemal, 0.13, 1), (jammad, 13, 2), (lights 0.13, 1), (coerelated, 0.15, 1), (quantum, 0.12, 4), (compled, 12, 2), (anallysis, 0.12, 1), (Forzz, 0.12, 1), (ealleidal, 0.12, 1), (order, 0,12, (pockings, 0.11, 13 (eyynchronizatio,, 0.11, (Band, 0.11, 2), (time, 0.31, (langevis, 0.11, 1), (ffictustions, 0,11, 1), (density, 0.1,
(model, 0.24, 5) Glymamics 0.22, 61, (dimensiomal 0.2, 3), (phase, 0.19, 5) (iquid, 0,15, 4), monlineet,, 0.15, 2), (systems, 0,14, 8), (field, 0.13, 2), (lime, 0.12, 4). (quantum, 4), (transition, 0.11, 5), (diffasion, 0.11, (flow 0.1, 3), (induced, 1)
(netwooks, 0.41, 10), (evalnating. 0.36, 1), (uncoorelated, 0,36, 1), (gencratios, 0.36, 1), (dinding, 0.3, 13, (stmucture, 0128,, 2), (commnnity. 0.28, 2), (frec, 0.26, 5), Iscale, 0.26, (random, 0.23,
Izern, 0,55, D. (epitome. 0.3, 1), (applied, 0.27, D. Capplications, 0.27, 1) (distributins, 0,25, (stress, 0.25, D) (arbitrary, 0.23, 2), (disoeder. 0.23, (degree, 0.23, 1), (lemperature, 0.23, (jamming, 0.23, 1), (grapes, 0.21, (random, 0.17.
Imetsuremenss 0.35, (hienrchiical 0.32, (differences, 0.32, taggenach, 0.3, 21, (organization, 0.3, 2), (mastor, (equilibrium, 0.27, 21, (nonequiibrrium, 0.25,2), 2). (free, 0.25, 9). (energy, 75, 5) (complex, 0.34, 3), (equation, 0.21, 4), (nerworks, 0.2, 10)
inucleotides, 0.29. (bove, 0,29, (mixing. 0.26, 1), (van, 0.26, (mosaic, 0.26, (correlation, 0,24, (dna, 0.24, D), (puttems, 0,24, 1), (organization, 23. (lesting. 0.22. 1). Emixtume 0.22, 1), (lenmed, 0.2, 1), (jness 0.2, 1), (superoooeed, 0.2, 1), (function, 0.19. 1), (coupling, 0.19, 1), (mode, 0.19, 1), (hinary, 0.19.
2), (theory, 0.17, 4) (networks, 0.15, 10)
flatiie, 0.42, 7) (peroslation, 0.32, 1), (boltzmann, 0.26, 6) (mante 0,21, 1), deem, 0.21, 1) (cadoo, 0.21, 1). (site, 0.19. 1). (forcing, 0.19, 1), (fiee, 0.17. 1), (bond, 0.17, 1), (transitions, 0.17, 1), (algorithm, 0.17, 1), leffeets, 0.16, 13 (lguid, 0.16, 4), (phese, 0,16, 5% (discrete, 0.16, 2), (network, 0,16, 2), (gas, 0,16, 2), (simulation. 2), (nonideal, 0 1), (smal), 0.15, 1) (xroeeld 0.15, 1) (scaling, 0.15, (gares, 0,10,,00111 0.15, (modle), 0.34, (mathod. 0:14, 4), (equttion, 0.12, 4)
(viscoplaticc 0.33, 1y (dissippttinnn 0.29, (deformation 0.29. (iscrrppy, 0.29. 1). (dispemion, 0.29. D). (amoephous, 0,27, 2), (stbiliiy, 0.27. 1), (solids, 0.27, I). (galilean, 0.27, invaniaccee 0.27. D, (dymmmics, 0.2, 6), (mothod, 4), (uatiie,
(boluzmnnn 0.19, (thoory. 0.19.4)
(bolezmonn, 0.63, 6) (latice. 0.5 (ogustion, 4), (Smulationn, 0.21, 1), (Bokd, 0.21, 2), (liquid, 0.19, (gm, 2), (binory, 0.18, (methed, 0.17, (theory, 0.16, 4), (systenss 0.16,
Iplane, 0.38, 1), (flo,, (bugnokd. 0.19. D) (nclined. 0.19, D. (partial, 0.17, D. (effective, 0.17, 1), iflows, 0.16, 1). (dease, 0.16, 2), (epidemic, 0.16, 12, ishear. 0.16, 2). (slom, 0.16, D).
3), (dynamics, 0.26, (granolan, 0.24, 6), Gtheophysics, 0.24, 1) fendemic, 0,21, (emperttures 0.19, (equilibration, 0.19,
(theology. 0.16. 2) (discrese 0,15, 2) (simulation, 0.15, 2), (states, 0.14, 2), (scaling, 0,14, 2), (materials, 0,14, 1), (emergy, 0,14, 3), (complex, 0.13, 3% (systems. 0,12. 8), (networks. 0.11,
38


Reviews:
[{"review_id": "d1AbqzZdpec", "reviewer": "Reviewer_x9Zy", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduces a unified framework called Ollivier-Ricci Curvature for Hypergraphs In Data (ORCHID). This framework is the first to generalize the Ollivier-Ricci curvature (ORC) of graphs to hypergraphs and yields a notion of curvature consistent with geometric intuition. This work provides rigorous theoretical and empirical analysis of the resulting curvature formulations and demonstrates the utility of these concepts in practice through extensive experiments.", "summary_of_the_review": "The sufficiency and necessity of the paper are the important part and generalization from graphs to hypergraphs should focus on considering higher-order associations of hypergraphs, as well as highlighting the advantages compared to graph-based frameworks.", "strength_and_weaknesses": "Strength:\nThis paper analyzes three probability measures based on random walks on hypergraphs. The related formulas and definitions of ORC in graphs are extended to hypergraphs, making their concepts consistent with geometric intuitions and rigorous proofs.\n\nWeaknesses:\n1. Figure 1 needs to be more clear and intuitive. For example, too many directed edges are used in Figure 1(d) to describe the random walk of weighted edges. It is recommended to use the relationship between the weighted edge and the hyperedge cardinality to represent, so that would be more concise.\n2. The definition of AGG(s) in Eq. (14) is ambiguous. In this paper, it is said that Eq.(14) is consistent with the previously defined hyperedge curvature. But should we understand it as the sum of AGG for nodes in subset s or  understand it as AGGM(s) ?\n3. In Corollary6, only Equal-Nodes Random Walk is analyzed, but Equal-Edges Random Walk and Weighted-Edges Random Walk are not analyzed.\n4. In Figure 3a, the shapes and colors in the legend indicate errors, languages should be represented by upper triangles, and Nerds should be represented by dots.\n5. This paper uses unlabeled datasets for experiments and then uses the Wasserstein Clustering Coefficient to measure the results. We recommend using a labeled dataset, so that ground truth can be accurately obtained, allowing for more intuitive comparison of results.\n6. This paper generalizes the Ollivier-Ricci curvature of graphs to hypergraphs, and the experimental part should focus on the advantages of using hypergraph curvature and compare ORCHID with methods which using Ollivier-Ricci curvature for graphs.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ys-MWoIaTM", "reviewer": "Reviewer_22tj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper introduces a notion of curvature on hypergraphs. It is related to Ollivier's notion, which works for metric spaces with Markov chains on them. In that case, curvature is (basically) the curvature describes the contraction of the map from points x to the transition probabilities from x. \n\nThere is a \"canonical\" choice of Markov chain for graphs -- (lazy) random walk -- but there's no obvious choice for hypergraphs, so the paper explores three possibilities. It also proves some bounds and intuitive properties of these definitions. \n\nOne motivation for introducing a new notion of curvature is to have a \"local\" (and thus simple to compute) parameter that is indicative of \"global\" features of the network. This idea is tested in an exploratory empirical study, where the newly introduced curvatures seem to function as meaninful features for clustering and hypergraph exploration/node differentiation. ", "summary_of_the_review": "The paper offers an intriguing new notion of curvature for hypergraphs that seems to perform well in practice. My main misgivings are about the lack of more systematic comparisons with other approaches. \n\n-- \n\nUPDATE on Nov 30th: \n\nI am a bit more positive about the comparison with other approaches, and have raised my score accordingly.", "strength_and_weaknesses": "*Strengths*\n\n- The paper presents a principled method for defining curvature parameters in hypergraphs. \n- Some mathematical results and properties are presented.\n- These new parameters seem to serve as good features for clustering and other tasks, as demonstrated in an experimental study. Figure 3 and Table 2 are compelling.\n\n*Weaknesses*\n\n- Although I am happy with some experiments, I found it hard to draw conclusions from the experiments in general. For instance, I do not understand to what the authors are comparing Table 13 to. \n- More broadly, since are other notions of curvature for hypergraphs, and other methods for extracting hypergraph features, I would like to understand how the new notion introduced here compares to the alternatives in practice. What is the state of the art? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4PnfK7Z3s2B", "reviewer": "Reviewer_Bvqz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper provides a framework for computing Olivier-Ricci curvature (ORC) on hypergraphs. In order to extend ORCs to hypergraphs, it provides multiple notions of probability measures and Similarity measures (extension to Wasserstein distance in graphs). The non-redundancy of these notions is shown through experiments on data from various domains.", "summary_of_the_review": "The novelty of the contributions overweigh the minor weaknesses.", "strength_and_weaknesses": "The paper is quite dense (especially for a non-expert in graph theory) but well-written. It seems that the proposed notions are diverse and maybe separately important in various applications. The experimental validation seems to be appropriate.\n\nWhat is missing is that how other curvature measures on hypergraphs, such as FRCs, compare to the proposed extension of ORCs. Since the framework does not extend FRCs, it might have been interesting to see how differently it act, if that is the case.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "-EuaVD_GbyR", "reviewer": "Reviewer_LgSf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a unified framework for Ollivier-Ricci curvature on hyper-graphs, by incorporating and generalising existing approaches to hyper-graphs. It can be regarded as the first attempt towards defining RC curvature, based on rigorous theoretical and empirical analysis of the resulting curvature formulation.", "summary_of_the_review": "The paper is in excellent shape and worth for an acceptance.", "strength_and_weaknesses": "strength:  1. they use several ways to generalize graph Ricci curvature into hypergraphs based on general features of hypergraphs. \n2. They derive the bound of the newly defined curvatures.  3. using the newly defined curvatures to show its empirical advantanges compare to single node information.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster