HyperPLR: Hypergraph Generation through Projection, Learning, and Reconstruction

Thanks for your insightful comments and for acknowledging novelty and model design. Below, we respond to your specific comments.

W1:
We thank the reviewer for their observation. Below, we address the concerns regarding training cost and performance comparison with rule-based methods：

1. The training cost for HyperPLR is not as large as implied. Taking the email-Eu dataset (998 nodes and 234,760 hyperedges) as an example: Node embedding learning takes only 4.5 seconds. CELL and GNN training together take 20 seconds, which is a one-time cost. Once trained, these components can be reused for similar datasets or applications.
2. There is a trade-off between graph statistics similarity and generation diversity: while methods like HyperLAP and THERA often optimize for closer graph statistics to the original hypergraph, our approach explicitly controls training iterations to ensure diversity in the generated hypergraphs. This is intentional, as the exact reproduction of graph statistics may lead to overfitting and reduced generalizability in practical scenarios. HyperPLR aims to strike a balance between structural fidelity and diversity in generated hypergraphs, which is critical for applications requiring realistic variations of the original data.

W2:
We thank the reviewer for raising concerns regarding scalability and the capability of HyperPLR to generate larger hypergraphs. Below, we clarify the limitations and capabilities of our method:

1. The training and generation phases of HyperPLR are efficient compared to many learning-based graph generation methods. For instance: Node embedding learning, CELL training, and the GNN weight predictor collectively incur a manageable one-time cost, as demonstrated on the email-Eu dataset (998 nodes and 234,760 hyperedges) with a total training time of ~25 seconds.
2. The scalability bottleneck is mainly in clique finding, which occurs before the reconstruction phase. This step is sensitive to the density of the projection graph, rather than the number of nodes or hyperedges directly. For sparse projection graphs, clique enumeration remains computationally manageable, even for hypergraphs with over 10,000 nodes. For dense projection graphs, the computational cost increases significantly, similar to other graph reconstruction methods that involve clique-based or edge-cover algorithms, such as SHyRe [1].

W3:
We appreciate the reviewer’s observation about the consideration for temporal aspects and dependencies. Here, we clarify the scope and focus of our proposed method. Hypergraph generators can be broadly categorized into static and dynamic models. HyperPLR is a static generator, designed to model the global structural properties of a hypergraph without explicitly incorporating temporal dynamics or interdependencies between hyperedges. This focus ensures broad applicability to static datasets and scenarios where temporal information is unavailable or secondary. While real-world hypergraphs often include temporal interactions, accounting for these dynamics requires a fundamentally different framework (e.g., incorporating temporal evolution models or causal dependencies). This is beyond the scope of HyperPLR, which aims to provide a static yet robust and general-purpose framework for hypergraph generation.

[1] From Graphs to Hypergraphs: Hypergraph Projection and its Reconstruction. ICLR 2024

We thank the reviewer for highlighting the importance of balancing fidelity and diversity in generative models. To the best of our knowledge, this is still an essential yet unresolved problem in the graph (and hypergraph) 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 (see note for THERA).

Previously, we empirically controlled the edge overlapping parameter in the CELL model [1] of HyperPLR to be less than or equal to 0.8 (and ≤ 0.6 for large graphs like Email-Eu). This limitation ensured that the topology generated in the HyperPLR did not become overly similar to the original hypergraph's projection, thereby maintaining the diversity of the generated samples.

During this period, we conducted some literature reviews related to the graph generation task. Despite the lack of discussion on diversity in hypergraph generation directly, we discovered a paper at this year’s NeurIPS [2] that proposed a theoretical framework for evaluating graph diversity. In summary, the paper defines the diversity of a set of graphs $S$ as $\text{Diversity}(S) = F(\{D(G, G^\prime): G, G^\prime \in S\})$, where $D(G, G^\prime)$ is a distance measure between two graphs, and $F$ is a function that computes the overall diversity from the set of pairwise distances.

Building on this theory, we conducted the following experiments, we have updated the evaluation code, and data results in the anonymous repository. First, we converted the hypergraphs generated by HyperLap, HyperLap+, and HyperPLR into bipartite graph representations for each dataset. In this representation, one set of vertices corresponds to the hyperedges, and the other set corresponds to the vertices connected by these hyperedges. This conversion is lossless with respect to the original hypergraph structure.

