题目：node2vec：学习网络的可扩展特征 会议：KDD2016 论文地址：node2vec: Scalable Feature Learning for Networks

本文将解读斯坦福大学的Aditya Grover和Jure Leskovec在KDD2016年发表的论文《Scalable Feature Learning for Networks》。本文提出了一种高效的网络扩展特征学习方法–node2vec。本论文是2021年北邮计算机学院大数据组夏令营的考核论文。考核方法如下:面试前一天告知论文名称，一天准备时间，面试时考察基础理论和实验。

这篇文章有很多实验，所以全文略长。

节点和边缘的预测任务都需要一个良好的特征工程工作。 目前的特征学习方法不足以表达网络中观察到的连接模式的多样性。

因此，本文提出node2vec方法：一种用于学习网络表示节点的连续特征算法框架node2vec 中，为了最大限度地保留节点网络邻域的可能性，可以学习节点到低维特征空间的映射。

node2vec核心是定义节点网络邻域的灵活概念，设计有偏差的随机游走过程，有效探索不同的邻域。

网络分析中的许多重要任务都涉及到对节点和边缘的预测。

本文的主要贡献是定义了一个灵活的节点网络邻域概念。通过一个有偏随机游走来有效地探索给定节点的不同社区，然后返回一个游走序列。

算法是灵活的，可以通过可调参数控制搜索空间，而不是像之前的方法那样死板。

搜索什么？我们需要学到一个节点的特征向量表示，在此之前，我们首先要找到该节点的邻域节点，这些节点可以通过某种方法来生成，而这也是本文的重点。

有了节点的特征表示后，通过将两个节点的特征表示进行某种组合，就能这对节点的特征表示，也就是边的特征表示，进而就能进行边的预测。

本文的实验部分主要进行了在网络中两个比较常见的预测任务：

• 多标签分类任务：预测某个节点的标签
• 链接预测任务：预测两个节点间是否存在边。

总结本文贡献：

1. 提出了一种高效的网络的可拓展特征学习方法：node2vec。
2. 展示了node2vec如何符合现有网络预测中已有的原则，但同时又有灵活性在里面。
3. 扩展了node2vec和其他基于邻域的特征学习方法，从节点到节点对，用于基于边的预测任务。
4. 对node2vec在多个真实数据集上的多标签分类和链接预测进行了评估。

这一节简单回顾了网络特征学习的相关工作。

无监督特征学习方法通常利用图的各种矩阵表示的性质，特别是拉普拉斯矩阵和邻接矩阵来进行特征学习。这点有在前文中提到，计算代价很大，并且效果也不是很好。

nlp中表示学习的最新进展为词汇等离散对象的特征学习开辟了新途径。Skip-gram模型旨在通过优化邻域保持似然目标来学习单词的连续特征表示。

skip-gram可以参考：论文阅读：Efficient Estimation of Word Representations in Vector Space

对于基于节点和基于边的预测任务，最近也有很多新的工作，这些体系结构使用多层非线性转换直接最小化下游预测任务的损失函数，从而获得较高的精度，但由于训练时间要求高，可扩展性不强。

于是必须提出一种新的方法！！

这部分介绍node2vec的细节。 将网络中的特征学习定义为一个最大似然优化问题。 G = ( V , E ) G=(V,E) G=(V,E)表示网络。 f : V → R d f:V \to R^d f:V→Rd表示节点到其特征表示的映射函数， d d d是特征表示的维度， f f f是一个大小为 ∣ V ∣ × d |V| \times d ∣V∣×d的矩阵， ∣ V ∣ |V| ∣V∣是节点个数，也就是说每个节点的特征表示都是一个 d d d维的向量。

对每一个节点 u u u，定义 N s ( u ) N_s(u) Ns​(u)是通过邻域抽样策略 S S S生成的节点 u u u的网络邻域， N s ( u ) N_s(u) Ns​(u)是原始图中结点集 V V V的子集。

将nlp中的skim-gram架构扩展到网络学习中：优化以下目标函数（使一个节点u根据其特征表示( f f f)观察到网络邻域 N s ( u ) N_s(u) Ns​(u)的对数概率最大化）

P r ( N s ( u ) ∣ f ( u ) ) P_r(N_s(u)|f(u)) Pr​(Ns​(u)∣f(u))表示根据一个节点的特征表示来观察其邻域的对数概率。最大化该概率的意义是什么？个人理解：经过 f f f的映射后可以很好地保持各个节点间的邻居概念。

为了使上述优化问题易于处理，作者给出了两点假设：

1. 有条件的独立。我们通过假设观察一个邻域节点的可能性与观察任何其他邻域节点的可能性是独立的： 很好理解！
2. 特征空间的对称性。源节点和邻域节点在特征空间中具有对称效应。据此，我们将每个源-邻域节点对的条件似然建模为softmax单元:

在上述两个假设下，公式1中的优化问题可以简化为： 其中 Z u Z_u Zu​的表达式如下所示： Z u = ∑ v ∈ V e x p ( f ( u ) ⋅ f ( v ) ) Z_u=\sum_{v \in V}exp(f(u)\cdot f(v)) Zu​=v∈V∑​exp(f(u)⋅f(v))

对于大型网络，每个节点的 Z u Z_u Zu​的计算代价很高，因此使用负采样来近似它。

那怎么得到 N s ( u ) N_s(u) Ns​(u)呢？下面将一一介绍！

