Dynamic Network Embedding by Modeling Triadic Closure Process 阅读笔记

转载 2020-06-16 11:10  阅读 49 次 评论 0 条

论文来源:AAAI 2018

论文链接:Dynamic Network Embedding by Modeling Triadic Closure Process

论文原作者:Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, Yueting Zhuang

论文模型源码:Github code

Abstract

Network embedding是最近网络挖掘领域很火的一块,目的是希望能够将网络中的节点用比较低维的向量去表达,同时在这个向量空间中,网络结构的一些性质仍能够保持。然而,之前这个领域上比较经典的算法比如Deepwalk,node2vec,LINE以及其他各种扩展的算法都大多是对静态网络进行研究。

在现实生活中,大多数网络是会随着时间变化的。因此,这篇论文提出了一个新的网络表示学习方法-DynamicTriad,使得在保持网络结构性质的同时,也将网络的时间变化特性嵌合到向量中。论文通过引入triad(三合音):三个顶点组成的一个网络基本单元,来作为网络动态变化的基本机制,从而使模型能够捕捉网络的动态,并在不同的时间点学习每个顶点的向量表示。

Introduction

在网络动态的演变过程中,不同节点的结构演变可能也是不同的,而传统的network embedding很难能够获取到这些结构的演变模式。以社交网络为例,用户A可能更愿意介绍他的朋友相互认识,因此可能在时间t时,与用户A相连的两个节点还未相连,而到了t+1时,用户A已经介绍他们两个认识了,则此时与用户A相连的两个节点也形成了边。而用户B可能倾向于让他的朋友保持他们的圈子,所以不会介绍他的朋友互相认识。不同的用户进化模式反映了他们自己的性格和社会策略之间的差异,这是用来满足他们的社会需要,比如发展与他人的联系。因此,是否能够很好地反映顶点的演化模式是动态网络嵌入方法的一个关键要求。

这篇文章主要是通过捕获网络的演化结构属性来学习顶点的嵌入向量。给出时间阶段1-T上的网络 \(G_1,...,G_T\) ,目标是希望能够学习出节点i 在时间阶段t 的向量表示 \(\textbf{u}_t^i\) 。之前的一些方法大多都是通过添加正则化项来表示平滑的动态变化,但这样做的话就不能够很好地表达一些急剧变化的节点,而且也不能体现出一些结构的演变。这篇文章通过triad来体现网络结构的动态变化,总的来说,存在两种traid:closed triads(三个顶点中的任意两点,都存在连接关系) 以及 open traids(三个顶点中有两点是没有互相连接的)。一个open traid发展到closed traid的过程叫做triad closure process,它是动态网络形成与演化的基本机制,而这篇文章就是通过量化open triad发展成closed triad的概率,从而在不同的时间点中学习每个顶点的嵌入向量。

Model

1.Definition.

网络由节点集 \(V = \{v_1,...,v_M\}\) 和边集 \(E = \{e_{ij} \} \) 组成, 其中 \(e_{ij}\) 指的是节点 \(v_i\) 和 \(v_j \) 的关系

动态网络: \(\{G^1,G^2,...,G^T\}\), 其中 \(G^t = (V,E^t,W^t)(1\leq t\leq T)\) 指的是t时刻的网络表达,每一条边 \(e^t_{ij} \in E^t\) 对应着权重 \(w^t_{ij} \) 。

动态网络嵌入表达主要是学习映射函数使得: \(f^t : v_i \rightarrow R^d \text{ for each t}\) ,其中d是嵌入空间的维数。对于函数 \(f^t\) ,希望它不仅能够保持得了节点 \(v_i \) 和 \(v_j\) 在网络 \(G^t\) 中的相似性,同时能够保持这些节点在之后拓展关系(比如说,在t+1后,与其他点建立了新的连接)的趋势。

用 \(\textbf{u}_i^t := f^t(v_i) \) 和 \(\textbf{u} = \{\textbf{u}_i^t\}_{i=\{1,...,M\},t=\{1,...,T\}}\) 来表示学习到的网络向量。

2.Model Description

整个模型的目标函数从三个方面去考虑:

<1>.Triad closure process.

以社交网络为例,在某个时刻t, \((v_i,v_j,v_k)\) 构成了一个open traid,其中节点 \(v_i\) 和 \(v_j\) 互相不认识但他们都是 用户\(v_k\) 的朋友,即: \(e_{ik},e_{jk} \in E^t \text{ and } e_{ij} \notin E^t\) . 在下一时刻t+1时,用户 \(v_k\) 会决定是否介绍 \(v_i\) 和 \(v_j\) 相互认识,而这个决定通常取决于 \(v_k\) 和他们两个有多熟悉,因为一般来说,我们都愿意把自己的好朋友介绍给另一个好朋友。所以,可以先用一个向量去量化用户k和他们两者的亲密程度:

