acceptodds
Under review as a conference paper at ICLR 2027

STAGE: Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

Abstract

Generating realistic and diverse graphs is a fundamental challenge because molecules, materials, circuits, and malware can all be represented as graphs. A useful generator must produce novel graphs that follow the underlying data distribution rather than simply reproduce training examples. For instance, regenerating training molecules yields no new drug or material candidates, while replicating known malware graphs provides no new variants for improving detectors. Graph generators must therefore scale to large, sparse graphs while producing novel, diverse, and distributionally consistent samples. Current methods fall short on at least one requirement. Dense autoregressive and diffusion models incur at least quadratic cost in graph size, and sparse autoregressive models scale but, like dense ones, fit the training distribution, so novelty arises only incidentally. To our knowledge, no existing method achieves both scalability and novelty. We introduce STAGE, a lightweight autoregressive graph generator designed for both scalability and novelty. For scalability, STAGE serializes graphs as flat bit-level streams of lexicographically sorted edges, yielding generation with any causal sequence backbone; to make this compact stream learnable, STAGE orders nodes by a breadth-first traversal that enqueues neighbors by SIR-GN structural rank, resolving many of the arbitrary choices left by plain BFS. For novelty, STAGE uses a two-phase training strategy that combines exploration-oriented edge perturbations with self-training on generated samples. Samples are retained either by a label-free Gaussian-mixture density in graph-embedding space or, when available, by a domain validity oracle, steering exploration toward plausible regions. With label-free filtering, STAGE achieves the highest joint validity–uniqueness–novelty (VUN) on QM9, QM7x, Transition1x, and ANI-1x (56.8% vs. 55.0% on QM9; 86.4% vs. 59.4% on QM7x), matches the strongest baseline on MOSES, and remains competitive on ZINC250K. With oracle filtering, it reaches 60.9% VUN on QM9 and 95.1% on MOSES, compared with 55.0% and 85.4% for the strongest baselines. Ablations show that ordering is critical, with random ordering sharply degrading validity. Finally, STAGE trains on MalNet-Tiny function-call graphs with a median of 2,272 nodes, a regime in which DiGress, DeFoG, and SparseDiff exhaust GPU memory.

Primary area:
generative models
Keywords:
Graph Generation, Autoregressive Models, Generative Models, Molecular Generation, Exploration–Exploitation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_FHm2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes STAGE, which generates attributed graphs by serializing sorted edges into binary sequences, using SIR-GN structural rankings within BFS to reduce ordering ambiguity. It combines training on edge-perturbed graphs with self-training on generated samples selected by either an embedding-space GMM or domain-specific criteria. Experiments cover six molecular datasets and one MalNet-Tiny family, with substantial novelty gains on several molecular benchmarks. The paper also demonstrates generation of larger sparse graphs and reports memory limitations of several competing implementations.

Critical strengths
  1. The edge stream avoids materializing a dense adjacency matrix and supports LSTM and Mamba backbones. The �0��0� sequence length and fixed-state backbone analysis provide a reasonable scalability argument under the assumptions in Appendix B.

  2. STAGE-U improves VUN from 59.36% to 86.35% on QM7x and from 83.82% to 90.52% on ANI-1x against the strongest reported baselines (Table 4). These are substantial gains, and the label-free selection option makes the approach relevant beyond domains with explicit validity checks.

Critical weaknesses
  1. The presentation of this paper should be polished. For example, the first sentence of the abstract: "Generating realistic and diverse graphs is a fundamental challenge because molecules, materials, circuits, and malware can all be represented as graphs". To be honest, I do not find any challenges in this statement.

  2. Higher VUN does not establish the claimed combination of novelty and distributional consistency. On MOSES, STAGE-L improves VUN to 95.07%, but its Filters score falls to 87.64 and SNN to 0.41, compared with 98.9 and 0.55 for DeFoG. On QM9, STAGE-U improves VUN modestly over SparseDiff, while molecular stability falls from 94.73% to 82.28%. The authors acknowledge this tradeoff, but the evaluation does not determine whether the additional novel samples remain comparably useful.

  3. In the MalNet evaluation, “Validity” means assignment to the target family by a classifier; uniqueness and novelty use quantized, mean-pooled SIR-GN signatures. However, classifier agreement does not establish functional validity, and signature novelty is not equivalent to graph-level novelty. Evaluation in the same representation family used by the method also warrants independent checks. Moreover, Table 5 uses only 100 generations, and the final VUN difference from AutoGraph is approximately four percentage points without uncertainty estimates. Independent structural statistics, quantization sensitivity, and larger repeated evaluations would strengthen this result.

  4. The manuscript does not specify sufficient settings for the generator architectures, optimizer, training schedules, actual GMM component counts and quantiles, candidate budgets, or molecular split sizes after deduplication. The binary decoder also needs explicit rules for termination, inconsistent repeated attributes, and malformed edge sequences.

Questions for authors

See weaknesses.

Reviewer_QWT3OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The manuscript proposes a novel autoregressive model for graph generation. The proposed model aims at improving the novelty of state-of-the-art generative models while retaining loglinear scalability. The model relies on learnable node ordering and a novelty-oriented training inspired by ReST.

Thanks to its scalability, the model manages to bring graph generative models to malware-related datasets, which would require significant amounts of computation with the prior art.

Critical strengths
  1. Scalability The model is argued to be cheap and scales up to thousands of nodes
  2. Interesting methodology The authors provided an interesting methodology that aims to improve novelty results, which is a relevant metric for tasks such as drug discovery or malware discovery.
