Feature-Aware (Hyper)graph Generation via Next-Scale Prediction

The paper introduces FAHNES (feature-aware (hyper)graph generation via next-scale prediction), a hierarchical generative framework that jointly models topology and features for both graphs and hypergraphs. The authors state: "Graph generative models perform well on small structured data but struggle to scale to large, complex structures. Hierarchical approaches improve scalability but often ignore node and edge features, which are critical in real-world applications, particularly for hypergraphs that model higher-order relationships."

Motivation and limitations of prior work: The paper notes that existing methods for featured graph generation struggle to scale. Most of these approaches use flat architectures that model the entire structure at once, leading to quadratic computational and memory complexities. Furthermore, "existing hierarchical methods only focus on unfeatured structures. Extending them to generate features is challenging because different regions of a graph or hypergraph often grow at uneven rates during the refinement process, making it difficult to maintain consistency across scales. Furthermore, sequentially generating topology first and then features—rather than modeling them jointly—is ineffective in complex settings."

Core methodology: FAHNES builds multi-scale representations through node coarsening and reconstructs fine structures via localized expansion, while directly predicting features alongside structure at each stage. The framework operates on the bipartite representation of hypergraphs (star expansion), where Left side nodes VL represent the nodes of the hypergraph, while right side nodes VR represent hyperedges.

Key innovations:

1. Hierarchical scale encoding: "Each cluster is assigned a scale encoding indicating its remaining expansions. Scale encodings are recursively divided among child nodes, starting from a single super-node with the full scale encoding and ending when all clusters have a scale encoding of one. This provides more local control over the final node count and improves global consistency compared to prior methods, which only append the desired size to node embeddings."

2. Multi-scale graph OT coupling: The authors generalize minibatch OT-coupling to align predictions and targets via a permutation that minimizes their matching cost. They restrict "permutations to children within a single cluster expansion, where equivalence naturally holds. With two or three children per cluster, only two or six permutations are possible, making the operation lightweight and easily parallelizable."

3. Graph inpainting: Nodes and hyperedges that are not expanded inherit their parent connectivity and features deterministically, allowing the model to focus only on regions undergoing structural refinement.

Coarsening process: The method uses spectrum-preserving coarsening applied to the hypergraph's clique expansion. Node features are aggregated via weighted averaging: the super-cluster feature is computed as the weighted mean of its constituent features. The paper proves (Proposition 1) that the optimal downsampled features minimizing the reconstruction error are the cluster-wise barycenter.

Expansion and refinement: The inverse of coarsening consists of expansion (upsampling by duplicating nodes and hyperedges) and refinement (adjusting connectivity, scale encodings, and features). During refinement, the model learns to (a) identify which edges should be removed, (b) predict the scale encodings of the children based on the parent's scale encoding, and (c) refine the features of newly expanded nodes.

Probabilistic modeling: The authors model the marginal likelihood of each hypergraph H as a sum over the likelihoods of its bipartite representation's expansion sequences p(H) = p(B) = Σ ϖ∈Π(B) p(ϖ). They assume a Markovian generative structure and model the distribution of expansion and refinement sequences with a combined likelihood term.

Theoretical guarantees: The paper provides proofs that: (i) the multi-scale graph OT coupling has marginals q0(x0), q1(x1) (Proposition 2), ensuring no bias is introduced; (ii) the coupling reduces the total variance of this displacement compared to uncoupled targets (Proposition 3); and (iii) graph inpainting recovers the generative signal by removing the identity-mapping bias (Proposition 4).

Implementation: The model uses a conditional flow-matching framework combined with a local PPGN backbone. At each refinement scale, the model jointly predicts: (i) node expansion decisions, (ii) hyperedge expansion decisions, (iii) incidence refinement variables, (iv) scale-encoding split proportions, and (v) node and hyperedge feature refinements. The training uses an endpoint flow matching framework where the model learns a vector field transporting random initial states toward the target refinement variables.

Complexity: The total computational complexity of our approach scales as O((n + m + k) log n) for a hypergraph with n nodes, m hyperedges, and k incidences.

Experiments: The method is evaluated on:

• Unfeatured hypergraphs: SBM, Ego, Tree, and ModelNet40 (bookshelf and piano) datasets

• Unfeatured graphs: SBM, Tree, Planar, Protein, and Point cloud datasets

• Featured hypergraphs: Manifold40 3D meshes (bench and airplane)

