【论文笔记】Structural Deep Network Embedding

Structural Deep Network Embedding
https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf
本文介绍图嵌入的一种方法——SDNE，用深度神经网络来做图嵌入，以下主要摘录论文以及记录一点个人理解。

摘要

1. network embedding，是为网络中的节点学习出一个低维表示的方法。
2. 目的在于在低维中保持高度非线性的网络结构特征，但现有方法多采用浅层网络不足以挖掘高度非线性，或同时保留局部和全局结构特征。
3. 本文提出一种结构化深度网络嵌入方法，叫SDNE
4. 该方法用半监督的深度模型来捕捉高度非线性结构，通过结合一阶相似性(监督)和二阶相似性(非监督)来保留局部和全局特征。

前言

1. 从网络中挖掘信息很重要，通常用学习网络表示的方法来实现，即将网络嵌入低维空间，为每个节点学习一个向量表示。
2. 学习网络表示的难点：(1)高度非线性；(2)局部和全局结构保持；(3)稀疏
3. 现有方法多采用浅层模型，如IsoMAP、Laplacian Eigenmaps、LINE等，缺少挖掘高维的能力
4. 我们用深层模型解决highly non-linear结构的问题
5. 我们结合一阶相似性(直连)和二阶相似性(隔一个)的方法，构建一个半监督模型来保留局部、全局结构特征，并缓解稀疏问题

相关工作

这部分简单介绍了下Deep Neural Network和Network Embedding的研究现状，表示自己的不同之处在于——学习可用于其他任务的网络低维表示、保留局部全局结构特征、挖掘高度非线性特征、明确的学习目标等。

SDNE

1. 定义

   • 图：$G=(V,E)$G=(V,E)；
   • 结点：$V=\{v_1,...,v_n\}$V={v1​,...,vn​}；
   • 边：$E=\{e_{i,j}\}^n_{i,j=1}$E={ei,j​}i,j=1n​；
   • 权：$s_{i,j}\ge 0$si,j​≥0
   • 一阶相似性：即$s_{i,j}$si,j​
   • 二阶相似性：$\mathcal{N}_u=\{s_{u,1},...,s_{u,|V|}\}$Nu​={su,1​,...,su,∣V∣​}表示结点$v_u$vu​与其他结点的一阶相似性，则二阶相似性为$\mathcal{N}_u$Nu​和$\mathcal{N}_v$Nv​的关系
   • 解释：二阶相似性表达了两个不直接相连的结点的关系，可以实现保持全局网络结构并缓解稀疏问题
   • 网络嵌入：学习一个映射函数$f:v_i \mapsto \mathrm{y}_i \in \mathbb{R}^d,d\ll|V|$f:vi​↦yi​∈Rd,d≪∣V∣

2. 网络结构
   

   • 整体采用AutoEncoder的思路，由Encoder和Decoder组成
   • 输入的$x_i=s_i$xi​=si​，表示结点$i$i的邻接特征$s_i=\{s_{i,j}\}^n_{j=1}$si​={si,j​}j=1n​
   • 在非监督的部分，通过重建每个节点的邻居结构，来保留二阶相似性，提取全局特征，即$y_i^{(K)}$yi(K)​到$\hat{x}_i$x^i​的过程
   • 在监督部分，通过使相邻节点在表示空间中尽可能相近来实现保留一阶相似性，提取局部特征

3. 符号说明
   

4. 公式

   • 神经网络的计算公式
     $\mathrm{y}_i^{(1)}=\sigma(W^{(1)}\mathrm{x}_i+\mathrm{b}^{(1)})$yi(1)​=σ(W(1)xi​+b(1))
     $\mathrm{y}_i^{(k)}=\sigma(W^{(k)}\mathrm{y}_i^{(k-1)}+\mathrm{b}^{(k)}),k=2,...,K$yi(k)​=σ(W(k)yi(k−1)​+b(k)),k=2,...,K
   • 自编码器部分的损失函数
     $\mathcal{L}=\sum_{i=1}^{n}\|\hat{\mathrm{x}}_i-\mathrm{x}_i\|^2_2$L=i=1∑n​∥x^i​−xi​∥22​
   • 考虑到未相连的结点不代表无关，即对于邻接矩阵中大量为0的部分网络会“错误地”重点关注，因此要加上一些惩罚权重，其中当$s_{i,j}=0时，b_{i,j}=1$si,j​=0时，bi,j​=1；否则$b_{i,j}=\beta>1$bi,j​=β>1
     $\mathcal{L}_{2nd} =\sum_{i=1}^{n}\|(\hat{\mathrm{x}}_i-\mathrm{x}_i) \odot \mathrm{b}_i\|^2_2\\ =\|(\hat{\mathrm{X}}-\mathrm{X}) \odot \mathrm{B}\|^2_F$L2nd​=i=1∑n​∥(x^i​−xi​)⊙bi​∥22​=∥(X^−X)⊙B∥F2​
   • 对于一阶相似性，类似于拉普拉斯特征映射，损失函数定义为
     $\mathcal{L}_{1st}=\sum_{i,j=1}^{n}s_{i,j} \|\mathrm{y}_i^{(K)} - \mathrm{y}_j^{(K)} \|^2_2\\ =\sum_{i,j=1}^{n}s_{i,j} \|\mathrm{y}_i - \mathrm{y}_j \|^2_2$L1st​=i,j=1∑n​si,j​∥yi(K)​−yj(K)​∥22​=i,j=1∑n​si,j​∥yi​−yj​∥22​
   • 所以，最后的目标为最小化损失函数，其中$\mathcal{L}_{reg}$Lreg​是L2正则项
     $\mathcal{L}_{mix}=\mathcal{L}_{2nd}+\alpha \mathcal{L}_{1st}+\beta \mathcal{L}_{reg}$Lmix​=L2nd​+αL1st​+βLreg​
     $\mathcal{L}_{reg}=\frac{1}{2}\sum_{k=1}^{K} ( \|W^{(k)}\|^2_F +\hat{W}^{(k)}\|^2_F )$Lreg​=21​k=1∑K​(∥W(k)∥F2​+W^(k)∥F2​)
     后边还有一段关于参数求解的，主要是针对一阶相似性的求解，转化为了求矩阵的特征向量等步骤，具体参考论文，大概与Laplacian Eigenmaps类似

5. 参数初始化：用Deep Belief Network来与训练参数

6. 算法的步骤
   

7. 讨论：在加入新节点的时候，将其邻接信息$s$s输入网络，即可得到表示向量。

实验

论文用了3个社交网络、1个引用网络和1个语言网络来做实验，包括多标签分类问题、链接预测和可视化。用DeepWalk、LINE、GraRep、Laplacian Eigenmaps和Common Neighbor来做baseline
结果没细看。。。大概就是SDNE和LINE比较好，其他都不行啊、、、