# GraphWeave: Interpretable and Robust Graph Generation via Random Walk Trajectories

arXiv: https://arxiv.org/abs/2509.17291 · HTML: https://mlsanity.com/paper/2509.17291/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 20 references that are in the map.
- First posted on arXiv 22 Sep 2025.

## Builds on (most cited first, 15 of 15)

- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [GraphNVP: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/1905.11600/) (2019)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [A Systematic Survey on Deep Generative Models for Graph Generation](https://mlsanity.com/paper/2007.06686/) (2020)
- [Autoregressive Diffusion Model for Graph Generation](https://mlsanity.com/paper/2307.08849/) (2023)
- [Fast Graph Generation via Spectral Diffusion](https://mlsanity.com/paper/2211.08892/) (2022)
- [Neural Graph Generator: Feature-Conditioned Graph Generation using Latent Diffusion Models](https://mlsanity.com/paper/2403.01535/) (2024)

## Abstract (arXiv)

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 to embeddings (say, adding noise) can mean uninterpretable changes in the graph. In discrete-space diffusion, each step may add or remove many nodes/edges. It is hard to predict what graph patterns we will observe after many diffusion steps. Our proposed method, called GraphWeave, takes a different approach. We separate pattern generation and graph construction. To find patterns in the training graphs, we see how they transform vectors during random walks. We then generate new graphs in two steps. First, we generate realistic random walk "trajectories" which match the learned patterns. Then, we find the optimal graph that fits these trajectories. The optimization infers all edges jointly, which improves robustness to errors. On four simulated and five real-world benchmark datasets, GraphWeave outperforms existing methods. The most significant differences are on large-scale graph structures such as PageRank, cuts, communities, degree distributions, and flows. GraphWeave is also 10x faster than its closest competitor. Finally, GraphWeave is simple, needing only a transformer and standard optimizers.