From Graphs to Hypergraphs: Hypergraph Projection and its Reconstruction
Authors: Yanbang Wang
Jon Kleinberg
Venue: ICLR 2024 poster (2024)
Keywords: hypergraphs
hypergraph projection
learning-based reconstruction
Primary area: general machine learning (i.e., none of the above)
TL;DR: We study the implications and remediations of the modeling choice to use a graph, instead of a hypergraph, to represent real-world complex systems whose relationships are of higher order by nature.

Abstract: We study the implications of the modeling choice to use a graph, instead of a hypergraph, to represent real-world interconnected systems whose constituent relationships are of higher order by nature. Such a modeling choice typically involves an underlying projection process that maps the original hypergraph onto a graph, and is prevalent in graph-based analysis.  While hypergraph projection can potentially lead to loss of higher-order relations, there exists very limited studies on the consequences of doing so, as well as its remediation. This work fills this gap by doing two things: (1) we develop analysis based on graph and set theory, showing two ubiquitous patterns of hyperedges that are root to structural information loss in all hypergraph projections; we also quantify the combinatorial impossibility of recovering the lost higher-order structures if no extra help is provided; (2) we still seek to recover the lost higher-order structures in hypergraph projection, and in light of (1)'s findings we make reasonable assumptions to allow the help of some prior knowledge of the application domain. Under this problem setting, we develop a learning-based hypergraph reconstruction method based on an important statistic of hyperedge distributions that we find. Our reconstruction method is systematically evaluated on 8 real-world datasets under different settings, and exhibits consistently top performance. We also demonstrate benefits of the reconstructed hypergraphs through use cases of protein rankings and link predictions.