Given the large size of the graphs, classical graph distance measures like graph edit distance are NP-hard and computationally prohibitive. Instead, we followed the suggestions of paper [2] and utilized two spectral-based distance measures introduced in paper [3]: NetLSD-heat and NetLSD-wave. For the function $F$, we adopted the sum of pairwise distances between elements, as it is the most natural and widely used approach. The tables below present the results of our experiments:

From the results, we can see that in most cases, HyperPLR achieves graph diversity that either surpasses or is competitive to that of random generators like HyperLAP and HyperLap+. We hope this can demonstrate the diversity achieved by HyperPLR during generation.

At the same time, we believe that the concept of diversity in the hypergraph generation task requires a more targeted definition and evaluation method. We plan to conduct further research on this in future work and warmly welcome any further discussions with you on this topic.

[1] NetGAN without GAN: From Random Walks to Low-Rank Approximations. ICML 2020.
[2] Challenges of Generating Structurally Diverse Graphs. NeurIPS 2024.
[3] NetLSD: hearing the shape of a graph. KDD 2018.

Note: For THERA, we encountered limitations as the provided code was not executable, and the authors only supplied a single generated sample per dataset. While we were able to compute graph metrics for this single sample, evaluating its diversity was not possible due to the absence of multiple samples.

Thank you for taking the time to review our work and for providing thoughtful feedback. We greatly appreciate your recognition of our efforts and are encouraged by your positive response. Your constructive comments have been invaluable in helping us refine the paper, and we remain dedicated to further enhancing its quality.

Thanks for your insightful comments. Below we respond to the specific comments:

W1
We thank the reviewer for highlighting these concerns and provide the following clarifications and resolutions. Below, we provide detailed responses and outline how these issues will be addressed:

• Definitions: We will include precise definitions in the Preliminaries section. For example, “Node degree in a weighted graph is the sum of the weights of all edges connected to the node.” Additionally, terms like “frequency of appearance in hyperedges” will be clarified to ensure clear links between hypergraphs and weighted graph projections.
• Notation Consistency: We will standardize all notations, ensuring consistency between figures and the text.
• Metrics in Table 1: Definitions for “G coefficient/modularity” and “B modularity” will be added under the evaluation metrics, explaining that they refer to clustering coefficients/modularity in graph and bipartite representations, respectively.
• Compact Representation: The statement in line 202 will be expanded to explain that weighted projections condense hyperedge information into edges, reducing graph size compared to bipartite representations, which require separate hyperedge nodes. An example or diagram will also be added.
• Strong Global Structures: We will refine “strong global structures” in line 214 to refer to long-range dependencies like overlapping cliques or communities in large hypergraphs, adding an example for clarity.
• Typo in Line 138: The typo $(v_i, v_j) \in e_i$ will be corrected. We hope these revisions will enhance the clarity and presentation of the paper and address the reviewer’s concerns effectively.

W2

1. We thank the reviewer for pointing out that weighted projections of hypergraphs have been explored in prior work. We would like to clarify that we do not claim the novelty of using weighted graph projections as a standalone contribution. Instead, the novelty of our work lies in the proposed HyperPLR framework and the Weighted Clique Edge Cover (WCEC) formulation, which leverage weighted projections to address critical gaps in hypergraph generation and reconstruction. While weighted projections are indeed well-established, the HyperPLR framework integrates this step with a learning phase that employs GNN-based edge weight prediction to refine the weighted graph. What's more, the HyperPLR framework integrates a reconstruction phase that introduces the WCEC problem and the Greedy Weighted Cover (GWC) algorithm for reconstructing hypergraphs. This combination enables the effective preservation of higher-order relationships and overlapping hyperedges, which is beyond the focus of prior works.
2. We appreciate the reviewer’s interest in the details of our edge weight prediction GCN module. Below, we provide clarification:
   The edge weight prediction is formulated as a regression task, where the GCN predicts edge weights based on node embeddings and the graph structure. The loss function is designed as the Mean Squared Error (MSE) between the predicted edge weights and the ground truth weights from the original weighted projection graph. Specifically, the loss function is given as: $\text{Loss} = \sum_{(i,j) \in E} \big( w^\prime_{i,j} - w_{i,j} \big)^2$ where $w^\prime_{i,j}$ is the predicted weight for edge $(i, j)$, and $w_{i,j}$ is the ground truth weight. Since this is a regression task and not a classification problem, the GCN does not require negative samples (i.e., edges that do not exist). Instead, the focus is on minimizing the error between the predicted and actual weights for existing edges. The GCN learns to approximate the edge weights based on node features and adjacency relationships within the weighted graph projection.
   In most cases, the edge weight distribution predicted by the GNN model closely matches the true edge weight distribution of the weighted projection. Both distributions appear to resemble exponential distributions or other heavily right-skewed distributions, where a significant portion of the data is concentrated near smaller values, with frequencies decreasing as the values increase. This picture in the anonymous repository is the visualization of their distributions for the email-Eu dataset.
