NodeNAR: Non-Autoregressive Graph Generation via Masked Sequence Modeling

Graph generation has garnered attention in recent years and has been applied across various domains. Autoregressive graph generation methods demonstrated promising performance. However, they suffer from inefficient decoding and are sensitive to the node orders. Diffusion models provide comparable performance and preserve permutation invariance, but require thousands of denoising steps and additional features. One-shot methods, in contrast, generate the whole graph in parallel, but struggle to capture the complex structure of graphs, thereby producing poor samples. In this work, we introduce NodeNAR, an efficient and effective graph generation approach. Specifically, we first design a structure-aware sequence representation that significantly improves the representation and generation efficiency compared to previous node-edge-, edge-, or adjacency-based representations. We further propose masked sequence modeling, enabling better communication across tokens with randomized orders. In inference, NodeNAR performs masked token prediction and can predict multiple tokens simultaneously. To ensure expressiveness, we further propose corrective parallel decoding with variable-size learning to refine generated graphs within a few iterations. Extensive experiments on real-world, synthetic, and molecular datasets demonstrate that our approach achieves superior performance, with speedups of 10¹ up to 10³ compared to baselines. Our code is open-sourced at https://gitfront.io/NodeNAR.