《High-order Proximity Preserved Embedding For Dynamic Networks》— 论文笔记

论文是清华cui peng老师组发表在TKDE18年的一篇文章,基本思路是基于他们组内KDD16年的文章《Asymmetric Transitivity Preserving Graph Embedding》,在此基础上扩展为动态网络embedding。论文基于广义SVD分解(GSVD)矩阵摄动理论(matrix perturbation),在保留高阶相似性的同时,动态更新动态网络的节点表示

论文聚焦于:在保留网络高阶相似性的同时,当网络结构在下一时刻发生变化时候(增加/删除节点/边),如何快速有效的增量更新下一时刻节点的表示。论文通过把Katz相似性转化为一般化的SVD分解,建模网络的高阶相似性,然后基于矩阵摄动理论动态更新网络下一时刻的节点表示。

1、Movitation

论文基于KDD16的文章,对于常用的相似性度量Katz指数,存在一般化的表示,可以通过广义SVD分解求得网络节点的embedding,而避免显式地计算高阶相似性矩阵。但是,对于动态网络embedding,如何利用GSVD有效快速更新变化后的网络节点embedding(增加/删除节点或边)还是一个待解决的问题。

通过把GSVD问题转化为广义特征值问题(generalized eigenvalue problem),论文基于矩阵摄动理论可以实现保留高阶相似性的同时,完成变化的网络节点的embedding的增量更新

2、Model

论文定义一个在t时刻的动态网络为$G^{(t)}=\{V^{(t)}, E^{(t)}\}$,其中$V^{(t)}=\{v_1^{(t)},v_2^{(t)},…,v_N^{(t)}\}$,节点数为N。论文的目标是保留动态网络的高阶相似性,同时对新增加或删除的节点或边,能够快速更新节点的表示。

需要注意的是:在网络演变中,在每个时间步,把新增加或删除的节点看作孤立点,那么网络的变化就是边的变化,所以论文认为网络中节点的数量不变

论文将动态网络embedding分为两部分:静态模型保留网络节点间的高阶相似性在每个时间步,动态更新节点的表示。论文分别给出了静态网络embedding和动态网络embedding的定义。其中静态网络embedding的定义比较常见,这里只介绍一下动态网络embedding。

给定网络在$t+1$到$t+i$时间步的网络的邻接矩阵$\{A^{(t+1)}, A^{(t+2)},…,A^{(t+i)}\}$,以及静态网络在t时刻的节点表示$U^{(t)}$,动态网络embeddin就是要输出在$t+1$到$t+i$时间步的节点表示$\{U^{(t+1)}, …, U^{(t+i)}\}$。

2.1 静态网络embedding

论文基于KDD‘16的模型,对于网络高阶相似性的建模,定义如下的目标函数:

其中$U, U’\in{\mathbb{R}^{N*d}}$分别是基(basis)和坐标(coordinate),论文以$U$作为节点的表示。$S$定义为高阶相似性矩阵,通过Katz Index计算得出。

根据KDD‘16模型,可以将问题转化为广义的SVD问题,S可以通过其特征值和特征向量近似得到,即:

所以U和U’可以计算得到:

但SVD过程需要计算相似性矩阵S,其中的计算复杂度很高($O(N^3)$)考虑到S只是模型学习过程的中间产物,目标是学习节点的表示U,所以论文将SVD问题泛化为广义SVD问题,避免直接计算S。

广义SVD可以定义为:

其中,$ V^{l(t)}, V^{r(t)}$是奇异向量构成的矩阵,$\Sigma^{(t)}=diag(\sigma_1^{(t)},…,\sigma_N^{(t)})$是奇异值构成对角阵。

但其实完成GSVD依然存在$O(N^3)$的复杂度,考虑到只需要最大的d个特征值及其特征向量,所以不需要对M矩阵进行多项式计算,只需要对M矩阵乘以一个瘦长的矩阵就可以了,这个瘦长的矩阵大小为$N\times d$。

2.2 动态模型更新embedding

在无向图中,邻接矩阵A和相似性矩阵S都是对称矩阵,所以可以将GSVD定义为广义特征值问题

其中$\{\lambda_i\}$是S的特征值,$X$是对应的特征向量构成的矩阵。

上式等号左右乘以$M_a$,可以得到 (广义特征值问题的一般形式)

因此,根据奇异值$\Sigma$和奇异向量$V^l,V^r$,可以推出广义特征值问题的解$\Lambda, X$,同样根据特征值和特征向量$\Lambda,X$,也可以推出GSVD的解$\Sigma, V^l$和$V^r$。

至此,网络动态更新的过程可以转变为 对特征向量$X^{(t)}$到$X^{(t+1)}$的更新。

在动态网络演变中,给定网络邻接矩阵的变化$\Delta A$,则矩阵$M_a$和 $M_b$的变化定义为:$\Delta M_a=-\beta \Delta A$和 $\Delta M_b=\beta \Delta A$。

对于公式9,有如下形式:

化简,约去高阶项$\Delta M_b\Delta x_i, \lambda_i \Delta M_a \Delta x_i$,左乘一个$x_i^T$,得到:

又因为 $M_a, M_b$是对称的,所以有:

公式12可以化简为:

可以求解得出:

为了简化书写,论文定义:

所以有

下面计算$\Delta x_i$,论文假设网络的演变是平滑的,每两个时间步之间的变化比较小。基于矩阵摄动理论,可以假设特征向量的变化$\Delta x_i$是和前d和特征值成线性关系的

其中,$\alpha _{ij}​$表示特征向量$x_j​$对特征向量变化的贡献,可以通过计算得出,这里不再详细介绍,具体计算可以参考论文。

3、 Experiments

论文实验分为两大部分,一部分验证了静态模型的有效性,另一部分验证了动态更新算法的高效性,具体实验可以参考论文。

4、 Sussmmary

这篇论文和2017年CIKM的一篇属性动态网络embeeding[1]的思想基本一致,两个工作也应该是同期出来的。基本思想都是基于矩阵摄动理论,对网络的邻接矩阵或者相似性矩阵进行矩阵分解(特征值分解和SVD分解),只不过两篇focus的点有些差别,一篇着重于属性信息网络,一篇着重于网络高阶性的保留。

Reference

[1] Li J, Dani H, Hu X, et al. Attributed network embedding for learning in a dynamic environment[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. ACM, 2017: 387-396.

写的还不错?那就来个红包吧!
0%