Pith. sign in

REVIEW 3 major objections 5 minor 15 references

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

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read FAHNES claims to be the first hierarchical generative model that jointly produces topology and features for graphs and hypergraphs, scaling to roughly a thousand nodes with quasi-linear cost.

desk verdict Real contribution with solid experiments; the unproven quasi-linear complexity claim and thin baseline error bars are the main things to fix in review. read the letter →

arxiv 2506.01467 v3 pith:2AJW6663 submitted 2025-06-02 cs.LG cs.DM

Dorian Gailhard , Enzo Tartaglione , Lirida Naviner , Jhony H. Giraldo This is my paper · ORCID
classification cs.LGcs.DM
keywords hypergraphgenerationgraphhierarchicalgenerativemodelsflowmatchingscaleencodingoptimaltransportcoupling3Dmeshpointcloud
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

FAHNES is a hierarchical generative model that generates both the topology and the node/hyperedge features of graphs and hypergraphs in one coarse-to-fine pass. The paper's central claim is that it is the first such method to scale to large featured structures, running in $\mathcal{O}((n+m+k)\log n)$ time for a hypergraph with $n$ nodes, $m$ hyperedges, and $k$ incidences, while matching or beating flat diffusion generators on small datasets and remaining the only tested approach that generates featured point clouds of roughly a thousand nodes. This matters because flat generators pay quadratic cost over all possible edges, which blocks real-world structures such as 3D meshes and point clouds, and earlier hierarchical generators ignore features. If the claim holds, joint topology–feature sampling becomes practical at sizes that previously forced sequential or featureless generation.

What carries the argument

The central object is the coarsening–expansion pair defined on a featured bipartite graph, driven by a hierarchical scale encoding: an integer per cluster, initialized to 1 for each node and hyperedge, summed when clusters merge, and split among children when clusters expand. Expansion clones each parent's connectivity and features into two or three children; refinement prunes spurious edges, redistributes scale encodings, and predicts refined features, with cluster-wise barycenters shown to be the optimal coarsened features. A multi-scale graph optimal-transport coupling generalizes minibatch optimal-transport couplings, restricting permutations to children of the same cluster so alignment stays exact and cheap. Endpoint flow matching over these variables is the learning engine, and because each expansion step is linear in the current bipartite graph while the number of steps is logarithmic, the pipeline carries the claimed quasi-linear complexity.

What would settle it

Run FAHNES on hypergraphs with known coarsening histories and record the hyperedge and incidence counts at every intermediate level before refinement; any level exceeding the final $m$ or $k$ would refute the stated bound. A complementary check is to measure wall-clock time on synthetic hypergraphs with fixed $n$ and growing $m$ and $k$ and compare the empirical scaling with $\mathcal{O}((n+m+k)\log n)$.

Watch

Extended reading notes

Core claim

Representing each hypergraph by its featured bipartite graph, with left-side nodes for vertices and right-side nodes for hyperedges, FAHNES coarsens training examples by merging vertices and collapsing duplicate hyperedges, then learns to reverse that process. Generation starts from one super-node carrying a scale encoding equal to the desired final node count; at each level the model decides how many children each cluster expands into, which duplicated edges to delete, how to split the parent scale encoding among children, and how to refine the children's features. A hierarchical scale encoding records how many final nodes each cluster must produce, giving precise local control over growth, and a multi-scale optimal-transport coupling aligns predicted children with target children within each cluster using only two or six permutations, avoiding permutation noise without changing the flow-matching marginals. The paper's claim is that this joint coarse-to-fine formulation is what allows topology and features to be generated together at sizes where flat models run out of memory, with structural fidelity competitive with flat state-of-the-art methods on small graphs.

Load-bearing premise

The complexity guarantee assumes that every intermediate coarse level has no more hyperedges or incidences than the final hypergraph, yet expansion duplicates all parent edges before refinement removes the extras, so the advertised $\mathcal{O}((n+m+k)\log n)$ bound is not actually guaranteed.

Editorial extensions

