GraphGAN

GraphGAN是一种结合了图神经网络和生成对抗网络（GAN）概念的机器学习模型。它旨在通过对抗学习框架解决图数据中的节点分类和链接预测问题，特别是在缺少标签数据的情况下。GraphGAN通过结合生成器和判别器两个主要组件来学习图中节点的有效表示。

GraphGAN的框架如下：设$G=(V,\mathcal{E})$为一个给定的图，其中$V=\left\{\begin{array}{c}{v}_1,\dots ,v_V\end{array}\right\}$代表顶点的集合，而$\mathcal{E}={\left\{e_{ij}\right\}}_{i,j=1}^V$代表边的集合。对于给定的顶点${\nu }_c$，定义$\mathcal{N}\left({\nu }_c\right)$为直接连接到${\nu }_c$的顶点集，也就是顶点${\nu }_c$的1-hop邻居。我们将顶点${\nu }_c$的真实连通性分布表示为条件概率$p_{\mathrm{true}}\left(\nu |{\nu }_c\right)$，它反映了${\nu }_c$的连通性偏好和它所连接顶点的类型。从这个视角来看，$\mathcal{N}\left({\nu }_c\right)$可以被看作是从$p_{\mathrm{true}}\left(\nu |{\nu }_c\right)$抽取的一组观察样本。给定图$\mathrm{G}$，GraphGAN旨在学习以下两个模型：

• 生成器$G(\nu |{\nu }_c;{\theta }_G)$：尝试近似顶点${\nu }_c$的真实连通性分布$p_{\mathrm{true}}\left(\nu |{\nu }_c\right)$，并生成（或选择）最有可能与${\nu }_c$相连接的顶点集。
• 判别器$D(\nu ,{\nu }_c;{\theta }_D)$：旨在鉴别顶点对$\left(\begin{array}{c}\nu ,{\nu }_c\end{array}\right)$的连通性。$D(\nu ,{\nu }_c;{\theta }_D)$输出一个标量值，表示边$\left(\begin{array}{c}\nu ,{\nu }_c\end{array}\right)$存在的概率。

生成器$\mathrm{G}$和判别器$\mathrm{D}$作为两个对手: 生成器$\mathrm{G}$将试图完美地匹配$p_{\mathrm{true}}\left(\nu |{\nu }_c\right)$并生成类似于${\nu }_c$的真实直接邻居的相关顶点以欺骗判别器。而判别器$\mathrm{D}$则相反，会尝试检测这些顶点是${\nu }_c$的真实邻居还是由其对手$\mathrm{G}$生成的。形式上， $\mathrm{G}$和$\mathrm{D}$在一个有以下价值函数$V(G,D)$的双人博弈中进行对抗：

$\underset{{\theta }_G}{min}\underset{{\theta }_D}{max}V(G,D)=\sum _{c=1}^V({\mathbb{E}}_{\nu \sim p_{\mathbf{tne}}(\nu |{\nu }_c)}[\log D(\nu ,{\nu }_c;{\theta }_D)]+{\mathbb{E}}_{\nu \sim p_G(\nu |{\nu }_c;{\theta }_G)}[\log (1-D(\nu ,{\nu }_c;{\theta }_D))])$       （1）

上式描述的最小最大（Minimax）博弈公式是生成对抗网络的核心。在图生成对抗网络（GraphGAN）的上下文中，生成器$\mathrm{G}$的目标是生成看起来像真实数据的样本。在GraphGAN的情境下，生成器试图生成看似是${\nu }_c$的1-hop邻居的顶点。而鉴别器$\mathrm{D}$的目标是区分输入样本是来自于真实数据还是生成器生成的假数据。在GraphGAN中，它试图区分一个顶点对$(\nu ,{\nu }_c)$是否是真实的1-hop邻点对。这个公式包含了两个期望（Expectations）：

第一部分为真实数据的期望$E_{v\sim p_{\mathrm{true}}(v\mid v_c)}[\log D(v,v_c;{\theta }_D)]$。这个期望表示对所有真实的顶点对$\left(\begin{array}{c}\nu ,{\nu }_c\end{array}\right)$，鉴别器$\mathrm{D}$输出它们是真实邻居的概率的对数。$\mathcal{V}$是从顶点${\nu }_c$的真实邻居分布$p_{\mathrm{true}}\left(\nu |{\nu }_c\right)$中采样的。理想情况下: 如果$\nu$确实是${\nu }_c$的真实邻居，我们希望鉴别器$\mathrm{D}$的输出$D(\nu ,{\nu }_c;{\theta }_D)$接近于1 (最大的可能性)。此时$\log D(\nu ,{\nu }_c;{\theta }_D)$会接近0（因为$\log (1)=0$）。

