FAHNES: Feature-aware (Hyper)graph Generation via Next-Scale Prediction

This post presents our paper, FAHNES: Feature-aware (Hyper)graph Generation via Next-Scale Prediction (1), accepted at ICML-26. It extends our previous work, HYGENE: A Diffusion-based Hypergraph Generation Method (2).

TL;DR: We introduce a framework for generating (hyper)graphs with both node and (hyper)edge features, based on an “unzoom–zoom” approach. In the unzoom phase, the input (hyper)graphs are progressively coarsened by clustering nodes and (hyper)edges. Each resulting cluster inherits the average feature of its constituent nodes or hyperedges, and keeps track of how many elements it contains. In the zoom phase, a model is trained to reverse this process by predicting finer-grained structure, cluster sizes, and associated features from the coarse version of the (hyper)graph. A new (hyper)graph can be generated by iteratively applying this zoom model until the full (hyper)graph is constructed.

In the following, we present our work for hypergraphs. It can be straightforwardly adapted to graphs by following the methodology of (3) and incorporating our new components.

Preliminaries

A random graph and a random hypergraph.

Graphs consist of nodes connected by edges, where each edge links exactly two nodes. Hypergraphs, by contrast, are more expressive: 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:

Polygon meshes can be represented with their faces as hyperedges,
Electronic circuits can be modeled with routers replaced by hyperedges connecting all associated components,
Molecules can be described more accurately by joining functional groups (e.g., carboxylic acids) into hyperedges.

Our goal is to develop a deep-learning framework that can generate new samples from a distribution of featured hypergraphs. For example, given a dataset of polygon meshes representing variations of an object, we want to train a model that can generate novel, realistic instances of the same object.

While our previous work, HYGENE (2), could generate hypergraph topologies, it was unable to generate features. Similarly, Efficient and Scalable Graph Generation through Iterative Local Expansion (3), which introduced the hierarchical framework for graph generation on which we built HYGENE, focuses only on topology and could not generate features. Our main contribution with FAHNES is the integration of node and hyperedge features into the generation process.

Example datasets used to evaluate our method. Edges are omitted for point clouds for clarity.

In short, given a dataset of featured hypergraphs—annotated with node positions or other attributes—our objective is to train a model that can generate new samples with similar structural and feature 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)

As working directly on hypergraphs is difficult, we used two complementary graph representations:

Clique Expansion: Each hyperedge is replaced with a clique whose edges are weighted by \(1/ \vert e \vert\), where \(\vert e \vert\) is the hyperedge size. This preserves spectral properties and allows us to apply traditional graph 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 corresponds to hyperedges, with edges connecting nodes to the hyperedges containing them.

We apply a spectrum-preserving graph coarsening algorithm (4) to the clique expansion in order 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 representation, 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 the connections from their parent nodes/hyperedges.
Refinement: Filters the resulting edges to reconstruct the details.

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

Our model starts from a single pair of linked nodes (in the bipartite representation) and iteratively expands the left-side nodes (in dark blue) and right-side nodes (in red), where each duplicate keeps the connections of its parent node. Then, our method refines the resulting bipartite graph, filtering edges to recover an appropriate local structure.

FlowAR: Scale-wise Autoregressive Image Generation Meets Flow Matching (5)

FlowAR progressively upsamples an image starting from a single pixel. At each scale, the current image is upsampled (*e.g.*, replacing each pixel with a 2×2 block of the same value), and serves as conditioning for the next round of flow-matching. The model starts from Gaussian noise and iteratively denoises the image at each resolution, guided by the coarse prediction from the previous scale.

FlowAR (5) introduces 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 allows the emergence of global structure early on, while finer details are incrementally added, which helps maintain global coherence.

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 details by introducing new nodes and hyperedges and refining their features and connectivity. As with FlowAR, every generation stage is conditioned on the previous, coarser representation.

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 and graphs that capture both structure and attributes, supporting various modalities such as polygon meshes or point clouds.

The main innovations in our method include:

