《Structural Deep Network Embedding》---论文笔记

SDNE是清华大学崔鹏老师组发表在2016KDD上的一个工作,目前谷歌学术引用量已经达到了85,是一篇基于深度模型对网络进行嵌入的方法。SDNE模型同时利用一阶相似性和二阶相似性学习网络的结构,一阶相似性用作有监督的信息,保留网络的局部结构;二阶相似性用作无监督部分,捕获网络的全局结构,是一种半监督深度模型。

1、Introduction

论文指出了网络嵌入存在的一些问题:1)高度非线性的网络结构,简单的浅层模型(shallow model)很难捕获到其中的结构信息;2)网络表示需要保留其局部和全局的结构信息;3)网络的稀疏性,真实网络大多是非常稀疏的,网络的连接是非常有限的。而现有网络嵌入模型大多是浅层模型(shallow model),浅层模型很对复杂的网络进行很好的建模学习,无法很好的捕获高度非线性的网络结构信息。

为了解决上述是三个问题,论文提出了一种深度模型学习网络的节点表示。针对问题一,SDNE构建一个包含多个非线性函数的多层深度模型,这些非线性函数把数据映射到高度非线性隐含空间,所以能够更好地捕获网络的高度非线性网络结构。对于问题二和问题三,SDNE模型同时利用一阶相似性和二阶相似性学习网络的局部结构信息和全局结构信息。SDNE是一种半监督的模型,其中有监督部分利用一阶相似性作为有监督信息以保留网络的局部结构信息,无监督部分重建二阶相似性以保留网络的全局结构信息。

论文的主要贡献:

  • 提出了一种用于网络嵌入的深度模型,SDNE模型能够把数据映射到高度非线性的隐含空间,保留了网络的结构信息,同时对于稀疏网络有很好的鲁棒性。
  • SDNE模型是一种半监督框架,同时利用一阶相似性和二阶相似性,分别保留了网络的局部结构信息和全局结构信息。
  • 实验很充分,在多个实验任务(multi-label classification, reconstruction, link prediction and visualization)上验证模型,效果显著。

2、SDNE

2.1、Framework

SDNE是一种半监督深度模型,包含有监督和无监督两部分。有监督部分由Laplacian矩阵建模一阶相似性,无监督部分由深度自编码机对二阶相似性建模。模型框架如下图,需要注意的是自编码器应该对应的应该是Global structure preserved cost,而图中标注为local structure preserved cost不知是否是图中标错了

2.2、Loss Functions

SDNE模型的损失函数分为两部分,一部分是由深度自编码机建模得到,一部分是通过laplace矩阵建模定义。

自编码机部分,编码器对输入$x_i$进行编码,其中每一层的隐含表示计算为:

再用解码器对隐含层表示进行解码得到$\hat{x_i}$,因此自编码器的优化目标是最小化输入与输出之间的重构误差,损失函数定义为:

论文[1]证明了虽然最小化重构损失并不明确保留样本之间的相似性,但重建准则可以平滑地捕获数据流形,从而保持样本之间的相似性。因此SDNE把网络的邻接矩阵作为输入,即$x_i=s_i$,$s_i\in{S}, s_i=\{s_{i,j}\}^n_{j=1}, s_{i,j}>0$ 当且仅当节点$v_i, v_j$之间有边连接,$s_i$表示节点$v_i$的邻居结构。自编码器对输入进行重构,能够保证有相似邻居结构的节点会有相似的隐含表示。

但是,在真实网络中,邻接矩阵往往是非常稀疏的,非零元素的个数远低于零元素的个数,因此论文对原始自编码器的损失函数进行了改进,定义为:

其中,$\odot$表示哈达马乘积(对应元素相乘),$b_i=\{b_{i,j}\}^n_{j=1}$,如果$s_{i,j}=0,$那么$b_{i,j}=1$,否则$b_{i,j}=\beta>1$。

为了保留网络结构的一阶相似性,论文借鉴拉普拉斯特征映射(Laplacian Eigenmaps)的思想,即当两个相似的节点在嵌入空间中被映射到相距很远的位置时候,增加惩罚项。论文定义了如下的损失函数:

SDNE模型的最终损失函数定义为:

其中,$\mathcal{L_{reg}}=\frac{1}{2}\sum_{k=1}^k{||W^{(k)}||^2_F+||\hat{W}^{k}||_F^2}$

3、Summary

这篇论文整体思路比较清晰,想法也很简单,论文提出的SDNE模型融合一阶相似性和二阶相似性,构建了一个半监督的深度模型。其中,一阶相似性保留网络的局部结构信息,由Laplacian Eigenmaps建模定义损失函数,二阶相似性保留网络的全局结构信息,通过两个自编码器对节点对的邻接向量进行重构。值得注意的是,在自编码器对输入的邻接向量进行重构时,论文在原有的自编码器损失函数上添加了一个B,可以看作是一种”权重“,来解决网络构重构过程中邻接向量过于稀疏(零元素个数远大于非零元素个数),这种做法似乎比较常见,在以后的模型设计中也可参考借鉴。

Reference

[1]R. Salakhutdinov and G. Hinton. Semantic hashing. International Journal of Approximate Reasoning, 50(7):969–978, 2009.

写的还不错?那就来个红包吧!
0%