avatar

【论文笔记】Structual Deep Network

概要

网络嵌入方法(Network Embedding)旨在学习网络中节点的低维度潜在表示,所学习到的特征表示可以用作基于图的各种任务的特征,例如分类,聚类,链路预测和可视化。

问题概述

 现存的网络嵌入方法几乎都是利用了浅层网络模型,但是随着网络结构愈发复杂,浅层模型无法捕捉到高度非线性化的网络结构,这就导致了得到的网络表示是次优的。网络嵌入面临的问题有:

  • 高度非线性结构:网络的潜在结构是高度非线性的,模型需要捕捉到这些特征
  • 结构保留:网络嵌入结果应该保留住网络的结构特征以便与应用
  • 稀疏网络:现实世界中许多网络都是稀疏的,只有有限的链接可供观察学习

相关对策

 对于上述三个问题的相关对策分别为:

  • 高度非线性结构:SDNE设计了多层非线性函数深度学习模型,将网络的非线性结构映射到高度非线性的潜在空间,更好地捕捉网络结构。
  • 结构保留:SDNE结合使用网络的first-order proximity(一阶估计)和second-order proximity(二阶估计)。first-order反映网络局部结构,second-order反映网络全局结构。
  • 稀疏网络:由于second-order proximity的思想是衡量两个节点的共同临近点的相似程度,其提供的信息量远远大于first-order,所以加入second-order proximity在一定程度上应对了网络稀疏的问题。

论文提出的主要模型如文章开头所述:
 将可用于降维的自编码机应用于network embedding,利用多层非线性函数捕捉网络的高度非线性结构,并利用first-order作为监督信息,并保留网络的局部结构,second-order作为无监督学习部分,保留网络的全局结构,从而整体构成一个半监督的深度学习模型。
 在针对于网络嵌入的顶点分类、连接预测、网络可视化的多个数据集的多个任务中,SDNE的表现都较为出色。

相关工作

 提及了先前一些研究的不足之处,比如只关注一阶邻信息,或者只是对各阶信息进行简单地拼接。而本文提出的方法能够同时学习两阶信息保留局部与全局的网络结构。

SDNE 模型

问题定义

  图A用 $G = (V,E)$ 表示,其中 $V= { v1,…,v_n }$ 表示该图的 $n$ 个顶点,$E={ e{i,j} }^n{i,j=1}$ 表示边的集合。每条边都有一个权重值$s{i,j} \geq 0$. 当 $vi$ 与 $v_j$ 之间没有边链接的时候,$s{i,j}=0$ , 否则,对于无权图 $s{i,j}=1$ , 对于带权图 $s{i,j} > 0$ .

  • 一阶估计: 两个存在链接的节点的相似程度,对于节点对 $vi,v_j$ 若 $s{i,j}>0$ ,就说明两个节点间存在一阶相似度为正。如上图节点 $6$ 与 $8$ 等。
  • 二阶估计: 不同节点相邻结构的相似程度,用 $N{u} = { s{u,1},…,s{u,|V|} }$ 表示节点 $v_u$ 的邻近结构,那么二阶估计就是比较两个节点 $N_u 与 N{\nu}$ 的相似程度。如上图中的节点 $1$ 与 $6$ ,$N1={s{1,2},…,s{1,5}}$ ,$N_6={ s{6,2},…,s{6,5},s{6,8},s_{6,9} }$ 。如此一来,如果两个节点拥有许多共同邻居节点,他们的相似度就比较高。该结论在多个领域都得到了验证,比如一个两个单词拥有相似的上下文那这两个单词的相似的就相对会高等等。

 网络嵌入指的是,给定一个图表示 $G={V,E}$ ,其目标在于学习一个映射函数 $f: v_i\mapsto y_i \in R^d$, 其中 $d \ll |V|$.函数 $f$ 的目的是使得映射后得到的 $y_i,y_j$ 能够保留 $v_i,v_j$ 之间的相似性。

模型描述

模型结构

模型结构

 先从宏观角度来说,本文提出的模型由无监督部分监督部分两部分组成。无监督部分由多个非线性映射函数组成用于提取与二阶估计相关的特征;同时由于部分节点是直接相连的,因而可以得到其的一阶估计,从而引入模型的有监督部分。这两部分的损失函数线性组合,联合优化。

损失函数

相关符号表示参考

