BLOG

个人博客,记录学习与生活

[KDD2016]SDNE

Published July 27, 2020, 4:23 p.m. by kkk

SDNE: Structural Deep Network Embedding1。首先,介绍网络表示的特性:高非线性、结构保存、稀疏,随后说明深度学习的进展和成就(图像、文本、语音)。

特点

为了更好地保存高维非线性网络结构,采用半监督的非线性深度模型,同时利用一阶相似性二阶相似性进一步解决网络结构保存和稀疏问题(类似于LINE)。网络的非监督部分保存二阶相似性(全局结构),监督部分保存一阶相似性(局部结构),下图可见,网络中通常具有二阶相似性的节点对远多于具有一阶相似性的节点对(为了说明二阶相似性的重要性)。

对一阶相似性和二阶相似性的定义同LINE,某一点$v$的一阶相似性$N_V$为节点在网络邻接矩阵中对应的向量,二阶相似性指点$v,u$的$N_v,N_u$之间的相似性

网络结构

通过拓展传统的自动编码器来保存二阶相似性。输入为网络的邻接矩阵$S={s_1,s_2,\cdots,s_n}$,输出为经过重构的邻接矩阵,通过比较$x$和$\hat x$可以检验网络学习的效果,其中$y_i^{(k)}$为训练得到的节点特征向量。

上图中为两个网络结构,实际上只有一个,图只是为了说明中间的Laplacian Eigenmaps的思想,体现对一阶相似性的保存(见一阶相似性损失函数)。

网络参数为:$\theta={ W^{(k)}, \hat W^{(k)}, b^{(k)}, \hat b^{(k)} }$,不带上三角形符号的参数是编码部分网络(图上从$x_i$到$y_i^{(K)}$),带上三角形符号的参数是解码部分网络(图上从$y_i^{(K)}$到$\hat x_i$)

损失函数

二阶相似性损失函数

首先是二阶相似性的损失函数,通过网络的无监督学习进行学习,损失函数如下: $$ \begin{align} \mathcal L_{2nd} &= \sum_{i=1}^n {\Vert (\hat x_i-x_i)⊙b_i}\Vert_2^2 \\ &= \Vert (\hat X - X)⊙B \Vert_F^2 \end{align} $$ 其中$⊙$叫做Hadamard积,听起来可能很陌生,其实就是两矩阵相同位置上的元素相乘。而$b_i$是为了修正网络对非零元素的重构,当$s_{i,j}=0$时,$b_{i,j}=1$,不然$b_{i,j}= \beta > 1$。

网络中的$y_i^{(.)}$通过下面两个式子计算而得($\sigma()$为sigmoid函数): $$ y_i^{(1)} = \sigma(W^{(1)}x_i +b^{(1)}) $$

$$ y_i{(k)} = \sigma(W^{(k)}y_i^{(k-1)} + b^{(k)}),k=2,\cdots,K $$

一阶相似性损失函数

对于一阶相似性的损失函数,借助了Laplacian Eigenmaps2中的思想:相似节点,在映射空间距离较远的两点,应该加大惩罚,在深度模型中运用该思想,使得网络得以保存节点的一阶相似性。 $$ \begin{align} \mathcal L_{1st} &= \sum_{i,j=1}^n s_{i,j}{\Vert {y_i^{(K)}-y_j^{(K)}}}\Vert_2^2 \\ &= \sum_{i,j=1}^n s_{i,j}{\Vert {y_i-y_j}}\Vert_2^2 \end{align} $$

正则化损失函数

此外,为了防止过拟合,对网络加上L2范数正则化: $$ \mathcal L_{reg} = \frac{1}{2}\sum_{k=1}^K(\Vert W^{(k)} \Vert_F^2+\Vert \hat W^{(k)} \Vert_F^2) $$

整体损失函数

如此之后,网络整体的损失函数为: $$ \begin{align} \mathcal L &= \mathcal L_{2nd} + \alpha \mathcal L_{1st} + \nu \mathcal L_{reg}\\ &= \Vert (\hat{X} - X) ⊙ B \Vert_F^2 + \alpha \sum_{i,j=1}^n s_{i,j} \Vert y_i - y_j \Vert_2^2 +\frac{1}{2}\sum_{k=1}^K(\Vert W^{(k)} \Vert_F^2+\Vert \hat W^{(k)} \Vert_F^2) \end{align} $$

优化

采用常用的基于反向梯度传播的SGD

由于模型的高非线性,导致参数空间中存在许多局部最优解,为了找到更好的参数空间区域,使用深度信念网络(Deep Belief Network)首先对参数进行预训练3

完整的算法流程如下图:

新节点处理

和其它的网络表示方式一样,只能处理与已有网络有边相连的新加节点,如果新节点与已有网络无边相连,则无法处理。对于这种情况的处理,需要诉诸于其它方面的信息,如新节点的内容特性。



  1. M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373–1396, 2003. 

  2. Wang D, Cui P, Zhu W. Structural deep network embedding. Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016: 1225-1234. 

  3. G. E. Hinton, S. Osindero, and Y.-W. Teh. A fast learning algorithmfor deep belief nets. Neural computation, 18(7):1527–1554, 2006. 


Share this post
< Pre: [KDD2016]Node2Vec Pos: [MLSP2016]Item2Vec >
2 comments
Similar posts
Add a new comment