生成图拓扑的进化优化：一种混合WGAN-GA方法

# 生成图拓扑的进化精炼：一种混合 WGAN-GA 方法
来源：https://arxiv.org/html/2605.29161
###### 摘要

生成逼真的图结构数据极具挑战性，原因在于其离散的连接性、可变的图大小以及特定于类别的结构模式。近年来，基于生成对抗网络（GAN）的图生成方法通过学习连接性并匹配特定类别的密度分布来改进边建模。然而，这些模型在与真实图进行比较时，在度和谱分布等方面仍表现出明显的偏差，这表明重要的结构属性并未完全保留。本文旨在通过使用遗传算法（GA）对现有基于GAN的图生成器框架生成的图进行精炼，从而减少这些偏差。在GAN框架中，生成器既产生节点特征也产生连接模式，而基于GNN的判别器评估图真实性和类别一致性，以确保全局结构和类别对齐。在此基础之上，我们应用GA对生成图的边进行精炼。精炼过程引导合成图更接近真实数据，同时保持多样性和新颖性。实验结果表明，与基础模型相比，GA精炼持续降低了组合最大均值差异（MMD），从而生成了更匹配真实结构模式的图。这表明进化精炼是一种有效且灵活的方式，用于纠正基于GAN的图生成器中的残余结构偏差，提升了其在真实图合成和数据增强中的适用性。

## I. 引言

图结构数据出现在许多应用领域，包括社交网络、分子图、生物系统和通信网络，其中节点和边捕捉了底层过程和系统属性的重要信息。逼真合成图的生成在隐私保护数据共享和基于图的机器学习模型的数据增强等应用中变得越来越重要。然而，生成图引入了与欧几里得空间中传统数据合成截然不同的基本挑战。与具有规则网格结构和固定维度的图像或文本不同，图具有不规则拓扑结构、可变大小以及没有规范节点顺序。因此，有效的图生成方法必须学习图结构与节点属性之间的复杂依赖关系，同时保留定义不同图类型的结构属性。

早期的深度学习方法尝试了多种策略来应对这些挑战。诸如DeepGMG[7]和GraphRNN[14]等方法通过序列生成过程对图进行建模，而GraphVAE[11]则利用变分自编码器学习图的潜在表示。生成对抗网络（GAN）显示出了巨大的潜力，其中GraphGAN[12]、EGraphGAN[13]和MolGAN[3]证明了对抗训练在图合成中的潜力。LGGAN[5]通过引入带标签图生成以及包括度、聚类系数和轨道统计量上的最大均值差异（MMD）在内的全面评估指标，进一步推动了该领域的发展。然而，这些基于GAN的方法常常面临训练不稳定、模式崩塌以及生成可变大小图的困难。

Wasserstein GAN（WGAN）[1]的引入标志着解决标准GAN固有稳定性问题的重要进步。WGAN-GP[6]通过梯度惩罚而非权重裁剪来强制Lipschitz约束，进一步改进了这一点，实现了更有效的训练和更好的样本多样性。近期工作已成功将WGAN框架与图神经网络（GNN）作为判别器相结合，用于图生成。在[9,10]中，生成器同时产生节点特征和连接模式，而基于GNN的判别器评估图的真实性和类别一致性。这些方法在生成类别条件图方面表现出色，并提升了训练稳定性。然而，尽管取得了这些进展，这些工作表明这些模型在与真实图进行比较时，在度和谱分布等方面仍存在明显偏差。这一局限性导致生成的图具有不真实的连接模式，无法捕捉节点之间的复杂结构依赖关系，也无法反映学习到的节点特征分布。

我们通过引入基于遗传算法（GA）的精炼阶段来扩展现有的图生成方法，从而解决这些核心局限性。在图生成器完全训练后，我们应用GA通过交叉和变异操作对生成的图进行精炼，这些操作直接改变图结构，如边的存在性和局部连接模式。精炼过程由来自真实图的结构统计量衍生的适应度度量引导，特别关注纠正度、聚类系数和谱分布上的偏差。

