node2vec笔记

article/2025/11/6 18:49:09

node2vec论文：https://dl.acm.org/citation.cfm?id=2939754

node2vec作者KDD口头报告视频：https://www.youtube.com/watch?v=1_QH5BEP5BM

node2vec是deepwalk的一个扩展，主要考虑了两点：(1)邻近性，即节点在图上的距离越近越相似；

(2)同构性，即如果两个节点周围的结构越相近，则越相似。

前面的公式没什么好说的，主要是作者定义了一种搜索策略来捕捉上述作者观察到的性质。

首先，node2vec通过如下分布来产生给定节点的邻居游走节点

$\mathrm{Pr}(c_i=x\vert c_{i-1}=v)= \begin{cases} \frac{\pi_{vx}}{Z} & \text{if } (v,x)\in E\\ 0 & \text{otherwise} \end{cases}$

其中， $\pi_{vx}$ 表示节点 $v$ 到节点 $x$ 的转移概率， $Z$ 是归一化因子。那么，如下图，如果当前节点为 $v$ ，上一次访问的节点为 $t$ ，那么下一次要访问的节点是由 $\pi_{vx}$ 来定的。

$\pi_{vx}$ 的定义为： $\pi_{vx}=\alpha_{pq}(t,x)\cdot w_{vx}$ ， $w_{vx}$ 为节点 $v$ 到节点 $x$ 边上的权重，如果是无权图则默认为1。下面就主要是关于的 $\pi_{vx}$ 定义了，如下

$\alpha_{pq}(t, x) = \begin{cases} \frac{1}{p} & \text{if } d_{tx}=0\\ 1 & \text{if } d_{tx}=1\\ \frac{1}{q} & \text{if } d_{tx}=2 \end{cases}$

其中， $d_{tx}$ 表示 $t$ 和 $x$ 之间的最短路径，这里作者定义的取值范围为{0,1,2}，这样作者定义的p和q就能有效的引导游走序列了。

下面讨论一下这两个主要的参数p和q。

Return参数p：参数p控制再次访问刚刚被访问过的节点的概率。如果p设置得比较大(如 $p>\max(q,1)$ )，则可以保证在后续的两个游走中尽量不再次访问刚刚被访问过的节点(除非当前的节点没有其他邻居了)。该策略能够引导进行适度的探索并避免采样重复。如果该值被设置得偏小(如 $p<\min(q,1)$ )，则游走更倾向于回溯，游走趋向于是节点 $u$ 附近的节点，也就是比较关注 $u$ 的局部信息。
In-out参数q：参数q控制探索向内节点和向外节点。如果 $q>1$ ，那么随机游走的节点与节点 $t$ 接近。这样的游走与BFS类似，能够获得节点 $t$ 的局部结构信息。如果 $q<1$ ，则随机游走的节点将尽可能的远离节点 $t$ 。这与DFS类似，趋近于探索源节点的外向节点。