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

Network embedding 是表示学习中很重要的一块
著名的算法有node2vec,line,SDNE,svd等等
这篇论文提出的模型主要是对社交网络中的三角闭包结构和社交网络的时间动态变化建模

Definition

点集 V = { v₁,v₂,…,v_M }
边集 E = { e_ij }

动态网络 G = { G¹,G²,…,G^T}
G^t = ( V , E^t , W^t ) 表示每个时间段的网络图,W^t是权重
u^t_i = f^t(v_i) 表示学习到的结点v_i向量

Triadic closure process 三元闭包过程

以社交网络为例
( v_i,v_j,v_k)在某时间段是个(open traid)开三角
即i,j互不认识,但k认识他俩
三元闭包过程就是以预测下一个时间段i,j会相识的概率
这个概率取决于k与他们的亲密程度
一般来讲越亲密越容易介绍他俩彼此相识
亲密程度建模如下,w为权重

$x^t_ {ijk} = w^t_ {ik} * ( u^t_ {k} - u^t_ {i} ) - w^t_ {jk} * ( u^t_ {k} - u^t_ {j})$

其中下个时间段相识的概率为
$x^t_ {ijk} = w^t_ {ik} * ( u^t_ {k} - u^t_ {i} ) - w^t_ {jk} * ( u^t_ {k} - u^t_ {j})$

极大似然估计
$(P^t_{tr}(i,j,k))^{\alpha_{k}^{t,j,k} } * (1-P^t_{tr}(i,j,k)))^{1-\alpha_{k}^{t,j,k}}$
α_ijk^t 为label ,下一时刻( v_i,v_j,v_k)为(close traid)闭三角则为1,反之为0

再遍历所有open traid的样本组累乘概率进行极大似然估计
loss函数为
$L^t_{tr} =- \sum_{(i,j)\in S_+}logP^t_{tr+}(i,j) - \sum_{(i,j)\in S_-}logP^t_{tr-}(i,j)$
S₊ 是下一段时刻会变成close traid的样本组集合
S_- 相反

$L^t_{sh} = \sum_{(i,j)\in E^t_+ , (i^{'},j^{'}) \in E^t_-}h(w_{j,k},[g^t(j,k) - g^t(j^{ '},k^{'}) + \xi ]_+ )$
E^t_- 为E^t中不存在的边
h(w,x) = wx
[ x ]₊ = max(0,x)
该loss即使用了 tripet loss 期望近邻结点相似,非近邻结点稍远

Temporal smoothness

$L^t_{smooth} = \begin{cases} \sum^N_{i=1} || u^t_i - u^{t-1}_i || & t>1 \\ 0 & t=1 \end{cases}$

基于结点随时间的动态变化是平缓的猜想

final

最终三个loss加权求和即为最终loss

Definition

Triadic closure process 三元闭包过程

Social homophily

Temporal smoothness

final