丁 玥，黄 玲，王昌栋

中山大学 数据科学与计算机学院，广州 510000

1 引言

在物理世界与人类社会关系中，存在着大量的已知或未知的个体与个体之间互相交错的连接关系。这些连接关系具象成链路，形成网络。近些年来，网络中链路预测问题逐渐兴起，利用链路预测，研究者可以分析网络关系形成的原因[1]，甚至进行事件监测[2]。如何通过已知的链路关系来推导未知链路关系存在的可能性成为链路预测研究的关键。

在传统链路预测算法中，大部分的链路预测方法都采取计算节点相似度的方式预测链路[3]。这种利用节点间的相似性进行链路预测的方法有一个重要前提：如果两个节点之间相似性越大，那么它们之间存在链接的可能性就越大。一方面，相似性的计算可以非常简单明了，如2007年Liben-Nowell和Kleinberg提出的共同邻居算法[4]，仅仅利用节点的共同邻居的个数判断相似性；另一方面，也可以基于复杂的数学与物理内容计算相似性，诸如通过计算随机游走的平均通讯时间[5]来计算相似度或者是利用基于图论的矩阵森林方法[6]来计算相似度。

然而，由于事先定义了相似度的计算方式，这些链路预测算法都在预测之前人为假定了某种特定的链路形成机制。因此，如果某特定网络的形成不遵从上述规定，则算法在该网络上的效果将不尽人意。实验证明，共同邻居算法虽然在社交网络上有很好的应用，但是在生物网络和电路网络上却不能获得较好的效果[3]。

近年，神经网络由于其能够自我学习的优点，为链路预测算法的研究提供了新的研究思路，一些新型算法，如WLNM（Weisfeiler-Lehman neural machine）[3]，通过使用神经网络来替代启发性算法，并取得了良好的实验效果。以神经网络为基础的链路预测算法逐渐成为重点研究领域。

本文将尝试抛弃启发式模型的固有思维，不事先假定网络的形成机制，而是利用生成式对抗网络来自我学习与发现网络的形成机制，从而实现基于生成式对抗网络的链路预测算法，以求得一种能够处理通用网络的链路预测算法。本文的主要贡献与创新点可概括如下：

（1）首次尝试将生成式对抗网络[7]运用于解决链路预测问题。

（2）基于CatGAN（categorical generative adversarial networks）半监督模型[8]，提出了一种适用于全监督的GAN分类模型，并将之与子图编码思想[2]结合，提出了基于生成式对抗网络的链路预测模型WL-GAN（Weisfeiler-Lehman generative adversarial networks）。实验证明，该算法拥有优秀的实验效果和稳定的收敛速率。

（3）通过数学推导，给出了分类GAN模型的相关梯度公式，该推导在原CatGAN[8]论文中未被提供。

2 链路预测问题的定义与相关算法

2.1 链路预测问题的定义

本文针对于无权无向图进行链路预测的研究。无权无向图可用符号G={V,E}定义，其中V={v1,v2,…,vn}表示为顶点集合，E⊆V×V表示为链路集。在实际运用中，为了方便使用矩阵运算来实现算法，网络图可以使用邻接矩阵A表示。若顶点i与顶点j之间存在链路，则Ai,j=1；若不存在链路链接，则Ai,j=0。由于在无权无向图中，链路不具有方向性，从而Ai,j与Aj,i代表相同的链路，A为对称矩阵。因此，在实际运用中，为了节省空间，无权无向图的邻接矩阵常被其上三角矩阵所替代。在本文算法中，这种替换也被使用。而链路预测所要解决的问题就是，对一个不完整网络G，判断两个独立节点x,y∈V，是否存在(x,y)∈E。

2.2 链路预测算法

2.2.1 基于相似度的链路预测算法

对于网络中未知连接关系的两个节点x和y，基于相似度的链路算法会根据某规则对两点之间存在链路的可能性“打分”，定义为score(x,y)。几种经典的基于相似度的算法（共同邻居算法（common neighbors，CN）、优先连接算法（preference attachment，PA）、Katz指数算法）的打分规则如表1所示。

Table 1 Score rules of CN,PA,Katz表1 CN、PA、Katz算法的打分规则