对节点的邻域进行采样的经典策略主要包括两种：BFS和DFS，如下所示： 给定一个源节点 u u u，我们的任务是找到它的邻域节点集合 N s ( u ) N_s(u) Ns​(u)，假设我们需要采样 k k k个节点。

• BFS：只能采样与 u u u相邻的节点，例如上图中要寻找节点 u u u的大小为3的邻域集合，则可以选择 s 1 , s 2 , s 3 s_1,s_2,s_3 s1​,s2​,s3​三个节点。
• DFS：按照距离源节点距离依次增加的顺序进行采样，比如说对于节点 u u u可以选择 s 4 , s 5 , s 6 s_4,s_5,s_6 s4​,s5​,s6​三个节点。

根据同质性假设，属于相似网络集群的高度互联节点应该嵌入到一起，比如上图中的 u u u和 s 1 s_1 s1​，它们就属于同一网络集群。

而根据结构等价假设，在网络中具有相似结构角色的节点应该嵌入到一起，比如上图中的 u u u和 s 6 s_6 s6​，虽然属于不同网络集群，但是它们都是相应集群的中枢节点，角色类似。

结构等价不同于同质性，它不强调节点间必须互连，它们可能距离很远，这一点很重要。

BFS仅限于与源节点相连的节点，倾向于在初始节点的周围游走，可以反映出一个节点的邻居的微观特性。

而DFS（可以重复访问）一般会跑得离源节点越来越远，可以反映出一个节点邻居的宏观特性。

两种方法的局限都很明显：BFS只能探索图的很小一部分，而DFS移动到更大的深度会导致复杂的依赖关系，因为采样节点可能远离源，并且可能不太具有代表性。

DFS和BFS都有各自的优缺点，于是本文提出了node2vec。下面介绍node2vec的细节。

给定一个源节点 u u u，我们需要获得一个采样序列，序列长度为 l l l。节点由以下分布生成： 其中 c i c_i ci​表示第 i i i个采样的节点。可以看出，第 i i i个采样的节点与第 i − 1 i-1 i−1个采样的节点有着密切关系。 π v x \pi_{vx} πvx​表示两个节点间的非归一化转移概率， Z Z Z是归一化常数。

简单解释下上述分布： 当第 i i i个节点是 v v v时（初始为 u u u），我们采样下一个节点时，先找出所有与 v v v相连的结点，然后算出 v v v与这些结点间的非归一化转移概率，随后再进行采样。

上图中，对于一个随机游走，如果已经采样了 ( t , v ) (t, v) (t,v) ，也就是说现在停留在节点 v v v上，那么下一个要采样的节点 x x x是哪个？作者定义了一个概率分布，也就是一个节点到它的不同邻居的转移概率： 简单解释一下：

• 如果 t t t与 x x x相等，那么 x x x被采样的概率是 1 / p 1/p 1/p
• 如果 t t t与 x x x相邻，那么 x x x被采样的概率是1
• 如果 t t t与 x x x距离为2，那么 x x x被采样的概率是 1 / q 1/q 1/q

要注意这里 t t t已经被采样了！！

本文提出了返回参数 p p p和出入参数 q q q：参数用于控制随机游走产生的方式。需要说明的是，距离取值只能为 0 , 1 , 2 0,1,2 0,1,2。

其中返回参数 p > m a x ( q , 1 ) p>max(q,1) p>max(q,1)（第二种或者第三种情况），选取下一个点时会尽量不往回走；如果 p < m i n ( q , 1 ) p<min(q, 1) p<min(q,1)（更倾向于第一种情况）会倾向于围绕某节点打转。

出入参数q>1会倾向于在初始节点周围节点之间跑，反映出BFS特性，如果q比较小会往远处跑，表现出DFS特性。

看一下算法的参数：图 G G G、节点特征向量的维度 d d d、每个节点生成的游走个数 r r r，游走长度 l l l，上下文的窗口长度 k k k，以及之前提到的 p 、 q p、q p、q参数。

首先根据 p 、 q p、q p、q和之前的公式计算一个节点到它的邻居的转移概率，此时形成了新的图 G ′ G^{'} G′。

1. walks用来存储随机游走，先初始化为空
2. 一共要进行 r r r次循环，每一次循环要为图中每个节点都生成一个长度为 l l l的游走序列
3. 第 r r r次循环中对所有节点都利用node2vec算法生成一个随机游走walk，然后将其加入walks
4. 得到所有节点的 r r r个游走序列后，根据上下文和该节点的游走序列利用SGD方法得到每一个节点的向量表示。

具体的node2vec算法：为某一个节点 u u u生成一个游走序列。描述如下：

1. 将初始节点 u u u加入到walk中
2. 当前节点curr为walk中最后一个节点
3. 根据curr和其对周围节点的转移概率选择下一个节点 s s s，并加入walk
4. 当walk长度为 l l l时采集结束

node2vec算法可以得到网络中节点的特征向量表示。为了进行链路预测，也就是判断两个节点之间是否相连，我们需要将节点对表示成一个特征向量。具体做法就是在两个节点特征向量的基础上构造一个二元算子，比如平均，相加或者相减： 其中 f ( u ) f(u) f(u)和 f ( v ) f(v) f(v)表示两个节点的特征向量表示。经过上述运算后，就能得到节点对 ( u , v ) (u, v) (u,v)的特征向量表示。注意 u u u和 v v v间可以不存在边。