导语: 生成对抗网络 (Generative Adversarial Network, 简称 GAN) 是非监督式学习的一种方法, 通过让两个神经网络相互博弈的方式进行学习. 自 2014 年 GAN 网络提出以来, 其在 Computer Vision(计算机视觉)领域获得了广泛的关注, 但 GAN 网络在其他领域的应用相对较少. 将 GAN 网络的思想应用在图网络 (network) 特征表达是近一年新兴的课题, 本文综述 GAN 模型在图网络表征学习方面的研究.
背景介绍
网络表征学习 (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 即为生成式模型和判别式模型的结合, 其包含两个重要部分, 即生成器 G(v|v c ; θ G ) 和判别器 D(v|v c ; θ D ). 生成器为每一个节点维护一个向量, 这些向量组合在一起构成θG.G(v|v c ; θ G ) 表示生成器认为给定节点 Vc 和参数θ G 下, V 与 Vc 之间 有一条边的概率. G(v|v c ; θ G ) 的目的就是通过学习去逼近真实分布 Ptrue(V|Vc). 判别器也为每一个节点维护一个向量, 这些向量组合在一起构成θ D .D(v|v c ; θ D )通过向量θ D 来判断 V 与 Vc 之间 是否有一条边 .
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|v c ;θ 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 θ (.) 尝试从噪音中产生离真实数据分布尽可能接近的数据, 而判别器 d w (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 模型或者说对抗学习思路在图表征学习当中的 研究还有很多, 本文仅仅抛砖引玉的调研了三种比较常见的使用场景. 这里是 http://deeplearningresource.com/2019/04/08/1087/ 一个图神经网络相关论文的集锦, 可以看到图神经网络在近两年受到很多的关注.
除了同学, 同事, 亲人这样的亲密关系, 微信上我们还加了许多房产中介, 招聘 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.
来源: http://www.tuicool.com/articles/FJZjIne