我们精炼策略的核心是进化边编辑的概念，其中图拓扑通过一系列离散的结构修改进行迭代优化。这种方法建立在使用基本操作（如添加、删除或切换边）的成熟生成表示之上，以将网络朝向特定的结构或功能目标进化[2,4]。通过利用这些直接的边操作，进化阶段可以施加精确的局部约束，并纠正深度生成模型中固有的连续近似所经常平滑掉的统计偏差。

我们在来自[8]的三个生物信息学图基准数据集上进行了实验。结果表明，所提出的精炼策略改善了生成图与训练数据统计属性之间的一致性。精炼后的图表现出更连贯和逼真的结构模式，其连接性更好地反映了节点特征中编码的关系。总体而言，GA精炼在保持变异性的同时减少了结构不匹配，从而产生了更高质量的合成图，适用于下游图学习任务。

数据和代码：均可在 github.com/shorinbonsai/WGAN-GA-Refine 获取。

参见图1说明：模型概述。阶段一：GAN训练（基于[9,10]）。生成器学习将节点放置在潜在空间中，其中距离较近的节点更有可能被连接。基于GNN的判别器使用多个卷积层处理图，池化节点特征，并将其与类别嵌入结合以计算Wasserstein分数。阶段二：遗传算法（GA）精炼。训练后，生成器产生合成图，然后使用GA对其进行精炼，产生与真实样本高度相似的图。适应度函数鼓励生成的图匹配真实数据分布和目标类别，同时保持独特性和新颖性。

## II. 方法论：进化精炼

我们的框架将深度生成模型的输出作为进化精炼的输入，以产生精确的图结构。这些阶段如图1所示：（1）使用Wasserstein生成对抗网络（WGAN）（基于[9,10]）的粗生成阶段，以及（2）使用用Rust开发的用于边编辑的遗传算法（GA）库的精炼阶段。我们注意到，本文的重点是进化精炼阶段，而粗生成阶段可以使用任何能产生图结构的方法。尽管该方法可应用于扩展现有的基于GAN的图生成模型，但由于其报告的强大性能，我们使用WGAN作为代表性示例。

### II-A. 粗生成：WGAN

WGAN生成粗图候选，这些候选捕捉了目标图分布的全局结构特征。图表示为邻接矩阵，生成器将潜在样本映射到连续的邻接估计。判别器使用具有Lipschitz约束的Wasserstein距离进行训练，这提供了比标准GAN更平滑、更稳定的训练信号。

WGAN在我们系统中的主要作用并非生成完全有效的图，而是捕捉训练数据中观察到的高级统计规律，例如边密度、度模式以及广泛的谱或聚类属性。这些粗输出作为进化阶段的有信息初始化。通过从WGAN生成的候选图而非随机图开始基于GA的精炼，精炼过程中探索的搜索空间被偏向于结构上合理的区域，从而提高了收敛速度和解决方案质量。因此，WGAN提供了图结构的全局初始化，而详细的精炼和结构优化则由进化阶段处理。WGAN实现基于[10]的代码。

### II-B. 微调：进化精炼

虽然基于GAN的模型捕捉了全局结构趋势，但它们常常难以满足精确的局部约束，例如精确的度分布或三角形计数。为了解决这一局限性，我们使用GA对生成的图进行精炼。

在这项工作中，我们提供了一个基于Rust的GA库，该库将基于WGAN的图生成与GA精炼模块集成在一起。Python环境与我们的库接口，将WGAN生成的图直接传递给GA初始化阶段。然后，GA通过优化在选定结构度量（例如聚类系数、谱间隙）上定义的适应度函数来迭代精炼图结构，这些度量也反映在WGAN训练目标中。

### II-C. 表示与初始化

为了有效桥接WGAN的连续潜在空间和图精炼器的离散搜索空间，我们采用了一种双重表示策略。这种方法区分了表型（实际图结构）和基因型（进化指令集）。

