acceptodds
Under review as a conference paper at ICLR 2027

GraphonFlow: Learning Latent Graphon Distributions for Structure-Preserving Graph Generation

Abstract

Graph generative models must capture complex structural dependencies while preserving domain-specific constraints. However, existing flow-based approaches typically initialise generation from independent noise or fixed priors, leaving the flow model to recover much of the target structure during generation. We propose GraphonFlow, a probabilistic framework that learns a latent-conditioned structured source distribution for flow-based graph generation. Our key idea is to integrate latent graph representation learning with graphon modelling, providing an informative structural starting point for subsequent flow learning. A two-stage training strategy first learns the latent representation and graphon-based source, and then freezes this source while learning a conditional velocity field that transforms structured source samples toward target graphs. To support structure-preserving generation, GraphonFlow further incorporates canonical graph representations for consistent graphon learning and connectivity-aware regularisation across the generative process. Experiments on four molecular benchmarks and three synthetic graph families demonstrate competitive performance in chemical validity, diversity, and structural fidelity. Extensive ablations further demonstrate the importance of the learned graphon source, canonical representation, two-stage optimisation, and connectivity-aware learning. Overall, our results show that learning the source distribution itself provides an effective alternative to initialising graph flows from unstructured or fixed priors.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Generation, Flow Matching, Graph Neural Networks

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_e5yoOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

Contributions:

  • Introduce a novel two-step generative model for graphs: Step one generates a draft graph together with an embedding, step 2 refines the draft with help of the embedding. Step one applies a VAE with graphons, step two uses flow matching
  • Empirically demonstrate competitive performance on molecule + synthetic graph generation benchmarks
Critical strengths
  • Novel approach for graph generation. I believe that the two-step graph generation process is an interesting pattern that can be applied in lots of variations
  • Strong empirical results
Critical weaknesses

The empirical results expose substantial gaps that make the empirical performance hard to judge:

  • Key metrics are missing: GuacaMol misses FCD, Moses misses validity, filters, and FCD.
  • Missing baseline: A current SOTA model, GraphBSI [1], is missing from empirical results
  • The ablations do not sufficiently uncover how much performance can be attributed to each step

Also, the clarity could be improved.

[1] Petersen, Ole, et al. "Discrete Bayesian Sample Inference for Graph Generation." International Conference on Learning Representations. Vol. 2026. 2026.

Questions for authors
  • Would you mind adding the missing SOTA baseline, GraphBSI [1] as well as the missing key molecular metrics?
  • Please clarify your contributions!
  • The method has a lot of sub-systems, and the paper does not sufficiently evaluate the contribution of each of them. In particular, I am interested in:
    • The performance of your flow matching model without graphon priors but with a non-learned prior
    • The performance of your flow matching model without conditioning on the embedding z
    • The performance of the graphon samples themselves without flow matching refinement
    • What happens when you swap out different parts of the system? E.g. use discrete diffusion, BFNs, or BSI for the refinement step instead of flow matching? Is there something that makes the graphons/VAE/flow matching combination especially powerful?
3 comments

We sincerely appreciate the reviewer's thoughtful comments and constructive feedback.

Q1. Would you mind adding the missing SOTA baseline, GraphBSI [1] as well as the missing key molecular metrics?

We have updated Table 2 in the revised manuscript to include the previously missing metrics and GraphBSI baseline.

Q2. Please clarify your contributions.

