FAHNES: Feature-aware Hypergraph Generation via Next-Scale Prediction

This blog post presents our paper, FAHNES: Feature-aware Hypergraph Generation via Next-Scale Prediction [1], which builds upon and extends our previous work, HYGENE: A Diffusion-based Hypergraph Generation Method [2].

TL;DR: We introduce a framework for generating hypergraphs with both node and hyperedge features, based on an “unzoom-zoom” approach. In the unzoom phase, the input hypergraph is progressively coarsened by clustering nodes and hyperedges, while averaging their features and tracking the size of each cluster. In the zoom phase, a model is trained to reverse this process—predicting finer-grained structure, cluster sizes, and associated features from the coarser representation. New hypergraphs are generated by recursively applying this zoom model, incrementally increasing detail until the desired size is reached.

Preliminaries

Traditional graphs consist of nodes connected by edges, where each edge links exactly two nodes. Hypergraphs, by contrast, offer a more expressive framework: their edges—called hyperedges—can connect any number of nodes simultaneously. This allows hypergraphs to capture higher-order relationships that go beyond pairwise interactions. For example:

• 3D meshes can be represented with triangles as 3-node hyperedges
• Electronic circuits can be modeled with routers replaced by hyperedges connecting all associated components
• Molecules can be described more accurately by grouping functional substructures (e.g., carboxylic acids) into hyperedges

Our goal is to develop a deep learning framework capable of generating new samples from a distribution of featured hypergraphs. For example, given a dataset of 3D meshes representing variations of an object, we aim to train a model that can generate novel, realistic instances.

While our previous work, HYGENE [2], addressed the generation of hypergraph topology, FAHNES builds upon this by improving topological quality and incorporating node and hyperedge features into the generation process.

Example datasets used to evaluate our method.

In short, given a dataset of featured hypergraphs—annotated with 3D positions, atom and bond types, or other attributes—our objective is to train a model that can generate new hypergraphs with similar structural and feature-based properties.

Main Inspirations

HYGENE: A Diffusion-based Hypergraph Generation Method [2]

Our method for hypergraph generation builds on our previous work HYGENE: A Diffusion-based Hypergraph Generation Method [2], which uses an “unzoom–zoom” scheme:

1. Hypergraph Downsampling (Unzoom)

To enable coarsening on hypergraphs, we project them into graph space using two complementary representations:

• Clique Expansion: Each hyperedge is replaced with a clique of edges weighted by \(1/ \vert e \vert\), where \(\vert e \vert\) is the hyperedge size. This preserves spectral properties, allowing us to apply traditional coarsening methods.

• Star Expansion (Bipartite Representation): The hypergraph is represented as a bipartite graph. One set of nodes corresponds to original hypergraph nodes, the other to hyperedges, with links connecting nodes to the hyperedges they belong to.

We apply a spectrum-preserving graph coarsening algorithm [3] to the clique expansion to produce a hierarchy of coarsened hypergraphs. The same node merges are mirrored in the bipartite representation, and hyperedges are merged when their node sets become identical (i.e., the same hyperedge appears twice).

Coarsening: (a) Compute the weighted clique expansion by collapsing each hyperedge into an appropriately weighted clique. (b) Coarsen the clique expansion while preserving the spectral properties of the hypergraph (dark blue nodes). (c) Update the bipartite representation: corresponding left side nodes (in dark blue) are merged, then right side nodes representing the same hyperedge (circled in black) are merged.

2. Hypergraph Upsampling (Zoom)

From a reduced bipartite graph, we train a neural network to reverse the coarsening process:

• Expansion: Predicts which nodes and hyperedges should be duplicated at each step. New entities inherit connections from their parent nodes/hyperedges.

• Refinement: Filters the resulting edges to ensure structural similarity.

For generation, starting with a single node and single hyperedge, we apply this expansion + refinement step iteratively to recover a full-size hypergraph.

FlowAR: Scale-wise Autoregressive Image Generation Meets Flow Matching [4]

FlowAR [4] presents a hierarchical approach to image generation, where images evolve from low to high resolution through successive rounds of upsampling and denoising. At each scale, a neural network transforms Gaussian noise into a refined image, guided by an upsampled version of the previous, coarser output. This process encourages the emergence of global structure early on, while finer details are incrementally filled in—leading to both stable and coherent generation.