其中，Γ(x)、Γ(y)分别代表了节点x与节点y的邻居集合；path(x,y)=l是节点x到节点y之间所有长度为l的路径的集合；β是一个阻尼系数，0＜β＜1。

2.2.2 基于神经网络的链路预测算法WLNM

WLNM算法[3]是一个以分类器学习为核心的链路预测算法，也是本课题提出的WL-GAN算法的重要参考算法之一。该算法可拆分为三个子模块：一个提取子图算法（算法1），一个子图编码模型（算法2），一个分类器模型。WLNM算法首先将网络中的每条已知链路信息转化为相应的子图和标签，再利用神经网络进行分类训练，以完成链路预测。其中，Palette-WL模型是一种为无标号图进行标记序号的算法，它不仅能够根据节点在网络中的结构角色来标记序号，而且能够保留各节点与目标链接的相对距离的信息[3]，非常适合用于链路预测。

2.3 生成式对抗网络

2.3.1 原始生成式对抗网络算法

生成式对抗网络[7]包括一个判别器模型与一个生成器模型。其中，判别器致力于识别输入数据的来源：来自真实数据还是生成器生成的虚拟数据，并提高自身识别数据真伪的正确性；而生成器D则致力于使自己生成的虚拟数据被判别器判别为真。这种生成器与判别器相互博弈、共同进化的构成使得D和G的性能在迭代中不断提升，直到双方达到纳什均衡状态。

GAN的生成器和判别器可以用任意可微分的函数G、D来表示[11]。其中，生成器G的输入为随机噪声变量z～P(z)，从而生成出模仿服从真实分布X的虚拟数据G(z)，使用符号x͂=G(z)表示。而这里判别器的D的输入则可以是真实数据x～X，也可以是虚拟数据。

GAN的损失函数如下[7]：

2.3.2 分类生成式对抗网络算法CatGAN

分类生成式对抗网络CatGAN[8]是以GAN为基础的半监督分类模型算法，其中判别器的目的不再是判断数据真假，而是为数据进行分类。其具体原理是利用香农熵与交叉熵[12]的性质使得判别器尽量满足以下要求：（1）真实数据能够被判别器以高度确定的概率划分到某一类中。（2）若真实数据标签已知，则尽量分入该类中。（3）由生成器产生的虚拟数据分到所有K类中的概率相似，无法被判别器分类。（4）判别器尽量使所有数据能在所有类别中均匀分布存在；而生成器则需做到（1）产生的虚拟数据能够被判别器以高度确定的概率划分到某一类中。（5）所有生成的虚拟数据能够在所有类别中均匀分布。CatGAN半监督模型中生成器与判别器的损失函数公式分别如下[8]：

其中，H(x)为香农熵函数，CE(x)为交叉熵函数。对于一部分已知其对应的分类类别y的真实数据x，定义(x,y)服从分布XL。式（3）、式（4）中各项的具体表达如下：

其中，N、M分别为真实样本与虚拟样本的数量，K为聚类数。

3 解决链路预测问题的WL-GAN模型

3.1 WL-GAN模型架构

本节将详细介绍WL-GAN模型。WL-GAN是一个结合编码子图算法与分类生成式对抗网络的新型链路预测模型。利用子图编码算法与分类生成式对抗网络，WL-GAN能够从网络的拓扑结构自动学习出网络的形成规律，从而利用有监督学习对不同的编码子图进行分类，达到链路预测的效果。WLGAN包括以下四个主要步骤：

（1）使用封闭子图提取算法[3]（算法1），对于网络中的所有节点对，生成以该目标节点对为中心的邻居子图，固定子图大小为K。

（2）使用子图模式编码算法Palette-WL（算法2）为所有子图的各节点标序，并由其合成邻接矩阵。将邻接矩阵中表明目标节点对的连接关系的数据从邻接矩阵中剔除，作为该子图的标签。所得新的邻接矩阵及其标签则为用于训练GAN判别器的真实数据。

（3）将噪声信息放入CatGAN生成式对抗网络的生成模型中，生成虚拟数据。

（4）使用虚拟数据与真实数据训练分类生成式对抗网络CatGAN[8]的全监督模型。训练模型使得CatGAN判别器模型和生成器模型达到纳什均衡，最终获得强劲的能够实现链路预测功能的判别器模型。

