1
文章信息
《GCN-GAN: A Non-linear Temporal Link PredictionModel for Weighted Dynamic Networks》。 北京大学电子与计算机工程学院、网络与通信研究中心、鹏程实验室、未来网络理论实验室、2012华为技术有限公司实验室、中国科学院深圳先进技术研究院发表的文章。
2
摘要
本文将各种网络系统的动态预测问题(包括移动性、流量和拓扑预测)定义为时间链路预测任务。 传统的时间链路预测技术忽略了动态网络中潜在的非线性特性和链路权重信息，为解决加权动态网络中具有挑战性的时间链路预测任务，引入了新的非线性模型GCN-GAN。 该模型利用了生成图卷积网络(GCN )、长短时存储(LSTM )以及对抗网络(GAN )的优点。 因此，可以利用加权动态网络的动态性、拓扑和演化模型来提高时序链路的预测性能。 具体而言，首先利用GCN挖掘各个snapshot的局部拓扑特征，然后利用LSTM表现动态网络的演化特征。 另外，利用GAN增强了模型生成下一个加权网络快照的能力，可以有效解决现实动态网络中边缘权重稀疏性和广值范围问题。 为了验证该模型的有效性，我们在四个不同的网络系统和应用场景的数据集上进行了广泛的实验。 实验结果表明，与先进的竞争对手相比，我们的模型取得了令人印象深刻的结果。
3
问题的定义
4
方法
模型结构
本研究在加权动态网络的时间链路预测中引入了一种新的非线性模型GCN-GAN。 如下图所示，提出的模型由3个主要部分构成：GCN、LSTM、GAN。
首先，利用GCN搜索各个图形快照的局部拓扑特征。 然后，将由GCN得到的综合显示输入到LSTM网络，捕获动态图像的进化模式。 另外，我们用GAN在一个对抗过程中生成高质量的预测graph snapshot，用GCN和LSTM构建生成网络g，介绍了另一个全连接判别网络d。 在对抗过程中，训练g根据动态图的历史拓扑预测下一个快照，训练d区分生成的加权链路和实际记录。 应用这种极小两人博弈，对抗过程最终通过调整g生成可靠的高质量预测结果。
GAN隐藏层
利用GCN模型对动态网络中每个graph snapshot的局部拓扑进行了建模。 GCN是卷积神经网络的一种有效变体，可以直接操作图。 假设静态图表包含n个节点，这些节点具有m维的特性(或属性)。 拓扑和节点属性可以分别用邻接矩阵a和特征矩阵z表示。 典型的GCN单元接收特征矩阵z作为输入并基于a执行局部一阶近似频谱卷积运算。 典型的GCN单元接收特征矩阵z作为输入并基于a执行局部一阶近似频谱卷积运算。
LSTM隐藏层
在GCN-GAN模型中，学习到的聚合网络表明，x输入到LSTM层，LSTM层具有学习序列数据长期依赖关系的强大能力，能够捕获加权动态网络的演化模型。 对于给定时间步骤t，LSTM单元将当前输入向量x和先前时间步骤ht-1的状态向量作为输入，输出当前时间步骤ht的状态向量：
最后，最后的隐藏状态h 1被表示为历史快照的分布，并且将其输入到所有连接层以生成预测结果。
生成对抗网络
与标准的GAN框架一样，我们的模型也在极小极大博弈下优化了两个神经网络：生成网络g和判别网络d。 在模型中，d试图区分训练数据中的实际图形快照和g生成的快照，但g最大限度地提高了d出错的概率。
判别网络：
我们通过完全连接的前馈神经网络、隐层、输出层实现判别模型d。 在训练过程中，d会交替选择g的输出或实际数据作为输入。 完全连接的神经网络中的每个输入数据通常表示为一个向量，因此在将输入矩阵输入d时，而不是作为矩阵重构为相应的行顺序长度向量。
此外，由于使用Wassersteingan(WGAN )框架来训练模型，因此可以将输出层设置为线性层，并直接生成输出，而不需要非线性激活函数。 简而言之，判别网络d的细节可以表现为：
生成网络G：
生成模型g由GCN层、LSTM层、全连接输出层构成。 GCN层以graph snapshots序列和噪声z作为输入，将其作为一个序列x输出，并将其输入到LSTM层。 需要注意的是，输入的相邻矩阵a应该在[ 0，1 ]之间规范化。 另外，采用sigmoid函数作为GCN层的激活函数
，并且使噪声z服从[0,1]的均匀分布。LSTM层将产生的序列X作为输入，输出为隐藏状态h。需要注意的是每一个输入矩阵X应该reshape为一个行序长向量，再输入到LSTM中。最后，最终的隐藏状态h输入到输出层产生下一个时间段的graph snapshot。
模型优化
由于网络的拓扑结构是随时间动态变化的，因此GCN-GAN模型需要不断更新其参数以适应网络的演化。此外，通常认为，与距离其较远的snapshot相比，接近下一个时间段的snapshot可以被认为具有更多与真实值相似的特征。基于这样合理的假设，我们采用以下优化策略。当出现一个新的时间段时，该模型首先利用之前的网络图序列作为输入，以当前snapshot作为真实值进行训练。当对时间段t进行训练后，我们进行预测步骤产生下一个时间段的snapshot。
对于时间链接预测任务，直接使用标准的对抗训练过程是不合适的，因为G可能生成一个可信的snapshot，可以成功欺骗D，但它与下一个graph snapshot不一致。事实上，我们期望预测结果应该尽可能接近真实值。为了解决这种可能的问题，我们为G引入了另一个预处理过程，其损失函数如下:
这样的过程可以帮助G完全捕获动态网络的最新时间信息，被认为是与真实snapshot最相似的特征。
经过预处理过程后，G具有生成预测结果的初始能力。进一步发展对抗性训练过程，可以提高G的生成能力，以应对加权动态网络的稀疏性和宽值范围问题。
在此过程中，我们首先利用梯度下降法更新D的参数(记为θD)，并通过以下损失函数固定G的参数:
在实验中，我们采用RMSProp算法交替更新θD和θG，直到收敛。
在进行完训练过程后，G能够生成预测结果，需要注意的是生成的预测结果在[0,1]范围内，需要反归一化到真实范围内。此外，还可以使用一些技巧来进一步细化预测结果，具体如下:
首先，我们使用(15)使Aτ+1对称，因为我们只考虑无向网络的情况。然后，利用(16)，设置Aτ+1的对角元素为0，以消除自连接边的影响。最后，将值小于一个小阈值ε的元素设置为0，以反映边界权值的稀疏性。
5
创新点
在本文中，我们提出了一种新的时间链路预测模型GCN-GAN，以解决网络系统中的动态预测问题(例如，移动性、流量和拓扑预测)。我们的模型能够有效地处理加权动态网络的预测任务，因为它结合了深度神经网络(即GCN和LSTM)在学习网络的全面分布表示方面的优势，以及GAN在生成高质量加权链接方面的优势，有效地解决现实动态网络中边缘权值的稀疏性和宽取值范围问题。
A
Attention
如果你和我一样是轨道交通、道路交通、城市规划相关领域的，可以加微信：Dr_JinleiZhang，备注“进群”，加入交通大数据交流群！希望我们共同进步！