[Graph Embedding] SDNE原理介绍及举例说明

俊俊 推荐算法工程师一枚

本人微信公众号为“推荐算法学习笔记”，定期推出经典推荐算法文章，欢迎关注。

本文主要介绍的是Graph Embedding算法SDNE。原始paper名称为《Structural Deep Network Embedding》

一. 需了解的基础知识


自编码器（Autoencoder）：一种无监督的学习算法
拉普拉斯映射（Laplacian Eigenmaps）：一种降维算法


二. SDNE原理介绍

在一个图中，我们定义两种相似性：一阶相似性和二阶相似性。
（1）如果两个节点之间有边，则说它们一阶相似，边的权值则表示了相似程度。
（2）将节点1的邻居和节点2的邻居进行对比来表示这两个节点的相似性，这是二阶相似性。
那么我们应该怎么进行建模，使得生成的embedding能够表征出节点之间的一阶相似性和二阶相似性呢？

论文采用了一种半监督的学习方法，利用autoencode无监督学习节点的二阶相似性，并借鉴拉普拉斯映射（Laplacian Eigenmaps），使用监督学习的方法来训练节点间的一阶相似性。如下图所示

下面举个实例来说明，如下图所示，给出一个有6个节点的图，我们很容易得出它的邻接矩阵。

以节点2为例，我们可以知道它的邻接向量为{1，0，2，0，0，0，}。然后我们将节点的邻接向量放入到自动编码器当中，通过自动编码器将节点的二阶相似性降维到一个低维的稠密向量。如下图左侧和右侧所示

与此同时，假如两个节点之间有边相连的话，我们希望它们降维之后的embedding越接近越好。因此，模型还额外增加了一个损失函数，如上图的中间部分，通过计算两个相邻节点的距离并乘以它们边的权重，我们可以使相邻节点的embedding是相似的。

这样，训练出来的embedding便可以表征出节点的一阶和二阶相似性。


三. 损失函数和优化

下面是模型的损失函数

（1）二阶相似性的损失函数为

这里对自编码器的损失函数做了优化，假如对于xi，假如其邻接向量为si，如果si,j=0, 则bi,j=1, 否则bi,j=(设置的超参数)>1

做这样的优化是因为邻接向量特别稀疏，让模型可以更加聚焦在非0的邻居的训练上。

（2）一阶相似性的损失函数为

可以发现这个和拉普拉斯映射（Laplacian Eigenmaps）是一模一样的，通过拉普拉斯映射公式的推导我们可以得到

其中

（3）结合一阶和二阶的损失函数，再加上L2正则化，便得到整个模型的损失函数

四. 总结


以上便是SDNE的所有内容。如果有问题，欢迎和我联系。本人微信公众号为“推荐算法学习笔记”，定期推出经典推荐算法文章，欢迎关注。

 

发布于 04-17