We would like to clarify the main contributions of GraphonFlow:

  1. Unlike existing graphon-based methods that primarily estimate graphons for graph reconstruction, or flow-based approaches such as Flowette that employ predefined structural priors, GraphonFlow learns a distribution of graph-specific graphons conditioned on graph-level latent representations (Sec. 3.1). The latent-conditioned graphon serves two complementary purposes: it acts as a probabilistic Bernoulli decoder for adjacency reconstruction during Stage 1 and provides a learned structural source distribution for continuous-time flow matching during Stage 2. This allows the source distribution to adapt to connectivity patterns observed in the training data, rather than relying on a manually specified graphon or unstructured noise.

  2. Graphon reconstruction is challenging because equivalent graphs can be represented by different node permutations, producing inconsistent reconstruction targets. We address this through canonical graph labelling with property-aware vertex colouring, establishing a consistent coordinate representation for learning graphon surfaces (Sec. 3.1 and Appendix C). Unlike explicit graph-to-graph optimal transport alignment, this approach does not require learning additional alignment parameters or computing pairwise source–target graph matching during flow training. The controlled canonicalisation ablations in Table 8 demonstrate the contribution of consistent structural supervision.

  3. GraphonFlow introduces a two-stage generative framework that learns a latent-conditioned graphon as a probabilistic structural source, followed by flow matching to refine the generated graphs towards the target distribution (Secs. 3.1–3.2). After learning the graphon-based source, we freeze the Stage 1 model and train a conditional velocity field that jointly evolves adjacency, node attributes, and edge attributes. Unlike approaches that use graphons solely as final graph decoders, GraphonFlow uses the learned graphon to initialise generation, while flow matching transports the resulting graph states towards the target distribution. The controlled source-prior ablations (Table 7) demonstrate that latent-conditioned graphon sources outperform Erdos-Renyi and unconditional graphon sources under the same flow-matching framework. Furthermore, Table 9 demonstrates the benefits of sequential two-stage training over joint optimisation.

  4. We introduce complementary connectivity-aware objectives at the two learning stages (Sec. 3.3 and Appendix G.5). The graphon-level connectivity regulariser encourages structurally coherent source graphs, while the spectral objective incorporates algebraic connectivity into flow learning. Together with the graph-aware velocity network and domain-specific constraints, these objectives promote structural fidelity during generation. Their individual contributions are evaluated through the regularisation ablations in Tables 10 and 11.

Overall, our key contribution is not simply combining a graph VAE with flow matching, but learning a graph-dependent probabilistic structural source that is subsequently refined through continuous-time transport. Canonical supervision makes this structural learning permutation-consistent, while connectivity-aware objectives improve the structural properties of the generated graphs. The controlled ablations in Tables 7-11 isolate the roles of these components and support their contributions beyond the overall benchmark comparisons.

Q3. Ablation study.

  • The performance of your flow matching model without graphon priors but with a non-learned prior.

This comparison is already included in Table 7 (Appendix I.5.1).

  • The performance of your flow matching model without conditioning on the embedding z.

This ablation is also included in Table 7, where the unconditional graphon (UG) removes dependence on the graph-level latent variable zgz_g, while retaining the same flow architecture and attribute-generation mechanism.

  • The performance of the graphon samples themselves without flow matching refinement.

We have added a controlled ablation in Appendix I.5.7 (Table 13), comparing standalone Stage 1 graphon samples with the complete GraphonFlow framework.

  • What happens when you swap out different parts of the system?

We have added a controlled refinement-swap ablation (Appendix I.5.8, Table 14), replacing Stage 2 FM with a DiGress-style Discrete-Diffusion (DD) model while keeping the learned Stage 1 graphon-VAE fixed.

Thank you for clarifying the contributions and being more transparent regarding empirical results! I will raise the score.

Esteemed Reviewer,

Thank you for such a quick reply, engaging with our work and helping to make it better. Rest assured we will implement all requested improvements.

Meantime, kindly let us know if there is anything else we can answer or improve.

Best regards,
Authors

Reviewer_aMQoOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes GraphonFlow, a latent graph flow matching method that leverages a more informed initialization of denoising process for improved performance. In particular, this initialization leverages graph structural information through a graphon-based formulation, instead of the usual fixed priors, with random independent node and edge initializations. This design modification is motivated by alleviating the flow model from having to recover the whole graph during generation. GraphonFlow, however, does not work as usual latent flow models (encode to latent, diffuse in latent, decode to raw space): their first stage is to learn latent-conditioned graphon, node, and edge-attribute generators. The second stage used these three latent conditioned components to generate the initial point for a flow matching denoising formulation. Therefore, the iterative denoising still occurs in the raw space. The paper provides theoretical details on their formulation and extensive experimental results. The method demonstrates strong performance, although with marginal to no gains (specially in the synthetic settings) with respect to strong baselines. Additionally, the paper is reproducible: the authors provide implementation details, protocols, and hyperparameters, as well their code.

