Node2vec简述

DeepWalk的缺点

用完全随机游走，训练节点嵌入向量，仅能反应相邻节点的社群相似信息，无法反映节点的功能角色相似信息。

Node2vec

在这里插入图片描述
通过调节p和q的参数，可以调节权重。

p值很小，更愿意返回，则类似BFS，反映的是微观视角。
q值很小，更愿意返回，则类似DFS，反映宏观视角。
DFS捕捉的是homophily同质社群(社交网络)的特征
BFS捕捉的是Structural equivalence节点功能角色(中枢、桥接、边缘)的特征。

伪代码

在这里插入图片描述

一些技术细节

Alias Sampling：用空间换时间，时间复杂度O(1)的采样算法。

Node2vec论文精读

任何监督学习算法要求有内含丰富语义，有分类区分性以及相互独立的特征。
图嵌入的方法：
1.手动构造特征
2.基于矩阵分解的图嵌入
3.基于随机游走的图嵌入
4.基于神经网络

同一个社群的节点、同一个功能角色的节点，应该被编码成相近的embedding

使用二阶随机游走方法来产生节点的邻域。

一阶随机游走(一阶马尔科夫性)：下一个节点仅与当前节点有关(deepwalk,pagerank)
二阶随机游走(二阶马尔科夫性)：下一个节点不仅与当前节点有关，还与上一个节点有关

p，q的不同对应不同的探索策略，具有可解释性。
最优的p，q可以通过调惨得到。

贡献

1.提出node2vec，可以通过调节p、q来探索网络的不同特性，使用SGD来优化
2.node2vec符合网络科学的准则，提供了灵活的表示
3.node2vec将节点嵌入推广到了连接嵌入
4.在多类别分类任务和连接预测任务上进行了实验。

3.Node2vec算法

图： $G = (V, E)$
采样策略： $S$
节点 $u$ 的领域节点 $N_S(u) \subset V$
任务：学习映射 $\rightarrow \mathbb{R}^d$ ：d是词嵌入后的维度
目标函数：
$\max _f \sum_{u \in V} \log \operatorname{Pr}\left(N_S(u) \mid f(u)\right)$
为了简化问题，做出两个假设：

条件独立性假设：周围节点互相不影响：
$\operatorname{Pr}\left(N_S(u) \mid f(u)\right)=\prod_{n_i \in N_S(u)} \operatorname{Pr}\left(n_i \mid f(u)\right)$
特征空间的对称性：两个节点之间相互影响的程度是一样的，因此可以用特征的点乘来表示概率
$\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))}$

设 $Z_u=\sum_{v \in V} \exp (f(u) \cdot f(v))$ ，称为配分函数，则目标函数可化为
$\operatorname{Pr}\left(n_i \mid 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))}$

3.1 传统搜索策略

如何定义领域 $N_S(u)$ 依赖于策略 $S$ 。不同策略下，邻域是不一样的。
在这里插入图片描述
BFS：只探索近邻。
DFS：渐行渐远，探索离原节点较远的节点。

在homophily(同质性)假设下(对应BFS)，同一个社区的节点，词嵌入后会比较相似。如s1和u
在structural equivalence假设下(对应DFS)，有相同结构角色功能的节点，词嵌入后会比较相似。如u和s6
在真实图里，这两种不是互斥的，一个图可能既有homophily特质，也有structural equivalence特质。
BFS采样结果比较稳定，方差较小。
DFS采样结果比较不稳定，方差较大。

3.2 node2vec

3.2.1 随机游走

$u$ ：起始点
$t$ ：上一节点
$v$ ：当前节点
$x$ ：下一节点
$N_s(t)$ ：上一节点的邻居节点
$k$ ：当前节点v的邻居节点个数
$l$ ：随机游走序列节点个数

下一个节点的生成概率公式：
$P\left(c_i=x \mid c_{i-1}=v\right)= \begin{cases}\frac{\pi_{v x}}{Z} & \text { if }(v, x) \in E \\ 0 & \text { otherwise }\end{cases}$
其中， $\pi_{v x}$ 是未归一化的转移概率。

3.2.2 搜索的偏向 $\alpha$

直接用权重作为游走概率，则无法调节搜索策略。直接用BFS或者DFS则太极端，无法平滑调节。
于是考虑带参数p和q的二阶随机游走：
$\alpha_{p q}(t, x)= \begin{cases}\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{cases}$
$\pi_{v x}=\alpha_{p q}(t, x) \cdot w_{v x}$

因为既要下一个节点x考虑当前节点v可达，也要考虑x与上一个节点t的距离，所以是二阶的随机游走

空间复杂度：随机游走需要存邻接表 $O (∣ E ∣)$ 。为了方便，二阶随机游走需要存 $O(a^2|V|)$ 来记录距离，其中 $a$ 是图中每个点的平均连接数。
时间复杂度： $O\left(\frac{l}{k(l-k)}\right)$ ，k是领域的节点个数
随着硬件的发展，空间复杂度没有时间复杂度重要