  Graph generation addresses the problem of generating new graphs that have a
data distribution similar to real-world graphs. While previous diffusion-based
graph generation methods have shown promising results, they often struggle to
scale to large graphs. In this work, we propose ARROW-Diff (AutoRegressive
RandOm Walk Diffusion), a novel random walk-based diffusion approach for
efficient large-scale graph generation. Our method encompasses two components
in an iterative process of random walk sampling and graph pruning. We
demonstrate that ARROW-Diff can scale to large graphs efficiently, surpassing
other baseline methods in terms of both generation time and multiple graph
statistics, reflecting the high quality of the generated graphs.
