题目： Structural Deep Network Embedding 会议： KDD 2016 论文地址：Structural Deep Network Embedding

这是继node2vec、DeepWalk和LINE论文中嵌入了读的第四张图。

SDNE和node2vec属于并行研究，两者同时发表KDD 2016上。在此之前，除了一些经典的嵌入或降维算法，如多维标度(MDS)、IsoMap、局部线性嵌入(LLE)行业主要采用拉普拉斯特征映射的方法有DeepWalk和LINE。DeepWalk更倾向于具有较高二阶相邻度的节点产生类似的低维表示，LINE一阶和二阶的邻近度同时保留。

几乎所有现有的网络嵌入方法都采用浅层模型。但由于底层网络结构复杂，浅层模型无法捕捉高度非线性网络结构。因此，如何找到高度非线性网络结构并保持整体和局部结构是一个开放和重要的问题。为了解决这个问题，本文提出了一种结构化的深度网络嵌入方法，即SDNE。

具体来说，本文首先提出了具有多层非线性函数的半监督深度模型，因此可以捕获高度非线性网络结构。然后，联合利用第一阶和第二阶度来维持网络结构：无监督组件使用二级相邻度来捕获整个网络结构，一级相邻度作为监督重量中的监督信息。联合优化半监督深度模型，SDNE能保持局部和全局网络结构，对稀疏网络具有鲁棒性。

网络嵌入主要面临以下挑战：

1. 高度非线性：网络的底层结构是高度非线性的，很难设计模型来捕捉高度非线性的结构。
2. 结构保持：网络的底层结构非常复杂，顶点的相似性取决于局部和全局网络结构。因此，如何同时保持局部和全局结构是一个难题。
3. 稀疏性：现实世界中的许多网络通常非常稀疏，仅仅使用非常有限的观测链路是不够的。

许多现有的网络嵌入方法都采用浅层模型，如IsoMAP、拉普拉斯特征映射(LE)和LINE，但浅层模型的表达能力有限，难以捕捉高度非线性的网络结构。虽然有些方法使用核技术，但核方法也是浅层模型。

在本文提出的模型中，设计了由多个非线性函数组成的多层系统结构。多层非线性函数的组合可以将数据映射到高度非线性的表示空间，从而捕获高度非线性的网络结构。

同时，为了解决深度模型中的结构维护和稀疏性问题，进一步提出将一、二阶的相似性与学习过程相结合。事实上，在LINE还建议将一阶和二阶相近度结合起来，保持局部和全局的网络结构，同时保持稀疏网络的鲁棒性。

本文贡献：

1. 提出了SDNE，该方法可以将数据映射到高度非线性的潜在空间，以保持网络结构，并对稀疏网络具有鲁棒性。
2. 该模型提出了一种具有半监督结构的新型深度模型，同时优化了第一阶和第二阶之间的相邻性。因此，所学的表示保留了局部和全球网络结构，并对稀疏网络具有鲁棒性。
3. 实验结果证明，SDNE在多标签分类、重建、链接预测和可视化方面具有良好的实用性。

深度神经网络的最新进展表明，它们具有很强的表达能力，可以为许多类型的数据生成非常有用的表达。但目前的研究很少使用深度模型来学习网络的潜在表达。

现有模型为浅层模型，无法捕获高度非线性的网络结构。

G = ( V , E ) G=(V, E) G=(V,E)； V = { v 1 , . . , v n } V=\left \{ v_1,...,v_n \right \} V={ v1​,...,vn​}； E = { e i j } i , j = 1 n E=\left \{ e_{ij} \right \}_{i,j=1}^{n} E={ eij​}i,j=1n​； v i v_i vi​和 v j v_j vj​间如果没有边存在，则 s i j = 0 s_{ij}=0 sij​=0，否则：如果为无权图， s i j = 1 s_{ij}=1 sij​=1，如果为有权图， s i j > 0 s_{ij}>0 sij​>0。

一阶邻近度：如果 s i j > 0 s_{ij}>0 sij​>0， v i v_i vi​和 v j v_j vj​间存在正的一阶邻近度，否则 v i v_i vi​和 v j v_j vj​间一阶邻近度为0。

二阶邻近度：一对节点之间的二阶邻近度描述了这对顶点的邻域结构的接近度。 令 N u = { s u , 1 , . . . , s u , ∣ V ∣ } N_u=\left \{s_{u,1},...,s_{u,|V|} \right \} Nu​={ su,1​,...,su,∣V∣​}表示 v u v_u vu​与其他节点间的一阶邻近度，那么两个节点间的二阶邻近度就是它们一阶邻近度的相似度量。

本文研究问题定义：给定图 G = ( V , E ) G=(V,E) G=(V,E)，目标是找到每一个节点 v i v_i vi​的 d d d维向量表示 y i ∈ R d y_i \in R^d yi​∈Rd，这里 d < < ∣ V ∣ d<<|V| d<<∣V∣， y i y_i yi​同时保留了节点间的一阶邻近度和二阶邻近度。

本文提出了一个半监督深度模型来执行网络嵌入，结果如下所示： 后面再详细解释这个框架。

一些术语定义： 下面介绍上述框架怎么来保持二阶邻近度：给定一个图 G = ( V , E ) G=(V,E) G=(V,E)，我们很容易获得它的邻接矩阵 S = { s i j } i , j = 1 n = { s 1 , . . . , s ∣ V ∣ } S=\left \{s_{ij} \right \}_{i,j=1}^n=\left \{s_{1},...,s_{|V|} \right \} S={ sij​}i,j=1n​={ s1​,...,s∣V∣​}，其中每一个 s i s_i si​都是一个向量。

为了来保证二阶邻近度，作者扩展了自编码器。关于自编码器，自编码器(AutoEncoder)中比较详细地介绍，这里简单回顾一下。

自编码器包含两个部分：编码器和解码器，编码器由多个非线性函数组成，这些函数将输入数据映射到表示空间，解码器同样包括多个非线性函数，将表示空间中的表示映射到重构空间。

这时候再来看看上面的框架： 对于一个顶点 v i v_i vi​，首先需要初始化一个 x i x_i xi​向量，经过一个中间隐层（非线性函数）后，变为 y i ( 1 ) y_i^{(1)} yi(1)​，然后一直变换，直到通过K个隐层后， x i x_i xi​将被映射到表示空间，即变为 y i ( K ) y_i^{(K)} yi(K)​，然后经过一层层解码， x i x_i xi​将被映射到重构空间，即变为 x ^ i \hat{x}_i x^i​。

变化过程如下： y i ( 1 ) = σ ( W ( 1 ) x i + b ( 1 ) ) y i ( k ) = σ ( W ( k ) x k − 1 + b ( k ) ) y_i^{(1)}=\sigma(W^{(1)}x_i+b^{(1)})\\ y_i^{(k)}=\sigma(W^{(k)}x_{k-1}+b^{(k)}) yi(1)​=σ(W(1)xi​+b(1))yi(k)​=σ(W(k)xk−1​+b(k)) 经过 K K K次变换，我们得到了 y i ( K ) y_i^{(K)} yi(K)​。然后我们反转编码器的运算过程，就能得到一个与 x i x_i xi​大小一致的向量 x ^ i \hat{x}_i x^i​。