论文笔记之Structural Deep Network Emb
Structural Deep Network Embedding
SDNE是半监督的deep model，这也是第一次将deep model用于graph embedding。并且SDNE同时考虑了first-order proximity和second-order proximity。second-order proximity用无监督学习的方法来捕捉global network structure，first-order proximity用监督学习的方法来捕捉local network structure。SDNE结合两者，用半监督学习同时考虑了local和global。
之前大部分的graph embedding方法使用shallow model，对于高度非线性的网络结构，很难捕捉。SDNE的核心关注点，就是捕捉highly non-linear structure。SDNE包括了多层的非线性函数，可以把data映射到highly non-linear latent space，从而捕捉高度非线性的网络结构。
STRUCTURAL DEEP NETWORK EMBEDDING
Problem Definition
G=(V,E)，其中V是节点，E 是边。si,j表示边ei,j的权重。
First-Order Proximity
如果si,j > 0，那么节点vi和节点vj之间的first-order proximity为正，否则为0。
Second-Order Proximity
设节点vu的neighbor节点集合为Nu，节点u和节点v的second-order proximity由Nu和Nv的相似度决定。
The Model
Loss Functions
一些相关的符号，其中带^的表示decoder的参数。
对于网络G = (V,E)，它的邻接矩阵为S，S中包括n个instances s1,s2,...,sn。对于si = {si,j} (j = 1,2,...,n)，si,j>0表示vi和vj之间有边。因此，si描述了节点vi的neighborhood，S描述了整个网络的neighborhood信息。结合S，用扩展的deep autoencoder的思想来preserve second-order proximity。
deep autoencoder
deep autoencoder是一个无监督模型，由encoder和decoder两部分组成。encoder包括多层非线性函数，把input data映射到representation space。decoder也包括多层非线性函数，把representation映射到reconstruction space。对于input xi，每一层的hidden representation为
获得yi_(K)后，通过decoder得到xi^，autoencoder的目标是最小化重构误差。
loss function为
传统的autoencoder不能直接用于graph embedding，因为：
•在network中，两个节点有边说明它们有关系，但两个节点没有边，并不能说明它们没有关系。
•network是稀疏的，零元素数量大于非零元素数量，如果直接把network放入autoencoder，它会更倾向于重构零元素。
因此，我们在重构误差中加上一些penalty，着重考虑非零元素。
修改后的目标函数为
○为哈达玛积，bi = {bi,j} (j=1,2,...,n)，如果si,j = 0，则bi,j = 1，否则bi,j = β>1。
通过这种方式，着重考虑了非零元素。
以上是model中的unsupervised component，通过reconstruct节点的second-order proximity保留了网络的global network structure。
与此同时，还需要考虑first-order proximity来捕捉local network structure。
supervised component考虑了first-order proximity，loss function为
上式结合了拉普拉斯特征映射(Laplacian Eigenmaps)的想法，直观理解一下，当vi和vj有边时，si,j>0，此时如果yi和yj相差很大，那么loss就大。通过这种方式，考虑了first-order proximity，保留了local structure。
为了同时保留first-order proximity和second-order proximity，通过半监督模型同时考虑等式(3)和(4)，最终的目标函数为
其中Lreg为L2正则项，来防止过拟合。
W是autoencoder的权重。
Optimization
最小化loss function求解参数，具体的求导细节直接看原文就好了，然后用SGD。
因为model中存在high nonlinearity，在参数空间存在很多局部最优点。为了找到比较好的解，文中提出用Deep Belief Network来对参数做pretrain。
算法总流程如下：
最后文中讨论了一些其他问题。
•New vertexes。对于一个新节点vk，如果它和已经存在的节点之间的连接关系是已知的，那么可以获得它的邻接向量x = {s1,k，...，sn,k}，si,k中隐藏了已存在节点vi和新节点vk之间的相似信息。将x放入模型中，用已经训练好的参数，即可得到vk的representation。如果不知道vk和已经存在的节点之间的连接关系，那么SDNE没有办法处理。
