LINE理论到复现

文章主要是提出了一阶相似性和二阶相似性

文章链接：Large-scale Information Network Embedding
参考链接：知乎笔记LINE
代码见：Colab

LINE可以适用于任何类型的graph，如无向图、有向图、加权图等，同时作者基于边采样进行了目标函数的优化，使算法既能捕获到局部的网络结构，也能捕获到全局的网络结构。

（福利推荐：阿里云、腾讯云、华为云服务器最新限时优惠活动，云服务器1核2G仅88元/年、2核4G仅698元/3年，点击这里立即抢购>>>）

优化目标

一阶相似度：如果两个顶点之间有直接相连的边，则一阶相似度由权重决定，若无则为0；
​
经验概率：（wij表示的是ij两点之间的权重，W表示的是所有边的权重和）
因此目标函数变为：

使用KL散度公式计算两个概率的差异（即），带入到公式，上式化简为：

优化更小也就是让联合概率更好地拟合经验概率，得到的各顶点向量能存储一阶相似度信息。
二阶相似度：
二阶相似度经验概率：（wij表示的是ij两点之间的权重，di表示的是所有顶点i的出边的权重和）

如何理解该经验概率可以表示二阶相似度？原文中对二阶相似度如此定义：The secondorder proximity between a pair of vertices (u, v) in a network is the similarity between their neighborhood network structures.
也就是说若将两点的临边经验概率向量表示：如下图示：
v1=(w14，w15，w16，w13)=(3/11,2/11,4/11,2/11)
v2=(w24，w25，w26，w27)=(3/9,1/9,4/9,1/9)
两向量的相似度即可表示此二阶相似度。

那么如何使得我们得到的顶点向量表示能够“蕴含”该二阶相似度的信息呢，关键在于两点向量表示在某一表达式处理后，能够得到近似于上述真实概率分布（经验概率）。
换言之，就是要更好地拟合下面的预测概率表达式和经验概率（和）
（|V|为所有顶点个数）

为保证二阶相似度能够被保证保留在向量信息中，如原文说，we should make the conditional distribution of the contexts specified by the low-dimensional representation be close to the empirical distribut也即目标函数如下：

其中，表示的是顶点i的重要度，在下面的化简中，以（顶点i的出度）近似之，在实际上也可用PageRank等方法估计得到。
使用KL散度公式计算两个概率的差异（即），带入到公式，上式化简为

模型优化

接下来的目标就是优化向量，也即两个嵌入矩阵（embeddings和context_embeddings）的内容（用两个矩阵的原因和w2v中的一样），使得上述式子（和）最小化。
在接下来，一阶二阶分别优化，最后得到的向量拼接即可。

负采样

由于O2式具体化之后为

在计算分母时，需要遍历所有顶点，效率极为低下，因此需要采用负采样的方法提高效率。

别名采样

在优化两个目标函数时，有以下问题：若为带权图，使用梯度下降法优化参数时，要将边权重乘上（直观上感受，这样的原因在于：）为了解决这个问题，可将权重为w的边拆分为w条无权边，但是会因此耗费很多内存，所以要考虑另外一种方法：对于权重较大的边以更高的概率采样，权重小的则以更低的概率采样，采样后的边都视为无权边，这样既能解决学习率低的问题，也能避免内存耗费的问题。
采样的方法参照Alias method，带入到此来说就是对于N条边，边权重之和为sum，每条边被采样的概率为，先从1-N取一个整数n，再随即从0-1取一值p，若p>Prob(n)，则采样别名Alias(n)，否则采样本名n。这样就可以采样得到真正需要训练的边。在生成batch时可用。

复现代码

这一部分花了较多的时间，主要是在复现的部分，网络上没有什么可供参考的复现的资料，且因为学习复现node2vev和deepwalk时并没有用到pytorch或者是tensorflow框架（直接用的gensim里面的word2vec），所以在这里我希望自己至少能动手改写一个pytorch的代码，以加深对整个框架使用的了解，找到了openne的开源代码（tf框架写成），在认真阅读代码并结合博客后，对代码有了更深入的理解，动手改写了pytorch版的，也就是在这里我意识到这些框架代码的共性和核心：一些基本的参数（iter，batch_size，epoch等的选择以及调整的意义），loss函数的确定和batch的选择是最为核心的部分。
在最初没有意识到一个小的细节问题前，改写后的pytorch代码loss下降效果远远不如tf版，于是尝试修改batchsize并看这个问题下的回答，（最后是在同学帮忙看找到的，问题在于误使两个矩阵相同了）虽然最后问题并不是batch_size，但也算有所收获。（batch_size会影响什么）
基于一个tf版本的代码（openne中的line.py）改写了一个pytorch版本，并以blogcatalog作为数据集，代码可见：Colab

MICRO-F1

使用数据集BlogCatalog得到的Micro-F1=0.3757828810020877

可视化

使用数据量较小的wiki进行可视化，可以看到有一定的聚集效果（代码见：Colab）

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)