Critical strengths
  1. The paper addresses a relevant problem, which remains largely unsolved in previous graph generation papers (to the best of my knowledge): how to more effectively initialize graph iterative refinement models in a graph meaningful way.
  2. The paper is overall sound: it is cleanly formulated, written, and theoretically analysed; it is extensively empirically tested as well.
Critical weaknesses
  1. The proposed method fully relies on canonization of the graphs. This step is done via McKay's nauty algorithm. As appropriately addressed by the authors "refinement-and-search procedure can require an exponential, and in the worst case potentially factorial-sized, search tree". Therefore, from my perspective this harms the proposed paper in 3 main ways:

    a. Scalability: the method can only be applied to small graphs. However, graphons consist of limits of dense graphs when the number of nodes increases (goes to infinity). Therefore, the motivation of using graphons for initialization, while being severely bound to small graphs seems a contradiction in the formulation. Additionally, from all the datasets explored, only one (SBM) has an associated graphon.

    b. Preprocessing runtime: in the reported training and sampling runtimes, it is not clear if the canonization times were included in the measured times. If not, this could be highly unfair for the baselines. The authors should clarify this detail. If the canonization times were not included, please report it.

    c. Canonizing graphs serializes graphs into sequences, thus making the object treated in this paper amenable to usual sequence models. From previous work, this seems to significantly improve performance (e.g, SMILES/Autoregressive models vs diffusion in [1]). It is therefore natural to raise two related questions: i) GraphonFlow may be just solving an easier problem than the remaining baselines considered (which are inherently permutation invariant/equivariant); ii) the graph-specific architecture may be no longer needed at all.

  2. GraphonFlow has a very complex training pipeline: it is composed of two stages (the authors motivate this 2-stage training procedure based on empirical performance vs a single joint optimization stage). The first stage has a loss composed of 6 terms, with 4 constants to balance their contribution (eq. 19); The second stage has a loss composed of 4 terms, with 3 balancing constants (eq. 20). This makes the method highly non-practical. Moreover, the ablations on the different regularization components of the loss (Tables 10 and 11), demonstrate that the performance of the method is severely harmed by removing each of these terms, which hints that the method is significantly non-robust/unstable. This raises serious concerns on its difficulty to train.

Questions for authors

Clarification requests:

  1. Would it be possible to add the remaining metrics for the synthetic graph benchmarks, as proposed in [2]? I want to have a better picture of GraphonFlow's performance with respect to the baselines in synthetic settings.
  2. Would it be possible to extend the method such that it can avoid the canonization dependency? For example, following an approach similar to [3], where the ordering of the nodes is preserved along the encoding, denoising, and decoding processes.
  3. Recent work motivates the utilization of graphons for scalability of graph generation, e.g., [4]. Did you perform any scalability analysis of your method vs baselines? This would shed light on the weaknesses raised as well.

Suggestions for Future Work:

  1. If the graph is modelled as a "continuous graph state", i.e., the adjacency matrix, AtA_t, the node features, XtX_t, and the edge features, EtE_t are all continuous, you lose the possibility of leveraging properties of actual graphs and have to compute full attention; Could it be beneficial to re-formulate the problem again in the graph-domain (to explicitly leverage graph properties, such as sparsity)?

[1] - DiGress: Discrete Denoising Diffusion for Graph Generation, Vignac et al., ICLR 2023

[2] - Efficient and Scalable Graph Generation through Iterative Local Expansion, Bergmeister et al., ICLR 2024.

[3] - Principled Latent Diffusion for Graphs via Laplacian Autoencoders, Siraudin et al., arXiv 2026.