#### II-C1. 图表型

表型表示用于适应度评估的物理图结构。它在GA库中实现为邻接表。

#### II-C2. 命令字符串基因型

我们的系统采用基于线性命令的基因型。种群中的每个个体由基因组g定义，一个由每个编码特定操作的基因组成的序列。最终图由表达函数Φ产生：

G_final = Φ(G_base, g) = op_n(... op_2(op_1(G_base)) ...)    (1)

其中G_base是由WGAN生成的粗图。这确保GA探索粗图的局部邻域，而非整个搜索空间。进化搜索通过对线性命令基因型的操作进行。

### II-D. 遗传算子与动态

关键在于，我们的算子并不直接操作邻接矩阵上的边；而是操作构建图的指令序列。

具体来说，染色体是一个按顺序应用的边编辑操作序列；因此它是确定性的并指定了一个特定的网络。染色体的长度是顶点数的两倍，以保持与[4]相对一致，同时针对不同基数的图进行缩放。

#### II-D1. 边编辑操作

这些操作应用于图G(V, E)，节点u, v, w, x来自V，如下所示。

- • Toggle(u, v)：如果边{u, v}在E中，则将其从E中移除，否则将其添加到E中。
  LocalToggle(u, w, v)：要求边{u, w}和{w, v}存在，然后调用Toggle(u, v)。
- • Hop(u, v, w)：如果边{u, v}和{v, w}在E中，且边{u, w}不在E中，则从E中移除{u, v}，并将{u, w}添加到E中。
- • Add(u, v)：如果{u, v}不在E中，则将其添加到E中，否则不做任何操作。
  LocalAdd(u, w, v)：要求边{u, w}和{w, v}存在，然后调用Add(u, v)。
- • Delete(u, v)：如果{u, v}在E中，则将其从E中移除，否则不做任何操作。
  LocalDelete(u, w, v)：要求边{u, w}和{w, v}存在，然后调用Delete(u, v)。
- • Swap(u, v, w, x)：如果{u, v}和{w, x}是E中节点u, v, w, x之间仅有的边，则从E中移除它们，并将{u, x}和{v, w}添加到E中。
- • Null()：不做任何操作。

这些操作以顺序方式在图2中展示。操作的概率在表II中给出。在初始调整中，Toggle、Add、Delete和Local toggle的概率都设置为其他操作的一半，否则度分布会受到负面影响。

0. 起始（环图）
012345
1. Add(0, 3)
添加不存在的边
012345
2. Toggle(1, 4)
边缺失 → 添加
012345
3. LocalAdd(2, 3, 4)
路径 2→3→4，添加 (2,4)
012345
4. LocalToggle(0, 5, 4)
路径 0→5→4，Toggle (0,4)
012345
5. Hop(5, 4, 3)
移除 (5,4)，添加 (5,3)
012345
6. LocalDelete(0, 1, 4)
路径 0→1→4，删除 (0,4)
012345
7. Delete(5, 0)
简单删除
012345
8. Swap(1, 0, 4, 3)
1-0,4-3 → 1-3,4-0
012345
图2：边编辑操作的顺序可视化。绿色边是添加的；红色虚线边是移除的。从起始图（左上）产生最终图（右下）的染色体因此依次由这8个操作组成。

#### II-D2. 交叉

我们采用两点交叉来重组种群中成功的编辑策略。

对于此应用，该方法优于均匀交叉，因为它保留了图操作的连续子序列。由于表型是通过顺序应用命令构建的，保留这些功能块允许后代继承有效的宏观操作（例如，创建有效子结构的特定编辑序列），而不会破坏生成过程的逻辑。

#### II-D3. 变异

变异随机选择1-4个基因，并用新的随机基因替换它们。这种轻微破坏性的操作促进了对搜索空间的更深入探索。

### II-E. 适应度函数

适应度函数量化了候选图G与目标图分布之间的结构偏差。

由于目标是生成在统计学上类似于