通过随机游走轨迹生成可解释且鲁棒的图结构。
GraphWeave: Interpretable and Robust Graph Generation via Random Walk Trajectories
- 先学随机游走中的模式，再反推最优图结构。
- 在9个数据集上优于现有方法，尤其擅长大尺度结构建模。
- 速度快10倍，仅需变换器和标准优化器。
给定一组未知家族的图，我们希望从中生成新图。现有方法在图嵌入或离散节点边空间上进行扩散，但嵌入微小扰动会导致图结构不可解释，离散空间扩散每步增删大量节点边，难以预测长期效果。本文提出GraphWeave，将模式生成与图构造分离：通过随机游走分析训练图中向量的变换规律，学习潜在模式；随后生成符合这些模式的随机游走轨迹，并通过联合优化推导出最匹配的图结构，提升对误差的鲁棒性。在四个模拟和五个真实世界基准数据集上，GraphWeave均超越现有方法，尤其在PageRank、割集、社区结构、度分布和流等大尺度特性上表现显著。其速度为最接近竞品的10倍。模型简单，仅需变压器和标准优化器。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。