Dynamic Network Link Prediction by Learning Effective Subgraphs using CNN-LSTM
摘要：现有的方法大多涉及整个网络和目标环节，这导致高计算成本。本文旨在通过使用深度学习方法提出一个新的框架来解决这些问题。DLP-LES使用基于公共邻居的目标链路子图，并学习给定动态网络的过渡模式。此外，我们的模型引入了新的机制来降低计算成本。DLP-LES生成一个查找表来保存所需的网络链路信息，并使用哈希方法来存储和获取链路信息。我们提出了一种构造进化子图特征矩阵的算法来学习过渡链接模式。我们的模型使用长短期记忆神经网络的卷积神经网络将动态链接预测问题转化为视频分类问题。
为了验证DLP-LES的有效性，在五个真实世界的动态网络上进行了大量的实验。我们将这些结果与四种网络嵌入方法和基本启发式方法进行了比较。
关键词： 社交网络，动态网络，链接预测，子图
为什么用子图：
（然而，目标节点及其邻居节点对链路预测的影响很大，分析整个网络的部分可以降低时间复杂度（提取子图）。
最近在静态网络中的突破性方法，WLMN [17]和SEAL[18]提出了神经网络方法来自动选择给定网络的最佳启发式，并介绍了基于邻居节点的预测目标链路的子图提取方法。然而，PLACN [19]声称目标链路的公共邻居节点的子图具有额外的信息仅仅来自邻居节点的子图，并且在各种类型的静态网络中取得了突出的结果。） 受此启发，我们从目标链接的公共邻居中提取子图，并将启发式的好处扩展到动态网络设置。
文章提出的方法介绍：
我们提出的模型DLP-LES从给定动态网络的最后一个快照中提取基于公共邻居的子图开始，并在每个时间步骤中使用启发式特征分析子图的过渡模式。由于复杂性，动态设置方面的研究大多忽略了链接权重，只考虑了链接的有无。在DLP-LES中，我们将链接权重作为具有启发式特征的附加信息。除此之外，我们用给定动态网络的每一个链路信息构造一个查找表。查找表的主要目的是当我们频繁使用相同链接的信息时，减少时间和空间的复杂性。我们将在构建查找表一节中进一步阐述这一点。此后，本研究引入了一种有效的编码方法来标记子图的节点。在训练神经网络时，保持子图的一致性是我们模型中的另一个重要任务。我们相信，检查子图的进化启发式特征对于在动态网络的任意两个节点之间引入新的链接具有显著的影响。
- 我们介绍了一种生成查找表的方法，以记录给定动态网络的链路信息，并在需要时使用哈希方法获取必要的信息。
- 我们引入了一种新的子图标记编码方法。
- 我们提出了一种算法来有效地构造子图的特征矩阵。
- 我们提出了一个新的动态网络链路预测框架，使用卷积神经网络(CNN)来有效提取子图的高级特征，使用长短期记忆(LSTM)神经网络来学习序列数据的长期相关性，并捕获动态网络中子图的演化模式。
动态网络链接预测建模
在这一节中，我们讨论了所需的理论和技术的背景，以建立一个框架来预测未来的链接。
A、启发式方法（Heuristic Methods）
1)公共邻居(CN):CN的思想是，如果节点与其他节点共享链路，则形成新链路的几率很高。这是最简单的方法，计算任意两个顶点v和u直接交互的邻居数。
2)Jaccard Coefficient(JC):JC基于v和u拥有的邻居总数产生归一化形式的CN。
3)Adamic-Adar(AA):AA是JC的修改版。AA的首要目的是给邻居很少或者程度较低的普通邻居更高的优先级。
4)优先连接(PA):PA的概念是如果一个节点拥有更高的度，则建立新连接的几率很高。
5)资源分配(RA): RA度量更类似于AA。不同的是RA给低度共同邻居的优先级比AA高
B、CNN-LSTM
DLP-LES包括卷积神经网络(CNN)和长短期记忆(LSTM)神经网络[27]。
在这里，我们利用CNN模型提取子图邻接矩阵的启发式特征，这些特征可以作为DLP-LES中的一幅图像；LSTM模型已被证明在捕捉任意长度的长期时间相关性方面极其有效。
DLP-LES的体系结构
该模型的四个步骤：
- 1)链接特征查找表构造。
- 2)子图提取和标注。
- 3)子图中链接的特征矩阵构造。
- 4)用CNN和LSTM建模
前k个等距快照作为输入，最后第(t)个快照作为输出。
DLP-LES (Dynamic network Link Prediction by Learning Effective Subgraphs) 突出了我们对有效的基于公共邻居的子图的关注，以处理动态链路预测。
A.链接要素查找表构造
如上节所述，我们有给定动态网络G的快照序列。对于最后的快照Gt，我们提取目标链接的子图用于预测，并分析子图中每个链接的启发式特征。如果我们从具有公共链接的子图中考虑两个目标链接，评估链接的启发式特征可能是一个重复的过程。为了避免这种重复的过程，我们首先构建一个查找表<R>，为给定网络G的每个链路存储以下信息。
tk<cn，jc，aa，pa，ra，wi>，指定tk处快照的启发式特征值
最小跳数表示在最后一个快照t + 1，v和u之间的最小跳数
平均路径权重是最小跳数的路径权重与最小跳数之间的比率，在最后一次快照t + 1
链路的平均路径权重可以计算如下：
我们的主要目标是构建一个仓库<R>，它可以用来检索链接的信息，而无需重复计算。使用散列函数访问信息比以表的形式访问存储库有更多的好处。为此，我们制定以下散列函数。
其中v和u是任意顶点，散列函数可以为任意顺序的顶点对提供特征信息。我们首先将节点对<v，u>转换成一个唯一的键，这个键对于任何顺序的节点v和u都是相同的键(即<v，u>，<u，v>)。为了收集我们存储在查找表中的任何信息，我们可以使用上面的函数9。所以，复杂度为O(1)来收集给定链接的信息。
B、子图提取和节点标注
我们使用任何目标节点v和u的公共邻居来创建子图。公共邻居可以从节点v和u的不同跳数中收集。收集节点v和u的公共邻居将有更多的信息来决定它们之间未来链路的存在，而不仅仅是收集邻居节点。我们设置了一个阈值θ来保持子图中节点数的限制。
定义2 (基于公共邻居的子图) 动态网络的最后一个快照Gt= <V，Et>，G' = <V'，E't> 是两个节点Vi∈V' 和vj∈ V' 的公共邻居节点集合的子集，并且当且仅当V'⊆ V和E't ⊆ Et，v'是目标链路的公共邻居集合，并且| v' | =θ。
(1)、基于公共邻居的子图提取
(2)、子图节点标记
节点标注有助于保持子图的一致性。在我们提取子图之后，包含目标链接的节点得到标签1和2。我们使用节点列表NΘ，它从子图提取中返回。然后，我们从NΘ中移除属于目标链路的节点。为了对剩余节点RΘ= NΘ - { 1，2} 进行排序，我们使用平均最小跳数和平均路径权重的信息。我们可以使用 散列函数等式 9 来获得所需的信息。然而，我们需要一个平均跳数(HAvg)和平均路径权重(WAvg)。所以，我们用下面的公式来计算Havg和Wavg
hv,i(hi,u)是v和I之间的最小跳数。wavg<v，i> (wavg<i，u>)是链路<i,u>的平均路径权重。
我们的目标是以一致的方式对Rθ中的节点进行排序。我们可以先按平均跳数升序排序，然后按平均路径权重降序排序，这有助于打破第一次排序的束缚。
因此，我们提出了一个办法，把hv,i和wavg编码成一个单一的形式，以降低复杂性如下图：
现在，我们根据编码值对剩余节点列表进行排序，并存储它们，直到总节点数等于阈值θ。算法2显示了标记的逐步标记过程。例如，图4表示子图节点标注的过程。最左边的图显示了目标链路<1,2>的给定动态网络的最后快照的子图。节点显示平均跳数和平均重量的信息。我们对这些值进行编码，生成一个唯一的代码，如图2中最右边的第二个所示。最后，在对编码值排序后，每个节点都获得一个唯一的标签。
基于编码方法的子图标注表示。最左边的图表示提取的具有边缘权重的子图，中间的图显示了编码值，最右边的图代表最终的标记
最后，在对编码值排序后，每个节点都获得一个唯一的标签。
C、特征矩阵构造
我们有一系列给定动态网络的快照。子图提取和节点标记已经在最后的快照t中进行了处理。相同的子图应该已经在整个时间序列tk，tk1，.... ，tt。因此，我们为每个快照的子图构建特征度量。正如我们在前面部分已经讨论过的，我们构建CN、JC、AA、PA、RA和权重的特征矩阵。
算法3描述了特征矩阵的构造过程。我们创建空的邻接矩阵列表来存储每个快照中的特征，如下所示:
其中l是子图的有序节点列表的大小。算法3继续，直到通过从查找表中获取节点列表的所需信息来填充上述空列表。
在加权图的邻接矩阵的每个最后快照中，我们将零分配给正目标链接，以隐藏链接存在的信息。在图5中，下图说明了我们如何构造邻接矩阵。我们只填充矩阵的上部三角形，以避免重复值。在最后一个快照中，我们用一个红色的方框表示该值始终为零。
D、用CNN和LSTM建模
DLP-LES使用CNN和LSTM对链路预测框架进行建模。如前所述，我们有一个目标链路子图的邻接矩阵序列，用于根据给定动态网络的最后快照进行预测。DLP-LES的输入数据是以θ×θ×h的形式构造的邻接矩阵序列，其中θ是子图的节点数，h是模型中使用的启发式特征数。在DLP-LES中，我们将每个邻接矩阵视为一幅图像。我们有tk，tk-1，.... ，tt 如图5底部所示。一系列图像其实就是一个视频。所以我们可以把我们的模型当作一个视频分类问题，其中正和负链接是两个不同的类。正链接表示链接存在，(vi，vj) ∈ Et，而负链接表示任意两个节点之间没有链接，(vi，vj)不属于 Et。为了训练分类器，我们使用动态网络的最后快照来构建数据集，其中正链接类的所有现有链接和相同数量的不存在的链接使用下采样技术。
CNN以图像分类著称。我们利用这个特征来学习和提取每个图像的特征，在我们的例子中是每个邻接矩阵。我们首先将输入数据馈送到卷积层以提取特征，然后将这些序列传递到单独的LSTM，以从输入序列中学习长期时间相关性。在CNN模型中，我们使用整流线性单位(ReLu)作为激活函数，它是使用f(x) = max(0，x)计算的，其中，x是输入数据。在LSTM模型和输出层，我们使用sigmoid激活函数。在DLP-LES中，我们为损失函数分配二元交叉熵来度量分类模型的性能。它可以写成 -(y.log(p)+(1-y).log(p)) ，其中y是标签，p是预测概率。