If this is right

  • A single coarse-to-fine pipeline replaces flat graph generators, making feature-aware generation feasible on graphs and hypergraphs with hundreds to thousands of nodes.
  • Because hypergraphs are handled through their bipartite representation, the same method covers 3D meshes, where faces become hyperedges, and point clouds, where local neighborhoods become edges.
  • Generating topology and features jointly beats the sequential 'topology first, then features' baseline on mesh datasets, since features guide where refinement should happen.
  • Scale encodings improve node-count accuracy and prevent gradient dilution from static nodes, yielding higher validity on structured datasets like trees, ego-networks, and planar graphs.
  • Under the quasi-linear complexity claim, the model is the only tested generator that produces featured point clouds of about 1,000 nodes without running out of memory.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct test of the complexity claim would instrument the sampler to count intermediate hyperedges and incidences; if those counts regularly exceed the final values, the asymptotic guarantee would need revision even if empirical scaling looks fine.
  • The scale-encoding mechanism looks transferable to other structured-data domains, such as molecules or circuit netlists, but the paper's continuous-feature assumption would need extra components for categorical or multi-modal attributes.
  • The optimal-transport coupling stays cheap only because clusters expand into two or three children; applying it to larger clusters would improve global alignment but at factorial cost, so a hierarchical or approximate coupling would be the natural next step.
  • The 'only method that scales' conclusion is drawn against flat models and featureless hierarchical baselines; another feature-aware hierarchical model would be the true competitive test.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces FAHNES, a hierarchical generative framework for graphs and hypergraphs that jointly models topology and node/hyperedge features. The method builds multi-scale representations by spectrum-preserving coarsening, then learns to invert the coarsening through localized expansion and refinement, using a hierarchical scale encoding and a multi-scale graph optimal-transport coupling. Experiments cover unfeatured hypergraphs and graphs, 3D meshes, and graph point clouds, and the authors claim that FAHNES is the first hierarchical method to generate both topology and features with quasi-linear complexity, uniquely scaling to large featured structures where flat baselines run out of memory. The paper includes proofs of four propositions, detailed appendices, and open-source code.

Significance. If the central claims hold, FAHNES fills a real gap: existing hierarchical graph/hypergraph generators (HSpectre, HYGENE) ignore features, while feature-aware flat models (DiGress, DeFoG) do not scale. The empirical results on ManifoldNet meshes and point clouds are promising, with lower Chamfer distance than the sequential and flat baselines, and the ablations support the value of the scale encoding and OT coupling. The paper also ships machine-checkable proofs for Propositions 1–4 and open-source code, which are strengths. However, the quasi-linear complexity claim rests on an unproven assumption about intermediate edge counts, and the graph-generation results are uneven, with DeFoG clearly outperforming FAHNES on SBM validity. These issues affect the headline scalability and state-of-the-art claims, so the paper needs revision before the contribution is fully established.

major comments (3)
  1. [Appendix H; Definition 2; Table 3] The quasi-linear complexity claim O((n+m+k) log n) rests on the assumption k_l ≤ k and m_l ≤ m for all levels, which Appendix H explicitly states as an expectation ('the model is expected to learn accurate edge refinement and avoid such accumulation') rather than a proved property. Definition 2 clones every incident edge of each parent before refinement, so a single expansion can multiply incidences by up to v_L^max · v_R^max (up to 6 under Algorithm 5 and the cluster-size constraints), and Definition 3 imposes no budget or capacity constraint on edge removal. Nothing in the analysis rules out intermediate incidence counts Ω(nm), which would make the per-level cost Ω(nm) and the total cost Ω(nm log n). Because no wall-clock or peak-memory scaling measurements are reported (Table 3 only shows that flat baselines run out of memory), the 'quasi-linear complexity' bullet and the 'only method that scales' conclusion in Section 5.2 are not established by the supplied analysis.
  2. [Table 2; Section 5.2] The claim of 'competitive or state-of-the-art performance' on graphs is uneven: on SBM graphs FAHNES achieves Valid = 50.0±5.0 versus DeFoG's 90.0±5.1, while the ratio metric is 4.8±0.7 versus 4.9±1.3, i.e., comparable on ratio but far behind on validity. Section 5.2 states that FAHNES 'obtains competitive results compared to state-of-the-art flat methods on small-graph datasets,' but this comparison should be qualified, and the abstract's state-of-the-art claim should be restricted to the datasets where it actually holds.
  3. [Section 5.4; Section 3.1] Section 5.4 concedes that FAHNES 'still struggles when generating very large hypergraphs... or very large graphs, such as point cloud datasets,' while Section 3.1 and the abstract emphasize scalability. These statements are not necessarily contradictory, but the paper should reconcile them: the only large-scale successes shown are point clouds and meshes with roughly 1,000 nodes, while the limitation text suggests quality degrades substantially on large structures. A precise statement of the regime where the scalability claim is intended to hold would strengthen the contribution.
