论文阅读笔记#5

论文：dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation

作者：Palash Goyal ，Sujit Rokka Chhetri ，Arquimedes Canedo

Research Questions

现今研究的网络一般是有复杂动态变化和不断演进的。如图这个社交网络，A在不同时刻可能会与不同人成为好友。静态网络无法预测这些变化，但通过观察多个快照（snapshot ）可以预测这些变化。这篇文章的目的就是通过时序快照来捕获潜在的网络动态演化。

Innovation Point

在网络中使用多个非线性（non-linear ）层来学习结构模式。
使用循环层来学习时序转变。

Basic knowledges

自编码器（autoencoders）

是前馈非循环神经网络，是一种无监督机器学习方法，具有非常好的提取数据特征表示的能力，它是深层置信网络的重要组成部分，在图像重构、聚类、机器翻译等方面有着广泛的应用。

可以将自动编码机看作由两个级联网络组成，第一个网络是一个编码器，负责接收输入 x，并将输入通过函数 h 变换为信号 y：\(y=h(x)\). 第二个网络将编码的信号 y 作为其输入，通过函数f得到重构的信号 r：\(r=f(y)=f(h(x))\)

定义误差 e 为原始输入 x 与重构信号 r 之差，e=x–r，网络训练的目标是减少均方误差（MSE），同 MLP 一样，误差被反向传播回隐藏层。

来源：http://c.biancheng.net/view/1958.html

Methods

Motivating Example

作者使用了三步来捕捉网络动态。

从黄色社区中随机选择十个不同的nodes
随机添加三十条边在选中的nodes(图中红色)和蓝色社区的nodes中
选中的nodes由黄色向蓝色转移，同时边也在按概率增加或移除
重复以上三步观察变化

文章的目的也变得明了，学习这10个nodes在社区中变化的embeddings predictive 。

Problem Statement

Dyngraph2vec

模型输入一组先前的图形，并在下一个时间步骤生成作为输出的图形。

模型通过优化损失函数来学习时间步t的网络嵌入。公式可视为预测出的t+l+1邻接矩阵与实际t+l+1的邻接矩阵的差与权重矩阵做elementwise product（两个同样维度的向量/矩阵每一个元素分别相乘）运算后所有元素的平方和。权重矩阵\(\mathscr{B}\)代表重构后可观察边权重值大于不可观察边。