Node2vec: Scalable Feature Learning for Networks(KDD16)

本文主要是介绍Node2vec: Scalable Feature Learning for Networks(KDD16)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Node2vec: Scalable Feature Learning for Networks(KDD16)阅读笔记

作者：斯坦福大学 Aditya Grover，Jure Leskovec

研究内容

研究问题：学习网络的特征表示，将节点映射到低维空间，并且最大程度的保留节点的邻居信息。
现有方法的不足：不能获取和表示网络中连接模式的多样性diversity
研究方法：提出node2vec算法框架，定义邻居节点的灵活表示，设计了一种biased随机游走步骤。
效果：能学习更加丰富的表示，在多标签分类和链接预测方面达到了state-of-the-art的水平。

具体实施

node2vec是一个半监督的算法，主要是学习网络中的节点边特征。使用二阶随机游走算法生成节点的网络邻居。

三个阶段：1. 预处理：计算节点间的转移概率 $\pi_{vx}$ ; 2. 模拟随机游走； 3. 通过SGD对目标函数进行优化。

搜索策略：对于大规模网络来说，计算一个节点的邻居节点需要耗费很多时间，所以我们可以采用采样的方法来估计它。而不同的搜索策略会导致节点的邻居节点不同。传统的搜索策略包括BFS(广度优先采样)，DFS(深度优先采样)。这两种策略对应于我们在对网络中的节点进行embedding时关注的两个假设，分别为：homophily(同质性) and structural equivalence(结构等价性)。

同质性假设：节点高度互联且在同一网络集群和社区的节点的embedding也应该相近。
结构等价性假设：在网络中担任角色类似的节点的embedding也应该相似。

如上图，上面的一个图表示的是同质性假设，相同颜色的节点说明在同一社区或者高度互联。下面的一个图表示的是结构等价性假设，相同颜色的节点说明在网络中担任的角色相同。

本文与其他工作的不同之处，在于结合了BFS和DFS，不再固定节点v到x的转移概率，而是通过一个权重来计算，即 $\pi_{vx}=\alpha_{pq}(t,x)*w_{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$ 之间的最短路径。因为是2阶随机游走，所以 $d_{tx}$ 只能是0,1,2三个值。 $p$ 和 $q$ 控制游走的速度。

2阶随机游走中的边权重

Return parameter, p: 控制了在遍历过程中立即重新访问节点的可能性。为了避免冗余，应该设置为一个比较高的值。
In-out parameter, q: 参数 $q$ 允许搜索区分向内和向外的节点。如果 $q > 1$ ，随机游走更偏向于在距离 $t$ 较近的地方游走，如果 $q < 1$ ，则偏向于距离 $t$ 较远的地方游走。