LINE理论到复现-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

LINE理论到复现

简介: LINE

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

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

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

优化目标

一阶相似度:如果两个顶点之间有直接相连的边,则一阶相似度由权重决定,若无则为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
image.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
展开
最新文章
相关文章