综述 | 生成对抗网络（GAN）在图网络中的应用 - 极术社区

生成对抗网络（Generative Adversarial Network，简称GAN）是非监督式学习的一种方法，通过让两个神经网络相互博弈的方式进行学习。自2014年GAN网络提出以来，其在Computer Vision（计算机视觉）领域获得了广泛的关注，但GAN网络在其他领域的应用相对较少。将GAN网络的思想应用在图网络（network）特征表达是近一年新兴的课题，本文综述GAN模型在图网络表征学习方面的研究。
作者： jerry
来源：腾讯技术工程微信号

背景介绍

网络表征学习(Graph Representation Learning、 Network Embedding、 Graph Embedding)的主要目的在于，将图中每一个节点都映射到一个低维向量空间，使得其在此空间内保持原有图的结构和距离信息。直观理解是，靠近的两个点在低纬空间中的距离接近。如下图所示（边上的数字代表边的长度）。

对于图表征学习的研究从很早就开始了，从最简单的邻接矩阵（Adjancency Matrix）表示，到后面对邻接矩阵进行矩阵分解（SVD），再到前几年比较火的基于随机游走的方法（DeepWalk、Node2Vec）以及最近基于深度网络的Graph Neural Network和基于注意力机制的Graph Attention Network模型，其目的都在于将网络结构映射到低维空间以应用到多项任务中，如链路预测、节点分类等等。

本文主要介绍生成对抗网络模型（Generative Adversarial Network）在图表征学习中的最新进展。本文中，网络模型如neural network中的network均称为模型；网络结构如social network中的network均称为图网络。

GraphGAN模型

论文[1]将图表征学习的方法分为两类，第一类叫生成式（generative）模型，第二类叫判别式（discriminative）模型。

生成式模型假设每一个节点都有一个潜在的概率分布，这个概率分布可以体现出该节点和其他每一个节点的连接情况。生成式模型的主要目的就是为图网络中的节点找到一个尽可能接近该潜在概率分布的向量表征。论文[1]中对这个潜在概率分布的表示为Ptrue(V|Vc)，其中Vc表示正在观测的节点，Ptrue(V|Vc) 就是指在除了 Vc 之外其他节点（V）与Vc之间构成一条边的概率。

判别式模型是指，模型直接去学习两个节点之间有边的概率。这种方法会将边<Vi, Vj>的两个定点Vi 和 Vj 联合作为 feature，然后输出的是边<Vi, Vj>存在的概率 P(<Vi, Vj>|Vi, Vj)。判别式模型往往是有监督的。

GraphGAN采用GAN网络中常见的对抗机制：生成器G尽可能的逼近Ptrue(V|Vc)以找到与Vc的相邻节点极其相似的节点来欺骗判别器D，而判别器D则会反过来检测给定的节点V是Vc的真实邻居还是由生成器生成的。GraphGAN方法的核心在于公式（1）中的目标函数：

在给定θD的情况下，生成器G希望尽可能减少下式的值：

即降低（V，Vc）被D判定为非邻居的概率；

在给定θG的情况下，判别器希望尽可能增大下式的值：

即判断真实样本为邻居的概率尽可能接近1

同时增大下式的值:

即判断生成器生成的样本的概率尽可能接近0。

理解了公式（1）就基本理解了GraphGAN的内在原理，下图给出GraphGAN工作的流程。θD和θG可以通过交替最小化和最大化V(G,D)函数来迭代更新得到。每次迭代，我们从 Ptrue 中抽样一些跟 Vc 真实相邻的绿点，从 G 中又生成了一些跟 Vc 接近的蓝点。我们将绿点作为正样本，将蓝点作为负样本来训练 D，在得到 D 之后，再用 D 中的信号，通过policy gradient去反过来训练 G。不断重复这个过程，直到生成器 G 和 Ptrue 极为接近。在刚开始的时候，G 相对比较差，因此对于给定的 Vc 而言，G sample 的点都是一些离 Vc 很远的点。随着训练的不断进行，G sample 的点会逐渐向 Vc 接近，到最后 G 抽样的点几乎都变成了真正跟 Vc 相邻的点，也就是 G 和 Ptrue 已经很难被区分了。

判别器D的实现是两个节点向量的内积再取sogmoid：

生成器G的基本实现是一个softmax函数，即选择离Vc向量距离最接近的V：

