Random Walk Diffusion for Efficient Large-Scale Graph Generation
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph GenerationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Clustering for directed graphs using parametrized random walk diffusion kernels
Clustering based on the random walk operator has been proven effective for undirected graphs, but its generalization to directed graphs (digraphs) is much more challenging. Although the random walk operator is well-defin…
ClusteringGraphWeave: Interpretable and Robust Graph Generation via Random Walk Trajectories
Given a set of graphs from some unknown family, we want to generate new graphs from that family. Recent methods use diffusion on either graph embeddings or the discrete space of nodes and edges. However, simple changes t…
Graph GenerationUnderstanding Parallel Samplers in Masked Diffusion via Random Walks on Graphs
In this paper, we propose using random walks on graphs as a verifiable sandbox to study different parallel sampling strategies in masked diffusion models (MDMs). We train an MDM on random walk samples from a fixed graph.…
Time-aware Random Walk Diffusion to Improve Dynamic Graph Learning
How can we augment a dynamic graph for improving the performance of dynamic graph neural networks? Graph augmentation has been widely utilized to boost the learning performance of GNN-based models. However, most existing…
Graph LearningCapturing Graphs with Hypo-Elliptic Diffusions
Convolutional layers within graph neural networks operate by aggregating information about local neighbourhood structures; one common way to encode such substructures is through random walks. The distribution of these ra…