[4] - DiPhon: Diffusion on Graphons for Scalable Graph Generation, Rozada et al., NeurIPS 2026.

10 comments

We sincerely appreciate the reviewer's thoughtful comments and constructive feedback.

*Weaknesses

W1(a). Scalability: Does relying on NAUTY restrict GraphonFlow to small graphs, contradicting the motivation for using graphons as limits of dense graphs? Why is SBM the only dataset with an associated graphon?

We agree that NAUTY's worst-case complexity is an important consideration for scalability. However, the graphon-based structural formulation and the computational cost of canonicalisation are distinct issues, and their combination does not create a theoretical contradiction. Assuming the reviewer's good graces, we would like the opportunity to clarify a number of points on this issue.

First, graphons are not restricted to generating dense or infinitely large graphs. Although classical graphon theory characterises limits of dense graph sequences, a graphon also defines a probabilistic connectivity model for finite graphs. In GraphonFlow, the learned latent-conditioned graphon Wψ(si,sj∣zg)W_\psi(s_i,s_j\mid z_g) generates source adjacency through A0,ij∼Bernoulli(Wψ(si,sj∣zg))A_{0,ij}\sim\mathrm{Bernoulli}(W_\psi(s_i,s_j\mid z_g)) (Sec. 3.1, Eqs. 7–8). Furthermore, Appendix E.3 (Eq. 86) explicitly discusses size-dependent graphon sparsification, Wn(x,y)=ρnW(x,y)W_n(x,y)=\rho_nW(x,y), where ρn→0\rho_n\to0. Under this formulation, E[m]∈Θ(ρnn2)\mathbb{E}[m]\in\Theta(\rho_n n^2), and choosing ρn=Θ(1/n)\rho_n=\Theta(1/n) yields bounded expected average degree. Our implemented model similarly controls source connectivity through the learned latent-dependent factor ρ(zg)\rho(z_g).

Second, GraphonFlow does not assume that observed graphs originate from a known graphon. Instead, it learns graph-dependent connectivity distributions directly from observed adjacency structures through the Stage 1 probabilistic reconstruction objective (Sec. 3.1, Eqs. 10–11). While SBM admits an explicit block-constant graphon representation, Tree, Ego-small, and molecular datasets do not have predefined underlying graphons. We deliberately evaluate these additional datasets to demonstrate that GraphonFlow can learn useful graphon-based structural sources even when the underlying graph-generating process is not specified by a graphon. The subsequent flow-matching and structural objectives further refine these sources to capture graph dependencies and domain-specific constraints.

Third, canonicalisation is a preprocessing requirement rather than an inherent limitation of graphon-based generation. We acknowledge that NAUTY has graph-dependent worst-case complexity. However, canonical permutations are deterministic and can be computed once per training graph and reused across training epochs and both optimisation stages, avoiding repeated canonicalisation when precomputation is employed. Moreover, NAUTY is not required during unconditional generation (Algorithm 3, Appendix G.8). We nevertheless recognise that canonicalisation and the current pairwise graph representation impose practical limitations for larger graphs (Appendix H). To further assess computational scalability, we conducted a controlled graph-size scaling experiment (see our response to Q3) on Tree and SBM graphs with up to 1000 nodes. The results demonstrate that GraphonFlow achieves lower training times than Flowette under both online and precomputed correspondence protocols across the evaluated varying graph sizes.

W1(b). Preprocessing runtime: Are the canonicalisation times included in the reported training and sampling runtimes in Table 6? If not, is the comparison with baselines fair?

We clarify that the training runtimes reported in Table 6 include the canonicalisation preprocessing cost, together with Stage 1 structural learning and Stage 2 flow-matching optimisation. Thus, the reported times reflect the complete training pipeline rather than excluding canonicalisation overhead.