A hierarchical feature generation process, in which features are predicted in a coarse-to-fine manner: at each level, children inherit an initial approximation from their parent, and the model refines these features based on the surrounding context. This not only makes feature generation tractable at large scales but also ensures that local details are globally coherent.
A node-budget mechanism, allowing us to track how many original nodes or hyperedges each cluster represents. Since different parts of the hypergraph can grow at different rates, this mechanism encodes the local resolution of each region, which helps the model coordinate the generation process across different parts of the structure. Beyond this, the node budget also serves as a way to explicitly mark which parts of the generated sample are complete. This allows the model to concentrate on modifying only the unfinished regions, without having to learn how to distinguish between finished and unfinished parts.
An adaptation of minibatch OT coupling (6,7) to our setting. During training, we reindex the prior noise samples of children within the same cluster to minimize the distance to their targets. Otherwise, because graphs and hypergraphs lack a natural ordering, the learning signal would be extremely noisy: all node permutations correspond to the same (hyper)graph, but loss computation requires a fixed order that may not be aligned with the predictions. Reindexing implicitly imposes a consistent order, and makes targets more stable.

Coarsening Sequence / Downsampling

We first construct a coarsening sequence of the input hypergraph. This process is similar to the “unzoom” phase in HYGENE, but now tracks the size of each node or hyperedge cluster, and also incorporates features.

Node/Hyperedge Budget: Initially, each node and hyperedge is assigned a budget of one, i.e. 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.
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 for the cluster.

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

Examples of coarsening sequences for various polygon meshes and point clouds. Thicker lines represent 2-edges. Each row shows a progressively coarser version of the input (hyper)graph.

Coarsening Inversion / Upsampling

When inverting the coarsening process, we upsample features similarly to hierarchical image generation, where coarse “pixelated” (blocky, low-resolution) intermediate images are progressively refined to produce high-resolution images. Initially, all child nodes within a cluster inherit the same features as their parent, producing a coarse representation of the hypergraph. The model then refines these features and recovers the original details.

Regarding node budgets, the model does not directly predict the absolute budgets for all children of a cluster. Instead, it predicts splitting ratios—the proportion of a parent’s budget allocated to each child: during training, the model learns to predict the ratio between a child’s ground-truth budget and its parent’s budget. This constrains predictions to the range \([0,1]\), which both stabilizes training (by reducing target variance) and allows us to use diffusion methods tailored for data on the simplex.

We further leverage the node budget mechanism to guide generation:

Nodes with budget = 2 that expand necessarily split their budget evenly between their two children.
Nodes with budget = 1 cannot expand further and are ignored during prediction. This allows the model to focus only on evolving parts of the hypergraph.

This greatly reduces the learning complexity: the model no longer needs to distinguish between “finished” and “unfinished” regions. Instead, it predicts values only for actively expanding parts. Feature refinement is similarly restricted to clusters undergoing expansion.

The figure below illustrates this strategy.

Combining everything gives the above pipeline: i) During training, input hypergraphs are progressively coarsened by merging nodes and hyperedges, yielding a multiscale representation. Node features are averaged during merging, and budgets are summed. ii) The model is trained to predict which nodes were merged at each scale. iii) In the expansion phase, merged nodes are expanded (shown in dark), inheriting their parent’s features, budget, and connectivity. The model is trained to (a) identify which edges should be removed (dotted lines), (b) predict how the parent’s budget should be split across the children, and (c) refine the features of newly expanded nodes (refinement).

Results and Limitations

Results

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

As shown above, our method can produce basic polygon meshes and point clouds, though their quality remains limited. For a detailed analysis of numerical results across multiple metrics, please see our paper.

Limitations

We found that performance is highly sensitive to hyperparameter choices, and that the model is especially prone to overfitting. Interestingly, unlike in image generation, where overfitting generally means reproducing the training data with high fidelity, here overfitting drastically reduces quality, and generalization and output quality are correlated rather than exhibiting a trade-off.

Conclusion

This work marks a foundational step toward hierarchical generation of graphs and hypergraphs with both topology and features. Future work will aim to improve the robustness of the framework against perturbations and prediction errors.

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.