Critical weaknesses
  1. Writing clarity I found the paper hard to read. Several key concepts are not introduced properly. For instance, the paper does not properly explain SIR-GN and ReST-style training which are key components of STAGE.
  2. Unclear methodology The methodology section is not detailed enough to properly understand what the authors implemented and the rationale behind their choices. For instance, in 3.4 the GMM is not properly introduced, and it is not explained how does STAGE benefit from its use. This also holds for SIR-GN in 3.1.
  3. Unclear novelty As a consequence of them not being properly introduced, it is unclear to me how STAGE compares to SIR-GN and other ReST-style training paradigms. This makes it hard to understand whether STAGE contributions are novel or not.
  4. Limited evaluation metrics The experiments do not evaluate graph data quality (e.g., MMD wrt test data) but rather focus on novelty and validity only.
  5. Unproven scalability The mentioned scalability of STAGE is not proven theoretically nor empirically.

Overall, I think that this paper introduces some interesting methodology, but the manuscript is not making clear how STAGE differs from the state-of-the-art and what is the rationale behind their choices. I believe this manuscript may benefit from some extensive rewriting. For this reason I suggest a clear rejection score. However, I do not exclude that this work could match the level of this conference if better presented and extended with clearer theoretical outcomes and empirical results.

Questions for authors

I pose the following questions to the authors.

  1. How does the STAGE implementation of ReST-style differ from known approaches?
  2. How does STAGE benefit from the usage of SIR-GN and GMM? What is the rationale behind choosing these components rather than other possible alternatives?
  3. Could the authors provide insights in how STAGE can faithfully reproduce the structural properties of the graph datasets it was trained on? (e.g., MMD wrt to test set of node degree, clustering coefficient, spectrum, etc.)
  4. Could the authors provide a clear and self-contained proof of the complexity of STAGE?
  5. Could the authors empirically demonstrate the scalability of STAGE? (e.g., a plot with synthesis time on the y-axis and node count on the x-axis)
Reviewer_tvThOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This work introduces a serialization and two-stage training strategy for lightweight, autoregressive generation of novel graphs. The proposed method serializes graph edges using a structure-guided BFS. Authors argue that both the structural order through the SIR-GN ranking signal and the connectivity enforced by BFS are necessary for learnability of the graph sequences. During training, models are trained through an exploration-oriented edge perturbation stage followed by an exploitation-oriented ReST-style self training. Compared to prior work, STAGE generally generates a higher fraction of graphs that are simultaneously valid, unique, and novel.

Critical strengths

The manuscript is generally well written, well motivated, and the claims are generally substantiated. Algorithms, tables, and figures are easy to follow.

Critical weaknesses
  1. [Critical] It is crucial for the ablation experiments to justify the choices made throughout the paper. Currently, these experiments do not include key details/results and sometimes conflict with claims of the paper.
    1. No final results: Ablation figures (Figures 2 and 3) only show Validity, Uniqueness, and Novelty across epochs. These results are limited to measurements across epochs, not the final performance once training has concluded. As such, I find it difficult to ascertain the final benefits of two stage training or the serialization method.
    2. No STAGE trace: Several arguments of the paper compare ablations in Figures 2 and 3 to properties of STAGE's training. However, there are no results in the paper (or appendices) that show STAGE's validity, uniqueness, and novelty across epochs (e.g., "Plain BFS recovers much of the lost structure but is less stable than the full structure-guided traversal on harder datasets" in lines 370-371). It is difficult to compare such training dynamics when STAGE's training traces are missing.
    3. Conflicting statements: Lines 108-110 state that "Ablations confirm that without perturbations novelty decays, and without refinement validity drops sharply". However, Figure 3 demonstrates that novelty decays irrespective of perturbations (from roughly 70% to 30-40%) and the drop in validity is a direct result of including perturbation rather than due to not including refinement. In another instance, lines 986-988 state that "without perturbed graphs and without ReST, the model remains conservative and Novelty declines steadily". I do not understand how both can be true. The first case ("remains conservative") implies that novelty was low during entire training set. However, as shown, it appears the model is simply overfitting and memorizing its training set past the 150-160th epoch (Figure 3b). Would it not be more reasonable to stop the training early in this instance?
    4. VUN (the main strength of the STAGE) is not depicted in either figure, which limits the conclusions that can be drawn.
  2. [Critical] All experimental results appear to be from a single training run and without any error bars or standard deviations. Training traces from Figures 2 and 3 further underscore the need for multiple runs and standard deviations as some metrics appear to be highly volatile during training.
  3. [Moderate] Reproducibility is severly limited by unspecified implementation details. For instance, how are the underlying backbones designed and trained? How many epochs were spent training on stage 1 vs stage 2? How is the GMM trained?
Questions for authors

Clarifications that will affect my assessment:

  • Please provide clarifications and additional results to address the weaknesses outlined previously. Standard deviations or error bars should be at least provided for STAGE results and ablations.

Some minor suggestions that could be addressed to improve the readability of the work.

  1. Undefined notation: ψ\psi in Algorithm 1 and aa and xvx_v in Algorithm 2.
  2. Conflicting notation: xix_i is used for both the node attributes and bit sequence in Algorithm 2 and 5.
  3. STAGE-L and STAGE-U are not explicitly defined anywhere but used in all tables.
  4. The complexity comparison to prior work is missing AutoGraph (Chen et al., 2025a). AutoGraph has a complexity of O(m)O(m) generation cost in the general case.
  5. Please clarify what Tempo N implies in Table 5.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.