Deep Dynamic Network Embedding for Link Prediction阅读笔记

原创 2020-06-16 11:41  阅读 39 次 评论 0 条

Deep Dynamic Network Embedding for Link Prediction阅读笔记

论文来源:2018 IEEE Access

论文链接:Deep Dynamic Network Embedding for Link Prediction

论文原作者:TAISONG LI, JIAWEI ZHANG, PHILIP S. YU, et al.

Introduction

近几年,很多网络嵌入算法被提出,它们可以很好地将网络信息在嵌入空间中表达出来,如IsoMAP、LE、LINE等这些经典算法。上述这些算法都是线性地映射到嵌入空间中,然而大多数情况下,网络结构映射到嵌入空间时都是非线性的,于是一些深度学习的模型就被提出用于网络表示学习领域,比如SDNE,node2vec以及Deepwalk等等。由于是深度神经网络结构,这些方法能够很好地对网络结构做非线性变换,然而它们大多是针对于静态的网络。

从动态网络学习嵌入向量表达的挑战主要是:1.如何利用历史以及当前的网络结构信息去预测未来的网络结构信息;2.如何在网络表达学习中捕捉到非线性的动态链接变化模式;3.在网络动态变化时,如何将网络节点的邻居相邻关系保持下来。

基于上述的考虑,这篇文章提出了模型DDNE,从历史快照(snapshot)中捕捉非线性变换来学习动态网络的顶点表示。DDNE算法的灵感来源于RNN,即循环神经网络,这样一来,网络中每个节点的非线性动态变化就能被学习出来。然而,动态网络每个节点虽然有着时域上的变化信息,但每个时刻它也会和邻居节点进行交互,而传统的RNN网络的每个输入样本都是独立的,这样就会忽略节点向量之间的联系。因此,DDNE算法还考虑了“交互接近度”这样一个概念,使得算法能够捕获节点的非线性变换,并保持动态网络的结构的同时,还能保持节点在一个演化周期中的交互信息。

专栏之前也介绍过动态网络嵌入算法DynamicTriad,该算法主要是通过Triad三元环这个载体来获取网络变化的信息;而DDNE算法则是通过RNN来获得非线性动态变化的参数来捕捉网络变化的信息。

Model-DDNE: DEEP DYNAMIC NETWORK EMBEDDING

DDNE算法主要是RNN+交互接近度,首先介绍一下RNN。

1.RNN

目前各种实验表明,GRU-RNN和LSTM-RNN性能上要比tanh-RNN好,而GRU在运行速度上要略优于LSTM,因此DDNE算法采用的是GRU-RNN去对动态网络数据建模。

GRU是由4个单元组成,分别是重置门 \(r^t\),更新门 \(z^t\) ,候选记忆单元 \(\tilde{h}^t\) 以及当前时刻记忆单元 \(h^t\) ;整个GRU结构如下图所示:

GRU的各单元函数为:

2.ENCODER-DECODER OF DDNE

DDNE算法的框架如下图所示:

之前说到过,GRU可以获取历史演变模式,然而,它对于每个节点的学习是独立的,这样就会忽略节点与其邻居节点之间的联系,因此该算法在DECODER步骤考虑“交互接近度”。更通俗地解释就是,通过对两个节点的隐藏层向量的距离进行优化,将两个紧密相连的节点映射到相似的嵌入空间上。

除此之外,在DECORER步骤,是将历史上每一个时刻的GRU输出拼接作为隐藏层的向量,这样一来该隐含层就能保存新网络的所有结构信息;DECORER的输出是一个推断的邻接向量,用来和新时刻的链接结果做比较,从而得到loss值。

3.LOSS Functions

误差函数主要由两部分构成。

首先介绍动态网络的结构误差。它指的是预测结构的精确程度,为了最小化这种偏差,需要对每个顶点的邻域转换进行建模。假设给定一个动态网络 \(G=\{{G_{t-N},...,G_{t-1},G_t}\}\) ,其中t为当前时刻,N为窗口长度;这样一来,就能得到邻接矩阵 \(\chi=\{\bf{{X}^{t-N}},...,\bf{{X}^{t-1}},\bf{{X}^{t}}\}\),且如果k时刻时,节点i和节点j之前存在链接,则 \(\bf{{X}^{k}_{ij}}>0\) 。

回到GRU-RNN,假如编码器输入为 \(\mathbf{x}\),则GRU的隐藏层为:

\(\mathbf{h}^t=f(\mathbf{h}^{t-1}+\mathbf{x}^t)\) ,其中f是非线性的激活函数。

在读取完整个动态网络序列后,编码器的输出则为所有GRU的隐藏层的总和,具体来说,即对于节点i来说,给定一个时序输入 \(\mathbf{{X}(i,:) = \{\mathbf{X}^{t-N}}(i,:),...,\mathbf{X}^{t-1}(i,:)\}\) ,则编码器的输出为:

其中,下面两个公式指的是序列的不同方向,前者为从(t-N)到(t-1),后者则相反,两者拼接成向量 \(h^k_i\) ,之后所有隐藏层状态向量拼接成向量 \(c_i\) ,作为编码器的输出。

之后,经过解码器后,就可以得到输出向量:

其中M表示的是解码器中隐藏层的层数。

这样一来,输出 \(y_i^{(m)}\) 即为推断出来的网络新链接关系,而输出层上一层的隐藏层即为我们所需的节点嵌入向量表达。解码器的目标是最小化预测误差,因此采用交叉熵作为损失函数,误差函数为:

然而,在真实网络中,绝大多数网络节点的邻居节点个数是少量的,因此在节点邻接向量中,非0值远远小于0值,如果直接使用节点邻接向量去学习,那么解码器就的输出向量就很容易预测为0。因此,文章引入一个参数,使得对非零元素的预测误差比零元素的预测误差惩罚更大。修改后的误差函数为:

其中, \(\mathbf{Z}(i,:)=\{{Z(i,j)}\}^n_{j=1}\) . 如果X(i,j)=0,则Z(i,j)=0;如果X(i,j)>0,则Z(i,j)= \(\alpha>1\) .

第二部分则是每个节点受邻居节点影响的网络内部结构误差,也就是考虑交互接近度。交互接近度可以看成一对节点的接近度,可以通过使用它们在先前快照中的链接来测量的,这样如果两个节点拥有更频繁的链接,则它们更有可能拥有相似的嵌入向量。用 \(N_{ij}\) 来衡量节点之间的亲密程度,它是两个节点之间链接的总和。因此,网络内部结构误差函数为:

最终,整个DDNE算法的总误差函数为:

其中, \(\beta,\gamma\) 是折衷参数, \(L_{reg}\) 是L2-norm的正则化项。

模型的训练采用的是自适应的随机梯度下降法。

Conclusion

这篇文章提出了针对链接预测的动态网络嵌入算法DDNE,它的创新点在于使用了双向GRU-RNN去对动态网络数据建模以及在解码器时考虑了节点与节点之间的亲密程度。总得来说,想法很简单,就是将循环神经网络应用到网络嵌入学习这个领域上。此外,该算法比较大的一个缺点在于因此RNN的复杂度,很难拓展应用到大规模网络中,该论文实验所用的数据集规模较小也证明了这一点。不过,如果更好地在大规模网络中学习嵌入向量,也是这个领域最棘手的问题,希望以后能有更好的方法来解决。

本文地址:http://51blog.com/?p=10592
关注我们:请关注一下我们的微信公众号:扫描二维码广东高校数据家园_51博客的公众号,公众号:数博联盟
版权声明:本文为原创文章,版权归 jnussl 所有,欢迎分享本文,转载请保留出处!

发表评论


表情