对二阶估计建模

 上文提到,二阶估计用于衡量两个节点的相邻结构之间的相似性。因此想对其建模就要对每一个节点的邻居结构进行建模。

 给定图$G=(V,E)$,可以得到其邻接矩阵表示$S$, 其包含$n$个实例$s1,…,s_n$,对于每个实例$s_i={ s{i,j} }^n{j=1}, s{i,j}>0$在当且仅当$v_i,v_j$之间有链接时成立。因此,$s_i$描述了节点$v_i$的邻居状况,矩阵$S$描述了每一个节点的邻居状况。有了$S$, 我们可以通过一个深度自编码器来保留二阶信息。

深度自编码思想:

 其实就是一个深度神经网络,其简单结构如下图:

image-20201125140104674

上图中输入$X$经过网络后得到$\hat{X}$, 根据损失函数$L=||\hat{X} - X||_2^2$优化调整权重,最终得到的中间层$Y$就是$X$的降维近似表示,它相当于一个非监督学习模型。因为利用输入自身来作为标签,以获得自身的降维表示,因此称为自编码。

在本文中给的是一个$K$层的自编码网络,对于给定的输入$x_i$, 每一层的计算过程如下:

在得到的$y_i^{(k)}$后,通过解码部分得到输出$\hat{x}_i$, 模型的目的是使得输入与输出的表示的误差尽可能小,故损失函数为:

在本例中,如果直接用$s_i$(表示$v_i$的邻居节点情况)作为输入,将其编码映射到一个潜在表示空间中。由于图可能是稀疏的,故模型会更倾向于重构$s_i$中的零元素,而这并不是我们想要的。为了解决这个问题,作者增加了重构非零元素的惩罚使得模型对有链接的节点对更加敏感:

$\odot$: 哈达玛积,矩阵运算$A \odot B = C$, 其中$C{i,j} = A{i,j} \times B_{i,j}$.

$bi={b{i,j}}^b{j=1}, if \text{ } s{i,j}=0,b{i,j}=1, else \text{ } b{i,j}=\beta > 1$

如此以来,模型就能通过非监督模块重构节点间的二阶估计。

对一阶估计建模

 上文提到,一阶估计用来衡量两个存在链接的节点的相似程度。作者使用了一个拉普拉斯特征映射作为其损失函数,当两个相似节点在嵌入空间中太过远离时会招致惩罚:

拉普拉斯特征映射:

拉普拉斯特征映射(Laplacian Eigenmaps)是一种不太常见的降维算法,它看问题的角度和常见的降维算法不太相同,是从局部的角度去构建数据之间的关系。也许这样讲有些抽象,具体来讲,拉普拉斯特征映射是一种基于图的降维算法,它希望相互间有关系的点(在图中相连的点)在降维后的空间中尽可能的靠近,从而在降维后仍能保持原有的数据结构。

混合损失函数

 结合上述分析,我们得到了一个混合损失函数:

其中$L_{reg}$是一个$L2-norm$(L2 正则化)即对参数加上L2范数的平方约束,目的是防止模型过拟合。

模型优化

  模型的目的是最小化以$\theta = { W^{(k)},\hat{W}^{(k)},b^{(k)},\hat{b}^{(k)} }$为参数的损失函数$L{mix}$. 关键是计算出损失函数对于参数的偏导:$\partial L{mix}/\partial \hat{W}^{(k)}$ 和 $\partial L_{mix}/\partial W^{(k)}$:

模型训练

image-20201125164057025

  • 通过深度信念网络预训练模型得到初始参数 $\theta$.

  • 将邻接矩阵$S$作为输入。

  • 重复下述过程:

    基于输入$X$和参数$\theta$,利用公式(1)前向得到$\hat{X}$以及$Y = Y^K$.

    利用公式(5)计算损失.

    利用公式(6)计算梯度并反向传播至整个网络更新参数$\theta$.

  • 得到网络的最终表示 $Y=Y{(K)}$

总结

 本论文提出了一种结构化深度网络嵌入算法SDNE,为了捕捉到高度非线性的网络结构,设计了一个半监督深度模型,其拥有多层包含非线性函数的网络层。为了解决稀疏网络导致的结构保留问题,加入了一阶估计和二姐估计两个模块,使得网络能够保留局部与全局的网络信息。并对该模型进行了对比评估,取得了非常好的效果。

文章作者: Liam
文章链接: https://www.ccyh.xyz/p/9828.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Liam's Blog
ღ喜欢记得五星好评哦~
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论