Node2Vec

关于

论文:node2vec: Scalable Feature Learning for Networks

摘要

特征学习框架

$$
\max_f \sum_{u \in V} \log Pr(N_S(u)| f(u) )
$$

$$
Pr(n_i|f(u)) = \frac{\exp(f(n_i) \dot f(u))}{\sum_{v\in V} f(v) \dot f(u)}
$$

和 word2vec 一样,可以通过负采样来优化分母的计算量!

邻居节点的搜索策略

$$
P(c_i=x|c_{i-1}=v) = \begin{cases}
\frac{\pi_{vx}}{Z}, if (v,x) \in E. \\
0, otherwise
\end{cases}
$$

其中$(\pi_{vx})$是未归一化的概率,Z是归一化常数。对于最简单的情况,可以用边的权重作为未归一化概率
$(\pi_{vx} = w_{vx})$。

对于2阶 random walk,未归一化概率和权重之间的关系为:$(\pi_{vx} = \alpha_{pq}(t,x)w_{vx})$
t是上一个节点,v是当前节点,x是下一个可能的节点,系数

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

$(d_{tx})$是两个节点的距离,p是return参数,q是in-out参数。