dyngraph2vec, Capturing Network Dynamics using Dynamic Graph Representation Learning ​

方法 ​

问题陈述 ​

  • 图：G(V,E)G(V, E)
  • 动态图：G=G1,...,GT\mathcal{G}={G_1,...,G_T}
  • 目标：将一个节点，通过学习一个映射方法：ft={V1,...,Vt,E1,...,Et}→Rdf_t=\lbrace V_1,...,V_t,E_1,...,E_t\rbrace \to \Bbb{R}^d转换为一组低维向量：yv1,...,yvty_{v_1},...,y_{v_t}，其中yvi=fi(V1,...,Vi,E1,...,Ei)y_{v_i}=f_i(V_1,...,V_i,E_1,...,Ei)，是一个 d 维的向量，捕获了1−i1-i时刻的图动态变换。

dyngraph2vec ​

dyngraph2vec 是一个深度学习模型，输入前面几个时间片段的图，即可输出下一个时刻的图。

模型通过优化下面这个损失函数，来学习时刻tt的图嵌入（network embedding，即其向量表达）。

Lt+1=∥(At+l+1^−At+l+1)⊙B∥F2 =∥(f(At,...,At+l)−At+l+1)⊙B∥F2\begin{aligned} L_{t+1} &= \parallel (\hat{A_{t+l+1}}-A_{t+l+1})\odot \mathcal{B} \parallel^2_F \\\ &= \parallel (f(A_t,...,A_{t+l}) - A_{t+l+1}) \odot \mathcal{B}\parallel ^2_F \end{aligned}

其中，A 表示图的邻接矩阵，ff函数用来计算A^\hat{A}，也就是对t+l+1t+l+1时刻的图的邻接矩阵的估计。

B\mathcal{B}是惩罚项，Bij=β,for(i,j)∈Et+l+1,else1\mathcal{B}_{ij}=\beta, for (i,j) \in E_{t+l+1}, else 1。

⊙​\odot​表示一种矩阵的布尔运算，具体定义可以在这个pdf里面找一下（https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_4.pdf），不再详述。

文章使用的深度学习模型有如下三种：dyngraph2vecAE,dyngraph2vecRNN,dyngraph2vecAERNNdyngraph2vecAE, dyngraph2vecRNN, dyngraph2vecAERNN。

image-20181126170553492

我们可以看到，这三种方法都分成两个步骤，Deep encoders 的目的，是输入动态的邻接矩阵，为每个节点生成低维向量；Deep decoders 则可以根据低维向量，来生成下一时刻的预测图。