[学习笔记]Node2Vec图神经网络论文精读

参考资料：https://www.bilibili.com/video/BV1BS4y1E7tf/?p=12&spm_id_from=pageDriver

Node2vec简述

DeepWalk的缺点

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

Node2vec

通过调节p和q的参数，可以调节权重。

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

伪代码

一些技术细节

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

AliasSampling参考资料：https://keithschwarz.com/darts-dice-coins/

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$
任务：学习映射$f:V\to {\mathbb{R}}^d$：d是词嵌入后的维度
目标函数：
$$\underset{f}{\max }\sum _{u\in V}\log \mathrm{Pr}\left(N_S(u)\mid f(u)\right)$$
为了简化问题，做出两个假设：

• 条件独立性假设：周围节点互相不影响：
  $$\mathrm{Pr}\left(N_S(u)\mid f(u)\right)=\prod _{n_i\in N_S(u)}\mathrm{Pr}\left(n_i\mid f(u)\right)$$
• 特征空间的对称性：两个节点之间相互影响的程度是一样的，因此可以用特征的点乘来表示概率
  $$\mathrm{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))$，称为配分函数，则目标函数可化为
$$\mathrm{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{array}{ll}\frac{{\pi }_{vx}}{Z}& \text{ if }(v,x)\in E\\ 0& \text{ otherwise }\end{array}$$
其中，${\pi }_{vx}$是未归一化的转移概率。

3.2.2 搜索的偏向$\alpha$

直接用权重作为游走概率，则无法调节搜索策略。直接用BFS或者DFS则太极端，无法平滑调节。
于是考虑带参数p和q的二阶随机游走：
$${\alpha }_{pq}(t,x)=\{\begin{array}{ll}\frac{1}{p}& \text{ if }{d}_{tx}=0\\ 1& \text{ if }{d}_{tx}=1\\ \frac{1}{q}& \text{ if }{d}_{tx}=2\end{array}$$
$${\pi }_{vx}={\alpha }_{pq}(t,x)\cdot w_{vx}$$

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

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

3.2.3 伪代码

总共分为三个阶段：

1. 已知p，q和图权重，生成随机游走的采样策略，存入表中
2. 每个节点生成r个随机游走序列，其中node2vecWalk函数用于生成起始点为u，长为l的随机游走序列。
   
3. 用生成的随机游走序列，通过skip-gram模型训练得到节点嵌入表示

AliasSampling是用空间(预处理)换时间的方法，它的时间复杂度是O(1)，特别适用于大量反复抽样情况下，优势很突出。它将离散分布抽样转换为均匀分布抽样。
随机游走过程中，会有隐式的偏差。所以每个节点都采样r次，尽可能减少偏差。
每个阶段都可以并行，并且可以异步训练，可扩展性非常好

3.3 学习连接的特征

将node embedding扩展到link embedding
给定两个节点，定义一个二元操作符$\circ$来生成连接的表示：

4.实验

4.1：悲惨世界人物关系图的图嵌入

4.2 实验设置

与其他算法对比
严格控制各对比实验的条件

4.3 多标签分类

4.4 参数敏感度

随机剔除一些连接，性能会缓慢下降

4.5 扰动分析

缺失连接：保证连通域不变的情况下，进行剪枝，不会造成新的孤岛。
噪声增加连接：随机增加连接，在传感器网络中更常见。

4.6 可扩展性

构建E-R随机图，节点数从100到100万，来做node2vec算法，来看时间。可以看到时间复杂度近似为线性。

4.7 连接预测

构建正负样本的二分类问题。
采集测试集：从网络中取50%的边，同时确保不改变剩下的网络的连通性。再从网络中随机选取一些不相邻的节点对，作为负样本。然后可以训练二分类模型了。

5.讨论和结论

node2vec展示了一定的可解释性，p、q参数是灵活可调的，在复杂任务上的性能不错，特别是在扰动数据集上。
节点嵌入可以拓展到连接嵌入上。

代码实现

参考：https://www.bilibili.com/video/BV1VS4y1E7Me/?p=14&spm_id_from=pageDriver