论文的另一个技术贡献在于设计了一个基于宽度有限搜索的生成规则，使得生成器每次寻找邻居节点的时候不需要将Vc和图网络中的每一个其他节点进行计算，这一部分优化与GAN网络思想关系不太紧密这里不做详细介绍了。

以上就是GraphGAN模型的主要思想和模型更改，GraphGAN基于回答“两个节点之间是否存在一条边”这个图网络研究中非常重要的问题而构建判别器和生成器，给后续GAN模型在图网络领域的研究一些启迪。代码：
https://github.com/hwwang55/GraphGAN

CommunityGAN模型

论文[2]中介绍了一种基于GAN模型的可重叠社区发现方法，称为CommunityGAN。实际上，基于前面GraphGAN中产生的节点表征，通过聚类的方法也可以得到图网络中的社区。但是，GraphGAN中的表征仅仅考虑了边的信息，而社区的形成往往需要更加紧密的结构如团（clique），所以CommunityGAN的基本思路就由GraphGAN中回答“两个节点之间是否存在一条边”变成了“多个节点之间是否两两相连”，来解决社区发现的问题。下面简单介绍一下CommunityGAN模型。

首先，CommunityGAN假设每个节点可以属于多个社区。论文中对每个节点维持一个社区归属度的向量，向量的每一维表示该节点属于对应社区的权重，如下图（V为节点id，C为社区id）：

论文首先证明，在现实图网络中，团的结构更容易出现在社区当中，即，在同一个社区中的几个节点比跨社区的几个节点更容易出现两两相连的情况。这一点也是符合我们的直观感受的。基于这一点，CommunityGAN设计了与GraphGAN非常类似的模型结构，唯一的差别就是，GraphGAN旨在判断两点之间是否有边，而CommunityGAN则是判断k个点之间是否成团。

生成G(s|vc;θG)在给定节点Vc的情况下，找到一个集合s，并认为s与Vc构成一个两两相连的团。假设我们以三团（3-clique）为目标，那么|s|=2。判别器D(s,θD)则是判断给定的节点集合s是否构成一个团。有了前面关于GraphGAN的背景，这里对于CommunityGAN的目标函数就很容易理解了：

其中Ptrue是真实团在网络中的分布。与GraphGAN类似，θG由每个节点的圈子归属度向量组成，θD由判别器中的每个节点的表征向量组合而成。

模型训练如下图所示：对于每一个节点Vc，我们根据Ptrue抽样真实的团结构作为正样本，生成器按照θG寻找向量接近的节点构成负样本，训练判别器。对应的，判别器在收到生成器的负样本后会对样本进行打分，然后将分数反馈给生成器，生成器通过policy gradient对θG进行更新。最终得到社区结果的方法是，θG中每一个维度上的归属度大于一定阈值的节点就属于该维度对应的社区。

CommunityGAN中对生成器产生样本的逻辑也有一定优化，通过随机游走的方式保证并非所有的节点在一次选取中都要被全部计算一次。论文中对θG的起始状态有一定要求，作者通过AGM算法对θG进行初始化。在实际实验过程中，我们也发现当θG没有被合理初始化时，CommunityGAN模型很难收敛，甚至根本不具备学习的能力。但在合理初始化的前提下，CommunityGAN可以明显提高社区划分的质量。代码：
https://github.com/SamJia/CommunityGAN

NetRA模型

为了对每个节点进行表征，前面两个模型都需要针对每一个节点去抽样正样本和生成负样本，这在现实生活中的巨型网络上是很难实现的。论文[3]采用了一种基于随机游走的图表征模型。实际上，基于随机游走的图表征模型已经有很多，例如DeepWalk。但这类模型有一个问题，就是当我们控制抽样数量不变时，walk的长度越长，则效果越差。原因在于walk的长度变长时，可能出现的walk所组成的sample也增多，而当我们采样不足时则会出现过拟合的问题。反过来讲，如果我们减小walk的长度，那么其对于网络表征的能力也会相应下降。论文给出了一组基于DeepWalk进行边预测的实验，假设图中节点的平均度数为d，walk的长度为l，而抽样的walk数量为k，他们三者之间的关系如下图所示。

如上图，当l或者d增大是，抽样变得越来越稀疏，使得模型过拟合导致效果变差。而当我们增加walk的数量时，模型表现就会提升。

论文[3]提出的NetRA模型(Network Representation with Adversatially Regularized Autoencoders)要解决的就是在抽样比较稀疏的情况下，避免图表征过拟合的问题。具体而言，NetRA通过引入一个GAN模型的正则项使得encoder能够提取到更有用的信息。NetRA的整体模型框架如下图。

