Technical Summary: Feature-Aware (Hyper)graph Generation via Next-Scale Prediction (FAHNES)

1. Problem Statement

Generating discrete geometric structures, specifically graphs and hypergraphs, is a fundamental challenge in machine learning with applications ranging from molecular design to 3D shape modeling. While existing deep learning methods have made progress, they face two primary limitations:

1. Scalability: Most state-of-the-art models (e.g., diffusion-based approaches) utilize flat architectures that model the entire structure simultaneously. This results in quadratic computational and memory complexities, restricting them to moderately sized graphs.
2. Feature Neglect: Existing hierarchical methods improve scalability by building structures from coarse to fine representations but typically focus solely on topology. They often ignore node and edge (or hyperedge) features, which are critical for real-world applications (e.g., 3D mesh coordinates). Furthermore, sequentially generating topology and then features proves ineffective in complex settings, as the two are often interdependent.

The core challenge addressed by this work is the development of a scalable, hierarchical generative framework that jointly models both the topology and the features of graphs and hypergraphs.

2. Methodology: FAHNES

The authors propose FAHNES (Feature-Aware (Hyper)graph Generation via Next-Scale Prediction), a hierarchical generative framework that operates on a coarsening-expansion pipeline. The method treats hypergraphs as the general case (with graphs as a specific instance) and utilizes a bipartite representation for hypergraphs (star expansion).

2.1. Hierarchical Pipeline

The framework follows a three-stage process:

1. Coarsening (Training Phase): Input hypergraphs are progressively coarsened by merging nodes and hyperedges. This is achieved via spectrum-preserving coarsening on the clique expansion of the hypergraph. During this process:

   • Scale Encoding: A novel hierarchical scale encoding is introduced. Each cluster is assigned a scale encoding representing the number of fine-level nodes it contains. This encoding is initialized to 1 for each node/hyperedge, summed upon merging, and propagated to super-clusters. This provides local control over growth rates.
   • Feature Aggregation: Node and hyperedge features are aggregated via weighted means (barycenters) based on the scale encodings.
   • Initialization: The process reduces the graph to a single super-node and super-hyperedge with zero features, serving as a feature-agnostic starting point for generation.

2. Expansion and Refinement (Generation Phase): The model learns to reverse the coarsening process through iterative steps:

   • Expansion: Clusters are recursively split (duplicated) into child nodes. Children initially inherit the parent's connectivity, features, and scale encoding.
   • Refinement: The model predicts:
     • Which edges should be removed (incidence refinement).
     • How to split the parent's scale encoding among children (ensuring integer constraints).
     • Refined features for the newly expanded nodes.
   • Flow Matching: The generation process is modeled using conditional flow matching, learning a vector field that transports random initial states toward the target refinement variables.

3. Reconstruction: Once the final bipartite graph is generated, it is collapsed back into a hypergraph by converting right-side nodes (representing hyperedges) into hyperedges connecting their adjacent left-side nodes.

2.2. Key Technical Components

• Hierarchical Scale Encoding: Unlike prior methods that append target size to node embeddings, FAHNES uses scale encodings to explicitly constrain local growth. This ensures cross-scale consistency, particularly in regions that expand at uneven rates.
• Multi-Scale Graph Optimal Transport (OT) Coupling: To address the permutation-alignment problem (where the model generates a permuted version of the correct output), the authors generalize minibatch OT coupling. This aligns predictions with targets by finding a permutation that minimizes matching cost while preserving graph structure and feature consistency. The coupling is restricted to children within a single cluster expansion to maintain computational efficiency.
• Graph Inpainting: To improve training stability, the loss is masked for "stationary" nodes (those that do not change between scales). This prevents the gradient signal from being diluted by trivial identity mappings, focusing the model on active structural refinements.

3. Key Contributions

The paper claims the following contributions:

1. First Hierarchical Feature-Aware Method: FAHNES is presented as the first hierarchical generative method capable of jointly generating topology and features for both graphs and hypergraphs with quasi-linear complexity.
2. Hierarchical Scale Encoding: A novel encoding mechanism that enhances global structural coherence by controlling local growth constraints during the refinement process.
3. Multi-Scale Graph OT Coupling: A theoretically grounded approach to solve the permutation-alignment problem in graph generation, improving training stability and coherence.
4. Empirical Validation: Comprehensive validation on synthetic, 3D mesh, and graph point cloud datasets, demonstrating the ability to scale to large featured structures.

4. Experimental Results

The authors evaluated FAHNES on a variety of datasets, including synthetic stochastic block models (SBM), real-world graphs (Protein, Point Clouds), and 3D meshes (ModelNet40, ManifoldNet).

• Featureless Hypergraphs: FAHNES outperformed baselines (HYGENE, HyperPA, VAE, GAN, Diffusion) in validity and spectral metrics across SBM, Ego, and Tree datasets.
• Featureless Graphs: On small graph datasets, FAHNES achieved competitive results against state-of-the-art flat models (DeFoG, DiGress) and improved upon the hierarchical baseline HSpectre.
• Scalability (Point Clouds): On large-scale point cloud datasets (Airplane, Bench), FAHNES was the only method that successfully scaled. Flat models (Flow Matching, DiGress, DeFoG) failed due to Out-of-Memory (OOM) errors, highlighting the quasi-linear complexity advantage of the hierarchical approach.
• Featured Meshes: On 3D mesh datasets (ManifoldNet), FAHNES achieved superior Chamfer Distance and coverage metrics compared to sequential disjoint generation and naive-joint approaches (WGAN, VAE), validating the necessity of joint topology-feature modeling.
• Ablation Studies: Removing either the scale encoding or the OT coupling resulted in significant performance degradation (e.g., increased Chamfer Distance), confirming the necessity of both components for high-quality feature generation.

5. Significance and Claims

The paper positions FAHNES as a significant step forward in generative modeling for structured data. Its primary significance lies in bridging the gap between scalability and feature integration.

• Scalability: By moving away from flat, quadratic-complexity architectures, FAHNES enables the generation of large-scale graphs and hypergraphs that were previously intractable for feature-aware models.
• Joint Modeling: The work demonstrates that jointly modeling topology and features yields better results than sequential or naive-joint approaches, particularly for complex structures like 3D meshes.
• Generalization: The framework is presented as a unified approach applicable to both graphs and hypergraphs, offering a generalizable solution for higher-order relationships.

The authors modestly acknowledge limitations, noting that while scale encoding mitigates missing node issues, generating extremely large hypergraphs (e.g., ModelNet Bookshelf) remains challenging. Additionally, the current framework assumes continuous feature distributions, and training large-scale datasets remains computationally expensive.