minor comments (5)
  1. [Appendix E.3] The baseline name is written 'Defog' in Appendix E.3 but 'DeFoG' elsewhere; please make the spelling consistent.
  2. [Section 3.5, Eq. (6)] Equation (6) uses P ∈ Π_n but defines X, Y ∈ R^{B×d}; the relationship between n and B, and whether P acts on the left or right, should be clarified.
  3. [Algorithm 5] The thresholds 1.66 and 2.33 used to map continuous hyperedge-expansion predictions to discrete counts are unexplained; please state how they were chosen.
  4. [Appendix C vs. Section E.1] Appendix C states a preserving eigenspace size of k=8, while Section E.1 reports K=2 for the spectral SignNet features; please disambiguate these two different uses of 'k' or correct the inconsistency.
  5. [Tables 1 and 7] The spacing in baseline names such as 'V AE' and 'V AE' should be normalized to 'VAE' throughout the tables and text.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the central claim (joint topology-and-feature generation with scale encodings and OT coupling) is not a restatement of its inputs; the main caveat is an unsupported complexity assumption, which is a correctness risk rather than a circular step.

full rationale

Walking the derivation chain, FAHNES builds on explicit algorithmic definitions (Definitions 1-3) and proves its supporting statements from those definitions: Proposition 1 follows from minimizing a convex MSE objective, and Propositions 2-4 are consequences of the minibatch/OT coupling and loss-masking procedures. The scale encoding is not a relabeling of an existing fitted quantity: Remark 1 explicitly contrasts it with the cluster-size vectors of HSpectre, and the ablation studies test it as a component. The multi-scale OT coupling is defined as a permutation optimization and is shown to preserve marginals by an isomorphism argument; it is not a fitted parameter renamed as a prediction. The main reliance on self-citations (Gailhard et al., 2025) is an inheritance of the coarsening-expansion machinery, which is prior published work, and the paper's new claim (joint topology and feature generation with hierarchical scale encodings) is not reduced to that citation. The strongest concern, Appendix H's assumption that k_l <= k and m_l <= m for all levels, is an empirical expectation rather than a proved bound; this undermines the quasi-linear-complexity claim as a correctness/scalability risk, but it is not a circular equivalence or a fitted-input-called-prediction. Section 5.4 also candidly acknowledges remaining scalability failures. No circular step meets the evidentiary bar of this review.

Assumptions & free parameters 6 free parameters · 7 assumptions · 1 invented entities

The central method rests on a set of modeling choices made by the authors: a Markovian decomposition of expansion sequences, bounded cluster sizes, spectrum-preserving coarsening, endpoint flow matching with hand-chosen priors, and an unproved bound on intermediate edge counts. These are not fitted constants pulled from data; they are assumptions that shape what FAHNES can generate and how the complexity claim holds. None of them is independently benchmarked outside the paper.

