# Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

arXiv: https://arxiv.org/abs/2606.04287 · HTML: https://mlsanity.com/paper/2606.04287/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 32 references that are in the map.
- First posted on arXiv 2 Jun 2026.

## Builds on (most cited first, 30 of 30)

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment](https://mlsanity.com/paper/2304.06767/) (2023)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [Autoregressive Diffusion Model for Graph Generation](https://mlsanity.com/paper/2307.08849/) (2023)
- [DeFoG: Discrete Flow Matching for Graph Generation](https://mlsanity.com/paper/2410.04263/) (2024)
- [Discrete-state Continuous-time Diffusion for Graph Generation](https://mlsanity.com/paper/2405.11416/) (2024)
- [Scalable Deep Generative Modeling for Sparse Graphs](https://mlsanity.com/paper/2006.15502/) (2020)
- [GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation](https://mlsanity.com/paper/2212.01842/) (2022)
- [Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation](https://mlsanity.com/paper/2106.06189/) (2021)
- [Cometh: A continuous-time discrete-state graph diffusion model](https://mlsanity.com/paper/2406.06449/) (2024)
- [Learning-Order Autoregressive Models with Application to Molecular Graph Generation](https://mlsanity.com/paper/2503.05979/) (2025)
- [Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation](https://mlsanity.com/paper/2402.03687/) (2024)
- [Graph Generative Pre-trained Transformer](https://mlsanity.com/paper/2501.01073/) (2025)
- [A Simple and Scalable Representation for Graph Generation](https://mlsanity.com/paper/2312.02230/) (2023)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [Let There Be Order: Rethinking Ordering in Autoregressive Graph Generation](https://mlsanity.com/paper/2305.15562/) (2023)
- [Overcoming Order in Autoregressive Graph Generation](https://mlsanity.com/paper/2402.03387/) (2024)
- [Diffusion-Free Graph Generation with Next-Scale Prediction](https://mlsanity.com/paper/2503.23612/) (2025)

## Abstract (arXiv)

Generating realistic and diverse graphs is a key problem in machine learning, with applications in molecular discovery, circuit design, cybersecurity, and beyond. However, current graph generative models remain limited by scalability and novelty. Diffusion-based methods often require costly full-adjacency operations and long denoising chains, while many autoregressive and hybrid models have at least quadratic complexity. In addition, these models often imitate training graphs rather than generalize beyond them. We propose a lightweight autoregressive framework to address these issues. It uses a structure-guided topological ordering to serialize graphs into regular edge sequences, enabling near log-linear generation, and a two-phase training strategy that combines exploration-oriented augmentation with iterative refinement to reduce overfitting and promote controlled novelty. Experiments on molecular and non-molecular benchmarks show that our approach improves novelty while preserving high validity and uniqueness. The framework also supports both LSTM and Mamba-style causal sequence backbones, with large-memory accelerators enabling longer graph-sequence experiments beyond typical GPU limits.