@[TOC]

论文信息

GC-LSTM: graph convolution embedded LSTM for dynamic networklink prediction

原文地址：https://link.springer.com/article/10.1007/s10489-021-02518-9

摘要

Dynamic network link prediction is becoming a hot topic in network science, due to its wide applications in biology, sociology, economy and industry. However, it is a challenge since network structure evolves with time, making long-term prediction of adding/deleting links especially difficult. Inspired by the great success of deep learning frameworks, especially the convolution neural network (CNN) and long short-term memory (LSTM) network, we propose a novel end-to-end model with a Graph Convolution Network(GCN) embedded LSTM, named GC-LSTM, for dynamic network link prediction. Thereinto, LSTM is adopted as the main framework to learn the temporal features of all snapshots of a dynamic network. While for each snapshot, GCN is applied to capture the local structural properties of nodes as well as the relationship between them. One benefit is that our GC-LSTM can predict both added and removed links, making it more practical in reality, while most existing dynamic link prediction methods can only handle removed links. Extensive experiments demonstrated that GC-LSTM achieves outstanding performance and outperforms existing state-of-the-art methods.

动态网络链接预测由于其在生物学、社会学、经济学和工业界的广泛应用，正成为网络科学的研究热点。然而，这是一个挑战，因为网络结构随着时间的推移而演变，使得添加/删除链接的长期预测特别困难。受深度学习框架，特别是卷积神经网络( CNN )和长短时记忆( LSTM )网络的巨大成功的启发，我们提出了一种新的端到端模型，将图卷积网络( GCN )嵌入LSTM，命名为GC - LSTM，用于动态网络链接预测。其中，LSTM被用作学习动态网络所有快照的时间特征的主要框架。而对于每个快照，GCN被用来捕获节点的局部结构属性以及它们之间的关系。一个好处是我们的GC - LSTM可以同时预测添加和删除的链接，使其在现实中更具实用性，而大多数现有的动态链接预测方法只能处理删除的链接。大量实验表明，GC-LSTM取得了出色的性能，并优于现有的最先进的方法。

主要内容

1. 对于动态网络链接预测，提出一种新颖的端到端深度学习模型，命名为GC - LSTM，通过图卷积提取每个快照网络的结构特征，通过LSTM学习时序结构。这个模型可以高效的学习时空特征，对动态网络进行精确预测。
2. 现有的大多数方法只能预测网络中增加的链接，而该方法可以预测所有即将出现、消失或不变的链接，从而得到整个动态网络演化的准确预测。
3. 进行了大量的实验来验证GC - LSTM在动态网络上的有效性，并与不同的基线方法进行比较。

问题定义

动态网络(Dynamic Networks)

动态网络可以表示为一系列离散的快照 {G~1~, G~2~, …, G~T~}，其中G~t~ = (V, E~t~, A~t~)( t ∈ [1, T])表示 t 时刻的网络。设V为所有节点的集合，E~t~为固定时间跨度[ t - τ , t]内的时态链路。A~t~表示G~t~的邻接矩阵，如果i和j之间存在链接A~t~ ( i , j) = 1，，否则A~t~ ( i , j) = 0。

在静态网络中，网络链路预测问题一般旨在通过当前网络预测未被观测到的或未来的链路。静态链接预测方法主要关注网络的结构特征。与静态网络链接预测不同，动态网络链接预测还需要根据以往快照的动态演化过程来学习网络的时序特征。我们的目标是通过图卷积提取每个快照网络的结构特征，并通过LSTM学习时间结构。

动态网络中的网络链接预测

给定长度为T的一系列图。动态网络链接预测被作为结构序列建模问题考虑。它旨在学习前T个snapshot的演化信息来预测t时刻所有链路的概率。定义如下：

其中，表示前T个快照的邻接矩阵，和分别是t时刻快照的真实邻接矩阵和预测邻接矩阵。

GC-LSTM

GC - LSTM由编码器和解码器组成，如下图所示：

编码器模型为GCN嵌入LSTM，利用GCN学习每个时刻快照的cell状态c和隐藏状态h的网络结构，同时利用LSTM学习每个链路状态的时序信息。解码器是一个全连接层网络，用于将提取的特征映射回原始空间。GC-LSTM将输出预测网络并以统一的方式实现网络链路预测。

编码器（Encoder）

使用提出的GC - LSTM模型作为编码器，从结构序列数据中提取相应的时间和结构信息，最后时刻的隐含层向量h~t~将作为GC - LSTM的输出。

在动态网络链接预测任务中，每个节点多次与其他节点的链接状态(存在或不存在)可以看作一个时间序列，等价于邻接矩阵中的行向量。

LSTM应用于捕捉时序数据的时序特征。因此，在GC - LSTM中，利用LSTM来解决长期依赖问题，并有效地学习动态图的时间特征。动态网络中每个节点的链路状态可以使用LSTM来实现时序预测，比如预测下一时刻的链路。另一方面，需要利用节点先前的链路状态信息，并考虑邻居节点链路状态的影响，以及网络结构特性。GCN在网络嵌入学习结构特征方面已经被证明是有效的。提出GC - LSTM模型，其中采用图卷积( GCN )模型提取每一时刻快照的结构特征，LSTM学习动态网络的时序特征。

在GC - LSTM模型中，第一步是决定哪些信息会从之前的cell状态中丢弃。下一步是更新cell状态。更新后的cell信息不仅可以保存长期信息，还可以有选择地过滤掉一些无用的信息。最后，通过输出门来实现输出什么信息。

解码器（Decoder）

为了输出最终的预测网络，我们使用全连接层网络作为解码器，将序列数据中上一时刻的隐藏向量h~t~转化为最终的概率矩阵：

损失函数与模型训练

训练整个GC - LSTM模型的目的是为了提高动态网络链路预测的准确性，所以训练的目的是使输出概率矩阵在t时刻与邻接矩阵更加相似。

在回归预测问题中，L~2~通常用来反映预测值与真实值之间的相似程度。

由于网络的稀疏性，会导致预测结果偏向于零。为了在一定程度上避免这种过拟合，还使用了正则化项L~reg~。

因此，训练过程中的总损失定义为：

其中，β是权衡L~2~和L~reg~重要性的参数，最佳β将在模型训练过程中找到。正则化损失L~reg~通过计算GC - LSTM模型中所有权重的平方和来计算。并采用Adam作为我们模型的优化器。