• Featured graphs: Point clouds sampled from the same mesh categories

Results: For unfeatured hypergraphs, FAHNES achieves state-of-the-art performance, e.g., 87.8±3.1 valid SBM hypergraphs versus 65.0 for HYGENE, and 99.5±1.1 valid Ego hypergraphs versus 90.0 for HYGENE. For unfeatured graphs, FAHNES obtains competitive results compared to state-of-the-art flat methods on small-graph datasets. For featured point clouds, our hierarchical approach is the only method that scales (baselines DiGress and DeFoG run out of memory). For 3D meshes, FAHNES obtains better results in general than other baselines like the sequential generation or naive-joint approaches.

Ablation studies: The authors show that using scale encodings instead of concatenating the target size to each node embedding improves generation quality and that the multi-scale graph OT coupling has a more nuanced effect, clearly improving quality on some datasets. Both components are essential for feature generation, as lacking one of them results in much worse results.

Limitations: The authors acknowledge that our scale encoding helps mitigate the issue of missing nodes, it does not fully resolve it, and our method still struggles when generating very large hypergraphs. Additionally, our framework currently assumes continuous feature distributions (e.g., 3D coordinates), and extending it to domains with richer or heterogeneous node and hyperedge attributes may require additional modeling components.

Based on the paper, here are the specific improvements I can implement and what the improved AI system can do:

Implementation: Replace flat size conditioning with per-cluster scale encodings that track how many fine-level nodes each coarse cluster should expand into. During generation, recursively divide scale encodings among child nodes.

Resulting capability: The system can generate structures where different regions grow at different rates while maintaining global coherence, avoiding the common failure mode of producing disconnected or malformed large structures.

Implementation: At each expansion step, simultaneously predict: (a) which nodes to expand, (b) how to split scale encodings, (c) which edges to remove, and (d) refined node/hyperedge features—all conditioned on parent features using FiLM layers.

Implementation: During training, align predicted and target nodes within each expanded cluster by testing all 2–6 possible permutations and selecting the one minimizing displacement variance, preserving graph isomorphism.

Implementation: During training, mask out loss contributions from nodes and hyperedges that do not expand (scale encoding = 1), focusing gradient updates only on active refinement regions.

Implementation: Use the coarsen-then-expand pipeline with Local PPGN backbone, restricting operations to local neighborhoods and limiting cluster sizes to 2–3 nodes.

1. Generate large featured hypergraphs (e.g., 3D meshes with 50–180 nodes and 3D coordinate features) that are both topologically valid and geometrically realistic, outperforming sequential generation baselines.

2. Generate featured graphs (e.g., point clouds with 1000 nodes and 3D positions) at scales where flat models like DiGress and DeFoG fail due to OOM errors.

3. Generate unfeatured graphs and hypergraphs (SBM, Ego, Tree, Planar, Protein datasets) with state-of-the-art or competitive validity rates and spectral similarity, while maintaining structural constraints (e.g., 100% valid trees, 97% valid planar graphs).

4. Maintain feature consistency across scales—when a parent node is expanded, children inherit appropriate features, and the model refines them conditioned on the parent, producing smooth geometric surfaces rather than disjoint fragments.

5. Train efficiently with the OT coupling and inpainting masking, requiring fewer steps to converge and producing more stable generations across runs (lower variance in metrics).

6. Handle heterogeneous growth rates—regions of the structure that need more detail (e.g., wings of an airplane) expand more than simpler regions (e.g., fuselage), all while keeping the overall structure coherent.

If you implement these improvements, the resulting system will be the first scalable, feature-aware generative model for both graphs and hypergraphs, capable of producing large, realistic structures with continuous features that current state-of-the-art flat models cannot handle.

Graph generative models perform well on small structured data but struggle to scale to large, complex structures. Hierarchical approaches improve scalability but often ignore node and edge features, which are critical in real-world applications, particularly for hypergraphs that model higher-order relationships. In this paper, we propose FAHNES (feature-aware (hyper)graph generation via next-scale prediction), a hierarchical framework that jointly generates topology and features for graphs and hypergraphs. FAHNES builds multi-scale representations through node coarsening and localized expansion, guided by a novel hierarchical scale encoding that controls granularity and ensures cross-scale consistency. Experiments on synthetic, 3D mesh, and graph point cloud datasets demonstrate competitive or state-of-the-art performance while uniquely scaling to featured large-scale graphs and hypergraphs. Our code is open source