WL-GAN框架架构整体结合了WLNM模型[3]与CatGAN模型[8]的全监督拓展模型，在实验中发现WL-GAN具有良好的实验效果与极高的收敛速率。WL-GAN框架的示意图如图1所示。

算法1提取子图算法[3]

输入：目标节点对(x,y)，网络G和子图节点数K。

输出：以(x,y)为中心节点对的子图G(V,K)。

Fig.1 Framework sketch of WL-GAN图1 WL-GAN的框架示意图

算法2The Palette-WL算法[3]

输入：以(x,y)为目标链路的封闭子图G(Vk)。

输出：对所有v∈V，最终标号结果c(v)。

3.2 构造全监督GAN模型

以2.3.2小节中CatGAN的半监督模型原理以及损失函数为原型，本文提出CatGAN的全监督模型公式。当拥有所有训练数据的类标时，可以简化网络中判别器的损失函数，只保留判别器对真实数据判别结果与真实类标的交叉熵信息而省略其信息熵信息项，此时判别器和生成器的损失函数如下：

Fig.2 Diagram of neural network图2 神经网络的示意图

随后，使用深度神经网络模型来构造判别器D。神经网络模型可使用图2表示。多层神经网络中，每一层网络的输出都会成为下一层网络的输入[13]，即：

其中，L为网络的层数。fl为第l层的激活函数，zl=Wlal+bl。网络工作时，第一层神经元从外部接受输入的数据集矩阵x，x的每一列即为一个输入样本，即a0=x。最后一层神经元的输出是整个网络的输出aL。对于神经网络判别器D的某个任意层数l而言，第l层的输出为：

其中，N为输入的样本个数，Nl为第l层的神经元个数。在神经网络对输入进行向前传播最后得到输出aL之后，将网络输出与目标输出相比较，并使用反向传播算法[13]结合判别器的损失函数LG调整网络参数使得损失函数最小化。其中，损失函数的最速下降算法[14]为：

这里l是层数，表示矩阵Wl中第i行的第j个元素，表示bl的第i行元素，k为迭代次数，η是学习率。

现在，具体考虑解决链路预测问题的全监督GAN模型算法反向传播过程中各梯度的计算。根据式（10）、式（11）与式（18），判别器的误差公式如下：

误差公式1（判别器D的误差公式） 对于上述CatGAN网络，判别器第L-1层第t个样本的误差为：

为了简化误差公式1的证明，先证明如下引理。

引理对于任意信息熵,其中，有：

证明

考虑到：

且：

从而可得：

证明（误差公式1）

对于判别器而言，结合其损失函数表达式LD以及上述引理（K=2），有：

同理，对于生成器G，也可以利用反向传播算法更新其网络参数，只不过此时需要将生成器G和判别器D看成相互连接的统一网络。生成器G的误差公式如下（误差公式2的证明过程与误差公式1相似）。

误差公式2（生成器G的误差公式） 对于上述CatGAN网络，当生成器输出生成数据至判别器网络时，判别器第L-1层第t个样本的误差为：

在WLNM中，判别器与生成器网络模型均为5层神经网络，其中判别器每层神经元的个数分别是[N,32,32,32,2],而生成器的神经元层个数则为[16,32,32,32,N]，其中N为输入样本向量的大小。而判别器与生成器神经网络模型中，除判别器最后一层的激活函数为softmax函数，其余层激活函数均为sigmoid函数。

4 实验设计与结果分析

4.1 模型评价指标与实验数据集

4.1.1 模型评价指标

本文采用AUC作为模型的评价指标，AUC（area under curve）是二元分类模型中的常见评价指标。相较于原始的accuracy评价指标，AUC避免了将预测概率转化为类别的过程，因此AUC是二元分类器中最常见的评价指标之一。AUC的公式可概括如下[15]：

其中，Np为正样本个数，Nn为负样本个数。ranki代表正样本i在被模型判别为正的概率在所有正样本中的排名。AUC得到的结果可等价看作所有样本中模型估测正类样本判别为正的概率大于估测负类样本判别为正的概率的次数再除以Np×Nn。

4.1.2 数据集

