题目：node2vec: Scalable Feature Learning for Networks
作者：Aditya Grover and Jure Leskovec
来源：KDD 2016
源码：https://github.com/aditya-grover/node2vec
node2vec是一种综合考虑DFS邻域和BFS邻域的graph embedding方法。简单来说，可以看作是deepwalk的一种扩展，是结合了DFS和BFS随机游走的deepwalk。
其中BFS对应结构相似性，DFS对应节点同质性。关于为什么BFS和DFS分别对应节点的结构相似性和同质性的讨论见知乎关于Node2vec算法中Graph Embedding同质性和结构性的进一步探讨。采用SkipGram方法对Graph提取表示。根据SkipGram的思路，重点在于定于上下文（Context），也就是Neighborhood。
为了将BFS和DFS结合，去融合发掘图中节点的两种相似性，采用一种二阶的方法Biased-random walk代替BFS和DFS，拥有两个参数p和q，来控制多大的概率反复经过一些Node和控制往回走和往前走。总之，整个Random Walk的目的就是在DFS和BFS之间采取某种平衡。
设 f ( u ) f(u) f(u) 是将顶点 u u u 映射为embedding向量的映射函数,对于图中每个顶点 u u u，定义 N S ( u ) N_{S}(u) NS(u) 为通过采样策略 S S S 采样出的顶点 u u u 的近邻顶点集合。
node2vec优化的目标是给定每个顶点条件下，令其近邻顶点（如何定义近邻顶点很重要）出现的概率最大。 max f ∑ u ∈ V log Pr ( N S ( u ) ∣ f ( u ) ) \max _{f} \sum_{u \in V} \log \operatorname{Pr}\left(N_{S}(u) | f(u)\right) fmaxu∈V∑logPr(NS(u)∣f(u)) 为了将上述最优化问题可解，文章提出两个假设：
条件独立性假设假设给定源顶点下，其近邻顶点出现的概率与近邻集合中其余顶点无关。 Pr ( N S ( u ) ∣ f ( u ) ) = ∏ n i ∈ N S ( u ) Pr ( n i ∣ f ( u ) ) \operatorname{Pr}\left(N_{S}(u) | f(u)\right)=\prod_{n_{i} \in N_{S}(u)} \operatorname{Pr}\left(n_{i} | f(u)\right) Pr(NS(u)∣f(u))=ni∈NS(u)∏Pr(ni∣f(u))
特征空间对称性假设这里是说一个顶点作为源顶点和作为近邻顶点的时候共享同一套embedding向量。(对比LINE中的2阶相似度，一个顶点作为源点和近邻点的时候是拥有不同的embedding向量的) 在这个假设下，上述条件概率公式可表示为 Pr ( n i ∣ f ( u ) ) = exp ( f ( n i ) ⋅ f ( u ) ) ∑ v ∈ V exp ( f ( v ) ⋅ f ( u ) ) \operatorname{Pr}\left(n_{i} | f(u)\right)=\frac{\exp \left(f\left(n_{i}\right) \cdot f(u)\right)}{\sum_{v \in V} \exp (f(v) \cdot f(u))} Pr(ni∣f(u))=∑v∈Vexp(f(v)⋅f(u))exp(f(ni)⋅f(u)) 根据以上两个假设条件，最终的目标函数表示为 max f ∑ u ∈ V [ − log Z u + ∑ n i ∈ N S ( u ) f ( n i ) ⋅ f ( u ) ] \max _{f} \sum_{u \in V}\left[-\log Z_{u}+\sum_{n_{i} \in N_{S}(u)} f\left(n_{i}\right) \cdot f(u)\right] fmaxu∈V∑⎣⎡−logZu+ni∈NS(u)∑f(ni)⋅f(u)⎦⎤ 由于归一化因子 Z u = ∑ n i ∈ N s ( u ) exp ( f ( n i ) ⋅ f ( u ) ) Z_{u}=\sum_{n_{i} \in N_{s}(u)} \exp \left(f\left(n_{i}\right) \cdot f(u)\right) Zu=ni∈Ns(u)∑exp(f(ni)⋅f(u)) 的计算代价高，所以采用负采样技术优化。
node2vec依然采用随机游走的方式获取顶点的近邻序列，不同于deepwalk无偏随机游走，node2vec采用的是一种有偏的随机游走。
给定当前顶点 v v v，访问下一个顶点 x x x 的概率为 P ( c i = x ∣ c i − 1 = v ) = { π v x Z if ( v , x ) ∈ E 0 otherwise P\left(c_{i}=x | c_{i-1}=v\right)=\left\{\begin{array}{ll}{\frac{\pi_{v x}}{Z}} & {\text { if }(v, x) \in E} \\ {0} & {\text { otherwise }}\end{array}\right. P(ci=x∣ci−1=v)={Zπvx0 if (v,x)∈E otherwise π v x \pi_{v x} πvx 是顶点 v v v 和顶点 x x x 之间的未归一化转移概率， Z Z Z 是归一化常数。
node2vec引入两个超参数 p p p 和 q q q 来控制随机游走的策略，假设当前随机游走经过边 ( t , v ) (t,v) (t,v) 到达顶点 v v v 设 π v x = α p q ( t , x ) ⋅ w v x \pi_{v x}=\alpha_{p q}(t, x) \cdot w_{v x} πvx=αpq(t,x)⋅wvx， w v x w_{vx} wvx 是顶点 v v v 和 x x x 之间的边权， α p q ( t , x ) = { 1 p if d t x = 0 1 if d t x = 1 1 q if d t x = 2 \alpha_{p q}(t, x)=\left\{\begin{array}{ll}{\frac{1}{p}} & {\text { if } d_{t x}=0} \\ {1} & {\text { if } d_{t x}=1} \\ {\frac{1}{q}} & {\text { if } d_{t x}=2}\end{array}\right. αpq(t,x)=⎩⎨⎧p11q1 if dtx=0 if dtx=1 if dtx=2 d t x d_{tx} dtx 为顶点 t t t 和顶点 x x x 之间的最短路径距离。
下面讨论超参数 p p p 和 q q q 对游走策略的影响
Return parameter,p参数 p p p 控制重复访问刚刚访问过的顶点的概率。 注意到 p p p 仅作用于 d t x = 0 d_{tx} = 0 dtx=0 的情况，而 d t x = 0 d_{tx} = 0 dtx=0 表示顶点 x x x 就是访问当前顶点 v v v 之前刚刚访问过的顶点。 那么若 p p p 较高，则访问刚刚访问过的顶点的概率会变低，反之变高。
In-out papameter,qq q q 控制着游走是向外还是向内，若 q > 1 q>1 q>1 ，随机游走倾向于访问和 t t t 接近的顶点(偏向BFS)。若 q < 1 q<1 q<1 ，倾向于访问远离 t t t 的顶点(偏向DFS)。
下面的图描述的是当从 t t t 访问到 v v v 时，决定下一个访问顶点时每个顶点对应的 α \alpha α。
采样完顶点序列后，剩下的步骤就和deepwalk一样了，用word2vec去学习顶点的embedding向量。 值得注意的是node2vecWalk中不再是随机抽取邻接点，而是按概率抽取，node2vec采用了Alias算法进行顶点采样。
node2vec在工业界的应用：当机器学习遇上复杂网络：解析微信朋友圈 Lookalike 算法