Inspired by this, we extend the same principle to hypergraph generation. Instead of working with pixel grids, we operate on nodes and hyperedges, treating coarseness in the hypergraph as analogous to image resolution. Each step in our model adds structural detail—introducing new nodes, hyperedges, and refining their features and connectivity. As with FlowAR, every generation stage is conditioned on the previous, coarser representation, ensuring that high-level structure guides fine-grained synthesis.

Our Work

FlowAR generates features at the pixel (node) level but cannot produce new topologies. In contrast, HYGENE can generate realistic topologies but lacks support for features. Our method, FAHNES, unifies both perspectives: it generates hypergraphs that capture both structure and attributes, supporting various modalities such as 3D meshes or molecular graphs.

The key innovations in our method include:

• A node-budget mechanism, allowing us to track how many original nodes or hyperedges each coarsened entity represents. As the hypergraph grows and distant regions may eventually struggle to communicate, this mechanism helps the model anticipate such limitations. By assigning node counts early on, it enables the model to make better-informed decisions in advance of any communication breakdowns.
• A hierarchical feature generation process, where node and hyperedge features are progressively refined and predicted level-by-level, conditioned on coarser representations.

Coarsening Sequence / Downsampling

To enable hierarchical generation, we first construct a coarsening sequence of the input hypergraph. This process mimics the “unzoom” phase in HYGENE, but now tracks how many original nodes are represented in each node or hyperedge cluster, and incorporate features.

• Node/Hyperedge Budget: Initially, each node and hyperedge is assigned a budget of one, indicating it represents itself. As the hypergraph is coarsened, merged clusters inherit the sum of the budgets of their components. This budget tracks how many elements each cluster represents and will later guide the generation process.

• Feature Averaging: When multiple nodes or hyperedges are merged, their features are averaged using their budgets as weights. This provides a coarse but representative feature vector for the cluster.

These bugets and averaged features will later serve as inputs to the upsampling model for reconstruction.

Coarsening Inversion / Upsampling

When inverting the coarsening process, the model does not directly predict the absolute node budgets for all children of a cluster. Instead, it predicts the splitting ratios of the node budgets. Specifically, during training, the model learns to predict the ratio between the ground truth child node budget and its parent node budget. This constrains predictions to the range \([0,1]\), which stabilizes training by reducing the variance of target values.

Feature upsampling follows a similar approach to hierarchical image generation, where coarse “pixelated” (blocky, low-resolution) representations are progressively refined to produce high-resolution images. Initially, all child nodes within a cluster inherit the same features as their parent, resulting in a coarse representation of the hypergraph. The model then refines these coarse features, progressively enhancing the details to reconstruct the full-resolution hypergraph.

The figure below illustrates this strategy.

Results and Limitations

Results

Examples of generated samples corresponding to the datasets shown at the beginning.

Limitations

Our experiments on molecule generation reveal that, unlike hierarchical image generation—which often outperforms regular one-shot methods—our hierarchical approach is currently less competitive than one-shot graph prediction models. We hypothesize this difference arises from the fundamentally discrete nature of graph generation in our setting.

In hierarchical generation, errors tend to accumulate because the output produced at each step serves as the input for the subsequent step. Consequently, inaccuracies introduced early in the process can propagate and amplify across successive levels, leading to compounded errors.

For continuous data with fixed topology—such as images—this accumulation is relatively limited. The latent space in such cases is effectively continuous: nodes (pixels) of similar images exhibit similar representations, so small prediction errors result in only minor deviations in the output. This inherent smoothness ensures that errors at one step do not substantially alter the starting conditions for the next step.

Conversely, discrete graph generation relies on binary, threshold-based decisions—such as whether to add or remove an edge or expand a cluster. Minor errors in these decision points can cause changes in the graph topology, which in turn significantly alter the node embeddings processed by the GNN. One-shot models avoid this instability as their topology—typically a fully connected graph—remains fixed throughout generation, preventing topology-induced variability.

Conclusion

This work marks a foundational step toward hierarchical generation of featured (hyper)graphs. Future research will aim to improve the framework’s robustness against perturbations and prediction errors to better handle the challenges inherent to discrete topology generation.

When using our work, please cite our paper:

@misc{gailhard2025featureawarehypergraphgenerationnextscale,
	title={Feature-aware Hypergraph Generation via Next-Scale Prediction}, 
	author={Dorian Gailhard and Enzo Tartaglione and Lirida Naviner and Jhony H. Giraldo},
	year={2025},
	eprint={2506.01467},
	archivePrefix={arXiv},
	primaryClass={cs.LG},
	url={https://arxiv.org/abs/2506.01467},
}

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.