该模型主要包含三个部分，Autoencoder（蓝色虚线框部分）、GAN（绿色虚线框部分）和图表征（红色虚线框部分）。下面分别介绍这三个部分。

Autoencoder

该部分包含两个函数，编码函数fφ(·)和解码函数hΨ(·)。编码函数将输入映射到一个低维空间上，而解码函数则可以通过低维向量反推出原输入。Autoencoder的目标就是输入（x）经过编码和解码之后，输出(hΨ(fφ(x)))和输入（x）尽可能的接近。假设Pdata为数据的真实分布，那么Autoencoder的目标函数则为

其中，距离函数采用交叉熵定义，即

值得一提的是，本文采用LSTM模型作为编码器，主要是因为LSTM模型对于序列型输入的有效处理能够使得由随机游走产生的节点序列被最好的表达。

GAN

图中绿色框线中即为GAN模型的图示。

生成器gθ(·)尝试从噪音中产生离真实数据分布尽可能接近的数据，而判别器dw(x)则会计算输入x来自真实样本的概率。假设真实样本分布为Pdata（x），而生成器采用分布为Pg（z），那么GAN模型中

这里的真实样本即为上面的Autoencoder中的编码器Encoder所产生的低维向量，所以当我们对GAN进行训练时，同时也将正负样本之间的差异反馈给Encoder，从而使得1）Encoder需要提取更有效的代表节点的信息以区分伪样本；2）Encoder需要避免过拟合，以免太容易被生成器学习。

Network Embedding

Autoencoder通过随机游走抽样网络中路径来获得节点与节点在整体网络上的结构信息，而Network Embedding这一部分则通过保留节点与节点之间的边信息来获得local的连接关系。这里Embedding的函数仍然是Autoencoder中的编码器，即fφ(·)。通过最小化下面这个函数使得编码器编码出的向量能够保证有边连接的节点的低维表达是接近的：

这里 φij 表示节点i与j之间是否有连边，有为1，没有则为0.

有了前面三部分的介绍，整体NetRA模型优化的函数则可以写为

这里LAE表示Autoencoder学习的目标，LLE和W分别是Network Embedding和GAN模型所承担的正则项，用来保证编码器的结果可以保留网络中的边信息以及防止过拟合。

NetRA模型的训练过程为：

给定一个网络，通过随机游走获得一些长度为l的路径。将这些路径中的节点通过one-hot encoding构建特征序列输入LSTM模型产生Encoder的输出，即节点的向量表征。
将这些向量表征输入Decoder函数，得到解码的特征向量。通过计算这些解码的特征向量与原始特征向量求交叉熵损失来更新Autoencoder的参数。
同时，Network Embedding保证相邻的节点的编码向量互相接近。
另外，将编码的向量与GAN模型中的生成器产生的向量分别作为正负样本去训练判别器。
最终的节点向量表征几时编码器产生的结果。

可以看见，NetRA模型并不仅仅是一个GAN模型的结构，而是将GAN模型当做正则项的一部分嵌入整个模型中得到节点的表征。这里为我们对GAN模型的应用提供了一个不同的思路。

小结

本文介绍了生成对抗网络模型在图表征学习中的基本方法（GraphGAN）、在社区发现任务中的应用（CommunityGAN）以及作为模型的正则项构建更复杂的图表征模型（NetRA）。基于GAN模型或者说对抗学习思路在图表征学习当中的研究还有很多，本文仅仅抛砖引玉的调研了三种比较常见的使用场景。这里是一个图神经网络相关论文的集锦，可以看到图神经网络在近两年受到很多的关注。

除了同学、同事、亲人这样的亲密关系，微信上我们还加了许多房产中介、招聘HR、商品经销商等等非亲密关系的好友。我们和非亲密关系的好友之间的边被称为weak ties（弱关系）。我们团队针对关系链的画像任务中，不仅仅挖掘出强关系，还找到了微信网络中的弱关系。

参考文献

[1] Wang etc. GraphGAN: Graph Representation Learning with Generative Adversarial Nets. AAAI'18.
[2] Jia etc. CommunityGAN: Community Detection with Generative Adversarial Nets. WWW'19.
[3] Yu etc. Learning Deep Network Representations with Adversarially Regularized Autoencoders. KDD'18.

综述 | 生成对抗网络（GAN）在图网络中的应用