Published as a conference paper at ICLR 2024
FROM GRAPHS TO HYPERGRAPHS: HYPERGRAPH PROJECTION AND ITS RECONSTRUCTION
Yanbang Wang. Jon Kleinberg
Department of Computer Science, Coreell University (ywangdr, k inneerrggg rg) @cs. cornell 1, edu
ABSTRACT
We study the implications of the modeling choice use a graph, instead of hypergraph, to represent real-world interconnected systems whose constituent relationships are of higher order by nature. Such modeling choice typically involves an underlying projection process that maps the original hypergraph onto a graph, and is common in graph-basee based analysis. While hypergraph projection can potentially lead to loss of higher-order relations, there exists very limited studies on the consequences of doing so, as well as its remediation. This work fills this gap by doing two things: (1) we develop analysis based on graph and set theory, showing two ubiquitous patterns of hyperedges that are root to structural information loss in all hypergraph projections;
also quantify the combinatorial impossibility of recovering the lost higher-order structures if no extra help is provided; (2) we still seek recover the lost higher-order structures in hypergraph projection, and in light of (1)'s findings we propose to relax the problem into a learning-base setting. Under this setting, method based on an important statistic of hyperedge distributions that we find. Our reconstruction method is evaluated on 8 real-world datasets under different settings, and exhibits consistently good performance. We also demonstrate benefits of the reconstructed hypergraphs via use cases of protein rankings and link predictions.
develop learning- -based hypergraph reconstruction
INTRODUCTION
Graphs are abstraction of many real-world complex systems, recording pairs of related entities by nodes and edges. Hypergraphs further this idea by extending edges from node pairs to node sets of arbitrary sizes, admitting more expressive form of encoding for higher-order relationships.
In graph-based analysis, fundamental and enduring issue exists with the modeling choice of using a graph, instead of a hypergraph, to represent complex systems whose constituent relationships of higher order by nature. For example, coauthorship networks and social networks, as popular subjects in graph-based analysis, often use edges to denote two-author collaborations or two-person conversations, respectively. Protein interaction networks do the same for protein co-occurrence in biological processes. However, coauthorships, conversations, and biological processes all typically involve more than just two authors, people, and proteins. Reviewing more concrete cases in previous research, we find that this issue usually arises in one of the following two scenarios:
"I "Unobservable": In some key scenarios, the most available technology for data collection can only detect pairwise relations, as is common in social science and biological science. For example, in the study of social interactions (Madan et al., 201T Ozella et al.) [02T] Dai al.. 2020). sensing methodologies to record physical proximity can be used to build networks of to-ceto-face interaction: an interaction between two people is recorded by thresholding distances between their body-worn sensors. There is no way to directly record the multiple participants in each conversation by sensors only. the study of protein interactions (Li et al. 2010; Yu & Kong 2022, Spirin & Mirny 2003), detecting protein components of multiprotein complex all at once poses way more technical barriers than identifying pairs of interacting proteins. Methods for the latter are often regarded being more economic, high-throughpun reliable, and thus more commonly used.
"Unpublished": Even when they are technically observable, in practice the source hypergraph datasets of many studies are never released. For example, many influential studies analyzing coauthorships do not make available a hypergraph version of their dataset (Newman 2004; Sarigöl
let al.] 2014). Many graph benchmarks, including stXiv-heptl (Leskovec et al. 2005 ), ogbl-collo ooblacoolab (Hu et al. (020). and agbnnproodctt(H et al. (2020). also do not provide their hypergraph originals. Yet the underlying, unobserved hypergraphs contain important information about the domain.

---

Published as a conference paper at ICLR 2024
In both cases above, there is often an underlying hypergraph projection process that maps the original hypergraph onto a graph on the same set of nodes, and that each hyperedge in the hypergraph is mapped to a clique (i.e. complete subset where all nodes are pairwise connected) in the graph. In other words, two nodes are connected in the projected graph iff they coexist within a hyperedge.
While it's easy to perceive the loss of some higher-order relations during hypergraph projection, to this date we still have many crucial unanswered questions regarding this issue's 's detailed cause, consequences, and potential remediation: (Q1) what connection patterns of hyperedges in the original hypergraph are combinatorically impossible recover after the projection? (Q2) What are the theoretical worst cases that these connection patterns can create, and how frequent do they occur in real-world hypergraph datasets? (Q3) Given a projected graph, is it possible to reconstruct a hypergraph out of it if some reasonable extra help is allowed, and if so, how? (Q4) How might the reconstructed hypergraph offer advantages over the projected graph?
Hypergraph reconsruction. We note that all the questions above essentially point to a common prob- lem structure which is the reversal of the hyper- graph projection process: there is an underlying hypergraph Hi that we can't directly observe; in- stead we can only access its projected graph (or projection) G1. Our goal is to reconstruct Hi as accurately as possible from G1. The first two ques- tions above assume no extra help (input) should be given in the reconstruction, other than the projected graph 11 itself. The latter two questions permit some extra input, which we will elaborate in Sec
Project
Reconstruct?
Graph G2
Hypergraph 36,
Figure I: hypergraph reconstruction as the reversal of hypergraph projection. Given projected graph GL. the goal is to reconstruct the original hyper- graph Hi in real world as accurately as possible.
For broad applicability, we assume no multiplicities for G1 's edges: they just say whether two nodes co-exist in at least one hyperedge. Appx.
F. addresses the simpler case with edge multiplicities.
Previous work. Very limited work investigated implications of hypergraph projection its reversal (i.e. hypergraph reconstruction). For implications, the only work to our knowledge is Wolf et al. (2016), which compares hypergraph and its projected graph for computational efficiency on spectral clustering; the former was found to be more efficient, For reconstruction, Young et al.) (202T) is by far the closest, which however studies how use least number of cliques to cover the projected graph, whose principle does not really apply to real-world hypergraphs (see experiment in Sec
In graph mining, two relevant problems are hyperedge prediction and community detection, yet both are still vastly different in setup. For hyperedge prediction (Benson et al.) [018a b. Yadati jtt al., 2020; Xu et al., 2013), its input is hypergraph, rather than a projected graph. Methods for hyperedge prediction also only identify hyperedges from given set of candidates, rather than the large implicit spaces of all possible hyperedges. Community detection, on the other hand, looks for densely connected regions of graph under various definitions, but not for hyperedges. Both tasks are very different from the goal of searching and inferring hyperedges over the projected edges. We include discussion of other related work in Appendix C
2 PRELIMINARIES
Hypergraph. A hypergraph H. is a tuple (Vε)): V is a set of nodes, and غ = (E1, Eg,..., E2,...,,mml 3m is set of sets with E, V for all 1 S i S For the purpose of reconstruction, we assume the hyperedges are distinct, i.e. V1 visijj S m, F, # F..
Projected Graph. H's projected graph (i.e. projection, clique expansion), G, is graph with the same node set V, and (undirected) edge set E', i.e. G (V.E'), where two nodes are joined by an edge in E' iff they belong to a common hyperedge in E. That is, E' = {(v,, U;) lu;, U/ E, E E). Maximal Cliques. A clique C' is a fully connected subgraph. We use C' to also denote the set of nodes in the clique. A maximal clique is a clique that cannot become larger by including more nodes. The maximal clique algorithm returns all maximal cliques M in graph, and its time complexity is linear to M (Tomita et al. 2006). A maximum clique is the largest maximal clique in a graph.
3 ANALYSIS OF HYPERGRAPH PROJECTION AND RECONSTRUCTION
We first analyze hypergraph projection and its reversal from the lens of graph theory and set theory, addressing (Q1) and (Q2) raised above.
2

---

Published as a conference paper at ICLR 2024
Dulaset
[E]
18"
LM
Ercl
Emrll
Emarl Patirn
Korar El Pattern
DRI P Henson
197,067
194,598
166,571
2.02%
18.9%
Beason
756
300
362
42.5%
53.3%
41
2018a
Suursquaae
1,019
874
8,135
1.74%
88.6%
Young 2t al.
"Nested Hyperedase"
"Ulesverr Trienge"
Hosts-
218
126
361
19.5%
58.19
Virus Young
hyperedges
2021)
I School Ben
3,909
2864
3,279
14.9%
82.7%
Error
maximal cliques M
2018a
Error
correct reconstructon
clique space
The upper panel shows hyperedge patterns that trigger errors in max-clique based reconstruction. Error I leads to missing Es (false negative), while Error results in an incorrect identification of max clique vi, 03, us as a hyperedge (false positive) and overlooks Un, Us (false negative). The lower panel shows the errors' associations with & and M.
Figure 2:
Table I: & is the set of hyperedges; E' is the set of hy- peredges not nested in any other hyperedges; M is the set of maximal cliques in G. Error I, II result from the violation of Conditions I, II, respectively. Error I
JE [aM]
Error [M("" Errors caused by violation of [&uM]
both conditions counted as Error 1.
Hyperedge patterns that are hard to recover after projection (Q1)
In principle, any clique in projection can be true hyperedge. Therefore, toward perfect reconstruc- tion we should consider U. the universe of all cliques G, including single nodes. To enumerate 44 a helpful view is the union of all maximal clique's power set: U UceM P(C) X Ø. In that sense, maximal clique algorithm is critical first step for hypergraph reconstruction, as also applied by Young et al. (2021) to initialize its MCMC solver. In the extreme case, it's easy to see that if H's hyperedges are all disjoint, G's maximal cliques would be exactly H's hyperedges. It is impossible to find all hyperedges without finding all maximal cliques. Therefore, we consider the reconstruction accuracy of maximal clique algorithm a good measure of the reconstruction' 's difficulty.
The maximal cliques of G are exactly all hyperedges H., i.e. M= E, if and only if the following two conditions hold:
Theorem 1.
I. for every hyperedge E e & there does not exist a hyperedge E' s.t. Ec II. every maximal clique in G is hyperedge in H. i.e. M
Theorem D gives the two necessary and sufficient conditions that characterize when H is "easy" to reconstruct. Note that Condition I is the famous Sperner property (Greene & Kleitman 1976), and Condition II is the definition of "conformal" as in Colomb & Nourine (2008). In terms of their implications on hyperedge patterns, Condition I is quite self-explanatory, which simply forbids the pattern of "nested" hyperedges. In comparison, Condition II is much less intelligible. Our following theorem further interprets Condition II by the hyperedge pattern of "uncovered triangle".
Theorem 2. A hypergraph H (V,E) is conformal iff for every three hyperedges there always exists some hyperedge F. such that all pairwise intersections of the three hyperedges are subsets of E, i.e.:
4 EE,, E,,EE,E, E,, EE, E E E, s.t. (E, (E,nE)) (E, n Eq) (Eg n E,) c E
Theorem 2 shows that for hypergraph to satisfy Condition II, it can't allow any three hyperedges in itself to form a "triangle" whose three vertices are "uncovered". Intuitively, the triangle in this pattern would induce a 3-clique among the "vertices" of the triangle, which would not be part of hyperedge the triangle is uncovered. The value of Theorem 2 is that it gives a nontrivial interpretation of Condition II in Theorem by showing how to check hypergraph's 's conformity just based on its hyperedge patterns, without computing any maximal cliques. Based on the two conditions, we can now further define the two types of errors made by maximal cliques.
Definition 1. Every error made due to treating all maximal cliques in G as true hyperedges in H can be attributed to H.'s 's violation of at least one the conditions in Theorem 7 An error is defined to be Error (Error II) if it is caused by the H''s violation of Condition I (Condition II).
Fig 2 illustrates the two error-triggering hyperedge patterns (i.e. "error patterns" for brevity hereafter) corresponding to the two errors. as well as their relationship to other important concepts. Also note that here the Errors I & II are different from (but related to) the well-known Type I (false positive)
and Type II (false negative) errors in statistics. See Appx. [B.3 more discussion.
Empirical frequency of the hyperedge patterns, and their theoretical worst case (Q2)
Both error patterns in Fig 2 have simple construct, so it is perceivable that they are common in
3

---

Published as a conference paper at ICLR 2024
Quay:
projected
Query:
Class Sangler
Clasilir
Trainiogs
projected
Go
62
(a)
(b)
Figure 3: (a) Supervised hypergraph reconstruction. Ha and Hi belong to the same application domain. Given Ho (and its projection Go), the task is to reconstruct Hi from its projection G2. (b) 4-step reconstruction: (1) the clique sampler is optimized on Go and Ho: (2) the clique sampler samples candidates from Go and C1. then passes result the hyperedge classifier; (3) the hyperedge classifier extracts features of candidates from Go and trains on them; (4) the hyperedge classifier extracts features candidates from C1 and identify hyperedges.
real-world hypergraphs. Table ssowss the frequency of the enror patterns and their resulted error rate in reconstruction. We see that Error patterns are common in hypergraphs of emails and social interactions. In the worst case, hypergraph contains one large hyperedge and many nested hyperedges as proper subsets.
That said, one can argue that there may be many real-world hypergraphs that (almost) satisfy Condition I. It turns out that the Error II patterns caused by violating Condition also disastrous.
Theorem 3. Let H (V,E) be hypergraph that only satisfies Condition in Theorem 7 with m [. Denote by (HH) the accuracy of maximal clique algorithm for reconstructing H. Then,
minu (H) S <2 ((mir)) .) << 2-m
Theorem 3 shows that our Error II pattern can also give rise to (super-)exponent) Jexponentially many hyperedges that are almost impossible to be combinatorically recovered, if we only rely on the projected graph.
4 LEARNING-BASED HYPERGRAPH RECONSTRUCTION
Overview.
This section will introduce new learning-basede hypergraph reconstruction paradigm, including the problem setup and the proposed method. The idea is that in addition to the projected graph as input, we also assume to know hypergraph (or part of it) from the same distribution as the reconstruction target. See 4.1 will formulate the problem and explain why this setup is meaningful in practice. Sec
4.2.3 will present details of the reconstruction method.
4.1 PROBLEM DESCRIPTION
We'v ve identified the inherent difficulty of reconstructing a hypergraph from its projection without additional information. However, presented at the beginning of this paper, in practice, there many cases where would be highly desirable if we can recover the lost higher-order relations from projection. How do reconcile this theoretical "impossibility" with practical necessities?
The key observations are two. First, the noted "impossibility" pertains specifically to the aim of flawlessly reconstructing a hypergraph solety based on its projection, especially in theoretical worst case. However, this doesn't 't preclude our option to approximate a hypergraph within specific application domain, particularly if we have insights about the domain's 's typical hypergraph structures.
Secondly, in the context of specific application domain with one more projected graphs to be reconstructed, collecting just a single "hypergraph sample" (or even a portion of it) within the domain can be immensely beneficial. This sample aids in understanding the typical structure and patterns of hypergraphs in that particular domain. For instance, to reconstruct the coauthorship hypergraphs from graphs claimed be built from earlier DBLP dataset, accessing and learning from a sample of another coauthorship hypergraph, perhaps from DBLP of more recent time period, or a different database like Microsoft Academic Graph (MAG, (iinaa al. (2015)), can be invaluable.
In addition, resources like human-labeled crowd-sourced data, such surveys (Ozella et al. (2021). can also be potential source of the hypergraph sample. In the case of protein interaction networks, ex expert-provided labels for distinct yet related species or organ could be particularly helpful
4

---

Published as a conference paper at ICLR 2024
for example, using one of the following databases to reconstruct the other: Reactome (Croft et al.) 2010) and Mu. 2.0 (Drew et al. (017). We also note that the hypergraph sample's 's size doesn't t necessarily need to match that of the reconstruction target. Sec will provide a detailed illustration of all the scenarios mentioned above.
The crucial observations above point us to a relaxed version of the problem, which involves the usage of another hypergraph from the same application domain as training data. The new learning- -ased paradigm is shown Fig Bal as an update to [ with the following the problem statement.
Learning- hypergraph reconstruction. (1) input X: a projected graph G; (2) output y: the original hypergraph H: (3) split: as in Fig Bal (Xuain Murain) ) =( (Go. Ho), (Xquery Hquery) = (G1, Hz).
given Ho. H1, D. (4) metric: following Young et al. (202I) we use Jaccard score to evaluate EinRell
reconstruction accuracy: EjUR.P
where E| is the true hyperedges; R, is the reconstructed hyperedges.
The reconstructed hypergraphs in this learning-based based setting offer two advantages. Most importantly, they still serve to crucially identify interactive node groups in a projected graph, irrespective of whether supervised signals are used. Also, they can potentially enhance various downstream tasks, such node ranking and link prediction (see Sec 5.4). as they aggregate information from both the projected graph and the application domain.
It's important to note that, in the second advantage above, our goal of hypergraph reconstruction isn't 't to outperform SOTA methods in downstream tasks. In fact, SOTA methods for a specific downstream task are often end-to-end customized, in which cases reconstructed hypergraphs would not be necessary. Rather, we highlight the value of reconstructed hypergraphs as informative and handy intermediate representation, especially when specific downstream tasks are undetermined at the time of reconstruction, which is similar to the role word embeddings play in language tasks.
4.2 PROPOSED METHOО FOR WARNINGG-BASED HYPERGRAPII RECONSTRUCTION
We are now ready to present our method for the problem. Apparently, even with the training hypergraph, the greatest challenge here is still the enormous search space of potential hyperedges (ie "clique space" in Fig[2). The novel idea here is that we will use a clique sampler to narrow the search space of hyperedges, and then use hyperedge classifier to identify hyperedges from the narrowed space. Both modules are optimized using the training data. Fig gives a more detailed 4-step view.
4.2.1 p(n, k)) ALLINNEEN
We now start by introducing an important statistic that we found, which is the foundation of our proposed method: p(n, k) is a statistic that describes distributions of hyperedges inside maximal cliques. Given a hypergraph H = (V,E), its projection G, maximal cliques M: p(n, k) is the probability that we find a unique hyperedge by randomly sampling size-k subset of nodes from an arbitrary size-n maximal clique. A (n, k) is called valid if S k S n S N; N is the maximum clique's size. p(n, k) can be empirically estimated via the unbiased estimator p(n,
|En,
{ Em, = #1 C C' M, M, n)
k(n,k)
where
Qn,k (($S
=))
En, is all size-k hyperedges in size-n maximal cliques; Qn = |[CC e M. = =n) is all ways to sample size-n maximal clique and then a size-k subset (i.e. k-clique) from the maximal clique.
Our key observation that if two hypergraphs e.g. Ho, H1, are generated from the same source (application domain), they should have similar p(n, 's, which we call p(n,k) -aligmment Fig 4a uses heatmaps to visualize p(n, k) aalignment on a famous email dataset, Enron (Benson et al. 2018a) 8a), where Ho and Hi are split based on middle timestamp of the emails (hyperedges). n is plot on the y-axis, l on the a-axis. Fig Fig|4b]plots p(n,k) k)'s for 5 other datasets. Both figures show the distributions of p(n, k) to align well between training and query splits; in contrast, the distributions of p(n, k) across datasets are much different. Appendix Fig 17 confirms this visual observation quantitatively.
k)'s,
Also note Fig 4als s second column and diagonal cells are darkest, implying that the (*) term in Qn,k can't 't dominate ((n, k): (*) is smallest at A 1, growing exponentially A + n/2 regardless of data. p(n, k)) peaking ie 2 shows that the data term [E,, plays numerically meaningful role. Complexity. The complexity for computing p(n, k) is O(M)). See Appx. D.1 for details.
5

---

Published as a conference paper at ICLR 2024
((nx. R) custraining (W (q)
p(nn, onguayy (AC
siectt)
masimmo clique ston
subsot size (k)
subect stzo (k)
(a)
(b)
Figure 4: (a) p(n, -laalimmment dataset Enron; Ho. Hi obtained by splitting all emails by middle timestamp.
(b) p(n, --aligmmentt on more datasets. Notice the column- similarity and row-wise difference.
4.2.2 CLIQUE SAMPLER
Given query graph. we can't afford take all its cliques U1 as candidates for hyperedges. Therefore. we create clique sampler. Assume a limited sampling budget 3 < M4l our goal is to collect as many hyperedges as possible by sampling / cliques from U. Any hyperedge missed in sampling will never get identified by the hyperedge classifier later so this step is crucial.
Query G₁ is not enough to locate hyperedges in the enormous search space of U1. Fortunately, we get hints from Go and Ho. The idea is that use Go and Ho optimize clique sampler that can provably collect many hyperedges. The optimization (Fig B step 1) is a process to learn "where sample". Then in G1, we use the optimized clique sampler to sample cliques (Fig 3b step 2). The clique sampler takes the following form:
For each valid (n, kt), we sample a total of fr..llQn. size=k subsets (i.e. k-cliques) from size-n maximal cliques in the query graph, subject to the sampling budget: Σn,x rn,, B.
To.k [0, 1] is the sampling ratio of the (n, k) cell, IQn.al is the size of that cell's sample space in Go. To instantiate a sampler, a fn,& should be specified for every valid (n,, k). How to determine the Tn 's? We optimize Tn,k towards collecting the most hyperedges from Go. with the objective:
(rn,k) argmax E([ U Tn,k En,k
(tn,k)
(n,,)
@ is set sampling operator that yields uniformly downsampled subset of & at downsampling rate rn essentially a generator for random finite set (Mullane et al.) 201 (See Appx. [B.4). E(I-I) is expected cardinality. Given p(n, ->aalinmment and objective fullfiled, the optimized sampler should also collect many hyperedges when applied to G₁. See Appx. F.8 for empirical validation.
To collect more hyperedges from Go. heuristic is to allocate all budget to the darkest cells the training data's 's heamap (Fig (elfft,,, where hyperedges most densely populate. However, caveat is that the set of hyperedges E,, in each (n, k) cell of the same column not disjoint. In other words, a size-k clique can appear in multiple maximal cliques of different sizes.
Optimization.
Algorithm 1 Optimize Clique Sampler
Require: 3; N; En.k. 2n.k for all s k NnknnsN
1: for k = 1 N do
b traverse & to initialize state variables union of En,A 's picked from column > available column-k cells > sampling ratios for column-k cells
2: Tı +
3: Wh (ki 1k.,+1,...,N) 1,...NN
4:
Ti.k <- for EWE
5:
DE. +- UPDATE (k, Wk. Ts E.ko 2.1c)
6:
end for
7:
while 3 0 do
the greedy selection starts >> selects the next best samples cell by ratio
8:
1: argmax, A.
9:
T minf 1, (l
TA + Tx T
updates state variables
11:
Wk + wu (nu)
12:
3 1- 1-
13:
AR, UPDATE (k, wi, Tk, E. Q.+)
if maxx A then break
breaks cells sampled
15:
end while
16:
return Fu.A for all 1 s NksNkkkkkk

---

Published as a conference paper at ICLR 2024
Therefore, taking the darkest cells may not give best result. In fact, optimizing the objective above involves maximizing a monotone submodular function under budget constraint, which is NP-hard. In light of this, we design Algorithm| [ to greedily approach the optimal solution with worst-case guarantee. It takes four inputs: sampling budget 3. size of the maximum clique N, En,k and Qn.* for all i k < S N. Lines I iiiittiliie state variables. Lines 15 run greedy selection iteratively.
Subroutine 1 UPDATE in I
The initialization is done column-wise. In each column k. I'k stores the union of all &n selected from column & so far; We stores the row indices of all cells in column & that haven't 't been selected; T is the sampling ratio of each valid cell: line calls the subroutine UPDATE to compute 6,, the best sampling efficiency among all available cells, and nu. the row index of that most efficient cell.
Require: k; we: RRi e, 2, if W/. Ø then
A' + maxnewx
ITUEEn.Nl-ITT @n.al TxuEn,
n' -argmax
12..
else
A' 0; n' 0:
Lines 7 run the greedy selection. In each iteration, we take the next most efficient cell among the best of all columns, store the selection in the corresponding r, and up- date (I, w, ōg. mk)); l is the column index of the selected cell. Only column & needs to be updated as En.k's 's with different k's are independent. We stop when reaching budget or having traversed all cells.
end
return A',n'
Appx. F88 visualizes Algorithm I iterations and does ablation studies on its necessity.
Theorem 4. Let be the expected number of hyperedges in Ho drawn by the clique sampler optimized by Algo. 7 let q" be the expected number of hyperedges in Ho drawn by the best-possible clique sampler, under the same B. Then, 9 (1 2)4" ~ 0.639".
Theorem bounds the optimality of Algo. T .. in practice can be much higher than 0.63. Also notice that Algo. leaves at most one (n, k) cell partially sampled. Is that a good design? In fact, there always exists an optimal clique sampler that leaves at most one cell partially sampled. Otherwise, we can always relocate all our budget from partially sampled cell to another to achieve higher 9. Appx furtteer discusses Algo. [Ts relationship with the standard submodular optimization, how further
q²
eliminates Errors I & II, and the tuning of /3 from the perspective of precision-recall tradeoff.
Complexity, Algo I average complexity is O(E)). worst complexity is O(N(E)) See Appx. D.3
4.2.3 HYPEREDGE CLASSIFIER
A hyperedge classifier is a binary classification model that takes a target clique in the projection as input, and outputs 0/1 label indicating whether the target clique is a hyperedge. We train the hyperedge classifier on ( (Ho. Go) which has ground-truth labels (step 3, Fig 3b). then use it to identify hyperedges from G2 (step 4, Fig Fig 3b). To serve this purpose, hyperedge classifier should contain two parts (1) feature extractor that extracts expressive features for characterizing a target clique, and (2) a binary classifier that transforms feature vector into 0/1 label. (2) a standard task, so we use MLP with 100 hidden neurons. (1) requires more careful design, discussed below.
Design Principles. Creating an effective feature extractor necessitates identifying the essential information about target clique in the projection. Since our setting doesn't 'tt assume attributed nodes or edges, leveraging the structural features both within and around the target clique is crucial. Also, positional embeddings like Deepwalk are not applicable here due unaligned node IDs.
In principle, any structural learning model for characterizing connectivities can be a potentially good choice and there are many of them operating on individual nodes (Henderson et al.) 2012 Li et al. 2020 Xu et al.) 2018 Yin et al., 2020). However, since this is new task involving complex clique structures, we want have a learning model as interpretable as possible in such a a"clique-rice context. Here, we introduce two feature extractors that achieve this via interpretable features, though alternative options exist.
"Count" Feature Extractor. Many powerful graph structural learning models use different notions of "count" to characterize local connectivity patterns. For example, GNNs typically use node degrees as initial features when node attributes are unavailable; the Weisfeiler-Lehmarr Test also updates a node's 's color based on the count of different colors in its neighborhood.
Viewing target clique a subgraph in projection, the notion of "count" can be especially rich in meaning: a target clique can be characterized by the count of its [own nodes neighboring nodes / neighhoring edges / attached maximal cliques] in many different ways. We create total of 8 types of
7

---

Published as a conference paper at ICLR 2024
i
large diqu
Dataset
[V]
[
[CCC)
[(C)
[M
a matrrna chique
Earoa Renson ct
2018a
142
756
362
sdge the larget clique
DBLP (Bassin et
20
319,916
197,067
3.0
1.7
18
166,571
contained by
digge
School [Beison et a.
2078a
242
6.352
2.4
0.6
64
15,017
H. School Bemson
2013:
327
3,909
2.3
0.5
28
3,279
tescluding zodes in the mout))
two matimall clique have infersediion
Foursquare Young ei au
2021
2,334
1,019
6,4
6.5
28
8,135
Hosis- Virus Younge el
A141
466
218
D Figure 5: 13 "clique motifs" that encode rich connec- tivity patterns around a target clique C. Each clique motif is formed by [I or nodes in the target clique] + or maximal cliques that contain the nodes].
K N
Directors Young el sl 2021
522
102
5,4
2.2
1.2
102
0,00,
Crimes Young ct
510
256
207
Table 2: Summary of the datasets (query split), u(E) and o(E) stand for mean and std. of hyperedge's 's size. d(V): average node degrees w.E.f hyperedges. M: maximal cliques. See for the full version.
generalized count-based features, elaborated in Appx. D.4 features works surprisingly well and can be easily interpreted. See Appx. D.4 also.
Despite technical simplicity, these count
"Motif" Feature Extractor. As a second attempt, we create a novel "clique motif" feature extractor. we use maximal cliques as intermediaries to bridge the gap between projection and hyperedges. The maximal cliques serve as initial estimations of the high-order structures, encompassing full projection information and offering partially refined insights into higher-order structures. Also, the interaction between maximal cliques and nodes in the target clique form rich connectivity patterns, generalizing the notion of motif (Milo et al., 2002).
Fig S lists all 13 connectivity patterns involving the target clique's 's or 2 nodes and maximal cliques. Clique motifs, compared to count features, more systematically extract structural properties, with two component types (node, maximal clique) and three relation types explained in the legend. clique motif is attached to target clique C' if the clique motif contains at least one node of C. We further use : to denote the set of type-i (1 S 13) clique motifs attached to C.
Given a target clique C, how to use clique motifs attached to C' to characterize structures around C? We define C's structural features as a concatenation of 13 vectors: [u] ;u? j..., u J. v0 is vector of statistics describing the vectorized distribution of type-i clique motifs attached to C:
SUMMARIZE, P(()) p(() [CouNt (C, i, {v)) ) for v in C],
if S i
(C) 4
[[CouNT(C (C, i, v2)) for U1 U2 in CJ. if 4 S sis 13;
P. is a vectorized distribution in the form of an array of counts regarding and C. COUNT( C, x)= (Ø e ( Ix S Φ)). Finally, SUMMARIZE( p(()) is function that transforms a vectorized distribution p(d) into a vector of statistical descriptors. Here we simply define the statistical descriptors as: SUMMARIZE
[mean( p()). std( P(()), min( P((),, max )P
As have 13 clique motif', these amount to 52 structural features. On the high level, clique motifs
extend the well-tested motif methods on graphs to hypergraph projections with clique structures. Compared to count features, clique motifs capture structural features in more principled manner.
EXPERIMENTS AND FINDINGS
5.1 EXPERIMENTAL SETTINGS
Baselines. We adapt 7 methods from four task domains for their best relevance or state-of-the of-the-art
performance: (1) Community Detection: Demon (Coscia et al. 2012). C'inddrr (Palla et al.] 2005):
(2) Clique Decomposition: MaxClique (Bron & Kerbosch]] 1973). Clique Covering (Conte al.)
2016); (3) Hyperedge Prediction: Hyper-SAGNN (Zhang et al.) 2019), CMM (Zhang al. 201 8).
HPRA (Kumar et al. 2020a); (4) Probabilistic Models: Bayesian- MDL et al., 202 See
more in Appendix
Data & Training. We use 8 real-world datasets from various application domains. For each dataset, we split the hyperedges to generate Ho. H4, Go. G1. The properties of Mi are summarized in Table 2 See Appx. for more details of dataset split, baselines selection and adaptation, and tuning.
Reproducibility. Our code and data are available here
5.2 EVALUATING QUALITY RECONSTRUCTION
We name our approach SHyRe (Supervised Hypergraph Reconstruction) whose performance is shown in Table 3] SHyRe variants significantly outperform all baselines in most datasets (7/8), with best improvement in hard datasets such as P. School, H.School, and Enron. This success is attributed
8

---

Published as a conference paper at ICLR 2024
DBLP
P.Scholl
H.School
Foursquare
Hosts-Virus
Directors
Crimes
Ciinder
11.35
0.45
0,00
0.00
0.39
5,02
41.18
6.86
Demon
2.35
0.09
2.97
16.51
7.28
90.48
63.81
Maximal Clique
79.13
4.19
0.09
2.38
9.62
22.41
100,9
78.76
Clique Covering
73.15
6.61
1.95
6.89
79,89
41,00
100.0
75.78
Hyper-She SSGGNN
0.13=0.01
4.79=0.08
12.55+0.33
8.9620.11
7.36=0.50
CMM
0.11=0.04
0.52=0.04
19.63+2.74
6.28:00.4
0.00+0.00
4.9% 1.21
2.61=0.60
0.57=0.29
HPRA
63.99x3.57
10,25+0.42
24.32+0.88
34.30:2.47
4.395=
0.52
73.44=5.60
53.16:0.93
Baycsion-MDL
73.08:0.00
4.57=0.07
0,18+0.01
3.58=0.03
69.93=0.59
40,24
100.0=0.00
74.91=0.11
SHyKe-Count
81.182-0001
13.50.20.32
42.006066
$4.5620.10
7:4,56=0.57
48.851-0.11
106.020.00
"19.1820442
Re-moot
81.19:0.02
16.02+0.35
43.06:0.77
54.39x0.25
71.88=0.28
45.1640.55
100.0=0.00
79.27=0.40
Table 3: Performance of hypergraph reconstruction measured in Jaccard score (%, defined in Sec 4.
Std.
dropped for deterministic methods. "_" means the algorithm did not stop in 72 hours.
DBLP
Hosts-Virus
Euron
Best Baseline (tull)
79.13
41.00
6.61
SHyyRe Re-toit (full)
81.19=0.02
45.16+0.555
16.02+0.35
DR6
SHyRe-comm (20%)
81.17=0.01
44.02+0.39
6.43+0.18
0007200
SHyRe-motif (20%)
81.17=0.01
44.48x0.21
10.56a0.92
NAG-lleen
Table 4: Performance of semi-supervised reconstruction Figure 6: Transfer learning performance: trained on DBLP2011, 1, tested on various coauthorship datasets.
using 20% training hyperedges, measured in Jaccard Score.
SHyRe's innovative use of the training graph and its ability to capture strong, interpretable features, as detailed in Appx. [.4]] Although Clique Covering and Bayesian- MDL perform relatively well, they struggle with dense hypergraphs. Hyperedge prediction methods have similar issues despite being also learning-based methods, topic elaborated in Appx.C..
More metrics. Fig 17 in Appendix further shows fine-grained performance measured by partitioned errors [Def[]) SHyRe variants significantly reduce more Errors I and II than other baselines do. Besides, we also study various topological properties of the reconstructed hypergraphs and compare them to those of the original hypergraphs. We find that on these new measurements SHyRe variants also produce more faithful reconstructions than baselines. See Appx F.2 for more details.
5.3 SEMI-SUPERVISED LEARNING AND TRANSFER LEARNING
We study more constrained scenarios where we only have access to small subset of hyperedges, or a a training hypergraph from a nearby domain. These settings correspond to semi-supervised learning and transfer learning. For semi-supervised setting, we choose three datasets of different difficulties: DBLP, Hosts- Virus, and Enron. For each dataset, we randomly discard 80% hyperedges in the training split. Table 4 shows the result: the reconstruction accuracy drops on all datasets, but SHyRe trained on 20% data still outperforms the best baseline on full data.
For transfer learning. we train SHyRe on DBLP 2011, and test on various other DBLP slices and Microsoft Academic Graphs (Sinha et al., 2015), shown in Fig 6 We can see that SHyRe remains robust the distribution shift as performance on DBLP 201 is 81.19% according Table
5.4 USE CASES OF RECONSTRUCTED HYPERGRAPHS DOWNSTREAM TASKS
We evaluate advantages of using reconstructed hypergraphs as informative intermediate representa- tions for downstream tasks in comparison relying on projected graphs, through two use cases: node ranking in protein-protein interaction (PPI) network and link prediction. The details are presented in Appx [:44 and [:5] respectively. For the former, we apply our method to recover multiprotein complexes from pairwise interaction data, which are then used to rank the essentiality of proteins based on their node degrees. This produces a ranking list that much better aligned with the ground truth than results based on the projected version of PPI network, as shown in Appendix Table 8
In the second use case, link prediction, we demonstrate that reconstructed hypergraphs enhance performance over projected graphs across multiple datasets measured by AUC and Recall. These use cases show the efficacy of our hypergraph reconstruction technique in deriving richer, more informative data representations that can benefit downstream analytical tasks.
More Experiment. We report more experiment in Appx [.122 including ablation studies on clique sampler, optimal sampling coefficients (rm,k (s) and running time and storage comparison.

---

Published as a conference paper at ICLR 2024
CONCLUSION
We studied hypergraph projection and its reversal. We identified specific hyperedge patterns that trigger errors, and introduced novel learning- based approach for hypergraph reconstruction. For future studies, considering different projection expansions like "star" or "line" can be highly promising. We also discuss the Broader Impacts of our work Appx.
ACKNOWLEDGEMENT
We thank Immanuel Trummer for his valuable feedback. This work is supported in part by Simons Investigator Award, Vannevar Bush Faculty Fellowship, AFOSR grant 1-9550019-1-0165 and grant from the MacArthur Foundation.
REFERENCES
Austin R Benson, Rediet Abebe, Michael TT Schaub, Ali Jadbabaie, and Jon Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences, 115 2018a.
192)-E11221EE11
Austin R Benson, Ravi Kumar, and Andrew Tomkins. Sequences of sets. In Proceedings of the 24th ACM SIGKDD International Conference, pp. 1148-1157, 2018b. 2018b..
Claude Berge. Graphs and hypergraphs. 1973.
Claude Berge and Pierre Duchet. A generalization of gilmore's theorem. Recent advances in graph theory, pp. 49-55, 1975.
Sonja Blasche and Manfred Koegl. Analysis of protein-protein interactions using lumier assays. In Virus-Host Interactions, pp. 17-27. Springer, 2013.
Coen Bron and Joep Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Communi- cations of the ACM, 16(9):575-577 1973.
Andries E Brouwer, CF Mills, WH Mills, and A Verbeek. Counting families of mutually intersecting sets. the electronic journal of combinatorics, pp. P8-P8, 2013.
Anna Brückner, Cécile Polge, Nicolas Lentze, Daniel Auerbach, and Uwe Schlattner. Yeast two- hybrid. a powerful tool for systems biology. International journal of molecular sciences, 10(6): 2763-2788, 2009.
Pierre Colomb and Lhouari Nourine. About keys of formal context and conformal hypergraph. In Formal Concept Analysis: 6th International Conference, ICFCA 2008, Montreal, Canada, February 25-28, 2008. Proceedings 6, pp. 1400-49. Springer, 2008.
Alessio Conte, Roberto Grossi, and Andrea Marino. Clique covering of large real-world networks. In 31st ACM Symposiun on Applied Computing, pp. 1139, 2016.
Michele Coscia, Giulio Rossetti, Fosca Giannotti, and Dino Pedreschi. Demon: a local-first discovery method for overlapping communities. In Proceedings of the 18th ACM SIGKDD international conference, pp. 615-623, 2012.
David Croft, Gavin O' O'kelly, Guanming Wu, Robin Haw, Mare Gillespie, Lisa Matthews, Michael Caudy, Phani Garapati, Gopal Gopinath, Bijay Jassal, al. Reactome: database of reactions, pathways and biological processes. Nucleic acids research, 19(suppl_1:DD611- 2010.
Sicheng Dai, Hélène Bouchet, Aurélie Nardy, Eric Fleury, Jean-Pierre Chevrot, and Márton Karsai. Temporal social network reconstruction using wireless proximity sensors: model selection and consequences. EPJ Data Science, 2020.
Yihe Dong, Will Sawin, and Yoshua Bengio. Hnhn: Hypergraph networks with hyperedge neurons. arXiv preprint 2006. /2278, 2020.
10

---

Published as a conference paper at ICLR 2024
Kevin Drew, Chanjae Lee, Ryan L Huizar, Fan Tu, Blake Borgeson, Claire D McWhite, Yun Ma, John B Wallingford, and Edward M Marcotte. Integration of over 9,000 mass spectrometry experiments builds global map of human protein complexes. Molecular systems biology, 13(6): 932, 2017.
David Eppstein. Maarten Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17 2010, Proceedings, Part I 21, pp- 403-414, Springer, 2010.
Paul Erdös, Adolph W Goodman, and Louis Pósa. The representation a graph by set intersections. Canadian Journal of Mathematics, 18: 10:106-1 1966.
Ernesto Estrada. Virtual identification of essential proteins within the protein interaction network of yeast. Proteomics, 6(1):35-40 2006.
Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: A new distribution-free model. SIAM journal on computing, 49(2):448 464, 2020.
Curtis Greene and Daniel Kleitman. Strong versions of sperner's theorem. Journal of Combinatorial Theory, Series A, 20(1):80-88, 1976.
Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: structural role extraction & mining in large graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012.
Renée V Hoch and Philippe Soriano. Generating diversity and specificity through developmental cell signaling. In Principles of Developmental Genetics, pp. 3-36. Elsevier, 2015.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18 11221188-313,, 2020.
Massih khorvash. On uniform sampling of cliques. PhD thesis, University British Columbia, 2009. URL httpss://pen. iibrary.ube.
0051 700
Florian Klimm, Charlotte M Deane, and Gesine Reinert. Hypergraphs for predicting essential genes using multiprotein complex data. Journal of Complex Networks, 9(2):cnaa028, 2021.
Yunbum Kook, Jihoon Ko, and Kijung Shin. Evolution of real-world hypergraphs: Patterns and models without oracles. In 2020 IEEE International Conference on Data Mining (ICDM), pp. 272-281. IEEE, 2020.
Tarun Kumar, K Darwin, Srinivasan Parthasarathy, and Balaraman Ravindran. Hpra: Hyperedge prediction using resource allocation. In Proceedings of the 12th ACM Conference on Web Science, pp. 135-143, 2020a.
Tarun Kumar, Sankaran Vaidyanathan, Harini Ananthapadmanabhan. Srinivasan Parthasarathy, and Balaraman Ravindran. Hypergraph clustering by iteratively reweighted modularity maximization. Applied Network Science, 5(1):1-22 2020b.
Geon Lee, Jaemin Yoo, and Kijung Shin. Mining of real-world hypergraphs: Patterns, tools, and generators. In Proceedings the s1 ACM International Conference on Information & KKnowlegge Management, pp. 1144-5147, 2022.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In SIGKDD, 2005.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33, 2020.
11

---

Published as a conference paper at ICLR 2024
Xiaoli Li, Min Wu, Chee-Keong Kwoh, and See- See-Kiong Ng. Computational approaches for detecting protein complexes from protein interaction networks: a survey. BMC genomics, 11(1):1-19, 2010.
Anmol Madan, Manuel Cebrian, Sai Moturu, Katayoun Farrahi, et al. Sensing the" health state" of community. IEEE Pervasive Compating, 1 (14)), 2011.
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824 827, 2002.
John Mullane, Ba-Ngu Vo, Martin D Adams, and Ba-Tuong Vo. A maddom-finit-ser approach to bayesian slam. IEEE transactions on robotics, 27(2), 2011.
Mark EJ Newman. Coauthorship networks and patterns of scientific collaboration. Proceedings of the national academy of sciences, (supl 1), 2004.
Laura Ozella, Daniela Paolotti, Guilherme Lichand, Jorge Rodríguez, Simon Haenni, John Phuka, Onicio B Leal-Neto, and Ciro Cattuto. Using wearable proximity sensors to characterize social contact patterns in a village of rural malawi. EPJ Data Science, 10(1):46, 2021.
Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Viesek. Uncovering the overlapping community structure of complex networks in nature and society. nature, 435(7043):814-815 2005.
Xinyu Que, Fabio Checconi, Fabrizio Petrini, and John A Gunnels. Scalable community detection with the louvain algorithm. In 2015 IEEE IPDPS. IEEE, 2015.
Emad Ramadan, Anijit Tarafdar, and Alex Pothen. A hypergraph model for the yeast protein complex network. In 18th International Parallel and Distributed Processing Symposium, 2004. Proceedings., pp. 189. IEEE, 2004.
Guillaume Rigaut, Anna Shevchenko, Berthold Rutz, Matthias Wilm, Matthias Mann, and Bertrand Séraphin. A generic protein purification method for protein complex characterization and proteome exploration. Nature biotechnology.
1999.
Emre Sarigöl, René Pfitzner, Ingo Scholtes, Antonios Garas, and Frank Schweitzer. Predicting scientific success based on coauthorship networks. EPJ Data Science, 3:1-16, 2014.
Arnab Sinha. Zhihong Shen, Yang Song, Hao Ma, Darrin Eide. Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference on world wide web, pp. 243- 246, 2015.
Victor Spirin and Leonid A Mirny. Protein complexes and functional modules in molecular networks. Proceedings of the national Academy of sciences, 100(2)):2123-1222 2003.
Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical computer science, 363(1):28 42, 2006.
Leo Torres, Ann S Blevins, Danielle Bassett, and Tina Eliassi-Rad. The why, how, and when of representations for complex systems. SIAM Review, 63(3))435--46 2021.
Vincent A Traag, Ludo Waltman, and Nees Jan Van Eck. From louvain to leiden: guaranteeing well-connected communities. Scientific reports, 9(1), 2019.
Michael M Wolf, Alicia M Klinvex, and Daniel M Dunlavy. Advantages to modeling relational data using hypergraphs versus graphs. 2016 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1-7, IEFF, 2016.
Qianghua Xiao, Jianxin Wang, Xiaoqing Peng, Fang-xiang Wu, and Yi Pan. Identifying essential proteins from active ppi networks constructed with dynamic gene expression. In BMC genomics, volume 16. pp. 1-7. Springer, 2015.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.000 2018.
12

---

Published as a conference paper at ICLR 2024
Ye Xu, Dan Rockmore, and Adam M. Kleinbaum. Hyperlink prediction in hypernttwrkk using latent social features. Discovery Science, 2013.
Naganand Yadati, Vikram Nitin, Madhav Nimishakavi, Prateek Yadav, Anand Louis, and Partha Talukdar. NHP: Neural Hypergraph Link Prediction, pp. 1705-1714. New York, NY, USA, 2020.
ISBN 978 178145036899.
Haoteng Yin, Yanbang Wang, and Pan Li. Revisiting graph neural networks and distance encoding from practical view. arXiv preprint vrXiv:2011.12222 2020.
Se-cun Yoon, Hyungseok Song, Kijung Shin, and Yung Yi. How much and when do we need higher-order information in hypergraphs? case study hyperedge prediction. In Proceedings of The Web Conference 2020, pp. 2627-2633, 2020.
Sean-Gabriel Young. Giovanni Petri, and Tiago P Peixoto. Hypergraph reconstruction from network data. Communications Physics, 4(1):1-11, 2021.
KH Young. Yeast two-hybrid: so many interactions, so little time.... Biology of reproduction, 58 (2):302-311, 1998.
Yang Yu and Dezhou Kong. Protein complexes detection based node local properties and gene expression in ppi weighted networks. BMC bioinformatics, 23(1):1-15, 2022.
Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. Beyond link prediction: Predicting hyperlinks adjacency space. In AAAI 2018, 2018.
Ruochi Zhang, Yuesong Zou, and Jian Ma. Hyper-sagnn: self-attention based graph neural network for hypergraphs. In ICLR 2019, 2019.
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19, 2006.
13

---

Published as a conference paper at ICLR 2024
Appendix
A
REPRODUCIBILITY
Our code and data can be downloaded from httiss://anonymouus sciencecience// Segeriisedhyyerrrpppp.eoooos
BEADD///RRADEE.... mdd
B PROOFS AND ADDITIONAL DISCUSSIONS FOR SEC 3
B. PROOF OF THEOREM 1
Proof. "Only if direction: Condition holds because every hyperedge is maximal clique, and two maximal cliques cannot be proper subset of each other. Therefore, it impossible for any two hyperedges E, E' 6 &, which are both maximal cliques, to still satisfy E c E'. Condition II holds trivially because M = = MEE.
"If" direction: starting from Condition II, it only remains to show that every hyperedge in H is also a maximal clique in G. We prove by contradiction. If there exists hyperedge E that is not maximal clique, by definition of maximal clique and because E itself is a clique, E must proper subset of some maximal clique E". However, based on Condition II, E' is also hyperedge. This leads the relationship E E", a contradiction with Condition I.
B.2 PROOF OF THEOREM 2
Proof. The "if" direction: Suppose that H is not conformal. According Def.2, we know that there exists maximal clique Σ. Clearly for every C with |C| s 2, |C| E. For a C' & & and |C] 3, pick any two nodes U1, 12 C. Because they are connected, v1 must be in some hyperedge E, Now pick a third node U3 & E.. Likewise, there exists some different Ej such that Ui, E E2, and some different Eg such that U2, U3 Ez. Notice that E, Eg because otherwise the three nodes would be in the same hyperedge. Now we have (U1, U2, 33 s (E, Eş) (E, Eg) U (Eg n E.). Because {V1, 12, 03) the same hyperedge.
same hyperedge, (F& F.)) u (F, FuyJ (Fig n F.)) is also not in
The "only if" direction: Because every two of the three intersections share common hyperedge, their union is clique. The clique must be contained by some hyperedge, because otherwise the maximal clique containing the clique is not contained by any hyperedge.
Alternatively, there is a less intuitive proof that builds upon results from existing work in a detour: It can be proved that H. being conformal equivalent its dual H' being Helly Berge (973). According to an equivalence to Helly property mentioned in Berge & Duchet (1975), for every set of 3 nodes in H'' the intersection of the edges E, with [,, n A is non-empty. Upon a dual transformation, this result can be translated into the statement of Theorem 2. We refer the interested readers to the original text.
B.3 PROOF OF THEOREM 3
Given set X (1.2,...,m) m) and hypergraph H = (V....EE...... we define f:2% - 2" to be:
f(S) n E,
In ieXis
n
E,
SeX
where F. = V/F
Lemma 5. (S(S)S E 2 is partition of V.
Proof. Clearly f(S.) f(S)) Ø for all S; + Sj. so elements in (f(S)S 2* are disjoint. Meanwhile, for every node V. we can construct a (ilw E,} so that v e f(S). Therefore, the union of all elements in (f(S)) 2*) spans V.
14

---

Published as a conference paper at ICLR 2024
Because Lemma 5 holds, for any V we define the reverse function (-) S + f(S).
Here f- is a signature function that represents a node in V by a subset of X, whose physical meaning is the intersection of hyperedges in H.
Lemma 6. S n S2 + 2, ,1,,, S2 & X, then for every en E (S()) and 02 E (S2), (vi, is an edge in H's 's projection G. Reversely, if U2) an edge in G. I (vi) (12) + Ø.
Proof. According to the definition of f(S), Vi S1 S2, 01 Eg. Appearing in the same hyperedge means that they are connected in G, so the first part is proved. If (vi, U2) is an edge in G, there exists an E, that contains both nodes, so f (vi) (v2) {i) Ø.
An intersecting family F is set of non-empty sets with non-empty pairwise intersection, i.e. S, # Ø. SJ F.F Given a set X, a maximal intersecting family of subsets, is an intersecting family of set JF that satisfies two additional conditions: (1) Each element of F is subset of X; (2) No other subset of X can be added to F.
Lemma 7. Given a hypergraph H the two statements below are true:
Fe.....m)) its projection G, and X 21, m).
Ifa node set C V is a maximal clique in G, then (f-l C} is a maximal intersecting family of subsets of X.
Reversely, if F is a maximal intersecting family of subsets of X, then User f(S) is maximal clique in G.
Proof. For the first statement, clearly Vo V, (v) = X. Because C' is a clique, every pair of
nodes in C is an edge in G. According to Lemma 6 Ven, 1/2 E C, f (v1) ) n f ( + Ø. Finally, because C' is maximal, there does not exist node u V that can be added to C. Equivalently there does not exist a S = f-(( (v) that can be added to (C). Therefore, (C) is maximal.
For the second statement, because F is an intersecting family, S2 FF, Si S2 Ø. According to Lemma 66 Vei, 12 e (FF). (vi,0)) is an edge in G. Therefore, J(F) is clique. Also, no other node can be added f(F). Otherwise, (v) J. is still an intersecting family while (v) is not in F, which makes F strictly larger a contradiction. Therefore, f(eF is maximal clique.
Lemma 7 shows there is a bijective mapping between a maximal clique and maximal intersecting family of subsets. Given H. G and X. Counting the former is equivalent to counting the latter. The result is denoted as A(m) in the main text. Lemma 2.1 Brouwer et al. (2013) gives an lower bound:
a(m)= 2 2( ()
B.4 PROOF OF THEOREM 4
We start with some definitions. A random finite set, or RFS. is defined as a random variable whose value is a finite set. Given a RFS A. we use S(A) to denote A's sample space; for a set a é S(A) we use (a(a) to denote the probability that A takes on value a. One way to generate a RFS is by defining the set sampling operator O on two operands r and X, where e [0, 1] and X is a finite set: r O X is RFS obtained by uniformly sampling elements from X at sampling rate r, i.e. each element I X has probability to be kept. Also, notice that the finite set X itself can also be viewed as a RFS with only one possible value to be taken. Now, we generalize two operations, union and difference, to RFS as the following:
Union Au B:
S(AUB) aubc=
PAuR(T)= Σ Pa(a)Pn(1)
Difference AB:
S(ABB) = -1/ B}
PAUB(*)= Σ (a(a)
A.b
15

---

Published as a conference paper at ICLR 2024
With these ready, have the following propositions that hold true for RFS A and B:
(i) E(IAU BI) E(|B AD
( E[[Au B|) ((A)))) I(():
(iii) EQAU BI) 2 [E([A)), B( u B)) 2 B(
(iv) E x)( -XXX\| - B(IXY));
(X, Y both set)
Lemma 8. At iteration 1i+1) when Algorithm I samples a cell kn. (line 8), it reduces the gap
between q and the expected number of hyperedges already collects, qo by fraction of at least 1
90+1 $ 14+1
Proof.
9² qi
E(I
-
(Thm.4 setup)
(Prop.ii)
(Prop.ii)
(Prop.
Σ
B(((r o (()(())))))))
(Prop.iti)
E
(Prop.iv)
B((EAA(U) 111) E)))
10
B \(U)-11) 2 E)
12
(Alg. line 7)
14+1l
rit (R(E \(4/-11) E,)1
3
(Def. of 3)
Q++1
B
E(((ri- Eco ((
(Prop.iv)
T(+ T Q++1l
B
(g++1 9:)
(Thm,4 setup)
Ti+1
Q
Therefore, g'-901 9-
Tw [uml
Now, according to our budget constraint we have
Tr 1n.kl =
Σ
B
n.k
is the total number of (n,,) k) pairs where Tn. which is a constant. Finally, have
9" -
2-1
q¹ 9++1
Fn. Qn.kk
s (1 1
II[(1
q"
5-
9-' 91
0.k
Therefore g (1- !)/²
B.5 ERRORS & II VS. "TYPE & II" ERRORS
Note that here Errors I and II are different from the well-known Type (false positive) and Type II (false negative) Error in statistics. In fact, Error I's are hyperedges that nest inside some other hyperedges, so they are indeed false negatives; Error II's can be either false positives or negatives. For example, in Fig "Eroo II Pattern (Vi, v3 05, U5) is false positive, (vi, (8) is false negative.
16

---

Published as a conference paper at ICLR 2024
C ADDITIONAL RELATED WORK
C.I COMPARISON BETWEEN GRAPII AND HYPERGRAPISS
Previous works have compared the graph representations (e.g., clique expansion) and hypergraph representations in various contexts, highlighting the concerning loss of higher-order information in graph representations. For example, TTores al.] (202T) provides unified overview of various representations for complex systems: it notes the mathematical relationship between graphs and hypergraphs, warning against unthoughtful usage of graphs to model higher-order relationships. Similarly, [ong et al. 2020) also raises concerns about information loss when designing learning methods for hypergraphs based on their clique expansions.
Yoon et al. (2020) further empirically compares the performance of various methods in the hyper- edge prediction task when the methods are executed on different lower-order approximations of hypergraphs, including order-2 approximation (clique expansion), order-3 approximations (3-uniform projected hypergraphs), etc.; their experiments show that lower-order approximations especially struggle more complex datasets more challenging versions of tasks.
Our work significantly extends the notions in these previous works, formulating the central problem of interest (i.e. comparing graphs and hypergraphs, and mitigating the information loss) and giving it a systematical, rigorous study.
C.2 RELATED METHODS TO HYPERGRAPH RECONSTRUCTION TASK
Besides the ones in Introduction, three lines of works are pertinent to the hypergraph reconstruction task discussed in this paper.
Edge Clique Cover is to find a minimal set of cliques that cover all the graph's 's edges. Erdös et al. (1966) proves that any graph can be covered by at most [[V]2/4] cliques. Conte et al. (2016) finds fast hcuristic for approximating the solution. Young et al. (2021) creates a probabilistic to solve the task. However, this line of work shares the "principle of parsimony", which is often impractical in real-world datasets.
Hyperedge Prediction is to identify missing hyperedges of an incomplete hypergraph from a pool of given candidates. Existing works focus on characterizing a node set's structural features. The methods span proximity measures Benson et al. (2018a), deep learning [Li et al. (2020); Zhang et al. (2019), and matrix factorization (Zhang et al. (2018). Despite the relevance, the task has a very different setting and focus from ours mentioned in introduction.
Community Detection finds node clusters in which edge density is unusually high. Existing works roughly comes in two categories by the community types: disjoint Que et al. (2015); Traag et al. (2019), and overlapping Coscia al. (2012); Palla et al. (2005). As mentioned, however, their focus on "relative density" is different from ours on cliques.
C.3 COMPARING LEARNING-BASED HYPERGRAPH RECONSTRUCTION WITH HYPERGRAPH PREDICTION
As observe in Table 3 the two hyperedge prediction methods have very poor performance. This is resulted from the incompatibility of the hypergraph prediction task with our task of hypergraph reconstruction, in particular:
Incompatiiility of Input: all hyperedge prediction methods, including the two basclines. require (at least partially observed) hypergraph as input, and they must run on hyperedges. In hypergraph reconstruction task, we don't have this as input. We only have projected graph.
Incompatibility of output:
hyperedge prediction methods can only tell us whether a potential hyperedge can really exist. They cannot tell where hyperedge is, given only projected graph as input. In other words, they only do classification, rather than generation. This is also the key issue that work has gone great lengths address.
17

---

Published as a conference paper at ICLR 2024
In order to hyperedge prediction methods hypergraph reconstruction, we have to make significant adaptations. First, we must treat all edges in the imput projected graph as existing hyperedges. Second, it is only fair that sample cliques from projected graph as "potential hyperedge" for classification completely at random, until we reach our computing capacity. This is because none of the hyperedge prediction methods mentions concerns about this procedure. These two adaptations enable hyperedge prediction methods to run on hypergraph reconstruction tasks, but the cost of vastly degraded performance.
D MORE DISCUSSIONS ON THE SUPERVISED HYPERGRAPH RECONSTRUCTION APPROACH
D.1 COMPLEXITY OF p(n, k)
The main complexity of p(n, k) involves two parts: Ma; (b) En,k for all valid (n,
(aJ's complexity is O(MM as mentioned in Sec Though in worst case [M] can be exponential to [V. in practice we often observe [M] on the same magnitude order as |8| (see Table T), which is an interesting phenomenon. Please
discussion below for more details.
(b) requires matching size-n maximal cliques with size-k hyperedges for each valid (n, k)) pair. The key is that in real-world data, the average number of hyperedges incident to a node is usually constant independent from the growth of [V] or |M| (see also d(V) in Table known as the sparsity of hypergraphs Kook et al. (2020). This property greatly reduces the average size of search space for all size-k hyperedges in size-n maximal clique from |&] to nd(V). As we see both and d(V (() are typically under 50 in practice. b's complexity can still be viewed as O(M)). Therefore, the total complexity for computing p(n, k)) is ((M)). 5.2 provides more empirical evidence.
More on the complexity of extracting maximal cliques:
As discussed above, the complexity of extracting data inputs for Algorithm[iis is bounded by the number of maximal cliques the projected graph, and for thinking about this, we believe it's useful to distinguish between the worst case and the cases encounter in practice. For the worst case, the number of maximal cliques indeed can be (super-)exponent)) Jexponential to the number of hyperedges, as our Theorem proved. We agree with the reviewer this point.
The interesting observation here is that in practice we don't ton't typically witness such an explosion when try to enumerate all maximal cliques in various datasets, see Table 5 in Appendix for example. This contrast between the worst case and the cases encountered in practice is of course a common theme in network analysis, where research has often tried to provide theoretical or heuristic reasons why the worst-case behavior of certain methods doesn't 't seem to generally occur on the kinds of real-world network that arise in practice. This theme has been explored in number of lines of work for problems that require the enumeration of maximal cliques.
In particular, there are multiple lines of work that try give thcoretical explanations for why real- world graphs generally have a tractable number of maximal cliques, thereby making algorithms that use maximal clique enumeration feasible. The reviewer's point is correct that some of these are related to the sparsity of the input graph, but they also include other structural features typically exhibited by real-world network structures. Here we include brief discussions on two metrics relevant to this:
k-degeneracy. The degeneracy of an n-vertex graph G is the smallest number A such that every subgraph of G contains a vertex of degree at most k. The k here is often used as a measure of how sparse a graph is, in a way that captures subtler structural information than simply the average degree, and with a smaller l indicating a sparser graph. Eppstein et al. (210)) found that graph of n nodes and degeneracy k can have at most (n k)3 maximal cliques. This result explains as restricts the size of hyperedges.
c-closure. An undirected graph G is c-closed if, whenever least common neighbors, (u, v) is an edge of G. The number c here measures the strength of triadic closure of this graph. Fox et al. (2020) shows that any (weakly) c-closed graph on vertices has at most (ce13)/3 maximal cliques. Our paper is benefiting from the tractable
distinct vertices u, have
18

---

Published as a conference paper at ICLR 2024
number of maximal cliques real-world networks, which there's 's been lot of progress in the theoretical underpinnings via these and follow-up papers.
D.2 NUMERICAL STABILITY OF k(n,k)
desirable property of p(n, to be hypergraph statistic is its robustness to small distribution shifts of the hypergraphs. Here we report a study of p(n, k)'s numerical stability based on simulation.
First, we introduce simple generative model for hypergraphs:
~ P(n, k, m)
where n is the total number of nodes, k is the size the largest hyperedge (measured by number of nodes in that hyperedge), and m is vector of length (k- - 1) whose i-th element denotes the number of hyperedges size (i 1). This model generates a random hypergraph by sampling from n nodes m[1] hyperedges of size 2. m[2] hyperedges of size 3, m[k 1J hyperedges of size k.
Next, we study how a small perturbation to vector m results in the faction of change in the distribution of p(n, k))'s. Fixing n and k, for each we add random noise (i.e. vector Am) at the strength of 5%, i.e. [Ami/mm] 0.05. As a result of the added noise, p(n, k) would become p(n, k) We can therefore quantify the instability of (nn, k) with respect m as
instability En, k) - ((n,))))? En, Ep))))
Amm//m |m
In our experiment, for each m we repeat the measurement for this stability quantifier for times. We study simple case where k 5, ranges from 10 to 60. In order to mimic the sparsity of the hypergraphs in real world, we further set each element m to be n (so that the hypergraph' density is on the order of O(1)). Here is the result of the instability test:
10
20
30
40
50
60
70
instability
0.45
0.58
0.47
0.39
0.29
0.20
0.18
Table 5: Numerical instability p(n, ke) with regard to small perturbations in the hypergraph.
We observe that the instabilities are smaller that 1. This means that the relative change in the distribution of rho(n.k) is actually smaller than the relative change in the distribution of hyperedges captured by hyperedge numbers m. And as goes large the influence of the disturbance decades. Finally, we also acknowledge that the result of this simulation may not apply universally, and that fully theoretical analysis of the numerical stability of rho(n,k) is unavailable to us at this point.
D.3 MORE DISCUSSION ON ALGORITHM 1
The effectiveness of the clique sampler can also be interpreted by the reduction of Errors I and II. Taking Fig Fig/4aaa as example: by learning which non-diagonal cells to sample, the clique sampler essentially reduces Error as well as the false negative part of Error II; by learning which diagonal cells sample, it further reduces the false positive part of Error II.
Relating Errors
Relating to Standard Submodular Optimization. There are two distinctions between our clique sampler and the standard greedy algorithm for submodular optimization.
The standard greedy algorithm runs deterministically on a set function whose form is already known. In comparison, our clique sampler runs on function defined over Random Finite Sets (RFS) whose form can only be statistically estimated from the data.
The standard submodular optimization problem forbids picking a set fractionally. Our problem allows fractional sampling from an RFS (i.e. T,, [0,1]] 1J).
We can see from the Proof Theorem 4 above that it is harder to prove the optimality of our clique sampler than to prove for the greedy algorithm for Standard Submodular Optimization.
Precision-Resd Tradeoff. For each dataset, B should be specified manually. What's the best /3? Clearly larger 3 yields a larger q. thus higher recall 2 in samples. On the other hand, larger
19

---

Published as a conference paper at ICLR 2024
Avs. Ranking
Fall
Feat2
Fai33
Foat4
Feat.
Feat6
Feat.7
Feat.8
Figure 7: Average rankings of the count features, More imporant features have smaller ranking numbers.
also yields lower precision $. as sparser regions get sampled. 4 being too low harms sampling quality and later the training. Such tradeoff necessitates more calibration of 3. We empirically found it often good to search / in a range that makes
4 [2] [0.6, 0.95]. with more tuning details in Appendix.
Complexity. The bottleneck of Algo. Dis is UPDATE. In each iteration after a is picked, UPDATE [
recomputes (II"s u x| [I& for all n wk. which is O N of iterations under the best [ always O(N).
Empirically we found the number is the size of the maximum clique, and mostly
falls in [10, 40] (see 4b). Therefore, on expectation we would traverse O(N)O Kl O(EE) hyperedges if | distributes evenly among different k's. In the worst case where | 's are deadly skewed, this degenerates ((V)))).
D.4 COUNT FEATURES
We define a target clique (11; 12, M[]]] The 8 features are:
size of the clique: |C';
2. avg. node degree: ले E(ec)(()):
3. avg. node degree (recursive); lo Evee wini Eventn d(t');
4. avg. node degree w.r.f max cliques: & Excl Mau e H;;:
5. avg. edge degree w.t.. max cliques: [C] Em {M M|x1, Up M)};
binarized "edge degree" (w.rt. max cliques)(lle..eee [e., where Enyagec [[ Muj, v2 M)
7. avg. clustering coefficient: 1 Emsc cc(v), where oc is the clustering coefficient of node v in the projection; [cj
EmeMe [M], where M {M M|Css M); 8. avg. size of encompassing maximal cliques: MoT
Notice that avg. clustering coefficient is essentially a normalized count of the edges between direct neighbors.All the above features, except features 2,3,7, new contributions of our paper. Features 2,3,7 are very commonly used count features.
Feature Rankings. We study the relative importance of the 8 features by an ablation study. For each dataset, we ablate the features one a time, record the performance drops, and use those values to rank the 8 features. We repeat this for all datasets, obtaining the 8 features' average rankings, shown in Fig 7 More imporant features have smaller ranking numbers. Interestingly we found that the most important feature has very concrete physical meaning: it indicates whether each edge of the clique has existed in at least two maximal cliques the projected graph. Remarkably, this is very similar to the simplicial closure phenomenon we' ve in in Benson al. (2018a).
E BROADER IMPACTS
Extra care should be taken when the hypergraph to be reconstructed involves human subjects. For example, Fig Sa] the reconstruction of DBLP coauthorship hy hypergraph has higher accuracy on larger hyperedges, missing more hyperedges of sizes 1 and 2. In other words, papers with fewer authors seem to be harder to recover this case. The technical challenge in solving this problem resides in the Error patterns as discussed in the main text. Meanwhile, small hyperedges also contain less structural information to be used by the classifier. the broader sense, this issue could lead to concerns that marginalized groups of people are not given equal amount of attention as other groups.
20

---

Published as a conference paper at ICLR 2024
Dataset
[
a(E)
o(E)
d(v)
Enron Benson et al. 2018g
142 recipients
756 emails
3.0
2.0
16
362
Hensin at.
20
319916 authors
197.067 papers
166,571
P. School Benson ef al.
242 students
6,352 chars
2.4
0.6
64
15,017
H. School Benson Bchool al
201
327 students
3,909 chars
2.3
28
3,279
Foursquare Young
2021
2,334 eateriess
1.019 footpiiuts
6.4
6.5
2.8
8,135
Hosts Virus Young et a
2222
466 hosts
218 virus
5.6
9.0
2.6
361
Directors Young
2021
522 directors
102 hoards
5,4
102
Crimes Young et at. (2221
510 victims
256 bomicides
3.0
2.3
1,5
207
Table 6: & is the of hyperedges; E" is the of hyperedges nested in any other hyperedges: M is the set of maximal cliques in G. Error I, result from the violation of conformal and Sperner properties, respectively. Error 1 jeve" [uMi
Error II= |MM
[BUM]
To mitigate the risk of this issue, we propose improvement to three places in the reconstruction pipeline, and encourage follow-up research into those directions. First, the training hypergraph Ho can be improved towards more emphasis on smaller hyperedges. In practice, for example, this can be achieved by collecting more data instances from marginalized social groups. Second, we can also adjust the clique sampler that it allocates more sampling budget small hyperedges. Technically speaking, we can manually assign larger values to the Tn,1 's and the Tn ss which originally are parameters to be learned. Third, the hyperedge classifier may also be improved towards better characterization of small hyperedges. One promising direction to achieve this is to utilize node edge attributes, which, similar the first measure, also boils down to data collected on marginalized groups.
F EXPERIMENTS
F.1 EXPERIMENTAL SETUP- ADDITIONAL DETAILS
Selection Criteria and Adaptation of Baselines. For community detection, the criteria are: 1. community number must be automatically found; 2. the output is overlapping communities. Based on them, we choose the most representative two. We tested Demon and found it always work best with min community size = 1 and c = 1. To adapt CFinder we search the best & between [0.1, 1..100. 0.5] quantile of hyperedge sizes on Ho. For hyperedge prediction, we ask that they cannot rely on hypergraphs for prediction, and can only use the projection. Based on that we use the two recent SOTAs, Zhang (ct al. (2018) 2019). We use their default hyperparameters for training. For Bayesian-MDL we use its official library in graph-tools with default hyperparameters. We implemented the best heuristic in Conte et al. (216)) for clique covering. Both our method and Bayesian- use the same maximal clique algorithm (i.e. the Max Clique baseline) as preprocessing step.
Datasets. The first 4 datasets Table 2 are from Benson et al. (2018a); the rest are from Young et al. (2021). All source links and data can be found in submitted code.
Generating training query set. To generate a training set and a query set, we follow two common standards to split the collection of hyperedges in each dataset: (1) For datasets that come in natural segments, such as DBLP and Enron whose hyperedges are timestamped, we follow their segments so that training and query contain two disjoint and roughly equal-sized sets of hyperedges. For DBLP, we construct Ho from year 2011 and Hi from year 2010; for Enron, we use 02/27/2001, 23:59 as a median timestamp to split all emails into Ho (first half) and Hi (second half). (2) For all the other datasets that lack natural segments, we randomly split the set of hyperedges into halves.
We note that the first standard has less restrictions the data generation process than the second standard, which follows a more ideal setting and is most widely seen as the standard train-test split in MI evaluations. We therefore also introduce the settings of semi-supervised learning and transfer learning in Sec compensate. We consider these settings together as a relatively comprehensive suite for validating both the proposed learning- based reconstruction problem and its solution pipeline.
To enforce inductiveness, we also randomly re-index node IDs in each split. Finally, we project Ho and Hi to get Go and G1 respectively.
21

---

Published as a conference paper at ICLR 2024
Hyperparameter Tuning. For Demon, tested all combinations of its two hyperparameters (min com
(min_com size, epsilon), and found that on all datasets the best combination is (1, 1). For CFinder, tuned its hyperparameter k by search through 10%, 20%..... 50% quantiles of distribution of hyperedge sizes in the dataset. For CMM, we set the number of latent factors to 30. For Hyper- SAGNN, we set the representation size 64, window size to 10, walk length to 40, the number of walks per vertex to 10. We compare the two variants of Jlyper-SAGNN the encoder variant and the random walk variant, and chose the latter which consistently yields better performance. The baselines of Bayesian- LDDL, Maximal Cliques and Clique Covering do not have hyperparameters to tune.
Training Configuration. For models requiring back propagation, we use cross entropy loss and optimize using Adam for 2000 epochs and learning rate 0.0001. Those with randomized modules are repeated 10 times with different seeds. Regarding the tuning of (3, we found the best & by training our model on 90% training data and evaluated on the rest 10% training data. The best values are reported in our code instructions.
Machine Specs. All experiments including model training are run Intel Xeon Gold 6254 CPU @ 3.15GHz with 1.6TB Memory.
F.2 ANALYSIS OF RECONSTRUCTIONS
F.2. BASIC PROPERTIES
We characterize the topologiaal properties of the reconstruction using the middle four columns of Table 2 ((E), (()), d()),((V). [V] is excluded as it is known from the input. For each (dataset, method) combination, we analyze the reconstruction and obtain a unique property vector. We use PCA to project all (normalized) property vectors into 2D space, visualized in Fig
In 8a colors encode datasets, and marker styles encode methods. Compared with baselines, SHyRe variants O and x) produce reconstructions more similar the ground truth (m). The reasons are two-fold: (1) SHyRe variants have better accuracy, which encourages a more aligned property space: (2) This a bonus of our greedy Algo. [ which tends pick a cell from a different column in each iteration. Cells in the same column has diminishing returns due to overlapping of & with same k, whereas cells in different columns remain unaffected they have hyperedges of different sizes. The inclination of having diverse hyperedge sizes reduces the chance of a skewed distribution.
Markers of the same colors are cluttered, meaning that most baselines work to some extent despite low accuracy sometimes. Fig Sa embeds a histogram for the size distribution of the reconstructed hyperedges on DBLP. SHyRe's distribution aligns decently with the ground truth, especially on large hyperedges. Some errors are made on sizes 1 and 2, which are mostly the nested cases in Fig 2
Fig &b visualizes portion of the actual reconstructed hypergraph by SHyRe-count on DBLP dataset. The caption includes more explanation and analysis.
F.2.2 ADVANCED PROPERTIES
Inspired by Lee et 2022 we further compare some of the advanced structural properties between the original hypergraphs and the reconstructed hypergraphs. The advanced structural properties include simplicial closure (Benson al.) 2018a). degree distribution, singular-value distribution, density, and diameter.
For simplicial closure, density, and diameter, we quantify the alignment by: |21 - -2/// max (#1 222). so that it is continuous value in [0, 1]; æ1, 2h are the values of ground truths and reconstructions, respectively. This gives us a unified measurement that can be compared across different datasets. A larger value here indicates better alignment. For the alignment degree and singular values, treat each them as a probability density function and report the cross entropy between the two distributions. A smaller value indicates better alignment.
The result is presented in Table 7 We observe that our method works well at recovering the density and diameter. We also find that the degree of alignment simplicial closure between ground truth and reconstruction seems to be correlated well with the Jaccard scores reported our main Table 3 not easy though to obtain an intuitive sense of the alignment between two distributions measured by
22

---

Published as a conference paper at ICLR 2024
Criaaa
CND
DELP
Joursquare
Mox Clipse
Hosts-Niria
25chool
prgjectoon
H. H.Scchoo
Directoos
carrect and oaey
Inservet (ibeepaddiin)
(a)
(h)
Figure 8: (a) 2D embeddings statistical properties reconstructed hypergraphs. Colors encode datasets; markers encode methods. SHyRe produces reconstructions closest to ground truth (m). (b) A part of SHyRe- motif's reconstructed hypergraph on DBLP dataset. The black edges are G,. The shaded ellipsis are the reconstructed hyperedges. Those with green dashed edges difficult reconstruct if using training data.
cross entropy. However, the ordering of the cross entropy on all datasets seems to decently correlate with the ordering of the Jaccard scores.
DHLP
Enron
PSChool
H.School
Foursquare
Hosts Virus
Directors
Chimes
Simplicial Closure
0.89
0.29
0,38
0.46
0.74
0.49
1.00
0.78
Density ((8)/V))
0.92
0.95
0.95
0.90
1.00
Diameter
Degree Distribution
6,69c-7
9,78c-2
3.46e-2
1.37e-2
1.91c-
1.10c-2
0
8.9c-6
Singular Value Distribution
1.73e-10 10
3.83e-4
5.61e-5
8.49e-4
4.83e-6
6.40e-1
0
1.29e-5
Table 7: Comparative analysis of advanced properties of the ground-truth hypergraphs and reconstructed hypergraphs. For simplicial closure, density, and diameter, quantify the alignment by: / max( 222), that it is continuous value in 1]: 222 the values ground truths and reconstructions, respectively. larger value indicates better alignment. For alignment degree and singular values, we treat each of them as probability density function and report the cross entropy between the two distributions. A smaller value indicates better alignment.
F.3 CORRELATION ANALYSIS BETWEEN HYPERGRAPH PROPERTIES AND RECONSTRUCTION PERFORMANCE
On some datasets, our proposed method significantly outperforms baselines; on some other datasets, improvement is less prominent. To understand what properties of the dataset makes our proposed method most suitable, we conduct a mini-study to interpret Table
In this mini-study, we fit linear regression model to the performance gap (1) between our method and the best baseline, using the four basic properties of hypergraphs (XX) listed Table X
average hyperedge size (μ(E));
standard deviation of hyperedge size (a(E));
node degree in hypergraph (d(V) (E]/[V);
number of maximal cliques in projection (IM));
The performance gap is computed by:
best performance of SHyRe variants best performance of baselines
(1)
based on Table 3 For example, for DBLP the performance gap 81.19 73.08 8.11.
The resultant four coefficients are shown in Figure 9 The bar plot shows that:
Our proposed method has more advantage on datasets with large average node degree, such Enron, P.School, and H.School. Notice that large average node degree means that the
23

---

Published as a conference paper at ICLR 2024
75-
5.0
linear
0.-
coef.
25-
-75
(E)
d(v)
M
Figure 9: Contributions of different datasct properties to the performance gap between method and baselines. We fit linear regression model to the performance gap using the four properties shown in the plot.
hypergraph has densely overlapping hyperedges. For example, in P.School dataset, each node appears in an average of 64 hyperedges. The dense overlapping of hyperedges, as we have analyzed in Section Creete highly challenging cases for reconstruction. This is why our proposed method stands out,as it can effectively leverages information embedded in the training hypergraphs.
Our proposed method has generally less advantage on datasets with large average hyperedge size, such Foursquare and Directors. A possible explanation is that, compared with small hyperedge, projections from large hyperedges are less likely to mix up with each other, making the reconstruction casier. Meanwhile, baselines like max clique, clique covering, and Bayesian- MDL, all favor large cliques reconstruction by their design. Therefore, we observe more competitive baselines datasets with large hyperedges.
F.4 USE CASE 1: NODE RANKING IN PROTEIN-PROTED INTERACTION (PPI) NETWORKS
Background. We applied our method to PPI networks, recovering multiprotein complexes from pairwise protein interaction data. More than half of the proteins in nature form multiprotein complexes. which perform many fundamental functions such as DNA transcription, energy supply, etc. (Spirin & Mimy 2003). Mainstream laboratory-basee methods for directly detecting proteins multiprotein complexes, such as TAP-MS (Rigaut et al. 1999) or LUMIER (Blasche & Koegl| 2013), are known to be expensive and error-prone (Brückner et al. 2009 Hoch & Soriano 2015)) Alternatively, well- studied high- tigh-throughhut methods such as Yeast 2 2-hybrid screening (Y2H) (Young 1998) captures pairwise protein interactions. Brückner et al. (2009) mentions that "MS is less accessible than Y2H due to the expensive large equipment needed. Thus, a large amount of the data far generated from protein interaction studies have come from Y2H screening. However, many studies (Klimm et al., @02T.SSpri & Mirny] 20033 Ramadan al., 2004) found that the pairwise PPT network produced by Y2H obscures much information compared to the hypergraph modeling of multiprotein complexes. This is natural setting for the hypergraph reconstruction task.
Our experiment follows the transfer learning's setting. We seek to recover multiprotein complexes from a dataset of pairwise protein interactions, Reactome Croft et al. (2010), given access different but similar dataset of multiprotein complexes, hu.MAP Drew et al. (2117) After preprocessing, the training dataset has 6,292 nodes (proteins), 51 ground truth hyperedges (multiprotein complexes); the query dataset has 8,243 nodes, 6,688 hyperedges. Our SHyRe-motif algorithm achieves Jaccard accuracy of 0.43 (precision 0.89, recall 0.45). This means that we sucessfully recover around half of all multiproteins complexes in the query dataset, and around 90% of those recovered are correct.
Node degrees for ranking protein essentiality. Many studies Xiao et al. 2015 Estrada (2006): Klimm et al. ()22)) found that the number of interactions that one protein participates in highly correlate to the protein's 's essentiality in the system. The best measure for this is hypergraph node degrees. In practice, node degrees in pairwise PPI networks are often used instead compromise due to the technical constraints mentioned.
Ranking the proteins with highest node degrees produces Table & the top-10 lists for their correspond- ing upstream gene names in the original multiproteins hypergraph (?(), the projected pairwise PPI ne) and the recovered multiprotein hypergraph (H). The recovered hypergraph produces a list much closer the ground truth than the pairwise graph does. Also, notice the different positions
24

---

Published as a conference paper at ICLR 2024
of UBB and GRB2 in all lists: GRB2 encodes the protein that binds the epidermal (skin) growth factor receptor; UBB is one of the most conserved proteins, playing major roles in many critical functions including abnormal protein degradation, gene expression, and maintenance of chromatin structure. Therefore, UBB is arguably more essential than GRB2 in cellular functions, despite interacting with fewer proteins in total. The middle list produced by our algorithm precisely captures this subtlety.
We further use node degrees in the ground truth hypergraph as a reference, and compare their correlation with node degrees in the projected graph and the recovered hypergraph. respectively. The latter was found to have a Pearson correlation of 0.93, higher than the former of 0.88 (p < 0.01). This means that our method helps recover protein essentiality information that closer to the ground truth.
Ground Truth (H)
UBB
UBC
RPS27A
UBA52
GRB2
JAK2
JAKI
SUMOI
FGF2
FGFT
Recovered (Hi
UBB
UBC
RPS27A
UBA52
GRB2
SUMOI
ITGBI
JAK2
JAKI
PIK3RI
Pairwise PPT
GRB2
RPSZ7A
FGF2
FGFI
FGP9
PGF17
FGF8
Table 8: Top- 10 most essential genes ranked by node degrees in different formalisms of hypengraphs/graph. Note that the recovered hypergraph yields a list much closer to the ground truth than the pairwise PPI does.
F.5 USE CASE 2: LINK PREDICTION
As the second use case, we conduct a mini-study to compare the performance of link prediction (as downstream task) the projected graph G, the reconstructed hypergraph H. and the original hypergraph H. To ensure fair comparison, all results are obtained using the same base model of a two-layered Graph Convolutional Network (GCN), including those hypergraphs: The initial node features are initialized using one-hot encodings; to utilize hypergraph features when training on H and H. we append several structural features of hyperedges to the final link embeddings, including: the number of common neighbors of the two end nodes, the number of hyperedges associated with each of the two end nodes and the average size of the hyperedges associated with each of the two end nodes, and the shortest distance (minimum number of hyperedges to traverse) between the two end nodes.
The results are shown Table We observe that the numerical results show that the reconstructed hepegrasphs are indeed helpful to link prediction task compared to the projection graph: 3 out datasets if measured by AUC, and 4 out of 4 datasets if measured by Recall. Cross referencing our Table 3 we can also see the general trend that a better-reconstruuted hypergraph would lead to more boost in link prediction performance. We also note that these results are not to demonstrate hypergraph reconstruction piece of evidence that the reconstructed hypergraphs are a good form of intermediate representation which, compared their projected graphs, is more informative and helpful in downstream tasks.
state-of-thh-art method for link prediction. It, however, provides
AUC-G
AUC-H
AUC-H
Recall-Gi
Recall-22
Recall-H
DBLP
92.82 a 0.11
93.54 =: 0.10
93.69 1 0.11
67.82 a 0.39
69.12 a 0.38
71.44 1 0.28
Enron
84.45 0.22
84.66 0.23
86.51 0.16
68.10 0.50
68.62 a 0.47
70.59 1 0.42
Foursquare
86.56 0.24
87.71 0.24
87.77
75.04 0.38
75.64 # 0.38
75.01 0.35
Directors
85.02 0.30
86.33 0.49
86.48 = 0.45
83.31 0.21
84.00 = 0.25
83.31 = 0.22
Table 9: Comparing the performance of link prediction (as downstream task) on the projected graph G. the reconstructed hypergraph 7. and the original hypergraph H.
Again, we want to emphasize that the goal of this mini-study here isn't to demonstrate the superi- ority of learning-based hypergraph reconstruction against the current state-of-the-art method for link prediction. In fact, SOTA methods for link prediction is often end-to-end customized, in which case the reconstructed hypergraph is not necessary. We reconstruct hypergraphs, instead of end-to-end training model for each downstream task with reconstructing hypergraphs, because we do not know the exact downstream task when we do reconstruction, and we may not even be the person to do the downstream task. Reconstructed hypergraphs be viewed product for more general purpose and versatile usage, which is similar to the role word embeddings play in language tasks.
intermediate
25

---

Published as a conference paper at ICLR 2024
Hypersmen
Guntering Projected Grach (4M
Gusteding Reconatmaction IW T1
200
200
123
125
100
100
75
10
30
00
Prockfed
Figure 10: Performance (NMI) and confusion matrix of spectral clustering on original hypergraph, projected graph, and our reconstructed hypergraph.
F.6 USE CASE III: NODE CLUSTERING
In this third use case, we demonstrate the benefits of reconstructed hypergraphs via another classical task: node clustering. The dataset we use is P.School, which is also used in our main experiment. Its statisties can be found in Table In this dataset, each node represents a student, and each hyperedge represents a face-to-face interaction among multiple students, recorded by their body-worn sensors during period. Meanwhile, each node is labeled as of the 11 classrooms to which the student belongs. We treat these node labels as the ground truth for clustering.
Similar to the first two cases, conduct clustering the original hypergraph, the projected graph, and the reconstructed hypergraph. To ensure fairess, we stick to spectral clustering as the clustering method. Notice that spectral clustering can be easily generalized from graphs to hypergraphs. and has been used as a classical clustering method for hypergraphs for a long time (Zhou et al. 2006). We use normalized mutual information (NMI) and confusion matrix to evaluate the performance. A larger NMI indicates better performance.
Figure I0 shows the result. We see that our reconstructed hypergraph has much better NMI than the projected graph does. We can also visually examine the confusion matrix and derive the same conclusion. This experiment shows that the reconstructed hypergraph crucially recovers a great amount of higher-order cluster structures in the original hypergraph.
F.7 RUNNING TIME ANALYSIS
We have claimed that the clique sampler's complexity is close to O(M) + O(EE) = M(MM) in practice. Here we check this by asymptotic rumning time. Both the elique sampler and the hyperedge classifier are tested. For p [30, 100]. We sample p% hyperedges from DBLP and record the CPU time for running both modules of SHyRe-motif, The result is plot in Fig shows that both the total CPU time and the number of maximal cliques are roughly linear to the data usage (size), which verifies our claim. Fig reports statistics for all methods.
Notice that among all baselines, only HyperSAGNN is suitable for rumning on GPUs. Other baselines run on CPUs. We can see that HypenSAGNN still runs slower than or on par with SHyRe in general. There are two main reasons for this. First, the original HlperSAGNi does not have any procedure for generating hyperedge candidates. Therefore, we have to adapt it so that it actually shares the same maximal clique algorithm with SHyRe. It also took portion of time to sample the cliques from maximal cliques. Second, similar to DeepWalk, HyperSAGNN's 's best-performed variant relies on random walks sampling to generate initial node features, which also takes extensive time.
F,8 ABLATION STUDY ON CLIQUE SAMPLER
One might argue that the optimization of the clique sampler (Sec 4.2.2) appears complex: adopt simpler heuristics for sampling, abandoning the notion of Tn,k 's? We study this via ablations.
We test three sampling heuristics to replace the clique sampler. 1. "randoo": sample cliques from the projection as candidates. While it is hard to achieve strict uniformness khorvash (2009). approximate this by growing clique from random node and stopping when the clique reaches
26

---

Published as a conference paper at ICLR 2024
clique sampler
hyperedge classifier
Amaxiima cliques (lod))
maximaa cliques
CPU time (6)
50%
610
1005
usago (full-100% heperrddgos)
Figure 11: Asymptotic running time of SHoRe-mmtti DBLP. The bar plot aligned with the left y-axis, the line plot with the right. We can observe that both the total CPU time and the number maximal cliques are roughly linear to the data usage (size).
Enron
P.School
H.School
Foursquare
Hosts-Virus
Directors
Crimes
CPU Time, log10 of seconds
Figure 12: Comparison running time. Notice that Bayesian- MDiiaa is written in C++, CMM Matlab, and all other methods in Python.
random size; 2. "s"mal"" we sample 3 cliques of sizes and (i.e. nodes and edges); 3. "head & tail": we sample / cliques from all cliques of sizes 1 and as well maximal cliques.
Fig 13 compares the efficacy in the sampling stage on Enron dataset. It shows that our clique sampler signihcantly outperforms all heuristics and so it cannot be replaced. Also, the the great alignment between the training curve and query curve means our clique sampler generalizes well. We further report reconstruction performance on 3 datasets in Table [O] which also confirms this point.
DBLP
Hosts-Virus
Enron
original (SHyRe-motit)
81.19+0.02
45.16=0.55
16.02+0.35
ablation:
"random"
0.17=0.00
0.00=0.00
0.5410.49
ablation: "small"
1.12+0.52
1.38+0.70
8.57+0.89
ablation: "head & tail"
27.42+0.54
29.92=0.54
11.99=0.10
Table 10: Ablation study: comparing the performance obtained by replacing the clique sampler with simpler heuristics for sampling.
27

---

Published as a conference paper at ICLR 2024
800
total hyperedges
hyperedges samplex diques
(same for Hig and H2)
700
600
SHyRe (Ho. Go)
SHyRe (H1, G1)
500
ablation: head & (Hi, G1)
400
300
ablation: small (7t,. G1)
200
100
ablation: random (H,, G1)
2000
4000
6000
8000
10000
sampled cliques
Figure 13: Ablation studies the clique sampler. Each marker is iteration in Algo. the two SHyRe curves shows that our clique sampler has the best generalizability.
The alignment between
F.9 TASK EXTENSION USING EDGE MULTIPLICITIES
Throughout this work, we do not assume that the projected graph has edge multiplicities. Relying on edge multiplicities addresses simpler version of the problem which might limit its upplicability. That said, some applications may come with edge multiplicity information, and it is important to understand what is possible in this more tractable case. Here we provide effective unsupervised method as a foundation for further work.
The multiplicity of edge (u, v) is the number of hyperedges containing both and It is not hard to show that knowledge of the edge multiplicities does not suffice to allow perfect reconstruction, and still must choose from among with multiplicity information, we need to ensure that the cliques we select add up to the given edges multiplicities. We do this by repeatedly finding maximal cliques, removing them, and reducing the multiplicities of their edges by 1. We find that an effective heuristic is to select maximal cliques that have large size and small average edge multiplicities (combining these for example using a weighted sum).
of available cliques form hyperedges. In doing this
Table I1 gives the performance on the datasets we study. We can see that with edge multiplicities our unsupervised baseline outperforms all the methods not using edge multiplicities on most datasets, showing the power of this additional information. The performance, however, still far from perfect, and we leave the study of this interesting extension to future work.
DBLP
Enron 19.79 (+3.77)
P.School 10.46 (-32.60)
H.School
82.75 (+1.56)
19.30 (-35.56)
Foursquare 83.91 (+10.35)
Hosts- Hosts-Virus Virus 67.86 (+19.01)
Directors 100.0 (+0.00)
Crimes
80.47 (+1.20)
Table 11: Performance of the proposed baseline using available edge multiplicities. In parenthesis reported the increment against the best-performed method not using edge multiplicities (cr. Table 3).
F. TASK EXTENSION II: RECONSTRUCTING FROM PROJECTION
Formulated in (3) of Kumar et al. (020b), node-degree preserving projection is novel projection method proposed in recent years that can preserve node degrees in the original hypergraph. It innovatively achieves this by scaling down the weight each projected edge by a factor of ([E) 1). where [E] is the size of the corresponding hyperedge.
28

---

Published as a conference paper at ICLR 2024
Our reconstruction method naturally extend to this novel type of projection. The reason is that our method has solved a strictly harder version of the reconstruction problem: our problem setting does not require the projected graph have edge multiplicities (weight). In comparison, node-degree preserving projection not only produces the same set of edges as our projection does, but also provides edge weights. More importantly, node-degree-preserving projection (as its name suggests) provides the degree of each node in the original hypergraph, which is a useful piece of information reconstruction. This information can be seamlessly integrated into our framework, as follows.
For each target clique:
1. We obtain the degree of each of its node in the original hypergraph (by computing that node's 's degree in the node-degree-presee
projection).
2. We compute the min and average of this new type of "node degree" for all nodes in the target clique.
3. We append the two features obtained in the last step to the "count" feature vector used in SHyRe-count.
This gives us customized SHyRe-count model for node-degree peeeeeeerresrving projection. We train and test this customized SHyRe-count model on all the 8 datasets used. The results are presented in Table 12 We observe that SHyRe's s reconstruction performance on every dataset's node-degree- preserving projection is better than its performance on the regular projection used throughout this paper. These results validate our claim that our reconstruction method can naturally extend to the novel sete-deerree-peseevvin projection.
DBLP 83.54 (+2.36)
Enron 14.30 (+0.80)
P.School
H.School
44.30 (+1.70)
55.43 (+0.87)
F Foursquare
Hosts- Virus
Directors
Crimes
76.68 (+2.08)
50.63 (+1.78)
100.0 (+0.00) 87.78 (+8.60)
Table 12: Performance of SHyRee-ouut method adapted for ponee-eeree-preeeevvee projection. Numbers the parenthesis are the increment over the performance SllyRe-count on the original projections (cross referecing Table 3).
F.11 STORAGE COMPARISON
A side bonus of having reconstructed hypergraph versus a projected graph that the former typically requires much less storage space. As a mini-study, we compare the storage of each hypergraph, its projected graph, and its reconstruction generated by SHyRe-count. We use the unified data structure of nested array to represent the list of edges/hyperedges. Each node is indexed by an int64. Fig [4] visualizes the results. We that the reconstructions take to 2 orders of magnitude less storage space than the projected graphs and are closest to the originals.
original hypergraph (Ma) projected praph (G)) Aug.
10
storage (bytes)
101
reconssruesed hypergraph
30'
10
Founguue Hiats Figure 14: Comparing the storage of original hypergraphs, projected graphs and reconstructed hypergraphs. Each hypergraph/graph is stored nested array with int 64 node indexes. Over the 8 datasets average, reconstructed hypergraph takes only 4.6% the storage of projected graph.
DBLP
Erson
PSehoa H.Sebaal
Direcins
Crine
F.12 MORE EXPERIMENTAL RESULTS
29

---

Published as a conference paper at ICLR 2024
Foursquare
Chiines
moot cho0 500. 15
Ficc cloue stee un
2.5-
stae
5
roc cla ston mo
Thir hooe sume mo
3
G
X
10.0
20 OUDeRt diw RQ)
10 CLiee COe 241
10 Gibeet C/
10 Gureet- (3)
0i0e COW
Frae Kow [9]
013041 nie D0
K.bre [4]
Figure 15: Distribution of the & 's of the optimal sampling strategy all datasets. Cells of the first column and the diagonal have better chance he included, but there also exist exceptions, such as Enron (second column), P.School and H.Scoool (second to fourth columns), etc.
DBLP
Enron
P.School
1.Scheol
Foursquare
Directors
Crimes
Perform (%)
Figure 16: Partitioned Performance of methods on datasets. Recall that the Errors and II are mistakes made by Max Clique [D Other methods may make mistakes that Max Clique does not make, which are counted as "Other Error". We can see that SHyRe reduces more Frrors I and II than other haselines do.
G MORE DISCUSSION ON LIMITATIONS AND FUTURE WORK
G.1 DIRECTION I: OPTIMIZING SAMPLING RATES USING DOWNSTREAM CLASSIFICATION LOSS
One limitation in the presented reconstruction method is that it does not adjust the sampling rate (i.e., the Tn,k 's) based on the downstream classifier's performance on cliques sampled at different (n, ks's. In other words, because we have constraint budget, idcally should allocate more sampling budget to sample the types of cliques on which the downstream classifier excels at making judgement. However, under the current framework, framework is not optimizable in end-to-end fashion using gradient descent. Formally speaking, the current reconstruction framework is essentially optimizing the following objective fr,
f(r, 0) max maxxinnB ED- 9
(2)
where r the sampling rates of all cells, i.e., the vector of all Tn,k 's as defined under Sec 4.2.1
the parameters of our hyperedge sampler; D is the distribution of all possible hyperedge candidate sets that we can construct based on given sample rates and the training hypergraph H; D is the specific instance of hyperedge candidate set that we end up sampling and constructing.
would obviously be highly desirable we can optimize f with respect to both r and using gradient descent. Fixing r, to optimize ff with respect to 0 via gradient descent is straightforward. which is exactly the job done by our current hyperedge classifier. However, optimizing f with respect to both r is much trickier. Notice that depends on through D which essentially is discrete data
30

---

Published as a conference paper at ICLR 2024
Detance
D81P
(lggin)
11Schl
locnquare
lomt-Ain
13
Cima
DHLP
Fane
Sutool
Hose Vina
Dintom
Cites
Figure 17: Pairwise distance between p(n,A k) distribution of all datasets using mean squared difference of all cell values (after alignment). The distance matrix obtained is shown above. The diagonal cell the darkest among its row (or column).
DBLP 1.086, (>6.0E10)
Enron 1.033, 6.9E4
P.School
H.School 6.0E4, 8.4E5
3.5E5 2.6E6 Directors 800, 4.555
Foursquare 2.0E4, > 1.1E12)
Hosts-Virus 6.0E3, (>> 2.2E12)
Crimes 1.0E3, 2.95
Table 13: Optimal clique sampling number and total number of cliques [24] ">> appears if the dataset contains too many cliques be enumerated by our machine 24 hours, which case a conservative lower bound estimated instead.
representation, i.e., set of cliques. This blocks the gradient flow and can could be very challenging to address.
We propose simple workaround here which is alternating the optimization of and 0, in two phases:
phase 1, we fix the parameters of our hyperedge classifier, and optimize the parameter r of our clique sampler using Algorithm in the paper;
In phase 2, we fix the parameter of our clique sampler, and optimize the parameters of our hyperedge classifier by standard supervised learning.
The proposed solution above works in similar manner as k-means. However, it is not guaranteed that the global minimum will be reached. We consider this as very intriguing direction to explore in the future.
G.2 USING ATTRIBUTES RECONSTRUCTION
Another direction we may consider is the usage of node attributes in the learning baased framework. Our current method targets the most difficult version of the reconstruction problem: we don't assume nodes edges to have attributes, and the reconstruction is purely based on leveraging structural information the projected graph. It would be interesting to think about how we can effectively integrating node attributes into the picture, since in practice some information about nodes in the projected graph. This is a nontrivial problem to research though, because the projected graph has special clique structures (and with max cliques that have preprocessed). Therefore, how to conduct graph learning most effectively on these type of clique structures could be something worth exploring the future.
may be able collect
31


Reviews:
[{"review_id": "2d93AwGIkq", "reviewer": "Reviewer_EEWq", "summary": "The authors (a) analyze the hardness of reconstructing a hypergraph from its clique expansion, (b) propose a supervised algorithm for hypergraph reconstruction, and (c) empirically demonstrate the effectiveness of the proposed algorithm, compared to previous approaches. The proposed algorithm begins by sampling potential hyperedges based on domain-based patterns, followed by the classification of these candidates.", "questions": "I served as a reviewer for this submission at other conferences and had enough opportunities to (anonymously) interact with the authors. I do not have any further questions or inquiries.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "S1. The proposed formulation and algorithm are a novel blend of empirical insights and theory.\n\nS2. The difficulty of problem at hand and the approximation guarantee of the proposed algorithm are theoretically analyzed.\n\nS3. The proposed method reconstructs hypergraphs more accurately, compared to baseline approaches, and the reconstructed hypergraphs are shown useful for downstream tasks compared to graph representations (i.e., clique expansions).\n\nS4. The paper is exceptionally well-written.", "weaknesses": "W1. The graph representations (e.g., clique expansions) and hypergraph representations have been compared in many contexts, which are largely ignored in the paper (see [R1]-[R3]).\n- [R1] The why, how, and when of representations for complex systems\n- [R2] How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction\n- [R3] HNHN: Hypergraph Networks with Hyperedge Neurons\n\nW2. The comparison between the structures of the original hypergraphs and the reconstructed ones is limited, relying on basic statistical metrics. It's important to note that hypergraph structures can exhibit variations even when their basic statistics align. To conduct a more comprehensive comparison, additional measures and analytical tools should be considered [R4].\n- [R4] Mining of Real-world Hypergraphs: Patterns, Tools, and Generators\n\nW3. The algorithm is divided into two components: sampling and classification. Notably, the classification accuracy may vary across different (n,k) combinations. However, this aspect was not considered during the formulation and theoretical analysis of the sampling part.", "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": "", "extra_scores": {}}, {"review_id": "vKBz1QMcgz", "reviewer": "Reviewer_zeZp", "summary": "This paper investigates the reconstruction of a hypergraph from a projected graph. The authors propose a learning-based hypergraph reconstruction method based on their observation of the distributions of hyperedges within maximal cliques. They utilize a clique sampler and a hyperedge classifier to reconstruct hypergraphs.\n\nThe authors evaluate their method for hypergraph reconstruction and downstream tasks using the reconstructed hypergraphs. They show that their method outperforms existing methods for hypergraph reconstruction. Using hypergraphs reconstructed by their method improves performance on downstream tasks compared to using projected graphs.", "questions": "1. Could the performance improvement in experiments on link prediction have originated from the use of additional structural information?\n\n2. Could the authors demonstrate the benefits of reconstructed hypergraphs through additional experiments?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well-written and easy to understand.\n\n2. The proposed method effectively address problems with appropriate approaches.\n\n3. It seems to provide a foundation for the underexplored problem of hypergraph reconstruction from a projected graph.\n\n4. The experimental setup for reconstruction is well-designed and the proposed method yields good performance.", "weaknesses": "1. I'm uncertain about the necessity of addressing this problem.\n\n2. It would be advantageous to incorporate supplementary experiments to illustrate the benefits of utilizing reconstructed hypergraphs. Although the experiments show the proposed method's strong performance in reconstructing hypergraphs, its impact on downstream tasks remains unclear.\n\n3. In experiments for link prediction (In F.4), the authors append several structural features of hyperedges to the final link embeddings. However, in cases of projected graphs, additional structural features cannot be used. Is it a fair comparision?", "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": "", "extra_scores": {}}, {"review_id": "C9WS2zMIk9", "reviewer": "Reviewer_rZdL", "summary": "This paper studies the task of recovering a hypergraph from its projected graph (i.e., the graph formed by forming an edge between any two nodes that are a part of the same hyper-edge). \n\nThe first main contribution is a set of theoretical results stating when it is possible to reconstruct the hyper-edges based on the maximal cliques of the projected graph, G. In particular, the authors identify two necessary and sufficient conditions for the recovery of the hypergraph from G: (1) the lack of any \"nested\" hyper-edges, and (2) the lack of any \"uncovered triangles\" (Thm 1). Moreover, when (2) is not satisfied, the reconstruction accuracy using maximal cliques can be exponentially small in the number of hyper-edges (Thm 3). \n\nThe second main contribution is a learning-based approach that leverages side information in the form of same-domain hypergraphs to reconstruct a hypergraph from its projection. The method follows a 4-step procedure. First, the distribution of hyper-edges within maximal cliques of G is computed for the training data (the known hypergraph of the same domain); these are denoted by the $\\rho(n,k)$'s. Using this information, cliques in G are sampled  in a way that is optimized for the $\\rho(n,k)$'s and a query budget (since the total search space is very large). Finally, cliques are classified as hyperedges or not based on the local structure of the cliques with respect to the surrounding graph. The methodology is assessed on a variety of datasets with favorable results.", "questions": "- Concerning the characterization of \"conformal\" in Theorem 2, it might be worth describing the explicit connection between uncovered triangles and hyper-edge reconstruction. That is, the triangle would induce a 3-clique among the \"points\" of the triangle, which would not be part of a hyper-edge if the triangle is uncovered. \n- Are there any natural strategies you'd expect to perform better than looking at maximal cliques, for the case of no side information?\n- The notation $\\mathbb{E}^c$ (denoting expected cardinality) is a bit nonstandard. Perhaps just write $\\mathbb{E}[|S|]$ for the expected size of a set S.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Reconstructing hypergraphs from their graph projections is an important task in several domains, and this is summarized very well by the authors in the introduction. This task has received little to no attention previously, making the fundamental analysis in this paper quite valuable.\n\nThe authors' contributions are substantive and fundamental, spanning both theory and practical implementations. The motivation for studying cliques is clear, and the authors derive a nice, fundamental characterization for general hypergraph recovery using maximal cliques. The authors' development of a scalable, learning-based approach to overcome the shortcomings of an approach without side information serves as a nice, practical complement to the theoretical results.", "weaknesses": "The approaches outlined in the paper are somewhat basic (which itself is not a weakness, as the problem is novel and the contributions fundamental). What are potential future directions for the design of possibly more sophisticated methods? What other types of information could be taken into account to improve guarantees for hypergraph reconstruction? Some discussion of these and related questions would be quite valuable.", "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": "", "extra_scores": {}}, {"review_id": "OzB9I0Mlmd", "reviewer": "Reviewer_U5QZ", "summary": "The authors propose a method of constructing a hypergraph from a given graph. The proposed method includes analyzing cliques present in the graph and classifying them into potential hyperedges. The proposed method is compared against baselines, and the results show superior performance of the proposed method.", "questions": "1. Conditions stated in Theorem 1 are explained as necessary conditions to reconstruct a hypergraph from a given projection using the max-clique algorithm. But are these conditions sufficient? Is there any theoretical justification for that?\n2. The clique-sampler tries to sample for as many as possible hyperedges. Will it not affect the size of hyperedges being predicted?\n3. The performance of the proposed method is not very different from the baselines on hypergraphs where the average hyperedge size is large. Is there any justification for that? Also, from the predicted hyperedges, is it possible to provide a stratified evaluation to understand how the proposed method works on large vs small hyperedges?\n4. Can you think of a real-world scenario where converting a graph to a hypergraph (where we know that there are underlying group interactions) is essential, and this approach can help?\n5. Apart from clique-based projections, there are other hypergraph projection methods, such as the node-degree-preserving method[4]. Can this approach recover hyperedges from such projected graphs?\n\n\n6. I request the authors to provide justification for the following.\na. In the Introduction section, whether the hyperedges are observable or not actually depends on the objective of experiments conducted on the system. For example, protein-protein, gene-gene interactions have semantics defined for pairwise interactions where protein complexes are inherently super-dyadic relations of proteins, and experiments observe them in the protein complex form [1].\nb. Unpublished: True, author-author interaction datasets do not provide the underlying hypergraph structure, but one should go with other bibliographic datasets such as AMiner[2] to get a complete view of the system.\nc. Relevance to the hyperedge prediction problem: The problem of hyperedge prediction is actually relevant. The hyperedge prediction methods consume a hypergraph as input, and the right way to see it is every graph is also a hypergraph (more precisely, 2-uniform hypergraph), and the methods [3] where a set of candidate hyperedges is not used can identify underlying hyperedges. Especially when you are using the sample hypergraphs from a given domain, methods like HPRA can generate new hyperedges using the known hyperedge degree distribution.\n\n\n[1] \"Hypergraphs and cellular networks.\" PLoS computational biology 5.5 (2009): e1000385.\n[2] https://www.arnetminer.org/\n[3] \"HPRA: Hyperedge prediction using resource allocation.\" Proceedings of the 12th ACM Conference on Web Science. 2020.\n[4]  \"Hypergraph clustering by iteratively reweighted modularity maximization.\" Applied Network Science 5.1 (2020): 1-22.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The problem is very important. Many times, getting hypergraph-based representation is hard. The proposed approach can be used to convert a graph-based representation to an underlying hypergraph.\n2. The proposed approach builds on the clique finding algorithm, a known approach for finding potential hyperedges. Its key challenges, such as predicting hyperedges that are a complete subset of larger hyperedges, computational challenges, etc., are tackled well.\n3. The results show that the proposed method outperforms the baseline approaches.", "weaknesses": "1. The paper lacks a comparison of their method with several other works in the domain. I have listed them in the Questions section. \n2. Writing lacks a clear outline of the contributions. In the proposed pipeline, what is already proposed vs. what is novel, is not clear.\n3. The problem and solution are discussed in detail, but the experiments and results are not justified. What properties of a hypergraph make the proposed algorithm more suitable? On some datasets. The baseline methods demonstrate comparable performance; what is the reason behind that?\n4. Other weaknesses are asked in the Questions section.  \n\nMinor typos (does not affect the rating):\nPage 3: as well as and", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)