GraphWeave: Interpretable and Robust Graph Generation via Random Walk Trajectories
This addresses the challenge of interpretable and robust graph generation for applications in network analysis and simulation, though it appears incremental as it builds on existing diffusion methods with a novel two-step approach.
The paper tackles the problem of generating new graphs from an unknown family by separating pattern generation and graph construction, using random walk trajectories to learn patterns and then optimizing for the graph that fits these trajectories, resulting in outperforming existing methods on benchmark datasets and being 10x faster than its closest competitor.
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.