理解node2vec

Written by    02:23 March 16, 2020 

最近在看一些graph embedding 相关,先从node2vec入手的,在这里大概记录一下一些理解和实践。

Theory

看到embedding,第一眼就容易想到2013Tomas Mikolovembedding开山之作word2vec,一开始主要是用于NLP领域,基于语料库中句子序列中词与词的共现关系,来学习词的向量表征,后来大家发现不仅是NLP,在其他领域只要我们能用item构造出合理的序列,同样可以基于item之间的共现关系来学习item的向量表征,而graph embedding的大部分工作,其实就是如何构造合理的序列。

KDD 2014上提出的DeepWalk算法,就是graph embedding 基于word2vec的一次尝试,给定一个节点,然后随机采样当前节点邻居节点中的一个来作为下一个节点,重复此过程直至采样期望长度的序列,最后使用word2vec中的skipgram模型来训练得到节点的向量。node2vec算法则是在KDD 2016上提出,是基于DeepWalk算法的一种改进,核心思想就是用一个有偏的随机游走来替代DeepWalk当中的随机游走。给定当前的节点,首先基于所有边的权重来计算出访问下一个节点的概率,然后再加入两个超参数pq来控制游走的策略。

如上图所示,假设由(t, v)边走到了vv有三个邻居 x1 x2 x3, 其中x1t邻接,则vx1的概率不变,x2 x3都不与t邻接,则vx2的概率为原有的概率除以qvt的概率则是原有的概率除以p,用公式描述就如下:

这里的d_tx就是tx在图上最短距离,d_tx等于0说明x就是td_tx等于1说明tx邻接,d_tx等于2就是tx不邻接,从这里其实就可以看出来两个超参数作用了,p就是控制重复访问已访问节点的概率(Return parameter)q就是控制游走是偏DFS还是偏BFS(In-out parameter),经过这种有偏游走产生序列过后,就和DeepWalk一样了直接跑skipgram model来获取节点的embedding了。

除了有偏游走以外,node2vec还引入了alias sampling来提高计算效率,alias sampling是一种可以在O(1)时间复杂度按照指定概率分布来采样的算法,node2vec作者在进行随机游走之前会执行一个预计算来获取alias_nodesalias_edges, alias_nodes存每个顶点决定下一个访问的点所需要的alias表,而alias_edges则存由(t, v)边访问到v的时候决定下一个访问点所需要的alias表,在作者给出的Python代码中preprocess_transition_probs函数就描述了这个预计算的过程。

 

Practice

在了解了node2vec的基本原理过后,具体实践的时候就碰到了一些问题,最关键的就是如果输入的图很大,那么node2vec的预计算求alias_nodesalias_nodes就会非常吃内存,其实主要是算alias_edges这一步,如果涉及到了千万级别的边,可能需要的内存就是百G级别,大部分实现都会在这一步跑着很困难,多番尝试无果之后,只能选择自己造轮子了,于是就实现了一版基于LRU Cachealias_nodes alias_edges,在访问到当前节点或当前边的时候首先去查LRU Cache,如果命中的话就直接取算好的,没有的话就算一个alias表并写入到LRU Cache里面,这样就可以控制住内存了。第一个版本是用Python实现的,因为Python对多线程计算并不友好,多进程通信成本又太高,所以只能多进程然后各个进程维护一个LRU Cache,可这样只是解决了燃眉之急,毕竟如果有20个进程的话就需要有20LRU Cache,随着进程数的增加也会浪费不少内存空间并且降低Cache命中率从而降低计算效率,最终还是用C++写了一个多线程版本,测试了一下,跑一个2.3w节点2300w边的图,开二十个线程只需要10G内存跑两个小时,总算是舒坦了,代码也开源在了github(https://github.com/razrLeLe/fastwalk),全部都是用标准库实现,开箱即用,欢迎PR or Star~

最后,用一盘产自家乡的清炒红菜苔来祝愿家乡早日脱离疫情:

References

  1. node2vec: Scalable Feature Learning for Networks
  2. https://github.com/aditya-grover/node2vec
  3. 【Graph Embedding】node2vec:算法原理,实现和应用

Category : study

Tags :