HyperPLR: Hypergraph Generation through Projection, Learning, and Reconstruction
Authors: Weihuang Wen
Tianshu Yu
Venue: ICLR 2025 Poster (2025)
Keywords: hypergraph
graph generation
clique cover problem
Primary area: learning on graphs and other geometries & topologies

Abstract: Hypergraphs are essential in modeling higher-order complex networks, excelling in representing group interactions within real-world contexts. This is particularly evident in collaboration networks, where they facilitate the capture of groupwise polyadic patterns, extending beyond traditional pairwise dyadic interactions. The use of hypergraph generators, or generative models, is a crucial method for promoting and validating our understanding of these structures. If such generators accurately replicate observed hypergraph patterns, it reinforces the validity of our interpretations. In this context, we introduce a novel hypergraph generative paradigm, **HyperPLR**, encompassing three phases: Projection, Learning, and Reconstruction. Initially, the hypergraph is projected onto a weighted graph. Subsequently, the model learns this graph's structure within a latent space, while simultaneously computing a distribution between the hyperedge and the projected graph. Finally, leveraging the learned model and distribution, HyperPLR generates new weighted graphs and samples cliques from them. These cliques are then used to reconstruct new hypergraphs by solving a specific clique cover problem.
We have evaluated HyperPLR on existing real-world hypergraph datasets, which consistently demonstrate superior performance and validate the effectiveness of our approach.

Published as a conference paper at ICLR 2025
HYPERPLR: HYPERGRAPH GENERATION THROUGH PROJECTION, LEARNING, AND RECONSTRUCTION
Weihuang Wen, Tianshu Yu School Data Science
The Chinese University of Hong Kong, Shenzhen we weihuangwen link.. cuhk. edu. cn, yutianshuuuukk.ed.
ABSTRACT
Hypergraphs are essential in modeling higher-order complex networks, excelling in representing group interactions within real-world contexts. This particu- larly evident in collaboration networks, where they facilitate the capture of group- wise polyadic patterns, extending beyond traditional pairwise dyadic interactions. The use of hypergraph generators, generative models, is a crucial method for promoting and validating our understanding of these structures. If such genera- tors accurately replicate observed hypergraph patterns, it reinforces the validity our interpretations. In this context, we introduce a novel hypergraph gener- ative paradigm, HyperPLR, encompassing three phases: Projection, Learning, and Reconstruction. Initially, the hypergraph is projected onto a weighted graph. Subsequently, the model learns this graph's structure within a latent space, while simultaneously computing distribution between the hyperedge and the projected graph. Finally, leveraging the learned model and distribution, HyperPLR gener- ates new weighted graphs and samples cliques from them. These cliques are then used to reconstruct new hypergraphs by solving a specific clique cover problem. We have evaluated HyperPL. on existing real-world hypergraph datasets, which consistently demonstrate superior performance and validate the effectiveness of our approach.
INTRODUCTION
Hypergraphs are powerful data structures that go beyond traditional graph theory by enabling more nuanced representation of multifaceted relationships. Unlike standard graphs, where edges connect merely pairs of nodes, hypergraphs employ hyperedges, each binding multiple nodes, thereby cap- turing complex, multi-way interactions with higher fidelity. This capability renders hypergraphs indispensable across a vast array of fields such as drug discovery (Kajino) 2019), electronics (Luo) et al. 2024), research collaboration networks (Benson et al., 2018). and protein interaction model- ing (Feng et al. 2021), where interactions often occur among more than two entities.
Despite the expansive potential of hypergraphs, the generative models that craft these complex struc- tures are still in their nascent stages. Existing models predominantly cater to simpler graph structures are bound by pre-assumed hypergraph characteristics, which might not be universally applicable to the diverse and intricate patterns present in the actual datasets (Lee et al.) 2021 Do et al. 2020
Kook 2020). Recent advancements include learning-basee generative models (Zuo al. Gailhard et al. 2024) that attempt to sidestep the necessity for predefined data structures; however, these too often fail encapsulate critical structural nuances that define hypergraph integrity.
2023
In light of these challenges, we propose a pioneering framework known as HyperPLR (Projection, Learning, and Reconstruction), which introduces robust three-phase process for the generation of hypergraphs. Initially, HyperPLR projects the complex hypergraph onto simplified weighted graph format, essentially maintaining key relationships. then transitions into a learning phase, wherein discerns the latent structures within this graph and models the inter-dynamies among the projected entities.
"oorresponiing author

---

Published as a conference paper at ICLR 2025
In the final phase, define novel clique cover problem to reconstruct new hypergraphs from the learned weighted projection graph: Weighted Clique Edge Cover (WCEC). is a common strategy to project hypergraphs onto graphs, but it is evident that this process results in the loss of some higher-order relationships. However, limited research has investigated the reverse direc- tion reconstcstrru hypergraphs from graph projections (Bresler et al. 2024 Wang & Kleinberg, 2024). The closest work so far is by Young et al. (2020), which proposes maximal clique recon- struction that uses the least number of cliques to cover the projected graph, following the principle of parsimony. However, this method does not consider the number of hyperedges or the degree in- formation of vertices. To address these issues, we use weighted graph as the projection, design the WCEC problem, and show that solving WCEC allows efficient and more controllable hypergraph reconstruction from the projection. Additionally, we develop a fast heuristic for approximating the solution.
Our extensive evaluations of various real-worke datasets underscore HyperPLR's adeptness at weav- ing hypergraphs that faithfully reflect the underlying complexities of group interactions. Thus, Hy- perPLR marks a significant technological leap in hypergraph generation.
The principal contributions of this paper are encapsulated in the following:
Introduction and formulation of the WCEC problem, complemented with an efficient algo- rithmic solution for reconstructing hypergraphs.
Development of the novel HyperPLR framework, which harmoniously integrates the struc- ture and intricate interactions within hypergraph.
Empirical validation of HyperPLR against multiple real-world datasets, showcasing en- hanced efficiency and remarkable performance in hypergraph reconstruction.
2 RELATED WORK
The study of hypergraph generation has garnered increasing attention as an extension of traditional graph generation techniques, addressing higher-order relational structures present in many real- world applications. Traditional graph generation models have advanced significantly with the intro- duction of deep learning techniques. (Kipf & Welling 2016 Jin et al. 2018 Bojjhhvski al. 2018) generate graphs by imitating the structural properties of given graphs. This is typically achieved by learning node/edge embeddings and injecting appropriate randomness (Grover al. 2019] Wang it al. 2019; Dai et al.) 2020). However, methods relying on node/edge embeddings often focus pr- marily on local structures, particularly in large graphs. While graph spectral theory offers an alter- native approach, some studies incorporate spectral information into deep models to capture global characteristics (Martinkus et al. [002]]]]] BBojchevski et al.) 20188] [Rendbburg et al.] (020).. Among these, CELL (Rendsburg et al.] 2020) stands out for its efficiency and scalability, achieved by re- moving unnecessary operations from Bojchevski et al. (2018). Another consideration is to generate
graphs with weights (edge features) (Grover al. 2019 Niu et al. 2020 Kocayusufoglu et al. 2022). which again heavily relics on embeddings.
Traditional graph generation models, while effective for molecular graphs and citation networks, not suitable for hypergraph generation. Hypergraphs, with hyperedges connecting multiple nodes, pose challenges that standard graph models cannot address. Several methods have been proposed for hypergraph generation. HYPERPA (Do et al.) (020) uses a statistical approach, relying on three key metrics from real-world hypergraphs: node count, hyperedge size distribution, and new hyper- edges per node. While HYPERPA generates hyperedges based on these metrics, its dependence on precomputed statistics and iterative generation process increases time complexity. HyperDK (Naka-) juma et al. 2022) generates hypergraphs that preserve local properties of nodes and hyperedges, controlled by two hyperparameters, d, and de. A higher de value indicates that higher-order in- formation regarding node degrees is preserved, while higher de value implies the preservation of higher-order information regarding hyperedge sizes. ThERA (Kim et al. 2023) organizes nodes in hierarchical structure across multiple levels, with nodes divided into disjoint levels and deeper levels containing more nodes. It generates hyperedges locally within each group based on a given probability. Compared to parameter-basee methods, only few deep learning models have explic- itly addressed hypergraph generation to date (Zuo et al. 2023) Gailhard et al.) 2024), and existing learning-basse based hypergraph generation approaches are limited by scalability issues.
2