第二部分是关于生成数据的期望$E_{\nu \sim p_G(\nu |{\nu }_c;{\theta }_G)}[\log (1-D(\nu ,{\nu }_c;{\theta }_D))]$。这个期望表示对所有生成器$\mathrm{G}$生成的顶点对$\left(\begin{array}{c}\nu ,{\nu }_c\end{array}\right)$，鉴别器$\mathrm{D}$输出它们不是真实邻居的概率的对数。$\nu$是从生成器$\mathrm{G}$的分布$p_G(\nu |{\nu }_c;{\theta }_G)$中采样的。理想情况下：如果$\nu$是生成器$\mathrm{G}$生成的，并不是${\nu }_c$的真实邻居，我们希望判别器$\mathrm{D}$的输出$D(\nu ,{\nu }_c;{\theta }_D)$接近于0。此时, $\log (1-D(\nu ,{\nu }_c;{\theta }_D))$也会接近0（因为$\log (1-0)=0$）。

可以看出这两部分期望的目标都是希望经过训练后，其值越来越小，理想情况下为0，因此可以看作GraphGAN的损失函数，GraphGAN的训练状态如图1所示。

阴影的圆代表从真实图结构中采样的真实与顶点${\nu }_c$连接的邻居，横条纹的圆代表生成器认为的应该与${\nu }_c$连接的邻居。在训练的初始阶段（左图），生成器$\mathrm{G}$的表现并不佳，其生成的顶点与实际的邻居相比，差异较大，很容易被鉴别器$\mathrm{D}$区分。随着对抗训练的进行（中图），生成器$\mathrm{G}$逐渐学习到更好的生成策略，使得生成的邻居和实际的邻居更难以区分。在经过充分的训练之后，生成器$\mathrm{G}$生成的邻居与实际的邻居非常接近，即右图中，阴影的圆和横条纹的圆存在大量重叠。鉴别器$\mathrm{D}$几乎无法区分。在这个博弈中，鉴别器尽量提高识别真实和生成数据对的准确性，而生成器尽量生成看起来越真实的数据。通过这种对立的训练过程，两个模型都在不断改进，直到达到一个平衡点，即生成器生成的数据非常逼真，鉴别器很难区分真假数据对。

下面具体的讲解GraphGAN的优化过程，对于判别器而言，定义鉴别器$\mathrm{D}$的输出为两个输入顶点$(\nu ,{\nu }_c)$内积的Sigmoid函数：

$D(\nu ,{\nu }_c)=\sigma \left(d_{\nu }^{\mathrm{\top }}{d}_{{\nu }_c}\right)=\frac{1}{1+\exp (-d_{\nu }^{\mathrm{\top }}{d}_{{\nu }_c})}$      （2）

定义${\theta }_D$是判别器的可学习参数。任何具有区分能力的模型都可以在此作为$\mathrm{D}$，例如一个神经网络模型，对顶点$\nu$和${\nu }_c$的特征向量进行学习映射后得到的$\mathrm{k}$维新的向量表示为$d_{\nu },d_{{\nu }_c}$，然后进行内积和Sigmoid处理。这个内积表示了两个顶点之间的相似性或关系强度。内积的结果通过Sigmoid函数进行处理，得到一个在0到1之间的值，可以解释为顶点对$\nu$和${\nu }_c$是图中真实连接的概率。其中$\nu$的采样有两种情况，换句话说，判别器随机接收两类输入数据（$\nu \sim p_{\mathrm{true}}$或$\nu \sim G$）。根据损失函数公式(1)，判别器的梯度${\mathrm{\nabla }}_{{\theta }_D}V(G,D)$计算如下：