3. We thank the reviewer for raising this important question. The primary bottleneck in HyperPLR lies in the enumeration step of potential cliques during the Weighted Clique Edge Cover (WCEC) reconstruction phase. This step, while crucial for generating candidate cliques, becomes computationally expensive as the size of the graph and the number of hyperedges increase. In practice, we don’t typically witness such an explosion when enumerate the cliques. The space/time complexity can be found in the general response.

W3:

1. The experimental results in our paper reflect a comprehensive evaluation across multiple datasets and metrics (e.g., density, average degree, clustering coefficient, modularity, etc.), rather than selecting specific metrics or datasets where HyperPLR excels. While HyperPLR may not outperform methods like HyperLap on all metrics, it achieves competitive and consistent performance across a wide range of datasets and metrics, demonstrating its generality and robustness. Our goal is not solely to achieve state-of-the-art performance but to offer a promising framework for hypergraph generation that balances simplicity and effectiveness. HyperPLR integrates weighted graph projection, GNN-based weight prediction, and WCEC reconstruction in a modular and efficient manner.
   Unlike parameter-specific methods like HyperLap and HyperDK, which directly require detailed structural inputs (e.g., hyperedge size distributions or specific node degree properties), HyperPLR only utilizes basic input parameters such as the number of nodes, edge weights, and maximum hyperedge size. These are general properties available in most real-world hypergraph datasets and do not encode problem-specific structural assumptions. This makes HyperPLR more adaptable and less reliant on dataset-specific tuning.

2. We appreciate the reviewer’s suggestion to consider more advanced evaluation metrics. Below, we explain our rationale for selecting the metrics used in the paper:

   • As noted in the literature, there is no universally accepted set of evaluation metrics for hypergraph generation. Most baseline methods propose their own tailored metrics to emphasize the strengths of their specific approaches, but these metrics are inherently biased and not widely adopted by the research community.
   • To ensure fair and unbiased comparisons, we used the most commonly accepted graph metrics, including density, average node degree, clustering coefficient, and modularity. These metrics are widely recognized for evaluating the structural fidelity and quality of graph representations and provide a general assessment of hypergraph generation performance.
   • By focusing on standard graph metrics, we aimed to evaluate HyperPLR’s ability to generate hypergraphs that are structurally consistent with real-world datasets, independent of any specific method’s tailored evaluation framework.

   To ensure a fair and transparent evaluation, we adopted commonly accepted graph metrics rather than method-specific tailored metrics. These metrics provide a robust basis for comparing HyperPLR with existing methods without introducing bias. We will clarify this rationale in the revised manuscript.

3. We appreciate the reviewer’s observation regarding the absence of a comparative baseline in Table 2. We need to clarify the purpose of this table and why a direct comparison with other methods is not applicable. Table 2 is designed to illustrate the evolution of graph metrics across the three stages of the HyperPLR generation process: original graph $G_w$, learned graph $G_w^L$, re-projected graph obtained through GWC $G_w^R$. The goal is to demonstrate that HyperPLR effectively preserves structural properties throughout the generation process while introducing a desirable level of diversity in the reprojected graph.