---

Published as a conference paper at ICLR 2025
weighted projected
projected
(a) Graph projection
(b) Hypergraph:
(c) Weigiate graph projection
Figure I: Hypergraph's 's graph projection (left direction) and weighted graph projection (right diree- tion), with line thickness referring to its weight.
summary, while deep learning techniques for graph generation have made significant strides, hy- pergraph generation remains emerging of research. Existing models, though promising, often rely on adaptations of graph generation methods and statistical approaches, with inherent limitations in scalability and evaluation. There is growing need for more robust models specifically designed for hypergraph generation, particularly ones that can efficiently capture the complex, higher-order relationships that hypergraphs represent.
PRELIMINARIES AND NOTATIONS
Hypergraph. A hypergraph is generalization of graph where edges, called hyperedges, can connect more than two vertices. Formally, a hypergraph is defined as (V,E) where V set of vertices and & is set of hyperedges (c1, ... , Cm) with C V. In a hypergraph, hyperedges can be of varying sizes, capturing higher-order relationships between sets of nodes beyond pairwise connections and assume the hyperedges are distinct in paper, which means VI i,j s m, 6 # Cj-
Graph Projection. A graph projection, or clique expansion, of a hypergraph, is a transformation process that converts hypergraph into traditional graph. In this projection, each hyperedge of the hypergraph is mapped to a clique (a complete subgraph) in the graph, where each pair of nodes in the hyperedge is connected by an edge in the projected graph. Formally, if H (V, E) is hypergraph, the projection graph G Proj(H) (V, E'), where E' consists all pairs (1,, Dy) E for hyperedge e, E E
Weighted Graph Projection. this paper, we introduce a novel graph projection method for learning-base based hypergraph generation, namely Weighted Graph Projection, which effectively pre- serves the frequency with which vertices co-occur within hyperedges. Formally, given a hy- pergraph H (V, E), the weighted graph projection is to project H into weighted graph G Proj...H = (V,E", w). The w is a weight function that assigns a weight to each edge e' E E'. The common way to assign weight is w(r,, 0z) Σ I(v, 0j E e) where ll is indicator aEE function that equals if both vertices vj and v are part of the same hyperedge.
Clique Edge Cover Problem. The Clique Edge Cover problem is concerned with covering all the edges of graph using the minimum number of cliques (complete subgraphs). This problem also referred to the Minimum Clique Edge Cover (MCEC) problem. Given graph G' (V, belongs to at least one clique.
a clique cover is a collection of cliques such that every edge The goal is to minimize the number of cliques in the cover. This problem is closely related to the projection of hypergraphs, as each hyperedge in a hypergraph corresponds to a clique in the projected graph, and reconstructing the original hyperedges can be seen clique cover problem in reverse Bresler et al. (2024).
Fig. illlustrates the two different projection methods between hypergraph and traditional graph.

---

Published as a conference paper at ICLR 2025
Graph G
Graph d'
Training
CELL
Weight
GWC
Hypergeapii
Node2Voe
Prediction
Testing
GNN
MSE
Lon
Ydg
Nornal
Weighted Graph
Weighted Geapla W
Projection
Learning
Reconstruction
Figure 2: An overview of HyperPI. framework. We use RED and BLUE arrowed lines to indicate flows in the training and the testing phases, respectively. Black arrowed lines are normal flows.
HYPERPLR
In this part, elaborate on the framework of HyperPLR in detail. A high-level overview of the HyperPLR framework can be found in Fig. 2 As shown, the framework consists of three core blocks: "Projection", "Learning", and "Reconstruction" acting in the presented order. Given input hypergraph H. the projection block project H. to the corresponding graph G and weighted graph G.. In the following learning block, we employ CELL (Rendsburg et al. 2020 to sample the new graph G". In parallel to CELL, we adopt a GCN (Kipf & Welling, (0117) 7 to trai a weight predictor taking node features of G input, to optimize the MSE error w.r.t. the real edge weight w in G During the testing phase, the sampled graph G' is instead fed into this predictor as the graph topology, and the new weighted graph G is obtained by filling predicted weights into G'. In the last block of reconstruction, GWC performs heuristic strategy to dynamically produce the most likely overlapping cliques out of G" Finally, this collection of cliques is readily converted to a new hypergraph H'. We detail each block in the following sections.
4.1 PROJECTION
Projecting hypergraphs onto graphs and utilizing graph algorithms is common technique for solv- ing hypergraph-related problems, as improves storage efficiency, interpretability, and allows for the of well-established data structures and algorithms. However, hypergraph projection often results in the loss of higher-order relationships. To address this, there has been research on the lim- itation when reconstructing hypergraphs from their graph projections (Bresler et al., 2024 Wang & Kleinberg 2024). Although exact reconstruction of the original hypergraph is generally infeasible, find that with appropriate "guidance", it possible to effectively reconstruct most of the patterns in the hypergraph. This insight motivates our investigation into the generation of such "guidance". Specifically, demonstrate that learning to generate this guidance can enable the creation of new hypergraph that retains most of the information from the original hypergraph's projection. In our study, we show that the weighted graph projection G serves as effective form of guidance during the reconstruction process.
On one hand, the weighted projection offers a more condensed hyperedge information into edges, reducing graph size compared to bipartite representations, which require separate hyperedge nodes. As discussed in [Bojchevski et al. (2018); Rendsburg et al. (2020), bipartite graphs are difficult to analyze using spectral tools, they do not possess steady states. On the other hand, the weighted projection provides a higher representational capacity than the unweighted projection. Notably, in the weighted projection, the weight of each edge in the graph reflects the co-occurrence frequency of its nodes within hyperedges, thereby preserving crucial information for the reconstruction of the original hypergraph.
4

---

Published as a conference paper at ICLR 2025
4.2 LEARNING
Learning to generate weighted projection G that resembles the projection from the real-world hypergraph is non-trivial, 1) G. with weights hard model and learn, and real-world hypergraph can easily scale up (to tens of thousands of vertices) with long-range dependencies like overlapping cliques or communities large hypergraphs. We first present how this can be achieved at high level. Considering a weighted graph with node feature X E IRaxd adjacency matrix A, and weight matrix W, we have:
P(W, A|X) A,
(1a)
= -P(WW A, X) II IP(A.))
(lb)
1.j
P(W e A.g. X) P(A..)
(Ic)
II Pa (W., A.g X1 ())P (.
(Id)
where P(.) measures the probability. Eq. la stands because A is derived solely from a spectral method, independent of X. Eq. (Tb) is due the fact that A is drawn from an edge-independent "score matrix" as in Bojchevski et al. (218)) Rendsburg et al. (020). Eq. (Ic) and (Id) are further
built upon the assumption that edge weight Wej only dependent on the features of the ending nodes X; and X,, and the existence of this edge Ai.j, under two distributions parameterized by and B.
We first introduce (.(()) allowing for generating large-scale graphs with high efficiency. To this end, we employ CELL (Rendsburg et al.) (020). CELL is a graph generative model working in the spectral space by removing redundant computation from NetGAN (Bojchevski et al. 2018). In NetGAN, the following objective is optimized
min 2 Z
Σ
log Trows (Zrows())nn (Z),
rank(Z) < h,
(2)
(N.D)R
where R is a collection of (massive) random walks and (u, v) is a transition. (zwws()) is a row-wise softmax function perform on the low-rank variable Z. In practice, NetGAN needs sample mil- lions of random walks from a graph with moderate size, which is prohibitively expensive. Besides, the extra computational burden is required as NetGAN trained generator to produce fixed-length random walks to obtain new graph.
CELL (Rendsburg et al., 2020) argued that such a massive amount of sampling procedures and the generator in NetGAN can be avoided by only considering the spectral properties in limit. Concretely, given the adjacency matrix A of a graph, its transition matrix can be obtained via P = D-1 A where D diag(d d) x"*" is the degree matrix. Assuming the stationary state of P exists and is unique, CELL considers acting an infinite number of infinite long random walks and calculates how many times node be visited. The time of visit for nodes can be encoded in "score matrix" S, and the normalized score matrix in limit is
lim
700 qT' = diag(T))
T-000
where q and are number and length of random walks, respectively. Thus S can serve as a surrogate of random walk set R in Eq.
T Su, log Trows )u,e-
min ZER
(4)
Since P x A and rescaling S will not change the optima in Eq. ④4) the final objective of CELL becomes
min ZEReXa
Σ
Au,o log Trows (Z),,v s.t. rank(Z) < h,
(5)
5

---

Published as a conference paper at ICLR 2025
whose solution is denoted as Z Then P Trows can be viewed low-rank-regg regularzdd transition matrix. We can obtain a new score 5 = diag(T") where xt is the stationary distribu- tion of P*, Finally, the edges of a new graph can be independently sampled according to S*
Next, we discuss P. (.). To allow generating graphs with weights, we extend CELL by providing predicted weights the sampled edges, where the edge weight predictor is Graph Convolutional Network (GCN) (Kipf & Welling, 2017). During the training phase, this predictor takes the vertex embeddings X (0) and the adjacency matrix A as input, and outputs a set of new embedding X!):
X = GCN(X (A),
(6)
where 1 is the number of basic GCN layers. The loss is the MSE between the predicted weights x00 and the ground-trun truth weights W' of the original WLIG on the observed edge set A:
Σ ((X)) (CJ)A
2
W1
This weight predictor can be trained not only on a single graph projection (though we train separate embedding networks for each instance) but throughout a set of formulas, since all these formulas may share common structures on weights. In the testing stage, we feed the embedding X and a sampled adjacency A' from CELL into the well-trained GCN:
x GCN(N (0) A').
(8)
Then weights can be derived using _ X!!TT We only consider the weights on the edges that appear in A'. See the "Learning" block in Fig. 2 for intuitive view.
One remaining problem is how to obtain the initial Node Embedding (0) for each vertex. One of the most intuitive ways to use a one-hot representation, but as the size of the hypergraph grows, train the node
the vertices number n and the required dimension increase rapidly. In practice, embedding with the Node2Vec algorithm (Grover & Leskovee 2016) from the simple projection graph G.
4.3 RECONSTRUCTION
As each hyperedge in the hypergraph H. is mapped to clique in the graph projection G or G it is straightforward to consider the reconstruction as a clique cover problem, for example, MCEC problem (Rodrigues) 2021). Here, we give proposition about the limitations of the MCEC:
Proposition 1. One hypergraph H can be reconstructed by solving the MCEC on the graph projec- tion G if and only if each hyperedge appears as an isolated clique.
Proof. A hyperedge must be clique in the graph projection, but not vice versa. A clique may not be a hyperedge in only two cases: 1) for a hyperedge e, there is a hyperedge e' set that e C e'; 2) for several hyperedges e.. ex. which's projections overlap together and form a bigger clique than each other. The first case would lead the solving of MCEC to ignore some hyperedges which are included by other hyperedges. The second case would lead the MCEC solving to produce the new hyperedges.
Although the MCEC has its limitations, it still can be a strong baseline in the hypergraph recon- struction task (Young et al.] 2020). Due to the "principle of parsimony", solving MCEC on the projection graph will ignore the frequency of node level pairwise appearance and always recover fewer hyperedges than the original hypergraph. To address these issues, inspired by MCEC, we make a step to raise novel Weighed Clique Edge Cover (WCEC) problem and an associated ef- ficient algorithm Greedy Weighted Cover (GWC) in hill-climbing manner. WCEC substantially differs from MCEC by taking into account an essential but less explored factor-frequency of node level pairwise appearance.
Weighted Clique Edge Cover Problem (WCEC). Though there exist several variants of clique covering problems, our problem of recovering clique covers from weighted graphs has been less studied. The most related problem in literature is Weighted Edge Clique Partition (WECP), which is

