目前的特征学习方法还不足以表达网络中观察到的连接模式的多样性

node2vec

• 学习网络中节点连续特征表示的算法框架
• 节点的网络邻域最大化

我们定义了一个灵活的节点网络邻域概念，并设计了一个有偏差的随机漫步过程，可以有效地探索不同的邻域。

在我们看来，探索邻域的额外灵活性是学习更丰富表征的关键

目前的技术未能满意地定义和优化网络中可扩展的学习所需的合理目标

node2vec

• 网络中可扩展特征学习的半监督算法
• 使用SGD基于图的自定义目标函数优化
• 返回的特征表示能在d维特征空间中最大限度地保留节点的网络邻域
• 节点生成(采样)网络邻域采用二阶随机游走法。

我们的关键贡献是节点网络邻居概念的灵活定义

选择合适的邻域概念，node2vec学习基于其网络角色和/或其社区组织节点的表达。

通过开发一系列有偏差的随机步行，我们可以有效地探索给定节点的不同邻居。

所得到的算法是灵活的，可调参数让我们控制搜索空间，而不是之前工作中严格的搜索过程[24，28]。

我们还展示了如何将单个节点的特征扩展到节点对(即边)。

为了生成边缘的特征表示，只需使用简单的二元操作符合组合学习的单个节点的特征表示。这种组合使node2vec可用于预测任务，包括节点和边缘。

我们的实验集中在网络中两个常见的预测任务：

• 一个是多标签分类任务，每个节点分配一个或多个类标签；
• 另一个是链路预测任务，我们预测一对节点的边缘是否存在

实验表明

• node2vec在多标签分类和链路预测性能分别达到26.7%和12.6%。
• 该算法对10%的标记数据具有良好的性能，对噪声或缺失边缘的干扰也具有鲁棒性。
• 在计算上，node2vec主要阶段是可并行化是的，它可以在几个小时内扩展到拥有数百万节点的大型网络。

我们把网络中的特征学习定义为优化问题

适用于任何有向(或无向)网络， 加权(或无权)网络

$G=(V,E)$

$f:V\to R^d$

将图$G$的一个顶点$v$映射为一个$d$维向量，所有顶点对应的$d$维向量构成一个大小为$|v|\times d$的矩阵 ，也就是$f$

$N_s(u)$：顶点u的邻域

其中$u\in V$，$N_s(u)\subset V$，注意这里的邻域是通过邻域采样策略$S$生成的
通过采样策略$S$，采集到的顶点u的邻域可能会不仅仅只局限其直接的邻居节点

运用Skip-gram架构的思路

对一个单词其最大概率的上下文

得到优化目标函数

$f(u)$是顶点u的一个d维向量表示
$Pr(N_s(u)|f(u))$表示：顶点u的邻域对f(u)的概率
上面函数的意思大概就是：使得对所有顶点来说，其邻域对于其d维向量的概率之和最大
也就是说，对于每一个顶点，其邻域对于其d维向量的概率是存在的，我们的目标就是找出一个向量空间，使得每个顶点这样的概率之和最大

为了使优化问题易于处理，我们做了两个标准假设:

1）条件独立

假设观察一个邻域节点的可能性与观察任何其他邻域节点的可能性是独立的

简单的理解就是：顶点u的邻域对$f(u)$的概率可以想象为邻域中每一个顶点$n_i$对$f(u)$的概率的连乘

2）特征空间的对称性

源节点和邻域节点在特征空间中相互对称

因此我们将每个源邻节点对的条件似然建模为一个softmax单元，由其特征的点积进行参数化:

这里的意思大概就是：定义$Pr(n_i｜f(u))$，因为$Pr(n_i｜f(u))$这个概率是很模糊的，没有明确怎么求，作者这里就是通过向量空间中的不同顶点对应的向量之间的运算（就是上面式子）来明确表示$Pr(n_i｜f(u))$

通过以上两个假设的简化，等式1就可以写为

其中

对于大型网络，$Z_{(}u)$的计算成本很高（），然后通过负采样来近似等式2

使用随机梯度上升求等式2最优值

这里等式2是求max
一般求min时，是用SGD，也就是随机梯度下降
随机梯度下降/上升区别可以参考：https://blog.csdn.net/weixin_41245919/article/details/85091133

我们将源节点的邻域采样问题视为一种局部搜索的形式

为了能够公平地比较不同的采样策略$S$

• 将邻域集$N_S$的大小限制为$k$个节点
• 对单个节点$u$进行多个集合的采样（对每个节点进行多次采样）

一般情况下，产生k个节点的邻域集NS有两种极端采样策略:

• Breadth-first Sampling (BFS)
• Depth-first Sampling (DFS)

网络中节点的预测任务需要利用到节点的同质性和结构等价性两种相似性

• 同质性
• 结构等价

参考图1：

• 在同质性假设下，高度互连的节点，属于类似的网络集群或社区，应紧密嵌入在一起(如图1中的节点$s_1$和$u$属于同一个网络社区)。
• 而在结构等价假设下，网络中具有相似结构角色的[10]节点应该紧密嵌入在一起(如图1中的节点$u$和$s_6$作为其对应社区的枢纽)。

