介绍

英文题目：node2vec: Scalable Feature Learning for Networks
中文题目：node2vec：面向网络的可扩展特征学习
论文地址：https://arxiv.org/abs/1607.00653
领域：图神经网络
发表时间：2016
出处：KDD
被引量：6181
代码和数据：http://snap.stanford.edu/node2vec/
参考其它翻译：【论文笔记】node2vec

说明

• 一切皆可vector
• 图神经网络经典必读第一篇

针对问题：自动学习图中结点和边的特征表示
目标：更好地表征图中的节点：兼顾同质性和结构等价性。
结果：在多领域与SOTA模型对比，展示算法有效性，可在复杂网络中生成任务无关的表征。
方法：note2vec框架，优化随机游走算法，结合深度优先和广度优先两种游走方式，用参数设置游走方式的选择，从而提升效率。

摘要

如果想使用机器学习算法对图中节点和边建模，需要自动学习对图中元素的描述以替代手动对图的特征工程。

文中提出node2vec框架，学习对图中节点的连续性特征的表示。将节点映射到低维空间，使图中相邻节点相似性最高。文中设计了一种有偏随机游走过程，核心在于加入有弹性的领域探索方法来增强特征的表达能力。

在多分类和连接预测任务中对比了node2vec与SOTA模型，展示出文中方法在复杂网络情况下，可有效地学习任务无关的表示。

……

3. 特征学习框架（核心章节）

设G=(V,E)，其中G为图，V是节点，E是边。设f为V-> 映射函数，将节点V映射成特征表示R，d是特征维度。对于每个节点u∈V，定义Ns(u)为使用采样策略S得到的节点u的邻居。

目标是找到映射f，以最大化节点u的邻居是Ns(u)的对数概率。

为了简化问题，做以下假设：

• 条件独立假设：假设节点与其各个邻居之间的关系相互独立

  
  

• 特征空间中的对称性：节点与其邻居的关系是对称的。

  
  
  

  基于上述两个假设，公式一可简化成：

  
  
  当网络很大时，使用负抽样来逼近它；并使用随机梯度上升法来优化模型参数。

特征学习方法使用自然语言处理中的Skip-gram方法。

经典搜索策略

常见两种采样策略：

• 广度优先(BFS）
  邻域由与它直接连通的节点组成，如上图所示，当邻居数据k=3时，BFS采样节点s1,s2,s3。
• 深度优先(DFS）
  邻域由距离源节点越来越远的顺序采样的节点组成，如上图中的s4,s5,s6。

同质性和相似结构：

• 同质性
  同质网络中各个节点往往是相互连通的，如上图中的u和s1就属于同质网络。
• 结构相似
  当节点有类似的网络结构时，这些节点可能充当相似角色，比如上图中的u和s6具有结构相似性（看起来像节点中的hub）。需要注意的，结构相似的网络可能并不相连，它们可能出现在网络的不同位置。

另外，同质性和结构相似性往往在网络中并存。

不同的采样策略决定了节点的特征表示，基于BFS的嵌入方法与结构相似性相关，它可以找到微观局部的邻居，当目标节点起到桥接或hub作用时，通过直接邻域就可以发现。用BFS只能探索图中比较少的区域。相对来说，DFS可以探索更大区域，它反映了邻域的宏观情况，即同源性。它不但需要推断节点间依赖性，还要推断精确的关系，这相对困难，另外，深度优先涉及更远更复杂的依赖，且一般来说距离越远，相关性越小。

3.2 node2vec

文中提出了一种弹性的邻域采样策略，兼顾深度和广度。

3.2.1 随机游走

对于节点u，先设定游走的步数l，用ci表示第i步游走的分布，比如第0步时c0=u。

其中πvx是节点v和x之间的转移概率，而Z是归一化常数。

3.2.2 有偏探索

最简单的方法是根据边的权重采样下一个节点，但这样无法兼顾网络结构以及不同的邻居类型。另外，还需要结合BFS和DFS，而非二选一。

文中使用了p,q两个参数，如图所示：上一步从t到v，目前处于节点v，此时计算边的转移概率πvx：

其中wvx是图中边的权重，dtx是从t到x的最短路径距离（注意这里指的是t和x的距离，不是v和x的距离）。

如图所示，参数p和q控制着游走的距离以及近邻数。

返回参数p：p控制是否返回t节点，p较大时，不容易返回t节点，它鼓励了模型向外探索，并避免了两跳冗余；当p较小时，则使距离足够短，使表示具有微观性。

向内/向外参数q：q允许选择探索向内或向外的节点，当q>1时，随机游走倾向回到t，使表示具有微观性；当q<1时，则倾向广度优先。与完全的深度优先不同，这里只考虑了两步。

相对于单纯的深度或广度优先，随机游走在空间和时间上都更加高效。

3.2.3 node2vec算法

PreprocessModifiedWeights根据参数p,q和图G生成转换概率；外循环表示生成r次随机游走；内循环对于每个节点u，用node2vecWork生成随机游走，最后使用随机梯度下降SGD优化模型参数。

函数note2vecWork用于生成每个节点的游走，遍历每种可能的游走长度l，将当前节点curr设为最后添加的节点，找到它所有的邻居节点，然后根据转移概率π进行有偏采样，得到邻居s并将其加入walk。

最终由三步构成：计算转移概率、模拟随机游走、使用SGD优化。

3.3 学习边的特征表示

node2vec提供了半监督的节点特征学习方法，有时我们对于节点间的关系更感兴趣，比如链接预测：两个节点间是否存在连接，随机游走方法可将节点的表示扩展成边的表示。

假设两个节点u和v，其特征向量为f(u),f(v)，则两个节点的关系被表示为g(u,v)。无论u与v之间是否有边存在，都可以用这种方法表示（存在边为true，不存在为false）。还有一些方法也可以用于表示边，如下表所示。

图3描述了节点的关系，上图为同质化，下图为结构一致性。