This blog post will summarize our paper, HYGENE: A Diffusion-based Hypergraph Generation Method (1), which was accepted at AAAI-25. To the best of our knowledge, this work introduces the first deep-learning method for hypergraph generation. Code is available here.
TL;DR: We introduce a hypergraph generation method based on an “unzoom–zoom” paradigm. First, we compute increasingly coarse versions of a hypergraph (“unzoom”). Then, we train a model to reconstruct the original details from these simplified versions (“zoom”). As working directly on hypergraphs is difficult, we use two different graph representations, each preserving specific characteristics. Generation is done by repeatedly applying the trained model to “zoom in” until the desired hypergraph size is reached.
Preliminaries
Graphs consist of nodes connected by edges, with each edge linking precisely two nodes. In hypergraphs, however, edges — then called hyperedges — can connect an arbitrary number of nodes simultaneously. This allows hypergraphs to capture higher-order and more nuanced relationships than standard graphs, which makes them much more expressive. For instance:
- Polygon meshes can be represented with triangles as 3-edges,
- Electronic circuits can be modeled by replacing routers with hyperedges connecting components together,
- Molecules can be represented more accurately, with the atoms of functional groups joined together by hyperedges, in order to highlight their higher-order relationship.
Our goal is to develop a deep-learning method that can learn from a distribution of hypergraphs and generate new samples from it. For instance, given a dataset of polygon meshes representing variations of the same object, we want to train a model that can generate new instances. As a first step, we focus solely on hypergraph topology, leaving node and hyperedge features for future work.
In other words, given a dataset of unfeatured hypergraphs (without 3D positions, component types, or other characteristics) that share similar topological properties, our goal is to train a model that can generate new samples with matching properties.
Main Inspiration
Our work builds on the foundation laid by the paper Efficient and Scalable Graph Generation through Iterative Local Expansion (2), which introduces a hierarchical method for graph generation. This approach draws inspiration from the literature on graph coarsening algorithms.
When graphs become excessively large, certain algorithms can become computationally infeasible. To address this, it is possible to create smaller, representative versions of the original graph (called coarsened versions) that retain the essential characteristics and properties. The authors of the aforementioned paper used a spectrum-preserving graph coarsening (3) technique, which merges pairs of adjacent nodes in a way that preserves a subset of the eigenvalues and eigenvectors of the original graph.
The coarsening algorithm is applied iteratively to create a coarsening sequence. The first element in this sequence is the original graph, while the last is a fully reduced version comprising a single node. The challenge then becomes training a model to invert this coarsening process.
Starting from a step in the sequence, the model must identify which nodes result from a merge at the previous step. These nodes are then duplicated and connected, with each child retaining the connections of its parent node (expansion). The model then determines which edges should be retained in the final graph (refinement).
The generation process simply involves applying this expansion and refinement procedure iteratively until obtaining a graph of the desired size. This approach scales more efficiently than existing techniques, as it leverages the sparsity of the target graph. When two parts of the graph become disconnected during an early generation step, there is no need to check for connections later, which significantly reduces the number of computations needed.
Our Work
We have successfully generalized this method to hypergraphs and tested it on several datasets. Given the challenges of working directly with hypergraphs due to the variable hyperedge sizes and complex node relationships, we reformulate the problem as an equivalent problem on graphs using two different representations.
Coarsening Sequence / Downsampling
To apply coarsening algorithms to hypergraphs, we represent them as their clique expansion. In this representation, each hyperedge \(e\) is transformed into a clique in which each edge is weighted by \(1/ \vert e \vert\) , where \(\vert e \vert\) is the size of the hyperedge. When an edge appears in multiple cliques, its weight becomes the sum of the weights from each clique.
The clique expansion is particularly convenient for coarsening, as it maintains the same number of nodes as the original hypergraph and shares its spectral properties. Consequently, node merges that preserve spectral properties in the clique expansion also preserve them in the hypergraph. To construct a coarsening sequence for a given hypergraph, we create an equivalent sequence for its clique expansion and merge the same pairs of nodes.
However, it’s important to note that while deriving the clique expansion from a hypergraph is straightforward, the reverse process is NP-hard, which makes it infeasible to work with the clique expansion during generation.
To address this limitation, we maintain another representation of the hypergraph in parallel: the star expansion. This representation depicts the hypergraph as a bipartite graph, with one set of nodes corresponding to the nodes of the hypergraph and the other representing hyperedges. Each node is connected to the hyperedges containing it.
When nodes are merged in the clique expansion, the same nodes are merged in the star expansion. If two nodes representing hyperedges have identical connections (i.e., represent the same hyperedge), they are also merged after the node merges in the clique expansion. Beware that in this scheme, merging only a pair of nodes can result in the merging of up to three hyperedges.
Coarsening Inversion / Upsampling
Starting from a coarsening step, we train a model to identify which nodes and hyperedges are the result of a merge at the previous coarsening step. These nodes are then expanded (nodes are duplicated twice, while hyperedges can be duplicated two or three times), with each child retaining its parent’s connections. Then the model is trained to selectively filter out the edges to reconstruct an accurate topology. Generation starts with a single pair of connected nodes (the minimal bipartite graph) and iteratively applies this scheme until obtaining a hypergraph of the desired size. Once done, we can retrieve the generated hypergraph by replacing each node representing a hyperedge with a hyperedge connecting all of its neighbors.
Pipeline
Results and Limitations
Results
As illustrated above, our method successfully imitates a variety of properties. For a comprehensive analysis of numerical results across various metrics, please refer to our paper.
Limitations
Our method currently appears to disregard the specified number of nodes during generation, instead sampling from the node count distribution of the training data. Additionally, it encounters difficulties when dealing with datasets containing large hypergraphs.
Conclusion
This work represents a significant first step towards deep-learning-based hypergraph generation. Our future research will focus on improving the accuracy of the model during generation, particularly regarding node count constraints, and expanding support for feature generation.
When using our work, please cite our paper:
@inproceedings{gailhard2025hygene,
title={HYGENE: A Diffusion-based Hypergraph Generation Method},
author={Gailhard, Dorian and Tartaglione, Enzo and Naviner, Lirida and Giraldo, Jhony H.},
booktitle={Proceedings of the AAAI Conference on Artificial Intelligence},
year={2025},
}
Acknowledgments
We acknowledge the ANR – FRANCE (French National Research Agency) for its financial support of the System On Chip Design leveraging Artificial Intelligence (SODA) project under grant ANR-23-IAS3-0004. This project has also been partially funded by the Hi!PARIS Center on Data Analytics and Artificial Intelligence.