在本实验中，共采用了四个数据集：USAir[3]数据集是美国航空系统的航线网络数据；NS[16]数据集是一个发表于《科学网络》杂志上的作者合作关系网络；Celegans[17]数据集是秀丽隐杆线虫的神经网络数据；Power[17]数据集是美国西部地域的电网网络数据。这四个网络涵盖生物、物理、人际关系等多个领域，能够很好地测试算法在不同性质的网络上各自的性能。所有数据集的具体信息如表2所示。

Table 2 Node information of datasets表2 数据集的节点信息表

4.2 参数分析实验

本节将探讨WL-GAN模型迭代次数epoch、目标函数交叉熵项权重参数λ和学习速率η对WL-GAN算法的实验效果的影响。

4.2.1 对参数λ的分析

参数λ是判别器的目标函数LD中交叉熵项的权重值。图3、图4分别代表了在两种不同数据集USAir和Celegans下，不同λ的取值对WL-GAN模型结果的影响，此时，学习速率η固定为0.5。从图3、图4中可以看出，若λ取值为0，即去除交叉熵项，则模型无法收敛，效果极差。但若λ＞0，则WLGAN均能够取得较好的实验效果。另外，λ取值越大，则模型收敛速度越快，但是收敛后的最终效果相似。

Fig.3 Performance of WL-GAN via different λon USAir dataset图3 USAir数据集上不同λ的WL-GAN性能

Fig.4 Performance of WL-GAN via different λon Celegans dataset图4 Celegans数据集上不同λ下的WL-GAN性能

4.2.2 对参数η的分析

参数η是神经网络梯度下降时的学习速率。图5、图6分别代表了在两种不同数据集USAir和Celegans下，不同η的取值对WL-GAN模型结果的影响，此时，λ固定为0.5。从图5、图6中可以看出，η取值越大，则模型收敛速度越快，但模型稳定性越差，AUC曲线曲折较多。当η=0.1时，虽然模型收敛速度较慢，但是曲线平滑。这是由于η取值越大则梯度下降越快，但不一定完全朝梯度下降方向下降，η取值越小则梯度下降越慢，但是能保证尽量朝向梯度下降方向移动的原因导致的。

Fig.5 Performance of WL-GAN via different ηon USAir dataset图5 USAir数据集上不同η下的WL-GAN性能

4.3 对比实验分析

本节将WL-GAN的实验效果与一些现有算法的实验效果进行对比。共选取了3个启发性算法与3个基于分类器的算法作为WL-GAN的对比算法，分别如下：

Table 3 Comparison performance of WL-GAN表3 WL-GAN对比效果

Fig.6 Performance of WL-GAN via different ηon Celegans dataset图6 Celegans数据集上不同η下的WL-GAN性能

CN[4]：共同邻居算法。

PA[9]：优先连接算法。

Katz[10]：Katz指数算法。其中参数β=0.01。

WL-KNN：WL-KNN是子图编码模型与KNN（Knearest neighbors）分类模型的结合模型。其中，KNN模型使用余弦距离作为距离度量，分类规则为随机分类。

WL-LR：WL-LR是子图编码模型与逻辑回归（logistic regression）分类模型的结合模型。

WLNM[3]：WLNM是子图编码模型与神经网络分类模型的结合模型。神经网络层数构造为Nl=[N,32,32,16,2]，N为样本的向量长度，与本文算法WL-GAN中的判别器的神经网络构成相同。其中，学习速率η=0.1，最大迭代次数200次。

对比结果如表3所示。从表3中可以看出，WLNM与WL-GAN算法的效果明显优于其他算法，而本文提出的WL-GAN算法的实验效果较之WLNM又有了进一步提升。这是由于WL-GAN算法能够利用自身生成的虚拟数据来辅助判别器进行模型的训练，进而提升了实验效果。

5 结束语

本文尝试使用生成式对抗网络解决链路预测问题，并创新性地提出了基于生成式对抗网络的链路预测模型WL-GAN，并在实验中证明了WL-GAN算法在性能上的优越性。生成式对抗网络在计算机视觉上已经较为成熟，但是将生成式对抗网络用于分类或其他用途的研究远没有计算机视觉领域成熟，如何更多地尝试将生成式对抗网络融入到更多的研究领域是一个值得研究的问题。