HyperPLR: Hypergraph Generation through Projection, Learning, and Reconstruction

Authors: Weihuang Wen, Tianshu Yu
Primary area: learning on graphs and other geometries & topologies
Keywords: hypergraph, graph generation, clique cover problem

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730188733018

thread_type:
official_review

<thread_object>
creator: reviewer_wfsl

<content>
summary:
***Overview.*** The authors study the hypergraph generation task. 

***Method.*** Specifically, they propose a learning-based hypergraph generative method, named HyperPLR.
HyperPLR learns the (potential) weight of each edge with GNN from the unweighted graph.
Therefore, (1) it generates an unweighted graph with CELL, and (2) it assigns edge weights by using the trained GNN.
Lastly, the weighted graph is transformed into a hypergraph.

***Experiment.*** The authors demonstrated the effectiveness of HyperPLR in several benchmark hypergraph datasets, compared to hypergraph generative baseline methods.

strengths:
***S1.*** This is the first learning-based hypergraph generative method. 

***S2.*** Overall method design is reasonable.

***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.

***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)? 

***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.

Please clarify if my understanding or claims are wrong.

questions:
See the mentioned weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730382045889

thread_type:
official_review

<thread_object>
creator: reviewer_c2hn

<content>
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.

strengths:
- HyperPLR introduces a new approach to hypergraph generation, based on three-stage framework. 
- The authors thoroughly discuss the limitations of the method. 
- Code and datasets are available.

weaknesses:
**Clarity and presentation issues**
- 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. 
- Inconsistent notations (e.g., Graph A in Figure 2 and Graph G in the text) are used.
- "G coefficient/modularity" and "B modularity" in Table 1 lack proper definitions.
- It is unclear in line 202, why weighted projection offers a more "compact representation" compared to the bipartite graph representation of hypergraphs.
- "Strong global structures" in line 214 require better contextual discussions. 
- A typo in line 138: $(v_i, v_j)\in e_i$.

**Method descriptions**
- 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).
- 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?
- What are the bottlenecks in HyperPLR? What is its space/time complexity?

**Evaluation**
- 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.
- More advanced evaluation metrics, such as those used in baseline papers, could have been considered.
- Table 2 lacks a comparative baseline.
- 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?


**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.

questions:
Please refer to the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730618913810

thread_type:
official_review

<thread_object>
creator: reviewer_zxbq

<content>
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.

strengths:
1. Hypergraph generation is important for understanding the nature of high-order relationships.
2. The proposed method is based on a simple, intuitive idea, yet shows good empirical performance on various datasets.
3. 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.
2. 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.
3. 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.

questions:
1. Refer to the weaknesses above.
2. Can we replace CELL with any recent graph generator models, like those introduced in [1]?

- [1] Liu et al. “Generative Diffusion Models on Graphs: Methods and Applications.” IJCAI 2023
</content>
</thread_object>

</thread>
<thread>
creation date:
1732463612207

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely appreciate the reviewers’ time, valuable feedback, and constructive suggestions.  Your expertise and insights have been instrumental in improving the quality and clarity of our work. The primary concerns revolve around the novelty of the WCEC and the theoretical guarantee for GWC. Here, we provide a consolidated response in the general response section.

