Research map / Image generation / Fast diffusion sampling
HYGENE: A Diffusion-Based Hypergraph Generation Method
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes HYGENE, a diffusion-based hypergraph generator that coarsens hypergraphs via spectrally-preserving clique-expansion contractions and learns to invert them by progressive bipartite-graph expansion and refinement.
Problem
Generating realistic and diverse hypergraphs is hard because hyperedges are variable-size and exponentially numerous, and existing deep generative models do not capture hypergraph structure.
Approach
Represent hypergraphs as bipartite star expansions and generate them by iteratively expanding a two-node seed (local node duplication plus edge refinement), with each reverse step learned by an EDM diffusion model using a PPGN, conditioned on spectral properties preserved by spectrum-preserving coarsening and capped hyperedge merge sizes.
Key results
- On the Ego hypergraph dataset HYGENE produces valid ego hypergraphs 90% of the time, versus 0% for all baselines (HyperPA, VAE, GAN, Diffusion).
- On SBM hypergraphs HYGENE reaches 65% valid SBM vs 2.5% for HyperPA and 0% for the image-based baselines, with the best Node Deg (0.321) and Edge Size (0.002) among the compared models.
- Ablation: removing spectrum-preserving coarsening or the hyperedge-cluster upper bound lowers validity (e.g., Ego valid drops from 90% to 77.5% when the upper bound is removed); removing both is worse on Node Deg (1.234 for SBM vs 0.321).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add HYGENE's progressive expansion and refinement generation method | Hypergraph generation · SBM Hypergraphs | Valid SBM: 2.5% -> 65% | Helped |
| add HYGENE's progressive expansion and refinement generation method | Hypergraph generation · Ego Hypergraphs | Valid Ego: 0% -> 90% | Helped |
| add HYGENE's progressive expansion and refinement generation method | Hypergraph generation · Tree Hypergraphs | Valid Tree: 0% -> 77.5% | Helped |
| remove the upper bound on hyperedge cluster size (ablation) | HYGENE · SBM Hypergraphs | Node Deg: 0.321 -> 1.234 | Hurt |
| remove the upper bound on hyperedge cluster size (ablation) | HYGENE · Ego Hypergraphs | Spectral: 0.004 -> 0.149 | Hurt |
| remove the upper bound on hyperedge cluster size (ablation) | HYGENE · Tree Hypergraphs | Valid Tree: 77.5% -> 20% | Hurt |
| remove the upper bound on hyperedge cluster size (ablation) | HYGENE · Erdős-Rényi Hypergraphs | Node Deg: 0.475 -> 1.018 | Hurt |
| remove spectrum-preserving coarsening (ablation) | HYGENE · SBM Hypergraphs | Valid SBM: 65% -> 47.5% | Hurt |
| remove spectrum-preserving coarsening (ablation) | HYGENE · Ego Hypergraphs | Spectral: 0.004 -> 0.004 | No clear effect |
| remove spectrum-preserving coarsening (ablation) | HYGENE · Tree Hypergraphs | Valid Tree: 77.5% -> 77.5% | No clear effect |
| remove spectrum-preserving coarsening (ablation) | HYGENE · Erdős-Rényi Hypergraphs | Edge Size: 0.012 -> 0.124 | Hurt |
Surprising findings
- Graph-based generators (two cited models) produced valid bipartite graphs only 30% of the time, making direct graph generation for hypergraphs unreliable.
- On ModelNet40 meshes HYGENE does not respect the requested node count well: Node Num errors (~42-70) are close to the dataset standard deviation, since the model samples sizes from the distribution rather than the target.
Limitations
- Fails to produce the specified number of nodes on ModelNet40 meshes; samples sizes from the dataset distribution instead.
- Relies on a clique-expansion coarsening restricted to adjacent-node contractions with at most three hyperedges per merge, a heuristic bound that does not hold for simultaneous merges without extra constraints.
- Evaluated only on small synthetic and low-poly mesh hypergraphs (about 32 to 180 nodes).
Experimental setup
Datasets: Erdos-Renyi hypergraphs Stochastic Block Model hypergraphs Ego hypergraphs Tree hypergraphs ModelNet40 piano ModelNet40 plant ModelNet40 bookshelf
Benchmarks: SBM hypergraphs Ego hypergraphs Tree hypergraphs Erdos-Renyi hypergraphs ModelNet40 piano ModelNet40 plant ModelNet40 bookshelf
Metrics: NodeNumDiff NodeDegreeDistrWasserstein EdgeSizeDistrWasserstein Spectral MMD ValidSBM ValidEgo ValidTree
Baselines: HyperPA VAE GAN Diffusion (incidence matrix images)
Builds on: EDM GRAN PPGN SignNet Bolla's Laplacian
Closest papers by meaning
- Hypergraph Generation via Structured Stochastic Diffusion (NeurIPS 2026 · similarity 0.89)
- HypeBoy: Generative Self-Supervised Representation Learning on Hypergraphs (ICLR 2024 · similarity 0.88)
- Hyperbolic Graph Diffusion Model (AAAI 2024 · similarity 0.87)
- HiGen: Hierarchical Graph Generative Networks (ICLR 2024 · similarity 0.87)
- Efficient and Scalable Graph Generation through Iterative Local Expansion (ICLR 2024 · similarity 0.87)
- Discrete-state Continuous-time Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.