Dynamic Network Embedding by Moding Tridaic Closure Process : 论文笔记

转载 2019-11-23 23:03  阅读 16 次 评论 0 条

这篇论文是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维的向量表示:

\(x_{ijk}^t = w_{ik}^t*(u_k^t-u_i^t)+w^t_{jk}*(u_k^t-u_i^t)\)

论文还定义了一个社交策略参数\(\theta\),是一个从节点隐含表示中抽取的d维的向量,表示社交策略信息。对于一个开三角\((v_i,v_j,v_k)\),在t+1时刻演变为闭三角的概率为:

\(P_{tr_+}^t(i,j)=\sum_{\alpha^{t,i,j\neq0}}{\prod_{k\in{B^t(i,j)}}(P_{tr}^t(i,j,k))^{\alpha^{t,i,j}_k}}\times{(1-P_{tr}^t(i,j,k))^{(1-\alpha^{t,i,j}_k)}}\)

考虑到\(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时刻建立的概率为:

\(P_{tr_+}^t(i,j)=\sum_{\alpha^{t,i,j\neq0}}{\prod_{k\in{B^t(i,j)}}(P_{tr}^t(i,j,k))^{\alpha^{t,i,j}_k}}\times{(1-P_{tr}^t(i,j,k))^{(1-\alpha^{t,i,j}_k)}}\)

\(p_{tr_+}^t(i,j)=\sum_{\alpha^{t,i,j}\neq0}{\prod_{ k\in{B^t(i,j)}}{(P^t_{tr}(i,j,k)} )^{\alpha^{t,i,j}_k}} \times {(1-P^t_{tr}(i,j,k)} )^{(1-\alpha^{t,i,j}_k)}\)

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

\(P_{tr_-}^t(i,j)= \prod _{k\in{B^t{(i,j)}}}{( 1-P^t_{tr}(i,j,k))}\)

合并两部分,

\(L_{tr}^t=-\sum_{(i,j)\in{S^t_+}}{logP^t_{tr_+}(i,j)} - \sum_{(i,j)\in{S^t_-}}{logP^t_{tr_-}(i,j)}\)

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

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

\(L_{sh}^t = \sum_{(j,k)\in{E^t_+},(j',k')\in{E_-^t}}{h(w_{jk},[g^t(j,k)-g^t(j',k')+\xi]_+)}\)

\(L_{smooth}^t =
\begin{cases}
\sum_{i=1}^N||u_i^t-u^{t-1}_i||^2_2& t>1 \\
0& t=1
\end{cases}\)

总的损失函数为:

\(\arg {\min{\sum_{t=1}^T{L_{sh}^t}+\beta_0L_{tr}^t+\beta_1L_{smooth}^t}}\)

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

3、Experiments

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

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

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

4、Summary

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

本文地址:http://51blog.com/?p=6285
关注我们:请关注一下我们的微信公众号:扫描二维码广东高校数据家园_51博客的公众号,公众号:数博联盟
温馨提示:文章内容系作者个人观点,不代表广东高校数据家园_51博客对观点赞同或支持。
版权声明:本文为转载文章,来源于 ROOTLu ,版权归原作者所有,欢迎分享本文,转载请保留出处!

发表评论


表情