node2vec

1.背景

DeepWalk中根据边的权重进行随机游走，而node2vec加了一个权重调整参数\alpha，最终生成的随机序列是一种DFS和BFS的结合；模型仍使用skip gram去训练。

2.原理

2.1 Random Walks

给定一个起始节点u，我们模拟一个固定长度l的随机游走，c_i表示行走中的第i个节点，起始节点：c_0 = u。节点c_{i-1}走到节点c_i概率定义为:


\pi_{vx}
是节点之间非归一化概率；
Z
是节点之间概率的和，用于归一化使用;

2.2 Search bias α

假设已知游走路径已从t走到v,从节点v 走到下一个节点x按照转移概率\pi_{vx}选择对应的节点；\pi_{vx}=\alpha_{ p q}(t,x)·w_{vx}



其中：
d_{tx}
是
t
到
x
的最近的距离，在论文中
d_{tx}
的取值为
[0、1、2]

p、q
这两个参数决定离开起始节点的速度；

2.2.1 参数p

  1. 表示访问已遍历节点的可能性；
  2. p > max(q, 1)：表示在连续两步，越小的可能访问已遍历节点；这种策略鼓励适度的探索，并避免了距离为2的节点抽样中的冗余
  3. p < min(q, 1)：表示遍历的节点接近起始节点；

2.2.2 参数q

  1. 允许搜索区分“向内”和“向外”节点；
  2. q > 1 : 表示越大的可能抽样节点靠近t；可以获得与遍历中的开始节点相关的底层图的局部视图，与BFS类似；
  3. q < 1: 表示越大的可能抽样节点远离t； 与DFS类似；
  4. p =q = 1 就是deepwalk

3. algorithm

3.源码

py版本代码结构：


4.参考文献

  1. 论文地址：https://arxiv.org/abs/1607.00653
  2. 代码地址：https://github.com/aditya-grover/node2vec
  3. 别名采样算法：https://hips.seas.harvard.edu/blog/2013/03/03/the-alias-method-efficient-sampling-with-many-discrete-outcomes/
  4. 别名采样算法：https://blog.csdn.net/lee813/article/details/51497012
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容