---

Published as a conference paper at ICLR 2025
proposed by Fellmann et al. (2020) and provide comprehensive analysis for the connec- tion and difference betwen WECP and WCEC in Appendix. A Here, we define the WCEC problem as follows:
Problem (Weighted Clique Edge Cover). Given a weighted graph 9 with weight matrix W, it asks to select k cliques from G, such that the distance d(W, W') 2 0 between W and W' is miminized, where weight matrix W' is derived from a new weighted graph G' by stacking k selected cliques.
In our setting, we let d(W, W be the LI Li-distance:
n Wis - W.y.
d(W, (W) =
j=1
where Way represents the entry of W at ith row and jth column. Comparing the proposed WCEC and MCEC, we have the following lemma:
Lemma 2. Suppose WCEC problem with weight matrix W is obtained by assigning positive weights to edges in adjacency A associated with an MCEC problem. Then solution clique cover to this WCEC such that d(W, W') = 0 must form a cover of the MCEC, but a clique cover of MCEC on A may not satisfy d(W, W*) = O.
Proof. We first prove the initial part. By definition, d(W, W") = implies that for every (i.j), the weight matrix G of the found cover satisfies W = W W..- Since W is derived by assigning positive weights to the non-zero entries in A, we have W > 0 = Aij = A.j = O. Therefore, the solution to the WCEC is a cover of the MCEC. For the second
and Wij
part. it suffices to provide easily verifiable example, which is presented constructive proof in Appendix. B
Lemma provides interpretation of why the proposed framework "weighted projection +WCEC" is more powerful than "projection + MCEC" utilized by Young et al.] (2020). In general, solving WCEC provides rich information for solving MCEC, but not vice versa. Nevertheless, solving either of them is NP-complete (Feldmann et al. 2020 Ullah 2022).
Greedy Weight Cover (GWC) Algorithm. Due NP-completeness, an exact solution to WCEC can be infeasible. Therefore, we develop specialized algorithm to obtain a local optima of WCEC via hill-climbing. Our algorithm works action with the largest gain. We term this procedure the Greedy Weighted Cover (GWC) algorithm. Concretely, GWC first enumerates or samples the cliques from the weighted graph projection, whose sizes are below the maximal hyperedge size of the original hypergraph, using the algorithm proposed by /Zhang al. (2005). Then we create a GainTable measuring how much one can improve by decoding the corresponding clique. In each subsequent step, GWC finds a clique with the largest gain and updates the GainTable in a dynamic programming fashion, until the number of found cliques reaches a preset threshold m or distance. To prevent redundant computation, we first build an EdgeTable mapping from an edge to its related cliques (see Alg. 2). which allows GWC only updates the gain of the local cliques in each step. The overall procedure is summarized in Alg. I
local search basis, wherein each iteration will take
EXPERIMENT
5.1 PROTOCALS
Implementation details. Throughout all the experiments, HyperPLR is running on an Apple MI CPU. The dimension of node embedding from Node2Vec is 50. The GCN consists of two layers, with input/output dimensions 50/128 and 128/128, respectively. We employ ADAM as the opti- mizer for all learning modules (i.e., Node2Vec, GCN, and CELL). For CELL, we set parameter edge overlap limit = 0.8 which controls the overlapping portion of the generated and the origi- nal graphs. For more details, one can refer to the supplementary material.
7

---

Published as a conference paper at ICLR 2025
Algorithm 1: Greedy Weight Coverage
Input: weighted adjacency matrix W, set of cliques C, clause number
Output: set of chosen cliques Cover function GWC(W,C, m)
Algorithm 2: Generate Edge Table
Cover + Ø
Input: set of cliques C edge table & a function GenerateeEdgeTTblee((
GT - table + GeneraleEdggTTableCC
[C1 .......... C. : 9n3// Gain
Output:
for k - to do
3
E (e
Ø3 // Edge
C' + (aines))) Cover CoverUC GT[C"] + - W Update(W. C*) for Edge E C" do
table forall e E, do if then Ele] Ele]uC
7 return 3
11
Cliques + Ele] for C E Cliques do
13
L GT(C] Update((W,
15
return Cover
Dataset.
Following the standard approach outlined in Nakajima et al. (2022); Lee et al.
(2021);
Kim et al. (2023), we evaluate performance on five datasets across three domains: contact (contact-high-school, contact-primary-scholl
email (email-Eu, email-Enron), and drug (NDC- classes) (Benson et 2018). In the contact datasets, each node represents an individual, and each hyperedge represents group communication event involving all participating individuals. In the email datasets, each node represents user, and each hyperedge corresponds an email, consisting of the sender and all recipients. In the drug dataset, each hyperedge corresponds to an NDC code for a drug, and the nodes represent the substances composing the drug. More details can be found in Appendix. C.
Baselines. We compared the performance of our proposed model against four existing hypergraph generation methods: HyperDK (Nakajima et al. (022). Hyperlap (Lee et al. [202]), Hyperlap+ (Lee) jet al. 202T), and THERA (Kim al. (023). HyperDK, Hyperlap, and Hyperlap+ are static gener- ators, primarily suited for producing static hypergraphs, while THERA generates dynamic graphs, such as temporal hypergraphs. Since HyperDK is highly sensitive to parameter settings, we evalu- ated it under two configurations: HyperDK,,0r which aims to generate hypergraphs that preserve the average node degree and the average hyperedge size, and HyperDK,,1 which seeks to preserve the degree of each individual node and the size of each hyperedge.
5.2 RESULTS
Graph statistics. The results of the comparisons between our model and state-of-the-art methods across five datasets, using various evaluation metrics, are presented in Table We further compare some of the advanced structural properties in Appendix. C22 Each dataset was generated five times, and the average results were reported. The graph properties evaluated include hypergraph structure- level metrics (density, average hyperedge size, average node degree), graph projection-level metrics ("G coefficient" and "G modularity"), and bipartite graph representation-levee metrics ("B modular- ity"). These properties provide comprehensive overview of the graph's structural characteristics. The detailed definitions about the metrics can be found in Appendix. C.3
Representation ability and reconstruction ability. We investigate how much the graph structure statistics can retain after feeding a hypergraph into different consecutive phases of HyperPLR from projection G learning G and reconstruction G Results are in Table We also visualize this process using the ema WLJGS well-preserved across all three phases.
instance in Fig. It is evident that the main structures of the
8

---

Published as a conference paper at ICLR 2025
(a) Gw of cmail-Enron
(b) Graph G in learning
(c) Graph G in reconstruction
Figure Visualization of weighted graph projection of hypergraph emai --Enron at different phases. Each node corresponds to one vertex and each edge (with thickness) indicates inter-node incidence (with frequency). (a) Weighted graph projection G., derived from original hypergraph; (b) Generated Weighted graph projection G based on (a) using hyperPLR; (c) Weighted graph projection G of generated hypergraph from (b) with GWC. Zoom in for a better view.
Table I: Results of hypergraph generation in terms graph metrics with 5 real-world hypergraphs
density
averuge size
average degree
G coefficient
modularity
modularity
contact-high-schen
23.908
2.327
55,633
0.504
0.582
0.754
HyperDKg..
272.161
3.089
840.796
0.999
0.000
0.324
HyperDK,,
142.573
2.178
310.567
0.861
0.016
0.459
Hyperlap
55.701
0.341
Hyperlup+
23.908
2.327
55.633
0.632
0,742
0.747
THERA
23,908
2.609
62.382
0.354
0.405
0.831
HyperPLR
24.055
2.703
65.011
0.471
0.556
0.649
contact-prinarr--choool
52.496
2.499
126.979
0.526
0.284
0.635
HyperDKa..
229.896
3.129
719.429
1,000
0.000
0.319
HyperDK,,1
143.343
2.285
327.516
0.924
0.010
0.437
Hyperlap
52.496
126.979
0.496
0.620
Hyperlap+
52.496
2,419
126.979
0.655
0.496
0.640
THERA
52.496
2.767
145.252
0.446
0.150
0.758
HyperPLR
52.714
2.648
139.593
0.491
0.281
0.600
Smail-Enron
10.373
3,009
31,888
0.593
0.352
0.656
HyperDKKg.
52.045
3.188
165.933
0.958
0.007
0.322
HyperDK,,1
39.596
2,885
114.252
0.796
0.040
0.355
Hyperlap
10.232
3.131
32,034
0.646
0.275
0.576
Hyperlap+
10.203
3,131
31,944
0.841
0.582
0.738
THERA
10.203
3.386
34.545
0.674
0.166
0.736
HyperPLR
10.723
3.244
34,782
0,593
0.351
0.569
email-Eu
25.077
3.426
85,909
0.492
0.371
0.675
HyperDKK.o
156.130
3.125
487.965
0.723
0.015
0.327
HlpeeDDK,,1
114.040
2.887
329.223
0.788
0.353
Hyperlap
25.778
3.621
93,338
0.623
0,280
0,571
Hyperlup+
25.860
3.621
93,633
0.785
0,745
0.751
THERA
24.868
4.696
116.792
0.837
0.099
0.793
HyperPLR
29.081
3.135
91.155
0,446
0.319
0.493
NDC-classee
0.937
5.922
5.350
0.611
0.610
0.741
HyperDKg.0
36.112
3.583
129.392
0.311
0.038
0.303
Iky,
111.711
Hyperlup
1.089
6.166
6.718
0.672
0.456
0.575
Hyperlap+
1.098
6.166
6.767
0.750
0.793
0.836
THERA
0.999
6.282
6.277
0.793
0.892
HyperPLR
1.210
5,501
6.655
0.791
0.623
0,733
5.3 ANALYSIS AND DISCUSSION
The experimental results demonstrate several key findings regarding the performance and capabili- ties of the proposed HyperPL. framework:
Graph Statisties Comparison. Towards geaph-level metrics, HyperPLR outperformed traditional hypergraph generation models, including HyperDK, Hyperlap, and ThERA, across various datasets. Remarkably, despite receiving any direct structural parameters from the original hypergraph,

---

Published as a conference paper at ICLR 2025
Table 2: Results of the graph metrics for the weighted graph projection G derived from origi- nal hypergraph; Generated Weighted graph projection Gw; and weighted graph projection G of generated hypergraph
Hypengraph coutact-iigl-schood
G. coefficient
G₁ modularity
G coefficient
G modularity
G coefficient
G modularity
0.504
0.582
0.388
0.546
0.472
0.556
confact- acimory
0.526
0.284
0.453
0.308
0.491
0.277
email-Earee
0.593
0.352
0.508
0.433
0.593
0.347
emaiil-Ea
0.492
0.371
NDC-classes
0.611
0.610
0.452
0.538
0.788
0.625
HyperPLR consistently demonstrates competitive similarity across nearly all graph metrics when compared to other parameter-bad based methods, underscoring its superior potential in hypergraph gen- eration. Additionally, the clustering coefficient distribution of the hypergraphs generated by Hy- perPLR exhibits the highest degree of similarity to real- world datasets. Furthermore, HyperPLR is parameter-insensitive. delivering stable and robust results with default parameter settings. For ex- ample, the default rank number of [end.bbeg et al. (020) is 9. To investigate how much this parameter impacts the generated results, we conduct extra experiments on varying rank = 8, 10, 12. We also present three generated weighted graph projections in Appendix. D Additionally, brief discussion on the trade-off between the fidelity and diversity of HyperPLR is provided in Ap- pendix. [ All these reuslt indicate that the HyperPLR framework, despite not requiring parameter tuning specific to each dataset, can generalize effectively across different domains. This robust- ness and parameter insensitivity highlight HyperPLR's advantage in practical applications, where real-world datasets can vary widely in structure.
Representation and Reconstruction Ability. Table 2 and Figure 3 provide insights into how HyperPLR maintains structural properties throughout the projection, learning. and reconstruction phases. The close similarity between the weighted graph projections derived from the original hyper- graph (G,,) and the generated hypergraph (G demonstrates that HyperPLR effectively preserves critical structural information. The consistency in clustering coefficients and modularity across the different phases (as seen in Table 2 suggests that the proposed weighted graph projection method captures essential high-order relationships This is further confirmed by the visualization in Fig- ure gl where the main structures are visibly well-retained, implying that the framework's 's learning and reconstruction processes are efficient in preserving hypergraph topology.
Limitations and Future Directions. Despite its strengths, HyperPLR has limitations. It requires significant computational resources, especially for larger datasets, and the GWC heuristic algorithm, while effective, doesn't 't guarantee optimality. Future research could explore advanced optimization techniques like reinforcement learning or MCTS for improving clique selection. Additionally, the complexity of HyperPLR constrained by the exponential nature of the maximal clique enumer- ation problem, though it remains manageable for real-world hypergraphs. Future work could also focus on accelerating clique enumeration using hyperedges as prior information.
6 CONCLUSION
Deep hypergraph generation models have demonstrated their ability to capture the complex distribu- tion of hypergraphs by leveraging the rich information embedded within them generate more real- istic structures. In this paper, we address novel clique cover problem-WCEC: WWCC--CCCOFF reconstructing hypergraphs from weighted graph projections, and we propose an efficient and effective framework, HyperPLR, for generating real-world hypergraphs. The weighted graph projection shows strong representational power compared to existing inexact graph representations, while also significantly enhancing learning and generation against the exact representation. This is the first work to achieve both. Our method demonstrated superior efficiency and stability compared to previous of the-art methods across various graph-based metries. In the future, aim to extend HyperPLR's capabilities to additional generation tasks, such as bipartite network generation or SAT instance generation, in order to capture the rich information inherent in these structures.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by the National Science and Technology Major Project of China under Grant 2022ZD01 16408. This work is also supported by the Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (2023B (02331212010001) We would like to thank all the anonymous reviewers for their insightful comments. We also sincerely thank Chaolong Ying and Huizhi Zhu for their valuable discussions, which greatly contributed to the development of this work.
REFERENCES
Austin Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon M. Kleinberg. Sim- plicial closure and higher-order link prediction. Proc. Natl. Acad. Sci. USA, 115(48):E11221- E11230, 2018. doi: 000.00///NASS.8000333333
URL
pnas 1800683115
Aleksandar Bojchevski, Oleksandr Shehur, Daniel Zügner, and Stephan Günnemann. Netgan: Gen- erating graphs via random walks. In ICML, 2018.
Guy Bresler, Chenghao Guo, and Yury Polyanskiy. Thresholds for reconstruction of random hy- pergraphs from graph projections. In Shipra Agrawal and Aaron Roth (eds.), The Thirty Sev- enth Annual Conference on Learning Theory, June 30 July 3, 2023, Edmonton, Canada, vol- ume 247 of Proceedings of Machine Learning Research, pp. 632-647. PMLR, 2024. URL
ml wttppp//ww////ssssssssso
html
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative model- ing for sparse graphs. In ICML, 2020.
Manh Tuan Do. Se-eun Yoon, Bryan Hooi, and Kijung Shin. Structural patterns and generative hypergraphs. In Rajesh Gupta, Yan Liu, Jiliang Tang, and Aditya Prakash (eds.), KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pp. 176-186. ACM, 2020, doi: 10. 14/1344/3. 3403060. URL https: doi org. 11000.1145/3350 000154448633433666 3403060
models of
Andreas Emil Feldmann, Davis Issac, and Ashutosh Rai. Fixed-paramett tractability of the weighted edge clique partition problem. In 15th International Symposium on Parameterized and Exact Computation, 2020.
Song Feng, Emily Heath, Brett A. Jefferson, Cliff A. Joslyn, Henry Kvinge, Hugh D. Mitchell, Brenda Praggastis, Amie J. Fisfeld, Amy C. Sims, Larissa B. Thackray, Shufang Fan, Kevin B. Walters, Peter J. Halfmann, Danielle Westhoff-Smith Qing Tan, Vineet D. Menachery, Timo- thy P. Sheahan, Adam S. Cockrell, Jacob F, Kocher, Kelly G. Stratton, Natalie C. Heller, Lisa M. Bramer, Michael S. Diamond, Ralph S. Barie, Katrina M. Waters, Yoshihiro Kawaoka, Ja- son E. McDermott, and Emilie Purvine. Hypergraph models of biological networks to identify genes critical pathogenic viral response. BMC Bioinform. 22(1):287, 2021. doi: 10.1186 $12859-021-04199722 URL https:://of 10010/000000111111//123000001010 021-9997-22---99-2
Dorian Gailhard, Enzo Tartaglione, Lirida Naviner, and Jhony H Giraldo. Hygene: A diffusion- based hypergraph generation method. arXiv preprint arXiv:2408. 16457, 2024.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Balaji Krish- napuram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pp. 855-864 864, ACM, 2016. doi: 00.1145/293967222993777 URL https: /tw.i/oiiiii// org/ 10. 01..:..1997...111129993932222 2939754
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In ICML, 2019.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In ICMI, 2018.

---

Published as a conference paper at ICLR 2025
Hiroshi Kajino. Molecular hypergraph grammar with its application to molecular optimization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp- 3183-3191. PMLR, 2019. URI. http://prooceeding ngs m1 prwss wv/
no 1 9a httl
Sunwoo Kim, Fanchen Bu, Minyoung Choe, Jaemin Yoo, and Kijung Shin. How transitive are real- world group interactions? measurement and reproduction. In Ambuj K. Singh, Yizhou Sun, Leman Akoglu, Dimitrios Gunopulos, Xifeng Yan, Ravi Kumar, Fatma Ozcan, and Jieping Ye (eds.), Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pp. 1132-1143, ACM, 2023. doi: URL https:: www.oo.//....... 1100..1455550 1 01111111////355111 3580305 3501//3333333333333333
00.1145/35803053359333
Thomas N Kipf and Max Welling. 161 2016.
Variational
graph auto-encoders.
arXiv preprint
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Furkan Kocayusufoglu, Arlei Silva, and Ambuj K Singh. Flowgen: A generative model for flow graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
Yunbum Kook, Jihoon Ko, and Kijung Shin. Evolution of real-world hypergraphs: Patterns and models without oracles. In Claudia Plant, Haixun Wang, Alfredo Cuzzocrea, Carlo Zaniolo, and Xindong Wu (eds.), 20th IFFE International Conference on Data Mining, ICDM 2020, Sorrento, Italy, November 17-20, 2020, pp. 272-281. JEFE, 2020. doi: 10. 101100//0000000 /DCCCC/DMM000802200000000..0 URL https: org. 10. 11 11011111I00 www.111III/IIII...... 2020 00036
Geon Lee, Minyoung Choe, and Kijung Shin. How hyperedges overlap in real-world hyper- graphs? patterns, measures, and generators. In Jure Leskovec, Marko Grobelnik, Mare Najork, Jie Tang, and Leila Zia (eds.), WWW '21: The Weh Conference 2021, Virtual Event / Ljubl- jana, Slovenia, April 19-23, 2021, pp. 3396 3406. ACM / IW3C2, 2021. doi: 10.1145/3442381. 3450010. URL hwtp::ttts///m /ww. org/ 100
Zhishang Luo, Truong Son Hy, Puoya Tabaghi, Michaël Defferrard, Elahe Rezaei. Ryan Carey, W. Rhett Davis, Rajeev Jain, and Yusu Wang- DE-HNN: an effective neural model for circuit netlist representation. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen (eds.), International Conference Artificial Intelligence and Statistics, 2-4 May 2024, Palau de Congressos, Valencia, Spain, volume 238 of Proceedings of Machine Learning Research, pp. 4258-4266 PMLR, 2024. URL htttss://pooceeennngg... .mw.ingss.mrrrmmmm........r..mmm mlr wrw.sressppeeepp. wwwp://v3////// wwt.:/a......p.....ee...emmeee
html
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. ICML, 2022.
Kazuki Nakajima, Kazuyuki Shudo, and Naoki Masuda. Randomizing hypergraphs preserving de- gree correlation and local clustering. IEEE Trans. Netw Sci. Eng., 9(3): 139-11553 2022, doi: 1109/TNSFF.22113333338 URL. htt.hhttts:/ott org/10. 1109 2021 .1133333800
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Per- mutation invariant graph generation via score-based generative modeling. In International Con- ference on Artificial Intelligence and Statistics, 2020.
Luca Rendsburg, Holger Heidrich, and Ulrike Von Luxburg. Netgan without gan: From random walks to low-rank approximations. In ICML, 2020.
Marcos Okamura Rodrigues. Fast constructive and improvement heuristics for edge clique covering. Discret. Optim., 39: 100628, 2021. doi: 10. 10.1111/...... 2TW..IDIOOTT..22110000222 URL ://otp.:: org/10. 101
2021 100628
12

---

Published as a conference paper at ICLR 2025
Hannah Sansford, Alexander Modell, Nick Whiteley, and Patrick Rubin-Delancie Implications of sparsity and high triangle density for graph representation learning. In Francisco J. R. de Meent (eds.), International Conference Arti- ficial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain, vol- 206 of Proceedings of Machine Learning Research, pp. 5449-544444 5473. PMLR, 2023. URL v206/
Ruiz, Jennifer G. Dy, and Jan-Willem
ht pttt:::/pprceedinng
mlr www..press.ee. http:////ooo///aafooaaaaaa sansford23a.......ooooooom.....m html
Anton Tsitsulin. Davide Mottin, Panagiotis Karras, Alexander M. Bronstein, and Emmanuel Müller. Netlsd: Hearing the shape of a graph. Yike Guo and Faisal Farooq (eds.), Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 2347-2356. ACM, 2018. doi: 10.1145/3219819.
3219991. URL https://doi. org/ 10. 1ww.11111111111 321
Ahammed Ullah. Computing clique ar0iv:2208. /2438, 2022.
with structural parameterization. arXiv preprini
Fedor Velikonivtsev, Mikhail Mironov, and Liudmila Prokhorenkova. Challenges of gen- erating structurally diverse graphs. In Amir Globersons, Lester Mackey, Danielle Bel- grave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.), Advances in Neural Information Processing Systems 38: Annual Conference on Neural Informa- tion Processing Systems 2024, NeurlPS 2024, Voncouver, BC, Canada, December 10 15, 2024, 2024. URL http::/papers nips. www.:iippppp...e..eeeeepppppp wttppaapeppepeeeeeepeaaaaaeaeeee wwtps//appeeee//////aeaeeaea Abstract at Conference. html]
Hongwei Wang, Jialin Wang. Jia Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Wenjie Li, Xing Xie, and Minyi Guo. Learning graph representation with generative adversarial nets. IEEE Transactions on Knowledge and Data Engineering, 3300)3300,,3 2019.
Yanbang Wang and Jon M. Kleinberg. From graphs hypergraphs: Hypergraph projection and its reconstruction. In The Twelfth International Conference on Learning Representa- tions, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https: /oopeneevee..nee
Jean-Gabriel Young, Giovanni Petri, and Tiago P. Peixoto. Hyperggaah from network data. CoRR, (bs/2008.04948, 2020. URL /ttt::://arxlv..org/bb/////
Yun Zhang, Faisal N Abu-Khzam, Nicole E Baldwin, Elissa J Chesler, Michael A Langston, and Na- giza F Samatova. Genome-scale computational approaches to memory-intensive applications in systems biology. In SC'05: Proceedings of the 2005 ACM/IEEE Conference on Supercomputing, pp. 12-12. IEEE, 2005.
Xianglin Zuo, Wenqi Chen, Song Xianduo, Xin Wang, and Ying Wang. Generating real-world hypergraphs via deep generative models. Inf. Sci., 647:119412, 2023, doi: 10.1016/J.NS.20233 119412. URL Matthttps.. /ooi org. 1016/ ins w023. 119412
13

---

Published as a conference paper at ICLR 2025
A WECP PROBLEM
Problem 2 (Weighted Edge Clique Partition). Given a graph G with weight function we EEG) zt and a positive integer k, it asks to select at most k cliques such that each edge appears in exactly as many cliques as its weight (if it exists, otherwise output NO).
Note that although the WECP may appear similar to the WCEC problem, they have essential dif- ferences. In WECP, the objective is partition the edges such that each edge is covered exactly as many times as indicated by its given weight. This means that if an edge has a weight greater than one, must be covered by multiple cliques, and no edge can be covered more fewer times than specified. This strict covering constraint makes the problem more restrictive. The solution either finds such a partition or determines that impossible, framing WECP as Constraint Satisfaction Problem (CSP).
In contrast, the WCEC problem aims to minimize the distance between the original weight matrix W of the graph and derived weight matrix W which is formed by stacking the selected cliques, In this sense, approximates or covers the edge weights using cliques. Unlike WECP, there is no strict requirement for how many times each edge must be covered; instead, the focus is minimizing the difference between the original and derived weight distributions. Therefore, WCEC essentially a combinatorial optimization problem.
B ADDITIONAL PROOF FOR THE SECOND PART OF LEMMA 2
Proof. Consider simple hypergraph H (V,8) where V {ur, U2 V3, U4 and &
{(V1, U2, va); (12, 24), (01, og)}. The graph projection G of 7 will be complete graph. If G is used as the input for the minimum clique edge cover problem, the optimal solution will be clique e (v1, 12, U3, v4). In the WCEC setting, let W be the weighted matrix of the weighted graph projection of hypergraph H. and let W" be the weighted matrix derived from the solution of the MCEC. Then we have:
0
1
17
0
1
17
1
0
1
2
1
0
1
W
W =
1
1
1
0
1
2
1
0
1
1
1
0
It is evident that d(W, W WCEC problem.
Wi
W
2, which is not the optimal solution for
C EXPERIMENTAL DETAILS
The code of our experiments is publicly available att::ps///gtthb..cm//000000////0 HyperPLR]
C.1 DATASETS
Our experimental evaluation utilizes five real-world datasets from Benson et al. (2018):
contact-high-schoot. This dataset is constructed from interactions recorded by wearable sensors at high school, consisting of 327 nodes, 172,035 timestamped hyperedges, and 7,818 unique hyperedges. The projected graph contains 5,818 edges and 6,151 maximum cliques.
contact-primary-schott This dataset is constructed from interactions recorded by wear- able sensors at primary school, consisting of 242 nodes, 106,879 timestamped hyper- edges, and 12,704 unique hyperedges. The projected graph contains 8,317 edges and 100,153 maximum cliques.
email-Enron: In this dataset, nodes represent email addresses at Enron, and each hyper- edge comprises the sender and all recipients of email. The dataset contains 143 nodes,
14

---

Published as a conference paper at ICLR 2025
Table 3: Comparative result of advanced properties of the ground-truth hypergraphs and generation
hypergraphs.
Diameter
contact-highh-schoo
contact-primary-sehhe
email-Earon
email-Eu
NDC-classes
HyperDKa.0
(1.300
0.333
0.500
0.667
0.778
HyperDK,,
0.250
0.333
0,250
0,333
0,533
Hyperlap
0.200
0.067
0,250
0.422
Hyperiapt
0.250
0.333
0.050
0.133
0.289
TheRA
0.250
0.000
0,250
0.667
0,222
HyperPI.R
0.250
0.000
0,000
0.033
0,010)
Triangles Num
KKop
167.117
21.456
41,427
156.738
184.785
HyperDK,,1
84,440
15.988
10.867
41.227
79.077
Hyperiap
0.599
0.409
3.315
8,998
3,536
Hyperlap+
0.942
0.284
1.517
2,981
2.124
TheRA
0.468
0.198
2.451
3,725
1,638
HyperPI.R
0.055
Degree Distribution
HyperDKa..
23.026
23.026
23.026
23.026
23.026
HyperDKK11
12.406
3,960
Hyperlap
5.958
8.072
9.294
6,946
4,415
Hyperlapt
5.336
8.812
9.023
6.448
4,474
TheRA
6.634
10.530
7.986
15.315
14.325
HyperPI.R
5.065
7.657
4.639
7,424
4,020
Singular Value Distribution
HyperDKa.o
6.212
5,730
4,653
6.422
6.750
HyperDKK1
5.462
5.147
4,513
6.345
7.008
Hyperlap
4,470
6.589
Hyperlapt
5.372
5.056
4,520
6,319
6.560
TheRA
5.377
4,465
6.620
HyperPLR
5,347
5.032
4.451
6,278
6.432
10,883 timestamped hyperedges, and 1,512 unique hyperedges. The projected graph con- tains 1,800 edges and 10,883 maximum cliques.
This dataset includes email addresses at a European research institution, with hyperedges representing the sender and all recipients of email with the same timestamp. The dataset consists of 998 nodes, 234,76, 760 timestamped hyperedges, and 25,027 unique hyperedges. The projected graph contains 29,299 edges and 237,23 231 maximum cliques.
email-Eu:
In this dataset, each hyperedge corresponds to drug, and the nodes are the class labels assigned to the drugs. The dataset consists 1,161 nodes, 49,724 timestamped hyperedges, and 1,088 unique hyperedges. The projected graph contains 6,222 edges and 624 maximum cliques.
NDC-classes:
C.2 ADVANCED PROPERTIES
Inspired by the reviewer, we expand the evaluation metrics to some advanced properties like SHyRe in Wang & Kleinberg (2024). The result is presented in Table 3 Notably, the simplicial closure metric from SHyRe evaluates the temporal evolution process of dynamic hypergraphs, is not ap- plicable to our work or the baseline static generation models. Therefore,
similar concept, triangle numbers, which is widely used graph structural metric (Sansford et al. (023)) For density, we have already presented the results in Table so is not repeated here. Similar to the approach in SHyRe, we standardized the metrics for triangle numbers and diameter using the formula: [x] -wal where I1 and 22 represent the values the ground truth and the generated graphs, respectively. For degree distribution and singular value distribution, value indicates hetter alignment for all the metrics. From the results, we observe that HyperPL. outperforms is competitive with other models across most datasets and metrics.
compared their cross-entropy. A smaller
C.3 EVALUATION METRICS
We evaluate the training and generated hypergraphs using the following six metrics:
15

---

Published as a conference paper at ICLR 2025
Density:
While multiple definitions of hypergraph density exist in different contexts, adopt a most straightforward definition as the ratio the number hyperedges to the number of nodes, given by Density [VI
Average Hyperedge Size: The average hyperedge
size is
calculated as:
Average Hyperedge Size =
1 [8]
EeEs lel.
Average Node Degree: The average node degree represents the average number of hyper- edges in which each node participates, given by: Average Node Degree
M Evey d(v).
Clustering Coefficient of Graph Projection: The clustering coefficient is computed for the 2-section (or graph projection) of the hypergraph, where each hyperedge induces clique among its nodes. This coefficient measures the likelihood that two neighbors of node are also neighbors. It is calculated as: C' = aV Evev C(v), where C(v) is the local
clustering coefficient of node in the projected graph.
Modularity of Graph Projection: The modularity of the graph projection measures the quality of partition of the graph into communities, with higher values indicating stronger
- Ei, Aiy represents the adjacency matrix, k and k- are the node degrees, m is the total number of edges, and 8(c;, 0ÿ) equals if nodes and j belong to the same community, and otherwise
community structure. is given by:
2m 8(c,, Cÿ), where Ai k.
Modularity of Bipartite Graph Representation: The modularity of the bipartite graph representation measures the quality of partition the bipartite graph, considering nodes representing original vertices and hyperedges. The formula for modularity is similar to that used for the projected graph.
D IMPACT OF RANK VALUE CELL
(c) rank 12 Figure 4: Visualization of generated weighted graph projection of Hypergraph email 1iiii--B -Enoon with different rank values. Zoom in for better view.
(a) rank 8
(b) rank 10
From fig. we can conclude that, terms graph structure, there is almost no influence from rank value. However, rank greatly impacts the generation speed in the CELL module. High rank can accelerate the generation greatly but lose some diversity in the generated hypergraph, which also discussed in Rendsburg et al. (2020).
E DIVERSITY OF THE GENERATION
To the best of our knowledge, this is essential yet unresolved problem in the graph (and hyper- graph) generation task. Below, we make the best effort to provide a fair comparison and discussion of the diversity of hypergraphs generated by our model and HyperLap. Despite the lack of discus- sion on diversity in hypergraph generation directly, Velikonivtsev et al. (2024) proposed a theoret- ical framework for evaluating graph diversity. In summary, the paper defines the diversity of set of graphs S as Diversity S) F(D(G, G') G, G" e S), where D G') a distance measure between graphs, and F is function that computes the overall diversity from the of pairwise
16

---

Published as a conference paper at ICLR 2025
distances. Building this theory, conducted the following experiments. First, converted the hypergraphs generated by HyperLap. HyperLapt, and HyperPLR into bipartite graph representa- tions for each datase L the other set corresponds to the vertices connected by these hyperedges. This conversion lossless with respect to the original hypergraph structure.
In this representation, set of vertices corresponds to the hyperedges, and
Given the large size of the graphs, classical graph distance measures like graph edit distance are NP-hard and computationally prohibitive. Instead, followed the suggestions of Tsitsulin et al. 2018) and utilized two spectral- -baedd distance measures introduced in NetLSD-heat and NetLSD- the
wave. For the function F, we adopted the sum of pairwise distances between elements, most natural and widely used approach. The Table presents the results of our experiments. From the results, we can see that most cases, HyperPI.R achieves graph diversity that either surpasses or is competitive to that of random generators like HyperL.AP and Hyperl.ap+: At the same time, we believe that the concept of diversity in the hypergraph generation task requires a more targeted definition and evaluation method.
Table 4: NeILSDD-Hee&&&NNeLLSD-Wwww results across various datasets.
NetLSD-Heat
contact-high-school contact-primry--shhdd email-Enron
email-Ea
NDC-classes
HyperL.ap
0.006
0.002
0.011
0.015
0.094
HyperLaap
0.007
0.056
0.009
0.007
0.087
HyperPLR
0.008
0.006
0.017
0.022
0.354
NetLSD-Wave
HyperLap
0.070
0.033
0.158
0.262
1.216
HyperLap+
0.086
0.975
0.097
0.127
0.562
HyperPLR
0.113
0.107
0.183
0.251
1.479
For THERA, we encountered limitations as the provided code was not executable, and the authors only supplied single generated sample per dataset. While were able compute graph metrics for this single sample, evaluating its diversity was not possible due the absence of multiple samples.
17


Reviews:
[{"review_id": "BS4fRiVL0m", "reviewer": "Reviewer_ZxbQ", "summary": "Hypergraphs are essential in modeling high-order relationships. Hypergraph generative models are crucial for promoting and validating the understanding of these structures. In this paper, the authors introduce a novel hypergraph generative approach, HyperPLR, encompassing three phases: Projection, Learning, and Reconstruction. They have evaluated HyperPLR on existing real-world hypergraph datasets, demonstrating superior performance and validating the effectiveness of HyperPLR.", "questions": "1. Refer to the weaknesses above.\n2. Can we replace CELL with any recent graph generator models, like those introduced in [1]?\n\n- [1] Liu et al. “Generative Diffusion Models on Graphs: Methods and Applications.” IJCAI 2023", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. Hypergraph generation is important for understanding the nature of high-order relationships.\n2. The proposed method is based on a simple, intuitive idea, yet shows good empirical performance on various datasets.\n3. Compared to deep learning frameworks, the proposed method is easier to interpret and trust.", "weaknesses": "1. Technical novelty is limited. (a) The idea to create a hypergraph structure from an ordinary (clique-expanded) graph has been studied already in (Bresler et al., 2024). (b) Training a GNN-based weight predictor for weighted graph structures seems new, but the technical contribution is limited, as the authors use typical GCN with node2vec-based features. (c) The proposed algorithm for weight cover is also a simple greedy algorithm which has no theoretical guarantee on its performance.\n2. Writing quality should be improved in general. (a) Section 4 includes things that are part of HyperPLR, e.g., lines 189 - 192, 233 - 243, etc. It would be easier to read the paper if the authors separate them from the “proposed” ones. (b) Some knowledge about MCEC should be given so that readers can understand the propositions in a better context.\n3. Theoretical claims do not support the proposed method well. Lemma 2 is straightforward, and it does not always support that WCEC is better than MCEC, considering that acquiring good edge weights is difficult. Even with the GNN predictor, we cannot guarantee the quality of this solution.", "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": "Wb2yX7VUH4", "reviewer": "Reviewer_C2HN", "summary": "This paper introduces HyperPLR, a hypergraph generative model employing a three-stage pipeline: projection, learning, and reconstruction. HyperPLR first projects the input hypergraph to a weighted projected graph and then utilizes this structure to learn graph structures, including both adjacency and edge weights. Then it reconstructs new hypergraphs by addressing a clique cover problem on the generated weighted projected graph. The authors evaluated HyperPLR by comparing it against SOTA hypergraph generative methods.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- HyperPLR introduces a new approach to hypergraph generation, based on three-stage framework. \n- The authors thoroughly discuss the limitations of the method. \n- Code and datasets are available.", "weaknesses": "**Clarity and presentation issues**\n- Important definitions, such as \"node degree in a weighted graph,\" are missing. This makes terms like \"the degree of each node corresponds to its total frequency of appearance in hyperedges\" unclear. \n- Inconsistent notations (e.g., Graph A in Figure 2 and Graph G in the text) are used.\n- \"G coefficient/modularity\" and \"B modularity\" in Table 1 lack proper definitions.\n- It is unclear in line 202, why weighted projection offers a more \"compact representation\" compared to the bipartite graph representation of hypergraphs.\n- \"Strong global structures\" in line 214 require better contextual discussions. \n- A typo in line 138: $(v_i, v_j)\\in e_i$.\n\n**Method descriptions**\n- While the authors suggest the \"novelty\" of the weighted projection of hypergraphs, this approach is well-studied and employed in prior hypergraph studies, even in early work like \"Learning with Hypergraphs: Clustering, Classification, and Embedding\" (2006).\n- More details are needed about the edge weight prediction GCN module. For example, how is the loss function designed? - Does it require any negative samples? How is the bias in the edge weight distribution addressed?\n- What are the bottlenecks in HyperPLR? What is its space/time complexity?\n\n**Evaluation**\n- The model's performance is not impressive enough; for example, it is outperformed by HyperLap in many cases. While the authors argue HyperPLR does not require structural parameters directly from the input, non-trivial features such as number of nodes, edge weights, and maximum hyperedges are given.\n- More advanced evaluation metrics, such as those used in baseline papers, could have been considered.\n- Table 2 lacks a comparative baseline.\n- The effectiveness of key components in HyperPLR remains unclear. For example, how does HyperPLR perform when excluding CELL (i.e., using the input graph G directly)? Is the proposed GWC module effective?\n\n\n**In summary**, the paper has room for improving the clarity of definitions and consistency of notation, highlighting the novelty, providing a more thorough description of the method, and strengthening the experiments with more comprehensive evaluation metrics and ablation studies.", "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": "Nx4kImBNuf", "reviewer": "Reviewer_WfsL", "summary": "***Overview.*** The authors study the hypergraph generation task. \n\n***Method.*** Specifically, they propose a learning-based hypergraph generative method, named HyperPLR.\nHyperPLR learns the (potential) weight of each edge with GNN from the unweighted graph.\nTherefore, (1) it generates an unweighted graph with CELL, and (2) it assigns edge weights by using the trained GNN.\nLastly, the weighted graph is transformed into a hypergraph.\n\n***Experiment.*** The authors demonstrated the effectiveness of HyperPLR in several benchmark hypergraph datasets, compared to hypergraph generative baseline methods.", "questions": "See the mentioned weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "***S1.*** This is the first learning-based hypergraph generative method. \n\n***S2.*** Overall method design is reasonable.\n\n***S3.*** Various baseline methods are considered.", "weaknesses": "***W1 (Performance).*** Despite the large training cost, performance gain compared to the rule-based methods seems a bit marginal. Specifically, HyperLAP and THERA often outperform the proposed method.\n\n***W2 (Scalability).*** The authors acknowledge that the proposed method lacks scalability, which is a significant limitation given that many real-world hypergraphs are typically large. Despite its slower training and generation, is the proposed method ***capable of*** generating larger hypergraphs (e.g., those with more than 10,000 nodes)? \n\n***W3 (Independent edge generation).*** Many real-world hypergraphs include timestamps, as interactions occur over time. Furthermore, interactions may influence one another, suggesting that hyperedges may not be independent. However, to my understanding, the proposed method generates pairwise edges without accounting for temporal aspects and dependencies.\n\nPlease clarify if my understanding or claims are wrong.", "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)