In GraphonFlow, NAUTY canonicalisation establishes consistent correspondence between observed graph structures and graphon coordinates during training (Algorithm 2, Appendix E.1). Since canonicalisation is deterministic and independent of model parameters, the canonical permutation can be computed once per training graph and reused across both training stages. Importantly, canonicalisation is not required during unconditional generation (Algorithm 3, Appendix G.8), so it introduces no additional inference-time overhead.

Under the reported experimental settings, GraphonFlow achieves training times of 7.00, 14.70, and 46.80 hours on QM9, ZINC250K, and MOSES, respectively, compared with 7.46, 15.35, and 48.18 hours for Flowette (Table 6). These results demonstrate that GraphonFlow remains computationally competitive despite its additional structural-learning stage and canonicalisation preprocessing. We will explicitly clarify the inclusion of canonicalisation time in the Table 6 caption and runtime analysis to avoid ambiguity.

W1(c)(i). Does canonicalising graphs into sequences mean GraphonFlow is solving an easier problem than permutation-invariant/equivariant baselines?

We acknowledge that canonicalisation provides an additional inductive bias compared with methods operating directly on arbitrary node permutations. However, canonicalisation does not convert GraphonFlow into an autoregressive sequence model or eliminate the challenge of learning graph distributions. Instead, it establishes consistent structural coordinates for graphon supervision, ensuring that isomorphic graphs induce equivalent reconstruction targets (Sec. 3.1; Theorem 3, Appendix C). GraphonFlow still operates on the complete graph state Gt=(At,Xt,Et)G_t=(A_t,X_t,E_t), jointly modelling topology, node attributes, and edge attributes through continuous-time transport (Sec. 3.2).

The contribution of canonicalisation is explicitly evaluated in Table 8 (Appendix I.5.2). On QM9, the Bernstein model achieves 88.67% validity with random permutations, 93.10% without canonicalisation, 96.20% with canonicalisation but without positional conditioning, and 99.93% with the complete formulation. These results confirm that canonicalisation contributes to performance, while also demonstrating that the full improvement cannot be attributed to canonical ordering alone, since position-conditioned latent modelling provides additional gains. We therefore acknowledge the representational advantage introduced by canonicalisation while emphasising that GraphonFlow continues to learn graph distributions rather than autoregressive graph sequences.

W1(c)(ii). Does canonicalisation eliminate the need for a graph-specific architecture?

Canonicalisation establishes a consistent node ordering, but it does not eliminate the relational dependencies that characterise graph data. Even with canonical coordinates, the generative model must capture interactions among node attributes, pairwise connectivity, and edge attributes while respecting graph-specific structural constraints.

GraphonFlow therefore employs an edge-aware GNN Transformer (Appendix G.4), where the evolving adjacency AtA_t provides a structural bias in attention, pairwise edge representations participate in message passing, and the model jointly predicts adjacency, node-attribute, and edge-attribute velocities. The predicted adjacency and edge-attribute updates are symmetrised to preserve undirected graph structure. While a generic Transformer could also operate on canonically ordered graphs, it would not automatically incorporate these graph-specific inductive biases. Thus, canonicalisation and the graph-aware backbone serve complementary purposes: the former provides consistent structural correspondence, while the latter explicitly models relational interactions during continuous-time transport.

W2(a). Does the two-stage training pipeline, with six loss terms in Eq. 19 and four loss terms in Eq. 20, make GraphonFlow highly complex and impractical?

We acknowledge the additional objective terms, but each serves a distinct probabilistic or structural purpose, and the two stages are trained sequentially without alternating optimisation.

Stage 1 (Eq. 19) learns the structural source: LXL_X, LEL_E, and LgraphonL_{\mathrm{graphon}} constitute the VAE reconstruction objective, while LKLL_{\mathrm{KL}}, Lℓ1L_{\ell_1}, and LconnL_{\mathrm{conn}} enforce prior consistency, compact graphon representations, and connectivity, respectively. Stage 2 (Eq. 20) learns the velocity field through LvelL_{\mathrm{vel}}, with LendL_{\mathrm{end}} providing (1−t)2(1-t)^2 reweighting of the squared velocity residual (Appendix G.5; Flowette [5], Appendix E.3, Eq. 38). The valence and spectral terms enforce chemical and connectivity constraints; valence is disabled for synthetic graphs.