free parameters (6)
  • Coarsening reduction fraction range [rho_min, rho_max] = [0.1, 0.3]
    Chosen by hand to control how aggressively graphs are coarsened during training; affects the number of expansion levels and the difficulty of the inverse problem.
  • Coarsening randomization parameter lambda = 0.3 (0.1 for mesh datasets)
    Greedy randomized acceptance probability in Algorithm 1; hand-tuned per dataset.
  • Spectral conditioning size K = 2 for most graph datasets, 0 for meshes and point clouds
    Number of Laplacian eigenvalues and eigenvectors fed to SignNet; chosen by hand.
  • Flow matching sampling steps = 256 for graphs, hypergraphs, and point clouds; 25 for meshes
    Number of numerical integration steps at inference; affects sample quality and cost.
  • Perturbed expansion radius and probability = radius=2, dropout=0.5
    Random extra edges added during expansion to avoid overfitting; hand-tuned.
  • Dirichlet prior concentration alpha = 1.5
    Prior for scale encoding split fractions in flow matching; chosen by hand.
assumptions (7)
  • domain assumption Expansion sequences factorize in a Markovian way: each refinement depends only on the immediate coarser graph (Appendix A, Eq. 7-10).
    The probabilistic model assumes p(B(l-1)|B(l)) factorizes and that expansion variables are conditionally independent of the expanded graph given the pre-expansion graph; this may fail if coarsening history matters.
  • domain assumption At most two nodes are merged per cluster, so right-side clusters in the bipartite graph contain at most three nodes (Algorithm 1).
    This constraint, inherited from Gailhard et al. 2025, limits the number of candidate permutations in the OT coupling and keeps expansion local, but restricts the space of coarsenings the model can learn.
  • domain assumption Spectrum-preserving coarsening (Loukas 2019) preserves enough information to reconstruct the original topology.
    Section 3.1 relies on this coarsening of the clique expansion; if the reduced spectrum omits features needed to reconstruct local topology, the learned inverse cannot recover it.
  • domain assumption Endpoint flow matching with Gaussian and Dirichlet priors can model discrete expansion decisions and continuous features.
    Section 4 maps discrete decisions to signs of continuous targets; this works empirically but is not a stated equivalence guarantee.
  • domain assumption Intermediate graphs have no more hyperedges or incidences than the final hypergraph (k_l <= k, m_l <= m).
    Appendix H uses this assumption to prove O((n+m+k) log n) complexity; it is stated without proof and can be violated during expansion before refinement deletes duplicate edges.
  • domain assumption Node and hyperedge features are continuous and can be aggregated by weighted averages (Section 3.2).
    The coarsening update averages features, and Section 5.4 states the framework assumes continuous distributions such as 3D coordinates; categorical or multimodal features are out of scope.
  • standard math Swapping equivalent children within a cluster produces isomorphic bipartite graphs, so local permutations do not bias the learned distribution (Proposition 2).
    The proof of Proposition 2 relies on isomorphism invariance; this requires the features and scale encodings of children to be identical at coupling time.
invented entities (1)
  • Hierarchical scale encoding
    purpose: A per-cluster integer vector recording how many fine-level nodes each coarse cluster must expand into, used to condition generation and mask inactive nodes.
    This is an internal representation with no independently falsifiable prediction outside the paper; its benefit is shown only through ablations on the same datasets used to develop the model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Feature-Aware (Hyper)graph Generation via Next-Scale Prediction." pith.science (2026). https://pith.science/paper/2AJW6663

@misc{pith2026250601467,
  author       = {Pith},
  title        = {Pith review of: Feature-Aware (Hyper)graph Generation via Next-Scale Prediction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2AJW6663}},
  note         = {Machine review of arXiv:2506.01467}
}
read the original abstract

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

Figures

Figures reproduced from arXiv: 2506.01467 by the authors.

