Random Walk Diffusion for Efficient Large-Scale Graph Generation

2024/08/08 by Bernecker, Tobias, Rehawi, Ghalia, Casale, Francesco Paolo +2 · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Social and Information Networks (cs.SI)

paper · doi:10.48550/arxiv.2408.04461

Abstract

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.

Cited by

• Learning Flexible Forward Trajectories for Masked Molecular Diffusion

Related

• Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling
• GraphWeave: Interpretable and Robust Graph Generation via Random Walk Trajectories
• Autoregressive Diffusion Model for Graph Generation
• SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion
• Diffusion-based Graph Generative Methods