Two-stage optimisation also improves training stability: joint updates continually alter the source distribution and flow targets, whereas freezing Stage 1 provides a fixed source-generating mechanism. Table 9 (Appendix I.5.3) supports this design: compared with joint training, two-stage optimisation improves QM9 validity from 95.90% to 99.93% (NSPDK: 0.0016 to 0.0002) and ZINC250K validity from 96.50% to 99.93% (NSPDK: 0.0013 to 0.0004).

Regarding practicality, Stage 1 is trained only once and then frozen, so the method does not require alternating optimisation or repeated structural-model retraining. Furthermore, end-to-end training times remain competitive with Flowette (Table 6): 7.00 vs. 7.46 hours on QM9, 14.70 vs. 15.35 hours on ZINC250K, and 46.80 vs. 48.18 hours on MOSES. Thus, although GraphonFlow has a more involved objective than simpler generative models, its components serve identifiable modelling purposes, and the controlled optimisation and runtime comparisons demonstrate that this additional complexity remains computationally practical on the evaluated benchmarks.

W2(b). Do the ablations in Tables 10 and 11 indicate that GraphonFlow is non-robust, unstable, and difficult to train because removing regularisation terms severely harms performance?

We agree that Tables 10 and 11 show substantial performance degradation when certain regularisation terms are removed. However, these ablations evaluate the functional contribution of individual objectives, rather than optimisation instability or sensitivity to small hyperparameter changes. Removing an entire regulariser is fundamentally different from perturbing its coefficient around the selected value.

In Stage 1 (Table 10), the KL objective is particularly important because the encoder samples latent variables from posterior distributions during training, whereas unconditional generation samples from their learned priors. Removing LKLL_{\mathrm{KL}} weakens this alignment, reducing QM9 validity from 99.93% to 87.15% and increasing NSPDK from 0.0002 to 0.0195. The remaining regularisers address distinct properties: removing Lℓ1L_{\ell_1} retains 95.37% validity, while removing LconnL_{\mathrm{conn}} yields 92.32% validity. These results demonstrate differing contributions to structural-source quality rather than a general failure of optimisation whenever a regulariser is removed.

In Stage 2 (Table 11), the endpoint objective is mathematically linked to velocity prediction. Under the interpolation (Gt=(1−t)G0+tG^1G_t=(1-t)G_0+t\widehat G_1), the predicted endpoint satisfies: G~1−G^1=(1−t)(vθ−ut)\widetilde G_1-\widehat G_1=(1-t)(v_\theta-u_t), where ut=G^1−G0u_t=\widehat G_1-G_0.

Consequently, under the same squared-error norm, LendL_{\mathrm{end}} corresponds to a (1−t)2(1-t)^2 reweighting of the velocity residual LvelL_{\mathrm{vel}}, emphasising accurate predictions earlier in transport (Appendix G.5; Theorem 10). Removing this objective reduces QM9 validity from 99.93% to 74.10%. Similarly, removing LvalL_{\mathrm{val}} reduces validity to 81.35%, while removing LspecL_{\mathrm{spec}} retains 91.56% validity but increases NSPDK to 0.0030. These changes are consistent with the respective roles of endpoint accuracy, chemical feasibility, and structural connectivity.

These results establish that the regularisation terms address meaningful and complementary failure modes; they do not, by themselves, demonstrate unstable optimisation.

Questions

Q1. Would it be possible to add the remaining metrics for the synthetic graph benchmarks, as proposed in [2], to provide a better picture of GraphonFlow's performance against baselines?