Figure 1
Figure 1. Examples of generated featured hypergraphs by a se￾quential disjoint generation baseline and our model (FAHNES). or geometric information, such as coordinates in 3D meshes. Despite recent advances, 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 complexi￾ties (Vigna… view at source ↗
Figure 2
Figure 2. Our framework adopts a coarsening-expansion strategy. i) During training, input hypergraphs are progressively coarsened by merging nodes and hyperedges, yielding a multiscale representation. Node features are averaged during merging, and scale encodings are summed. ii) The model is then trained to predict which nodes were merged at each scale. iii) In the expansion phase, merged nodes (shown in dark in the leftmost … view at source ↗
Figure 3
Figure 3. Examples of coarsening sequence for various meshes and point clouds. Thick lines represent 2-edges. Edges are omitted in point clouds for clarity. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Edge structure is preserved:(v, w)∈ E1 ⇐ ⇒(σL(v), σR(w))∈ E2,

    work page

  2. [2]

    Scale encodings are preserved:b 1(v) =b 2(σL(v))for allv∈ V 1 L,b 1(w) =b 2(σR(w))for allw∈ V 1 R,

    work page

  3. [3]

    Node and hyperedge features are preserved:F 1 L(v) =F 2 L(σL(v)),F 1 R(w) =F 2 R(σR(w)). Proof. Let B= (V L,V R,E,x 1) be an arbitrary target bipartite graph, and f be an arbitrary test function defined on bipartite graphs. To alleviate notations, we will denote f(x) the value of f for the same bipartite graph where values of x1 are replaced by those ofx....

    work page 2024

  4. [4]

    Our model (4M parameters) is trained for 1M steps on the topology of mesheswithoutlearning to generate the features

    work page

  5. [5]

    A simple Local PPGN model (4M parameters) is trained for 20 epochs as a flow-matching model to learn to generate the 3D positions, with the topology fixed

    work page

  6. [6]

    Additionally, we compare our method to the following three simple baselines:

    We use the best checkpoint of the first model to generate the topology, then apply the second model on this topology to generate the 3D positions. Additionally, we compare our method to the following three simple baselines:

    work page

  7. [7]

    A flow-matching model of 6M parameters, using self-conditioning

    work page

  8. [8]

    A Wasserstein GAN whose generator has 23M parameters and critic has 7M parameters

    work page

Show all 15 references
  1. [9]

    All models are trained for 100 epochs using the following framework: • Each model is trained to produce binary images where white pixels signify node-hyperedge membership

    A V AE with 23M parameters. All models are trained for 100 epochs using the following framework: • Each model is trained to produce binary images where white pixels signify node-hyperedge membership. An additional set of 3 dimension is concatenated to the row for each node, co...

    2024

  2. [10]

    These encodings are replicated according to the respective expansion numbers

    Positional encoding:Node positions within the graph are encoded using SignNet (Lim et al., 2022). These encodings are replicated according to the respective expansion numbers. 23 Feature-Aware (Hyper)graph Generation via Next-Scale Prediction

    2022

  3. [11]

    FiLM conditioning (Perez et al., 2018) is applied to incorporate contextual information into node and hyperedge features

    Attribute embedding:Five separate linear layers are used to embed the bipartite graph attributes: left node features, right node features, edge features, node-specific features, and hyperedge-specific features. FiLM conditioning (Perez et al., 2018) is applied to incorporate c...

    2018

  4. [12]

    Graph processing:The attribute-enriched bipartite graph is processed through a stack of sparse PPGN layers, following the architecture from (Bergmeister et al., 2024)

    2024

  5. [13]

    • Left node head: Predicts expansion values, scale encoding splits, and refined node features

    Output prediction:The final graph representations are passed through three linear projection heads to generate outputs. • Left node head: Predicts expansion values, scale encoding splits, and refined node features. • Right node head: Predicts hyperedge expansions and refined h...

    2024

  6. [14]

    Randomcorresponds to random mergings of nodes, where the local variation cost in Algorithm 1 is replaced by a random value

  7. [15]

    Results are shown in Table 12

    Featurecorresponds to mergings that prioritize pairs of adjacent nodes with similar features, where the local variation cost in Algorithm 1 is replaced by the squared Euclidean distance between features. Results are shown in Table 12. Table 12.Ablations on the coarsening strat...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.