${\mathrm{\nabla }}_{{\theta }_D}V(G,D)=\{\begin{array}{l}{\mathrm{\nabla }}_{{\theta }_D}\log D(\nu ,{\nu }_c),\mathrm{if}\nu \sim p_{\mathrm{true}}\\ {\mathrm{\nabla }}_{{\theta }_D}(1-\log D(\nu ,{\nu }_c)),\mathrm{if}\nu \sim G.& & \end{array}$        （3）

在训练过程中，GraphGAN交替地更新生成器$\mathrm{G}$和判别器$\mathrm{D}$的参数，以便最小化生成器的损失函数和最大化判别器的损失函数，这个过程通常被称为对抗训练。式(3)便是固定生成器$\mathrm{G}$更新判别器$\mathrm{D}$时，判别器的梯度计算方法。

类似的，生成器$\mathrm{G}$具体的模型类型也没有限制，GCN、GAT甚至简单的神经网络等等都可以，只要能具备预测某顶点与其他顶点间连接概率的能力即可。当固定判别器$\mathrm{D}$，更新生成器$\mathrm{G}$的参数时，式(1)中的$E_{\nu \sim p_{\mathrm{true}}(\cdot \mid {\nu }_c)}[\log D(\nu ,{\nu }_c;{\theta }_D)]$部分可以看作常数，只需要关注另一部分，即$E_{\nu \sim G(\cdot \mid {\nu }_c;{\theta }_G)}[\log (1-D(\nu ,{\nu }_c;{\theta }_D))])$。此时，生成器的梯度${\mathrm{\nabla }}_{{\theta }_G}V(G,D)$为：

$\begin{array}{rl}{\mathrm{\nabla }}_{{\theta }_G}V(G,D)& ={\mathrm{\nabla }}_{{\theta }_G}\sum _{c=1}^V{E}_{\nu \sim G(\cdot \mid {\nu }_c)}[\log (1-D(\nu ,{\nu }_c))]\\ & =\sum _{c=1}^V\sum _{i=1}^N{\mathrm{\nabla }}_{{\theta }_G}G\left({\nu }_i|{\nu }_c\right)\log (1-D({\nu }_i,{\nu }_c))\\ & =\sum _{c=1}^V\sum _{i=1}^{N}G\left({\nu }_i|{\nu }_c\right){\mathrm{\nabla }}_{{\theta }_G}\log G\left({\nu }_i|{\nu }_c\right)\log (1-D({\nu }_i,{\nu }_c))\\ & =\sum _{c=1}^V{\mathbb{E}}_{\nu \sim G(\cdot |{\nu }_c)}[{\mathrm{\nabla }}_{{\theta }_G}\log G\left(\nu |{\nu }_c\right)\log (1-D(\nu ,{\nu }_c))]\end{array}$            （4）

在式(4)的推导中，$\sum _{c=1}^V{E}_{\nu \sim G(\cdot {\nu }_c)}[\log (1-D(\nu ,{\nu }_c))]$是对所有顶点${\nu }_c$的期望求和，其中每个期望是从生成器$\mathrm{G}$生成的顶点$\nu$对应的$\log (1-D(\nu ,{\nu }_c))$的平均值。这表明我们在考虑所有生成器产生的假顶点与真实顶点${\nu }_c$之间关系的平均对数概率。期望的实现可以转化成对每个生成样本的求和，即$\sum _{i=1}^N{\mathrm{\nabla }}_{{\theta }_G}G\left({\nu }_i|{\nu }_c\right)\log (1-D({\nu }_i,{\nu }_c))$，这里对每个生成样本${\mathcal{V}}_i$求和，计算生成概率相对于${\theta }_G$的梯度与$\log (1-D({\nu }_i,{\nu }_c))$的乘积。又因为概率的梯度可以写作概率乘以似然比例的梯度，因此可以使用$G\left({\nu }_i|{\nu }_c\right){\mathrm{\nabla }}_{{\theta }_G}\log G\left({\nu }_i|{\nu }_c\right)\log (1-D({\nu }_i,{\nu }_c))$代替${\mathrm{\nabla }}_{{\theta }_G}G\left({\nu }_i|{\nu }_c\right)\log (1-D({\nu }_i,{\nu }_c))$。最后，我们用期望值来代替求和，因为期望值是随机变量的平均值，这里的随机变量是$\nu$的生成概率，得到推导后生成器的梯度计算公式：$E_{\nu \sim G(\cdot \mid {\nu }_c)}[{\mathrm{\nabla }}_{{\theta }_G}\log G\left(\nu |{\nu }_c\right)\log (1-D(\nu ,{\nu }_c))]$。整体上，这个梯度表达式说明：为了更新生成器$\mathrm{G}$的参数，我们需要考虑由$\mathrm{G}$生成的每个顶点$\mathrm{v}$对损失函数的贡献，并根据该贡献来调整${\theta }_G$。梯度的方向指示了如何更新参数${\theta }_G$以减少生成的顶点$\mathrm{v}$被判别器$\mathrm{D}$识别出的概率，从而使生成器产生更真实的样本。