To address this concern, we have updated Tables 3 and 4 in Appendix I.1 to include the previously missing synthetic graph evaluation metrics: the eigenvalue-based spectral discrepancy of the normalised graph Laplacian (Spec.), wavelet-based graph statistics (Wavelet), and the Ratio metric, following the evaluation protocol in [2]. These additional metrics complement the existing degree, clustering, and orbit statistics, providing a more comprehensive assessment of structural fidelity against the available baselines. The updated results show that GraphonFlow achieves competitive performance across these additional structural measures on both Tree and SBM graphs. We kindly refer the reviewer to the revised Tables 3 and 4 for the extended comparisons.

Q2. Would it be possible to extend GraphonFlow to avoid the canonicalisation dependency, for example by preserving node ordering throughout encoding, denoising, and decoding as in [3]?

Yes, in principle, canonicalisation could be avoided, but this would require modifying how GraphonFlow establishes consistent graphon-coordinate supervision. Canonicalisation is not inherent to graphon modelling; it ensures consistent correspondence between graph structures and fixed graphon coordinates. Since Wψ(si,sj∣zg)W_\psi(s_i,s_j\mid z_g) assigns probabilities to specific coordinate pairs, arbitrary node permutations can introduce inconsistent reconstruction targets (Sec. 3.1; Theorem 3, Appendix C).

The permutation-equivariant approach in [3] offers a potential alternative. GraphonFlow could preserve equivariant node representations throughout encoding and transport while replacing canonical supervision with permutation-consistent latent coordinates or an alignment-aware graphon reconstruction objective. However, preserving node ordering alone is insufficient because the current graphon decoder uses fixed structural coordinates.

Our ablation (Table 8, Appendix I.5.2) supports this distinction: removing canonicalisation reduces QM9 Bernstein validity from 99.93% to 93.10% and increases NSPDK from 0.0002 to 0.0065. These results establish the importance of coordinate consistency in our current formulation, not the necessity of NAUTY itself. A canonicalisation-free extension could therefore preserve the learned graphon source while replacing explicit canonical labelling with permutation-consistent structural supervision.

Reviewer_MYsVOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents GraphonFlow, a novel graph generation approach. GraphonFlow adopts a flow-based model to generate graphon structure of graphs. Benchmark experiments show the promising performance of GraphonFlow.

Critical strengths
  • This paper proposes a novel approach for graph generation, and showes that modeling the structural distribution of graphons is a promising direction.
  • The writing of this paper is excellent, method details and formulas are well elaborated.
Critical weaknesses
  • The paper lacks a clear motivation. Why we need graphon structure as generation targets? Is it working better with flow generative framework? Or its distribution capture is more accurate? No strong advantages can be found in benchmark metrics of tabel 1 & 2 or computation time in table 6. Authors are encouraged to highlight more (theory or experiment results) about the advantages of graphons over direct graph structures.

------------------Post Rebuttal----------------------
My concerns have been addressed so I increase my rate.

Questions for authors

No other questions, see "Critical Weaknesses" section.

3 comments

We appreciate the reviewer's constructive feedback.

Our key motivation is to learn an informative, graph-dependent structural source distribution, allowing flow matching to refine learned connectivity patterns rather than construct graph topology entirely from unstructured or predefined sources. We clarify the motivation and supporting evidence below.

Q1. Why do we need graphon structures as generation targets?

We clarify that graphons are not the generation targets. They are the learned probabilistic structural sources; the targets remain the observed graphs.

Unlike an adjacency matrix representing a single graph, the latent-conditioned graphon Wψ(si,sj∣zg)W_\psi(s_i,s_j\mid z_g) captures shared connectivity patterns that vary with zgz_g, while node-level latents capture local attributes (Sec. 3.1, Eqs. 7-11). Canonical labelling ensures consistent graphon supervision (Theorem 3, Appendix C). The resulting graphon generates an informative initial adjacency A0A_0, which flow matching subsequently refines jointly with node and edge attributes (Sec. 3.2, Eqs. 14-16).

Q2. Does the graphon improve flow-based generation, or capture the underlying distribution more accurately?

Both. Within the same flow-matching framework, a learned graphon source improves generation quality and matches the data distribution more closely than a non-learned source.

