Diffusion-Free Graph Generation with Next-Scale Prediction
Samuel Belkadi, Steve Hong, Marian Chen, Miruna Cretu, Charles Harris, Pietro Liò · 2025
Read Diffusion-Free Graph Generation with Next-Scale Prediction by Samuel Belkadi, Steve Hong, Marian Chen, Miruna Cretu, Charles Harris, Pietro Liò (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23612.txt.
Introduction
Samuel Belkadi and five co-authors present a 2025 paper on MAG, a fast method for generating graphs with AI. Graphs model networks and molecules, but their lack of natural order clashes with sequence-based generators. Diffusion models respect that disorder yet can need thousands of steps. The team borrows a trick from image generation: predict the whole graph at growing scales, step by step.
The model builds a stack of compressed views of a graph, then generates from coarse to fine without fixing any node order. Tests on general and molecular graph sets showed output quality on par with top methods. Speed was the headline gain, with inference up to a thousand times faster in some comparisons. The authors present scale-by-scale prediction as a practical route to graph generation for chemistry and network design.
Catalog record
| CREATOR | Samuel Belkadi, Steve Hong, Marian Chen, Miruna Cretu, Charles Harris, Pietro Liò |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23612
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Diffusion-Free Graph Generation with Next-Scale Prediction Samuel Belkadi, Steve Hong, Marian Chen, Miruna Cretu, Charles Harris, Pietro Liò Abstract Autoregressive models excel in efficiency and plug directly into the transformer ecosystem, delivering robust generalization, predictable scalability, and seamless workflows such as fine-tuning and parallelized training. However, they require an explicit sequence order, which contradicts the unordered nature of graphs. In contrast, diffusion models maintain permutation invariance and enable one-shot generation but require up to thousands of denoising steps and additional features for expressivity, leading to high computational costs. Inspired by recent breakthroughs in image generation, especially the success of visual autoregressive methods, we propose MAG , a novel diffusion-free graph generation framework based on next-scale prediction. By leveraging a hierarchy of latent representations, the model progressively generates scales of the entire graph without the need for explicit node ordering. Experiments on both generic and molecular graph datasets demonstrated the potential of this method, achieving inference speedups of up to three orders of magnitude over state-of-the-art methods, while preserving high-quality generation. † † affiliationnotice: Equal contribution 1 Introduction Graphs provide a natural and flexible information representation across a wide range of domains, including social networks, biological and molecular structures, recommender systems, and infrastructural networks. Consequently, the ability to learn a graph distribution from data and generate realistic graphs is pivotal for applications such as network science, drug discovery, and protein design. Despite significant progress in generative models for language and images, graph generation remains challenging due to its inherent combinatorial nature. Specifically, graphs are naturally high-dimensional and discrete with varying sizes , contrasting with the continuous and fixed-size techniques that cannot be directly applied to them. Furthermore, rich substructures in graphs necessitate an expressive model capable of capturing higher-order motifs and interactions. Several graph generative models have been proposed to address some of these challenges, undertaking approaches based on autoregressive (AR) models ( You et al., 2018 ) , varational autoencoders (VAE) ( Jin et al., 2018 ) , generative adversarial networks ( De Cao & Kipf, 2018 ) , and diffusion models ( Niu et al., 2020 ; Jo et al., 2022 ; Vignac et al., 2023 ) . Among these, diffusion and autoregressive models excel in performance and offer complementary strengths—diffusion’s permutation invariance and AR’s efficiency—that make them especially promising avenues ( Kong et al., 2023 ; Zhao et al., 2024 ; Yan et al., 2024 ) . On one hand, diffusion models offer the ability to achieve exchangeable probability in combination with permutation equivariant networks, under certain conditions ( Niu et al., 2020 ; Jo et al., 2022 ) . However, given the high-dimensional nature of graphs and their complex internal dependencies, directly modeling the joint distribution of all nodes and edges presents significant challenges. Recent work by Zhao et al. (2024) demonstrates that, as a cost for permutation invariance, capturing the full joint distribution and solving the transformation difficulty via diffusion requires thousands of sampling and denoising steps as well as additional node-, edge-, and graph-level features, such as eigenvectors, to break symmetries and achieve high generation quality, rendering diffusion a promising but very expensive approach. On the other hand, in addition to their improved efficiency, studies into the success of AR models have highlighted their scalability and generalizabilty . The former, as exemplified by scaling laws ( Henighan et al., 2020 ) , allows the prediction of large models’ performance to better guide resource allocation during training, while the latter, as evidenced by zero-shot and few-shot learning ( Sanh et al., 2021 ) , underscores the adaptability of unsupervised-trained models to unseen tasks. Furthermore, the aforementioned discrete and varying-size properties of graphs suggest a promising fit for autoregressive modeling. However, unlike natural language sentences with an inherent left-to-right ordering, the order of nodes in a graph must be explicitly defined for unidirectional autoregressive learning. Previous AR methods ( You et al., 2018 ; Liao et al., 2020 ; Shi et al., 2020 ) attempted to enforce node ordering or approximate the marginalization over permutations such that, once flattened, one can train an autoregressive model to maximize its likelihood via next-token prediction. This gives rise to the three main issues of autoregressive graph generation: 1. Long-range dependency. Generating nodes one at a time results in sequential dependencies that make it difficult to capture long-range interactions and global structures. Furthermore, early predictions errors can propagate throughout the generation process, and dependencies may decay when working on larger graphs. 2. Forced node ordering. Enforcing a specific node ordering is at odds with the inherent invariance property of graphs, forcing the model to learn over a specific ordering, thereby increasing complexity and reducing generalization. 3. Inefficiency. Generating a graph sequence (x_{1},x_{2},...,x_{N}) with a conventional self-attention transformer incurs \mathcal{O}(n) autoregressive steps and \mathcal{O}(n^{3}) computational cost (see Appendix B ). Drawing inspiration from recent breakthroughs in image generation—notably the Visual Autoregressive Modeling (VAR) framework ( Tian et al., 2024 ; Ren et al., 2025 ) —our proposed method suggests a new ordering for graphs that is multi-scale, coarse-to-fine . We introduce MAG , a novel transformer-based graph generation framework based on next-scale prediction instead of traditional next-node and next-edge approaches, thereby infusing autoregressive properties with graphs’ structural constraints. As shown in Figure 1 , our method first encodes a graph into multiple scales of latent representations and learns to generate scales autoregressively, starting from a singular token and progressively expanding its resolution. At each step, a transformer predicts the next-resolution token map, conditioned on previous scales and a class label [C] for conditional synthesis. MAG poses significant improvements over traditional autoregressive methods on both generic and molecular graph datasets. Notably, it reduces the performance gap with diffusion baselines, surpassing them in wall-clock training and inference time, with strong performance. This provides strong evidence regarding the effectiveness of next-scale prediction for high-quality graph generation. In summary, our contributions are threefold: Figure 1: Overview of the Mutli-Scale Graph Generation Framework. The input graph is first encoded through an MPNN, which produces a latent representation that is quantized at multiple scales. A Transformer then predicts the scales autoregressively via a coarse-to-fine next-scale process, and a GCN-based decoder reconstructs the graph from the final discrete latent representation r_{K} . 1. A novel next-scale prediction framework for hierarchical graph generation that overcomes the limitations of traditional AR approaches on graph properties. 2. A thorough theoretical and empirical analysis of how multi-scale latent representations can effectively capture high-order motifs while remaining significantly more efficient than counterparts. 3. Experiments on diverse graph datasets, demonstrating significant improvements over AR baselines and promising performance when compared to state-of-the-art diffusion methods. 2 Related Work Diffusion and score-based models Diffusion models achieve permutation-invariance by parameterizing the denoising/score function with a permutation equivariant network, at the cost of up to thousands of sampling steps. EDP-GNN ( Niu et al., 2020 ) is the first work to adapt score-based models to graph generation by representing graphs as matrices with continuous values. GDSS ( Jo et al., 2022 ) generalizes this approach by leveraging SDE-based diffusion and replacing adjacency matrices with node and edge features. However, by using continuous-state diffusion, these approaches ignore graphs’ discrete nature, resulting in fully connected graphs. DiGress ( Vignac et al.,