值得注意的是，在给定顶点${\nu }_c$时，生成器$\mathrm{G}$计算其他顶点与${\nu }_c$的连通性概率$G\left(\nu |{\nu }_c\right)$需要使用Softmax函数计算出${\nu }_c$外的所以节点。公式如下所示：

$G\left(v|v_c\right)=\frac{\exp \left(g_v^{\mathrm{\top }}{g}_{v_c}\right)}{\sum _{v\ne v_c}\exp \left(g_v^{\mathrm{\top }}{g}_{v_c}\right)}$        （5）

当图数据体量庞大时，上述公式的计算复杂度是非常高的。因此，在GraphGAN框架中，提出了一种称为Graph Softmax的新方法，它的核心思想有三点：

（1）规范化（Normalized）：生成器应该产生一个有效的概率分布，这意味着对于一个给定的顶点${\nu }_c$，所有可能与之相连的顶点$\mathrm{v}$的生成概率之和应该等于1，这也是Softmax函数的基本思想。

（2）图结构意识（Graph-structure-aware）：生成器在确定顶点之间的连通性概率时，应该利用图的结构信息。具体来说，如果两个顶点之间的最短路径距离增加，它们被认为是相连的概率应该下降。

（3）计算效率（Computationally Efficient）：与Softmax不同，Graph Softmax在计算时只考虑图中少数的特定顶点，从而提高计算效率。

为了实现Graph Softmax，首先需要执行一个从顶点${\nu }_c$出发的广度优先搜索（Breadth-First Search，BFS），来构建一棵以${\nu }_c$为根的BFS树$T_c$。使用这棵树，我们可以计算每个邻居顶点${\nu }_i$相对于${\nu }_c$的相关性概率$p_c\left({\nu }_i\right)$，这是一个标准的Softmax函数，它在${\nu }_c$的直接邻居集$N_c(\nu )$上运算。 接着，为了计算任意顶点$\nu$与${\nu }_c$之间的连通性概率$G(\nu |{\nu }_c;{\theta }_G)$，我们使用$T_c$中从${\nu }_c$到$\nu$的唯一路径。路径上每对相邻顶点的相关性概率的乘积定义了$\nu$和${\nu }_c$之间的连通性概率。通过这种方式，图Softmax只关注${\nu }_c$通过BFS可达的部分图，而不是整个图，这极大地提高了计算效率。同时，它也自然地考虑到了图的结构信息，因为它直接在BFS树上进行操作，这棵树反映了图中顶点之间的真实距离关系。因此这种方法是规范化的，具有图结构意识，且计算效率高，具体示例如图2所示。

如图2所示，从顶点${\nu }_c$开始，我们有原始的图$\mathrm{G}$和一个以${\nu }_c$为根节点的 BFS 树。第一步是从${\nu }_c$的直接邻居中选择下一个顶点。在这个例子中，顶点${\nu }_{r1}$被选中，与它相关联的概率是0.7。接下来，从${\nu }_{r1}$的邻居中选择下一个顶点。顶点${\nu }_{r2}$被选中，与它相关联的概率是 0.3。然后，从${\nu }_{r2}$的邻居中选择下一个顶点。可能的选择只有两种，与它们相关联的概率是 0.6和0.4，假设此时以0.6的概率选择了${\nu }_{r1}$，那么${\nu }_{r2}$的路径采样过程完成，否则路径采样继续延续。最后一步是更新采样路径上所有顶点的概率。计算路径${\nu }_c\to {\nu }_{r1}\to {\nu }_{r2}$上所有顶点的相关性概率的乘积得到0.7×0.3×0.6=0.126 ，这个数字代表从${\nu }_c$到${\nu }_{r2}$的连通性概率。