1. **Novelty Claim.**
We acknowledge that weighted projections of hypergraphs have been explored in prior work. However, the novelty of our work does not lie in the use of weighted projections as a standalone contribution, but in the principled and effective integration of components into the HyperPLR framework:
    - **Topology Generation:** HyperPLR uses CELL to generate a low-rank topology that serves as a robust foundation for weight prediction.
    - **Edge Weight Prediction:** A GNN-based model refines the weighted graph using learned embeddings, effectively bridging graph structure and edge weights.
    - **Reconstruction via WCEC:** We introduce the Weighted Clique Edge Cover (WCEC) problem and the Greedy Weighted Cover (GWC) algorithm, explicitly considering edge weights to enable the preservation of higher-order relationships and overlapping hyperedges. This challenging direction has not been explored in prior work. 

    The HyperPLR framework combines these steps into a three-stage learning mechanism that models both graph structure and edge weights simultaneously. This integration allows us to reconstruct hypergraphs that better match the properties of the original datasets, as demonstrated by our experiments. The novelty of HyperPLR lies in its framework-level integration of established and novel components, rather than in isolated techniques such as weighted projections or GNNs. We hope this clarifies our contributions and addresses concerns about the novelty of our work. Additionally, to the best of our knowledge, we are the only learning-based hypergraph generation paper that has been open-sourced, where the source code can be found at the anonymous repository in [here](https://anonymous.4open.science/r/hyperplr-C0F3/README.md).
2. **Theoretical guarantee for GWC.**
Reviewer ZxbQ, C2HN raised concerns about our theoretical guarantee of performance and complexity for GWC. Here, we provide some clarifications from the optimization perspective and the computational complexity perspective.
    - **From an optimization perspective:** for the MCEC problem, which aims to select the minimum number of cliques to achieve edge coverage, can be transformed into a set cover problem. This allows for a theoretical analysis of its greedy algorithm, ultimately proving that the greedy approach achieves a 2-approximation of the optimal solution. In contrast, WCEC optimizes the L1 distance between the coverage counts of all edges and their corresponding weights, inherently making it an integer programming problem. This non-standard objective function poses significant challenges for all heuristic algorithms to achieve effective optimization guarantees on general graphs. In practice, greedy algorithms often yield good solutions for similar optimization problems, even if a formal approximation ratio isn’t established.
    - **From a computational complexity perspective:** without specific properties of the graph or additional constraints, it will be challenging to establish a precise analysis for the computation complexity. Therefore, we assume the weights in the weighted projection graph are in uniform distribution. Let $n$ be the node number, $m$ be the hyperedge number, and $S$ be the  grand sum of the weighted matrice $W$, each edge has the probability $p$ to be covered, where $p = 1 - (\frac {\binom{n}{2} - 1}{\binom{n}{2}})^S$. Let $Z_d$ be a random variable corresponding to the number of cliques with size $d$. We have $\mathbb{E}(Z_d) = \binom{n}{d}p^{\binom{d}{2}}$. Let $Z$ be the clique number, so we have $Z = \sum_{d=2}^n \mathbb{E}(Z_d) = \sum_{d=2}^n\binom{n}{d}p^{\binom{d}{2}}\leq (1+p)^n$. The time complexity of the algorithm is $O(m (2 - (\frac {\binom{n}{2} - 1}{\binom{n}{2}})^S)^n)$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733143383996

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Reviews and Discussion

comment:
As the discussion period comes to an end, we would like to express our gratitude to all the reviewers for their constructive discussions and positive feedback. Based on these suggestions, we conducted additional theoretical and empirical analyses, incorporating numerous experiments to further demonstrate our method’s effectiveness in achieving both **similarity** and **diversity** in hypergraph generation. These contributions have significantly improved the quality of our paper.

We would like to summarize the key takeaways and contributions highlighted during the discussion. **Learning-based hypergraph generation** remains a challenging yet vital problem in the field. The difficulties stem not only from modeling and learning from large-scale hypergraph data but also from defining and evaluating **similarity** and **diversity** in generated hypergraphs. In our paper, we made an innovative attempt to tackle these challenges. We decomposed the hypergraph generation process into three modular steps: **projection, learning, and reconstruction**. This decomposition alleviates the computational burden on the learning module and enhances the overall scalability of the framework. Another key contribution of our work is the introduction of the **Weighted Clique Edge Cover (WCEC)** optimization problem. Empirical results demonstrate that solving WCEC enables effective reconstruction of hypergraphs from weighted graph representations, bridging the gap between pairwise data and higher-order relationships.

We hope our work inspires further exploration and advancements in this area of research. Once again, thank you for all the valuable input and thoughtful feedback, which have been instrumental in shaping this paper and moving this field forward.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The authors propose a learning-based generative model for large-scale hypergraphs (e.g., email networks), which have commonly been modeled using rule-based or mathematical models. Their approach reformulates the problem at the graph level, focusing on generating a realistic projected graph based on the ground-truth projected graph (also referred to as clique expansion). Subsequently, a realistic hypergraph is reconstructed from the projected graph. The experiments demonstrate that the proposed model yields hypergraphs with reasonably realistic structural properties.

The reviewers recognized the use of a machine-learning approach to large-scale hypergraph generation as an interesting and valuable direction, and they found the overall method design compelling.

However, they also raised several limitations, including limited scalability, marginal performance improvements over rule-based models, and areas where the presentation could be enhanced.

While no reviewer expressed strong enthusiasm for the submission, all reviewers leaned slightly toward acceptance. The meta-reviewer also believes that, as the first machine-learning-based approach to tackle an important problem, the merits of accepting the paper outweigh the drawbacks of rejecting it. Therefore, the meta-reviewer recommends acceptance, provided the authors diligently improve the paper based on the discussions.