node2vec

Paper : node2vec: Scalable Feature Learning for Networks
Code : official

摘要

作者在DeepWalk思想的基础上，对RandomWalk算法进行改进，结合了深度优先搜索和广度优先搜索的优点，提出了node2vec的搜索策略，用来定义点的局部邻域。不过在GNN方法出来之后类DeepWalk的方法差不多算是过时了。该篇论文的主要贡献点有以下几点

• 作者提出了node2vec，一种用于网络特征学习的有效可扩展算法，该算法使用SGD有效地优化了一种新颖的网络感知的邻域保留目标函数。
• 作者将基于邻域保留目标的node2vec和其他特征学习方法从节点扩展到成对的基于边的预测任务的节点对。

基于语言模型的图特征学习

对于任意一点 u ∈ V u \in V u∈V ，定义使用搜索策略 S S S 得到的节点 u u u 的邻域表示为 N S ( u ) ⊂ V N_S(u) \subset V NS​(u)⊂V。那么使用Skip-Gram模型来进行图学习，优化的目标函数是

max ⁡ f ∑ u ∈ V log ⁡ P ( N S ( u ) ∣ f ( u ) ) \max_f \sum_{u\in V}\log \text{P}(N_S(u)|f(u)) fmax​u∈V∑​logP(NS​(u)∣f(u))

其中 f : V → R d f:V\rightarrow \R^d f:V→Rd 表示点特征映射函数。

为了优化以上表达式，做出以下两点假设：

• 条件独立性：
  P ( N S ( u ) ∣ f ( u ) ) = ∏ n i ∈ N S ( u ) P ( n i ∣ f ( u ) ) \text{P}(N_S(u)|f(u)) = \prod_{n_i\in N_S(u)}\text{P}(n_i|f(u)) P(NS​(u)∣f(u))=ni​∈NS​(u)∏​P(ni​∣f(u))
• 对称性：点与点之间的影响是对称的。
  P ( n i ∣ f ( u ) ) = exp ⁡ ( f ( n i ) T f ( u ) ) ∑ v ∈ V exp ⁡ ( f ( v ) T f ( u ) ) \text{P}(n_i|f(u)) = \frac{\exp(f(n_i)^\text T f(u))}{\sum_{v\in V}\exp(f(v)^\text T f(u))} P(ni​∣f(u))=∑v∈V​exp(f(v)Tf(u))exp(f(ni​)Tf(u))​

因此，优化目标的表示转化为

max ⁡ f ∑ v ∈ V [ − log ⁡ ∑ v ∈ V exp ⁡ ( f ( u ) T f ( v ) ) + ∑ n i ∈ N S ( u ) f ( n i ) T f ( u ) ] \max_f\sum_{v\in V}[-\log\sum_{v\in V}\exp(f(u)^\text T f(v))+\sum_{n_i\in N_S(u)}f(n_i)^\text Tf(u)] fmax​v∈V∑​[−logv∈V∑​exp(f(u)Tf(v))+ni​∈NS​(u)∑​f(ni​)Tf(u)]

第一项计算量较大，因此需要进行降采样。

node2vec

在图上最常见的两种极端的搜索策略分别是BFS与DFS，如下图所示

假定采样 k = 3 k=3 k=3 个节点作为 u u u 节点的邻域，那么使用两种搜索策略的结果分别是

• BFS：节点 s 1 , s 2 , s 3 s_1,s_2,s_3 s1​,s2​,s3​
• DFS：节点 s 4 , s 5 , s 6 s_4,s_5,s_6 s4​,s5​,s6​

在图节点特征学习的任务中，主要需要学习到两种图的特性——同质性和结构相似性。同质性是指高度互连且属于相似网络集群或社区的节点应紧密地嵌入在一起，即距离相近的节点低维特征更相似；结构相似性是指局部结构相似的节点具有相似的节点低维特征。作者认为，BFS更倾向于通过邻域抽样学习到结构相似性，而DFS更倾向于通过邻域抽样学习到同质性，因此提出node2vec算法将两种极端的搜索策略相结合。

考虑随机游走算法，设上一次的节点转移为 ( t , v ) (t,v) (t,v) ，当前位于节点 v v v 上，那么下一步的转移节点 x x x 上的概率 π v x = α p , q ( t , x ) ⋅ w v , x \pi_{vx} = \alpha_{p,q}(t,x) \cdot w_{v,x} πvx​=αp,q​(t,x)⋅wv,x​，其中 w v , x w_{v,x} wv,x​ 为正则化系数，而 α p , q \alpha_{p,q} αp,q​ 定义为

α p , q ( t , x ) = { 1 p d ( t , x ) = 0 1 d ( t , x ) = 1 1 q d ( t , x ) = 2 \alpha_{p,q}(t,x) = \left\{\begin{matrix} \frac{1}{p} & d(t,x) = 0\\ 1 & d(t,x)=1\\ \frac{1}{q} &d(t,x) = 2 \end{matrix}\right. αp,q​(t,x)=⎩⎨⎧​p1​1q1​​d(t,x)=0d(t,x)=1d(t,x)=2​

其中 d ( t , x ) d(t,x) d(t,x) 表示节点 t t t 与节点 x x x 之间的距离，可视化该过程为

回程参数p：参数p控制返回上一步节点的可能性，将其设置为较高的值可确保我们在之后两步不太可能对已访问的节点进行采样。这种策略鼓励适度的探索，并避免采样中的冗余。另一方面，如果p值较低，它将导致步行回溯一步，这将使步行“局部”靠近起始节点u。

出入参数q：参数q允许搜索区分“向内”和“向外”节点。如果q较大，则随机游走偏向靠近节点t的节点。这样的行走可获取相对于行走中的起始节点的局部视图，近似BFS行为。相反，如果q较小，则步行更倾向于访问距离节点t较远的节点，近似DFS，它鼓励向外探索。

对于边特征学习，作者提出使用二元运算符从点特征计算边特征表示，给出以下几个例子

作者通过实验发现Hadamard积效果会更优一些，但是原因有待进一步探索。

总结

在本文中，作者给出了一种灵活且采样规模可控的随机游走算法。DeepWalk和LINE都可以视为网络上的严格搜索策略。 DeepWalk提出使用统一的随机游动进行搜索，这种策略的明显局限性在于，它使我们无法控制所探索的社区。LINE主要提出了广度优先策略，对节点进行采样并仅对1跳和2跳邻居进行近似优化。这种探索的效果更容易表征，但在探索更深的节点时没有灵活性。尽管将图看作语言模型处理已经过时了，但是这种搜索策略可能可以替代GraphSAGE中的降采样训练方法，也不知道有没有人做过实验。既然LINE算法被该方法拍在沙滩上了，我就不再考古写LINE算法的blog了。