重要的是，与同质性不同，结构等价并不强调连通性：网络中的节点可以相隔很远，但仍然具有相同的结构作用

在现实世界网络中，这些等价概念并不是单独存在的

• 网络通常表现出这两种相似性，可能其中一些节点表现出同质性，而另一些则反映出结构等价

BFS 《==》结构等价：BFS采样的邻域导致了与结构等价性密切对应的嵌入

• 为了确定结构上的等价性，准确地描述局部邻域通常就足够了
• 此外，在BFS中，采样邻域中的节点往往会重复多次。这也很重要，因为它减少了表征1跳节点相对于源节点的分布的方差
• 然而，对于任何给定的$k$（采样的节点数量），使用BFS，只有图的一小部分被探索到。

DFS 《==》同质性：DFS采样的节点更准确地反映了邻域的宏观情况

• 可以探索到网络的更大部分，因为它可以远离源节点u(样本大小k是固定的)

然而，DFS的问题在于

• 不仅要推断网络中存在哪些节点到节点的依赖关系
• 而且还要确定这些依赖关系的确切性质。这是很难的，因为我们有一个样本大小的限制和一个大的邻域来探索，导致高方差。
• 其次，移动到更大的深度会导致复杂的依赖关系，因为采样的节点可能离源很远，可能不太具有代表性

基于上述观察结果，我们设计了一种灵活的邻域采样策略，使我们能够在BFS和DFS之间平滑地插值。我们通过开发一个灵活的有偏随机漫步程序来实现这一点，该程序可以以BFS和DFS的方式探索社区

形式上，给定源节点$u$，我们模拟固定长度$l$的随机游走。

令$c_i$表示遍历中的第$i$个节点，从$c_0=u$开始。

节点$c_i$由以下分布生成:

式中

• ${\pi }_{vx}$为节点$v$与$x$之间的非标准化跃迁概率
• $Z$为标准化常数。

上式简单理解为：

• 节点v的下一个节点是节点x的概率为：如果节点v,x之间有边，则为$\frac{{\pi }_{vx}}{Z}$，否则为0

最简单的有偏随机游走：

• 抽样下一个节点是基于静态边权值$w_{vx}$，即${\pi }_{vx}$ = $w_{vx}$。(对于非加权图，$w_{vx}$ = 1)

然而，这并不允许我们考虑网络结构，并指导我们的搜索过程来探索不同类型的网络邻居。

这么简单的随机游走不行的

BFS和DFS是分别适用于结构等价和同质性的极端抽样范例

我们的随机游走应该适应这样一个事实

• 这些等价的概念不是竞争或排他性的，
• 现实世界的网络通常表现出两者的混合。

个人理解：

• BFS是适用于结构等价的采样策略
• DFS是适用于同质性的采样策略
• 两个方法都是极端的采样策略，只侧重一个方面的等价
• 真实的网络是存在两者等价关系的，我们需要通过参数控制，使得采样策略位于BFS和DFS之间

我们定义了一个二阶随机游走，通过两个参数$p$和$q$来引导游走

以下图为例

假设已经从节点$t$遍历到节点$v$（从$t$游走到$v$），现在位于节点$v$

现在需要决定从v开始，下一步游走的节点是哪一个节点（也就是需要判断下一次游走）

因此需要计算从节点$v$开始的边$(v,x)$上的跃迁概率${\pi }_{vx}$

跃迁概率${\pi }_{vx}$：从节点$v$游走到节点$x$的概率

我们设非标准化跃迁概率为${\pi }_{vx}={\alpha }_{pq}(t,x)\cdot w_{vx}$

其中

• $w_{vx}$表示顶点$v$与$x$之间的权重（无权图为1）
• $d_{tx}$表示节点$t$和$x$之间的最短路径距离。
  • 注意，$d_{tx}$必须是{0,1,2}中的一个
  • $t$是节点$v$之前已经遍历的前一个节点
  • 也就是我们需要判断上一次已经遍历过的一个节点$t$与目前节点$v$的邻域节点的距离distance

直观地说

• 参数$p$和$q$控制游走搜索和离开起始节点$u$邻域的速度
• 特别地，参数允许我们的搜索过程(大约)在BFS和DFS之间插值，从而反映了不同节点等价概念的亲和力

Return parameter, p

参数p控制在遍历中立即重新访问某个节点的可能性（比如又一次遍历节点t）

• 将其设置为一个高值(> max(q, 1))可以确保我们不太可能在接下来的两个步骤中采样一个已经访问过的节点(除非遍历中的下一个节点没有其他邻居)。这种策略鼓励适度的探索和避免采样中的2跳冗余
• 另一方面，如果p很低(< min(q, 1))，它将导致很大概率遍历返回上一个已经遍历的节点(图2中的节点t)，这将保持遍历起始节点u的“局部”

In-out parameter, q

参数$q$允许搜索区分“内向”和“外向”节点