In Table 7 (Appendix I.5.1), replacing a density-matched Erdos-Renyi (ER) source with the Bernstein latent-conditioned graphon improves QM9 validity from 88.65% to 99.93% and reduces NSPDK from 0.0097 to 0.0002. The unconditional Bernstein graphon achieves 94.25% validity and 0.0025 NSPDK, demonstrating the additional benefit of latent conditioning.

This is consistent with the flow-matching formulation Gt=(1−t)G0+tG^1G_t=(1-t)G_0+t\widehat G_1, where the velocity target depends on the source G0G_0 (Sec. 3.2): an informative graphon source allows flow matching to refine learned structural patterns rather than recover them from uninformative initial states. Our additional Stage 1-only ablation (Appendix I.5.7, Table 13; also addressing Reviewer e5yo, Q3(c)) shows the two parts are complementary: the graphon source alone reaches 86.08% validity on QM9, and flow refinement raises this to 99.93%.

Q3. No strong advantages are evident in Tables 1-2 or computational time in Table 6.

We agree that Tables 1-2 show competitive rather than dominant results, because these benchmarks are close to saturation. The advantage of the graphon is visible in the controlled comparison of Table 7, and training is slightly faster than Flowette, not slower (Table 6).

GraphonFlow–Bernstein achieves 99.93% validity on QM9 and ZINC250K, 99.30% validity on GuacaMol, and 98.85% novelty on MOSES. Its key advantage is more clearly demonstrated by the controlled source-prior comparisons in Table 7.

For efficiency, GraphonFlow eliminates Flowette's FGW+Hungarian source–target matching. Despite the additional structural-learning stage, Table 6 reports training times of 7.00 vs. 7.46 hours on QM9, 14.70 vs. 15.35 hours on ZINC250K, and 46.80 vs. 48.18 hours on MOSES (GraphonFlow vs. Flowette).

Our additional scalability study (see Reviewer aMQo, Q3) evaluates Tree and SBM graphs with up to 1000 nodes. With precomputed correspondence, GraphonFlow reduces training time from 8.67 to 6.17 hours on Tree and from 11.58 to 9.56 hours on SBM relative to Flowette. These findings support the computational practicality of GraphonFlow for the evaluated graph sizes of up to 1000 nodes.

Q4. What theoretical or empirical advantages do graphons offer over direct graph structures?

In theory, graphons provide a probabilistic representation of connectivity patterns rather than a single adjacency realisation. Empirically, our controlled ablations show that learned graphon sources improve generation quality and structural-distribution fidelity over simpler source priors (Table 7).

Theoretically, our latent-conditioned graphon captures shared and graph-dependent connectivity patterns, supports evaluation at different node counts through basis expansion (Sec. 3.1, Eqs. 7-8; Appendices A-B), and controls source connectivity through ρ(zg)\rho(z_g) (Eq. 8). Appendix E.3 (Eq. 86) further discusses size-dependent sparsification.

Empirically, Table 7 compares increasingly expressive sources under identical flow settings: ER →\rightarrow unconditional graphon →\rightarrow latent-conditioned graphon. On QM9, validity improves from 88.65% →\rightarrow 94.25% →\rightarrow 99.93%, while NSPDK decreases from 0.0097 →\rightarrow 0.0025 →\rightarrow 0.0002. On ZINC250K, replacing ER with the latent-conditioned graphon improves validity from 89.05% to 99.93% and reduces NSPDK from 0.0084 to 0.0004. These controlled results show that learning position-dependent, latent-conditioned connectivity improves structural-distribution fidelity compared with a density-matched ER source.

Reviewer_MYsVOpenReview ↗

Follow-up Response

I appreciate authors' efforts in rebuttal. My concerns have been addressed so I increase my rate.

Esteemed Reviewer,

Thank you for such a quick reply, engaging with our work and helping to make it better. Rest assured we will implement all suggested improvements. Meantime, kindly let us know if there is anything else we can answer or improve.

Best regards,
Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.