4. We appreciate the reviewer’s suggestion to clarify the effectiveness of key components in HyperPLR. Below, we address the two specific points raised.

   • Effectiveness of CELL. The inclusion of CELL in HyperPLR is critical for generating a low-rank transition matrix that incorporates spectral information from the input graph. This process captures important global properties, enabling the GNN-based weight predictor to work on a refined graph topology rather than directly on the original projection graph. If we use the input graph directly, the generated graph would lack diversity, leading to poorer generalization and reconstruction fidelity.
   • Effectiveness of the GWC. Empirical evidence (e.g., Table 2) demonstrates that GWC achieves prominent reconstruction ability between the learned graph $G_w^L$ and reconstructed weighted graphs $G_w^R$. This indicates that GWC effectively captures the frequency-based relationships encoded in the edge weights.

W3-2:
We acknowledge the reviewer’s suggestion to expand the evaluation metrics to the Appendix F.2.2. of paper [1]. Below are our experimental results. Notably, the simplicial closure metric from paper [1], which evaluates the temporal evolution process of dynamic hypergraphs, is not applicable to our work or the baseline static generation models. Therefore, we use a similar concept, triangle numbers, which is a widely used graph structural metric [4]. For density, we have already presented the results in Table 1, so it is not repeated here.

Similar to the approach in paper [1], we standardized the metrics for triangle numbers and diameter using the formula: $\frac{|x_1 - x_2|}{x_1}$, where $x_1$ and $x_2$ represent the values of the ground truth and the generated graphs, respectively. For degree distribution and singular value distribution, we compared their cross-entropy. A smaller value indicates better alignment for all the metrics. Also, we have updated all evaluation codes and data in the paper’s anonymous repository.

From the results, we observe that HyperPLR outperforms or is competitive with other models across most datasets and metrics. We hope this demonstrates that we did not engage in any cherry-picking metrics when presenting the results in our original paper. Furthermore, as discussed with Reviewer WfsL, we have shown that HyperPLR generates graphs with higher diversity compared to other models while maintaining strong structural similarity to the original data.

Thank you for your insightful advice and for providing us with the opportunity to engage in this valuable discussion. We hope our response satisfactorily addresses your concerns, and we will incorporate all these meaningful empirical results and discussions in the final version of our paper. We remain open and willing to address any further concerns you may have.

[1] From Graphs to Hypergraphs: Hypergraph Projection and its Remediation (ICLR 2024).
[2] Using wearable proximity sensors to characterize social contact patterns in a village of rural malawi (EPJ Data Science 2021).
[3] Open Graph Benchmark: Datasets for Machine Learning on Graphs (NeurIPS 2020).
[4] Implications of sparsity and high triangle density for graph representationlearning (AISTATS 2023).

We are pleased that our response was able to address your concerns, and we sincerely appreciate your willingness to re-evaluate our work and the thoughtful follow-up comments. Your questions and suggestions are instrumental in further strengthening our paper. Below are our responses to the remaining comments:

W2-1:
We agree with the reviewer that the weighted graph projection itself is not a novel contribution of this work. What we aim to convey is that this is the first time weighted graph projection has been utilized in learning-based hypergraph generation. We will rephrase the statement in line 140 to avoid overstating the novelty of the weighted projection in our paper. The adjustment will ensure clarity and avoid any misinterpretation of our claims.

W2-2:
We appreciate the reviewer’s observation that the edge weight used in HyperPLR may capture non-trivial structural information and acknowledge that these edge weights are uniquely utilized in our framework. We argue that edge weights are more accessible and inherently more robust in practice, especially in scenarios where hypergraph-level structural information is either unavailable or unpublished. These scenarios inspired paper [1], which in turn strongly influenced our work. Below, we elaborate on this point:

• In many real-world cases, hypergraph data is not directly available, as data collection methods often capture only pairwise interactions rather than higher-order relationships. For example, the social science studies often record pairwise interactions using physical proximity sensors or communication logs but lack direct records of multi-person interactions [2]. However, the frequency of these pairwise interactions can be used to approximate edge weights for graph projection.
• Even when hypergraph-level data exists, it is often unpublished or inaccessible in widely used datasets. For instance, the benchmark such as ogbn-proteins [3] provide weighted graph based data but not their corresponding hypergraph structures. In such cases, weighted graph projection offers a practical and robust intermediate representation.