\(\textbf{x}^t_{ijk} = w^t_{ik} * (\textbf{u}_k^t - \textbf{u}_i^t ) + w^t_{jk} * (\textbf{u}_k^t - \textbf{u}_j^t) \) , 其中 \(\textbf{u}_i^t\) 指的是t时刻下的节点i的嵌入向量。

除此之外,还要定义一个社会策略参数 \(\boldsymbol{\theta} \in R^d\) ,从而将社会策略的一些信息也嵌入到对应的隐式空间中。

这样一来,可以将open traid演变成closed traid,即在t+1时刻时,节点 \(v_i \) 和 \(v_j\) 会在节点 \(v_k\) 的介绍下建立连接的概率,定义为:

\(P^t_{tr}(i,j,k) = \frac{1}{1+exp(-\langle \boldsymbol{\theta},\textbf{x}^t_{ijk} \rangle)}\)

由于节点 \(v_i \) 和 \(v_j\) 可能会被其他共同好友介绍,所以要将这些可能联合起来。用集合 \(B^t(i,j)\) 来表示 \(v_i\) 和 \(v_j\) 在时刻t的共同邻居,并定义一个向量 \(\boldsymbol{\alpha}^{t,i,j} = (\alpha^{t,i,j}_k)_{k \in B^t(i,j)}\) , 表示如果在t+1时刻时open triad \((v_i,v_j,v_k)\) 演变成closed traid(即 \(v_i\) 和 \(v_j\) 有连接),则 \( \alpha^{t,i,j}_k = 1\) 。可以想到,如果 \((v_i,v_j,v_k)\) 演变成closed traid的话,那么其他与 \(v_i\) 和 \(v_j\) 相关的open traid 也会变成closed,所以在t+1时,一个新的连接 \(e_{ij}\) 会被产生的概率为:

\(P_{tr_+}^t = \sum_{\boldsymbol{\alpha}^{t,i,j} \ne \bf{0}}\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}\)

当然,如果 \(v_i\) 和 \(v_j\) 都没有被它们的共同好友所影响到,那么新的连接 \(e_{ij}\) 就不会被产生,这个概率为:

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

为了更清晰地表达,定义两个集合: \(S^t_+ = \{ (i,j) | e_{ij} \notin E^t \wedge e_{ij} \in E^{t+1}\}\) 表示的是t+1时刻能够建立连接,以及 \(S^t_- = \{ (i,j) | e_{ij} \notin E^t \wedge e_{ij} \notin E^{t+1}\}\) 指的是不能建立连接。 所以triad closure

process的损失函数表达为:

\(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)}\)

<2>. Social homophily

第二个方面考虑的是网络内部的性质。

首先定义在嵌入向量空间下节点 \(v_j \) 和\(v_k\) 的距离: \(g^t(j,k) = \| \textbf{u}_j^t - \textbf{u}_k^t\|^2_2\) . 另外,在定义两个集合,分别是边集 \(E^t_+ = E^t\) 和非边集 \(E^t_- = {e_{jk} | j \ne k, e_{jk} \notin E^t}\) .

在向量学习中,我们希望原本网络中相连的节点在嵌入空间中仍然接近,而不相连的节点可以稍远些。因此,损失函数可以表达为:

\(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)]_{+} )\) ,其中 \([x]_+ = max(0,x)\) , \(\xi \in R^+\) 是边际值,函数 \(h(w,x) = w * x\) .

<3>.Temporal smoothness

第三个是时序上变化的考虑。一般来说,网络的变化是平缓的,也就是说,连续时间戳下,网络的向量表达的变化相差不能太大。因此,对应的损失函数可以表达为:

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

综上,考虑了动态网络中traid的演变,网络内部的性质,以及平缓的变化趋势,最后整个模型的求解是最小化损失函数:

\(\mathop{\arg\min}_{ \textbf{u}_i^t,\boldsymbol{\theta}} \sum_{t=1}^{T}{L^t_{sh} + \beta_0L^t_{tr} + \beta_1L^t_{smooth}}\)

3.Model optimization

由于损失函数比较复杂,因此要对它进行优化。论文中对优化步骤都提及到了,但有些细节因为文章篇幅的限制所以省略了,在这里我们也稍微提及下。

对于损失函数 \(L^t_{tr}\) ,它由两项组成。对于 \((i,j) \in S^t_-\) 来说,损失函数可以很简单地求解,只需要将 \(P^t_{tr_-}(i,j,k)\) 代入即可。然而对于 \((i,j) \in S^t_+\) 来说,由于隐式变量 \(\boldsymbol{\alpha}^{t,i,j}\) 的存在,因此无法直接代入求解,因此论文使用了EM算法去计算出上界,从而方便去求导。

对于损失函数 \(L^t_{sh}\) ,在大型网络中,遍历每一对节点的代价是昂贵的,因此这里使用了采样的方法。

最后求导是使用自适应的随机梯度下降进行的,整个训练过程伪代码如下图所示,如果想更加具体了解优化过程的,可以到论文原文看看。

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

发表评论


表情