《Dynamic Network Embedding by Moding Tridaic Closure Process》— 论文笔记

这篇论文是AAAI18年的一个工作,主要做的是动态网络的表示学习。在实际生活中,网络是动态演变的,不断有新的节点、新的边添加,同时也有旧的节点和边消失。论文立足于动态网络embedding,旨在保留网络结构特征的同时,能够刻画网络的演变模式(evloution patterns)

论文利用了网络分析中的三角闭合过程(triadic closure process)来建模动态网络,通过预测由开三角演变成闭三角的概率,来学习每个节点的隐含表示。

1、Motivation

在实际生活中,网络是动态演变的,也就是说网络中的节点和边都在动态的增加或者消亡。现有的一些网络嵌入方法大多数都局限于静态网络的表示学习,而忽略了网络的动态性这一重要信息。网络演变过程中,不同节点或边有不同的演变模式,而不同的演变模式反映了节点或边之间的不同特征和性质。因此,动态网络embedding要学到网络演变的结构特征。(网络演变模式)

论文基于三角闭合过程,建模网络的动态演变过程。三角闭合过程即是:从一个开三角 演变为 一个闭三角的过程,其中开三角指三个节点中有两个节点是没有连接的,闭三角指三个节点互相连接。其过程可以看下图。

2、Model

论文给出了动态网络及动态网络embedding的定义。对于动态网络的定义,论文假设网络中节点数不发生改变,只有边及其权重发生变化。对于动态网络embedding的定义,论文定义,对于每一个时间步的网络快照 $G^t$, 模型都学习一个映射函数$f^t: v_i \to \mathbb{R}^d$, 其中函数保留网络的结构特性和网络的演变趋势

值得注意的是,DynamicTriad对于每个节点$v_i$在每个时间步t上都会学到一个表示$u^t_i=f^t(v_i)$, 然后构成一个张量 $u=\{u_i^t\}_{i=\{1,…,M\},t=\{1,..,T\}}$. (M是节点总数,T是时间总数。)

一个开三角定义为$(v_i,v_j,v_k)$,其中$v_i$和$v_j$互相没有连接,但都和$v_k$有连接。论文假设$v_i$和$v_j$ 只会经过他们共同的朋友$v_k$的介绍认识,而$v_k$是否介绍取决于他们之间的相似程度(距离),通过一个d维的向量表示:

论文还定义了一个社交策略参数$\theta$,是一个从节点隐含表示中抽取的d维的向量,表示社交策略信息。

对于一个开三角$(v_i,v_j,v_k)$,在t+1时刻演变为闭三角的概率为:

考虑到$v_i$和$v_j$ 会有不止一个共同邻接,所以定义一个t时刻的共同邻居集合$B^t(i,j)$,和一个向量$\alpha^{t,i,j}=(\alpha{_k^{t,i,j}})_{k\in{B^t(i,j)}}$. 当$\alpha{_k^{t,i,j}}=1$表示在下一时刻,开三角$(u_i,u_j,u_k)$会闭合。

定义一个新连接会在$t+1$时刻建立的概率为:

对于不受共同邻居影响的节点,不会建立连接,定其概率为:

合并两部分,

这里的$S^t_+$表示在当前t时刻没有边连接的节点对集合,但在下一时刻会有边连接;$S_-^t$表示在当前时刻和下一时刻都不会有边连接的节点对集合。

论文还定义了两个常用假设,社交的趋同性和时序平滑性,从而定义一下两个损失函数:

总的损失函数为:

模型的基本内容到这就介绍的差不多了,最后论文中还介绍了如何学习模型,以及采样的一些问题,在这里就不再细写了,感兴趣可以参考论文。

3、Experiments

论文实验比较充分,用了三个数据集,其中两个是通话网络,还有一个学术合作网络,数据量都在万级以上,可以看下面的统计表。

实验共有6个,可以分类两类:一类是在t时刻进行常规任务,包括:节点分类,链路重构和变化链路重构;还有一类是对t+1时刻的预测任务,包括节点预测,链路预测和变化链路预测。实验效果可以看下图:

实验的详细描述可以参考论文。

4、Summary

总结一下,个人觉得论文想法很新颖,通过复杂网络分析中的三角闭合问题,建模动态网络的演变,很好的描述了网络的变化。论文的基本思路也很清晰,做法也比较容易理解。但其中我觉得存在几个问题:首先,从损失函数来看,还是沿用了以正则来建模动态性的思路,整体的损失函数还是以社交趋同性为主,而三角闭合过程和时序平滑性作为一种正则,建模网络的动态演变过程;其次,在三角闭合过程中,论文假设$v_i$和$v_j$只会经过$v_k$的介绍(作用)才会互相认识(建立连接),但是否存在不经过$v_k$而自行认识的情况??,对于这种情况,如何建模是否需要考虑呢?最后,论文似乎没有考虑不同邻居对$v_i$和$v_j$是否建立连接的影响权重,这个权重是否都一样?值得区别对待不同的邻居吧?

上面只是个人的一些理解和疑问,可能存在问题,欢迎指正。

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