Unlike parameter-based hypergraph generators, HyperPLR effectively leverages edge weights without requiring detailed global hypergraph parameters, which are difficult to obtain when the hypergraph is unobservable or unpublished. This makes HyperPLR both practical and widely applicable. We will incorporate these clarifications into the revised manuscript.

Thanks for your valuable comment, and nice suggestions, as well as for acknowledging our non-trivial contributions. Below, we respond to your specific comments.

W1:
HyperPLR is inspired by some excellent previous works. However, we must note that the technical contributions of HyperPLR are highly non-trivial.

1. Unlike [Bresler et al., 2024], our approach integrates the frequency of node co-occurrences into the weighted projection. This provides a more nuanced representation of hypergraph relationships, capturing higher-order structural information often lost in simpler clique-expanded methods. Our proposed WCEC problem, extends the reconstruction process by explicitly considering weights in clique covers, a challenging direction unexplored by prior work. This additional layer of detail enables the generation of hypergraphs that better match the properties of the original datasets, as demonstrated by our experiments.
2. While we employ established techniques such as GCNs and node2vec embeddings, our novelty lies in the introduction of the principled HyperPLR framework. Although we employed some previous works at the module-level, the effective and principled design at framework-level is non-trivial. Specifically, the combination of CELL-generated topology with GNN-based weight prediction and the innovative WCEC formulation provides a three-stage learning mechanism that effectively models both graph structure and edge weights simultaneously. For more concerns about the novelty, please kindly refer to the general response for the novelty claim.
3. For the theoretical guarantee, please kindly refer to the general response for the theoretical guarantee claim.

W2:
We appreciate the reviewer’s constructive feedback regarding the clarity and organization of the manuscript. Below, we outline how we plan to address the issues raised to improve the readability and comprehension of our work:

1. To improve clarity, we will restructure Section 4 by separating general background content into the preliminaries section and focusing another section exclusively on the Proposed HyperPLR Framework. This distinction will help readers easily identify our contributions.
2. We will add a brief introduction to Minimum Clique Edge Cover (MCEC) in Section 3 to explain its purpose, limitations, and how it connects to our Weighted Clique Edge Cover (WCEC) approach. This will provide the necessary context for understanding the propositions.

W3:

1. We agree with the reviewer that Lemma 2 is relatively straightforward, as it builds on the definitions of MCEC and WCEC. However, its purpose is not to claim the theoretical superiority of WCEC over MCEC but to provide an interpretive bridge between these two approaches. WCEC incorporates edge weights into the reconstruction process, which encodes the frequency of co-occurrence between nodes in hyperedges. This allows WCEC to capture both the structure of the hypergraph and the strength of relationships between nodes. In contrast, MCEC focuses solely on minimizing the number of cliques, ignoring this frequency information, which limits its ability to reconstruct overlapping or nested hyperedges accurately. Also, solving MCEC to reconstruct the hypergraph cannot guarantee the hypergraph size, which empirically tends to generate a significantly smaller number of hyperedges compared to the original hypergraph [1].
2. We acknowledge the reviewer’s concern that our method lacks strong theoretical guarantees. We provide the theoretical guarantee claim in the general response.

Q2:
our novelty mainly lies in the framework/pipeline and WCEC. While CELL has specific advantages, we acknowledge that recent advances in graph generation may offer improvements in flexibility, scalability, or modeling power. Replacing CELL with a newer model is indeed feasible within our framework because: 1) The HyperPLR framework is modular, allowing for the substitution of the graph generation step with any model that can generate realistic weighted graph structures. 2) The weighted graph generator only needs to output an adjacency matrix and weights that are compatible with the downstream reconstruction process.

CELL was chosen as the graph generation component in HyperPLR primarily due to its: 1)Spectral Efficiency: CELL focuses on spectral properties, which are computationally efficient to compute and scale well for large graphs; 2) Alignment with Weighted Graph Projection: CELL provides a low-rank transition matrix, which integrates seamlessly with our pipeline, particularly for predicting edge weights and reconstructing hypergraphs.

[1] From Graphs to Hypergraphs: Hypergraph Projection and its Reconstruction. ICLR 2024