Graph Embedding(1) Struc2Vec-推荐相似度度量算法

SDNE（Structural Deep Network Embedding ）是和node2vec并列的工作，均发表在2016年的KDD会议中。可以看作是基于LINE的扩展，同时也是第一个将深度学习应用于网络表示学习中的方法。 不清楚LINE的同学可以参考：

LINE：算法原理，实现和应用

SDNE使用一个自动编码器结构来同时优化1阶和2阶相似度(LINE是分别优化的)，学习得到的向量表示能够保留局部和全局结构，并且对稀疏网络具有鲁棒性。

SDNE 算法原理

相似度定义

SDNE中的相似度定义和LINE是一样的。简单来说，1阶相似度衡量的是相邻的两个顶点对之间相似性。2阶相似度衡量的是，两个顶点他们的邻居集合的相似程度。

2阶相似度优化目标

这里我们使用图的邻接矩阵进行输入，对于第

个顶点，有

，每一个

都包含了顶点i的邻居结构信息，所以这样的重构过程能够使得结构相似的顶点具有相似的embedding表示向量。

这里存在的一个问题是由于图的稀疏性，邻接矩阵S中的非零元素是远远少于零元素的，那么对于神经网络来说只要全部输出0也能取得一个不错的效果，这不是我们想要的。

文章给出的一个方法是使用带权损失函数，对于非零元素具有更高的惩罚系数。 修正后的损失函数为

其中

为逐元素积，

，若

，则

，否则

1阶相似度优化目标

对于1阶相似度，损失函数定义如下

该损失函数可以让图中的相邻的两个顶点对应的embedding vector在隐藏空间接近。

还可以表示为

其中L是图对应的拉普拉斯矩阵，

，D是图中顶点的度矩阵，S是邻接矩阵，

。

整体优化目标

联合优化的损失函数为

是正则化项，

为控制1阶损失的参数，

为控制正则化项的参数。

模型结构

先看左边，是一个自动编码器的结构，输入输出分别是邻接矩阵和重构后的邻接矩阵。通过优化重构损失可以保留顶点的全局结构特性(论文的图画错了，上面应该是Global structure preserved cost)。

再看中间一排，

就是我们需要的embedding向量，模型通过1阶损失函数使得邻接的顶点对应的embedding向量接近，从而保留顶点的局部结构特性(中间应该是 Local structure preserved cost)

实现

文章提出使用深度信念网络进行预训练来获得较好的参数初始化，这里我就偷个懒省略这个步骤了~

损失函数定义

l_2nd是2阶相似度对应的损失函数，参数beta控制着非零元素的惩罚项系数。y_true和y_pred分别是输入的邻接矩阵和网络重构出的邻接矩阵。

l_1st是1阶相似度对应的损失函数，参数alpha控制着其在整体损失函数中的占比。

def l_2nd(beta): 
 def loss_2nd(y_true, y_pred): 
 b_ = np.ones_like(y_true) 
 b_[y_true != 0] = beta 
 x = K.square((y_true - y_pred) * b_) 
 t = K.sum(x, axis=-1, ) 
 return K.mean(t)
 return loss_2nd
def l_1st(alpha): 
 def loss_1st(y_true, y_pred): 
 L = y_true 
 Y = y_pred 
 batch_size = tf.to_float(K.shape(L)[0]) 
 return alpha * 2 * tf.linalg.trace(tf.matmul(tf.matmul(Y, L, transpose_a=True), Y)) / batch_size 
 return loss_1st

模型定义

create_model函数创建SDNE模型，l1和l2分别为模型的正则化项系数，模型的输入A为邻接矩阵，L为拉普拉斯矩阵。输出A_为重构后的邻接矩阵，Y为顶点的embedding向量。

函数中两个for循环分别对应encoder和decoder结构。

def create_model(node_size, hidden_size=[256, 128], l1=1e-5, l2=1e-4): 
 A = Input(shape=(node_size,)) 
 L = Input(shape=(None,)) 
 fc = A 
 for i in range(len(hidden_size)): 
 if i == len(hidden_size) - 1: 
 fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2),name='1st')(fc)
 else: 
 fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2))(fc) 
 Y = fc 
 for i in reversed(range(len(hidden_size) - 1)): 
 fc = Dense(hidden_size[i], activation='relu',kernel_regularizer=l1_l2(l1, l2))(fc)
 A_ = Dense(node_size, 'relu', name='2nd')(fc) 
 model = Model(inputs=[A, L], outputs=[A_, Y]) 
 return model

应用

使用SDNE在wiki数据集上进行节点分类任务和可视化任务(感兴趣的同学可以试试别的数据集，我比较懒就选了个很小的数据集)。 wiki数据集包含 2,405 个网页和17,981条网页之间的链接关系，以及每个网页的所属类别。

本例中的训练，评测和可视化的完整代码在下面的git仓库中：

https://github.com/shenweichen/GraphEmbedding

分类任务

micro-F1: 0.6341 macro-F1: 0.4962

可视化

这个貌似某些类别的点的向量都聚集在一起了，可能和超参的设置还有网络权重的初始化有关，我懒得调了~

这里还有一个SDNE在业界的应用的介绍：

阿里凑单算法首次公开！基于Graph Embedding的打包购商品挖掘系统解析

参考资料：

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

https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf

转自https://zhuanlan.zhihu.com/p/56733145