概述

Node2Vec是一种半监督（Semi-supervised）算法，旨在学习图中节点的特征，同时有效地保留它们的邻域信息。它引入了一种灵活的搜索策略，可以探索节点的BFS和DFS邻域。此外，它还将 Skip-gram模型扩展到图中，用于训练节点嵌入。Node2Vec由斯坦福大学的A. Grover 和J. Leskovec在2016年开发。

• A. Grover, J. Leskovec, node2vec: Scalable Feature Learning for Networks (2016)

基本概念

节点相似性

Node2Vec学习将节点映射到低维向量空间，同时确保在网络中相似的节点在向量空间中具有接近的嵌入。

网络中的节点经常表现两种相似性：

1. 同质性

同质性（Homophily）在网络中是指具有相似属性、特征或行为的节点更有可能相互连接在一起，或者属于同一个或相似的社区（上图中的节点u和s₁属于同一社区）。

例如，在社交网络中，具有类似背景、兴趣或观点的个体更有可能建立连接。

2. 结构等效性

在网络中，结构等效性（Structural Equivalence）是指根据节点在网络内的“结构角色”（Structural Role）而被视为等效的概念。结构等效的节点具有类似的连接模式和与其他节点的关系（即局部拓扑结构），即使它们特征不同（上图中的节点u和v都在各自的社区中充当枢纽的角色）。

例如，在社交网络中，结构等效的个体可能在其社交群体中占据类似的位置。

与同质性不同的是，结构等效性不强调连接性；节点可能在网络中相距较远，但仍有相同的结构角色。

在讨论结构等效性时，有两个要点：首先，在实际网络中实现完全的结构等效是不常见的，因此我们更关注评估“结构相似性”（Structural Similarity）。其次，随着分析范围扩大，两个节点之间的结构相似性程度往往会降低。

搜索策略

通常来说，有两种极端的搜索策略来生成包含k个节点的邻域集合N_S：

• 广度优先搜索（BFS）：N_S仅包含与起始节点直接相邻的节点。例如，在上图中，如果k = 3，N_S(u) = {s₁, s₂, s₃}。
• 深度优先搜索（DFS）：N_S 包括距离起始节点逐渐远的节点。例如，在上图中，如果k = 3，N_S(u) = {s₄, s₅, v}。

BFS和DFS策略在生成反映节点之间同质性或结构等效性的嵌入时起关键作用：

• 通过BFS抽样的邻域生成的嵌入与结构等效性密切相关。通过限制搜索范围在附近的节点，BFS 能获取起始节点邻域的微观视图，这通常足以描述其局部拓扑。
• 通过DFS抽样的邻域生成的嵌入与同质性密切相关。通过远离起始节点，DFS能获得其邻域的宏观视图，这对于推断社区中节点之间依赖关系是至关重要的。

Node2Vec框架

1. Node2Vec游走

Node2Vec使用带有返回参数（Return）p和远近参数（In-out）q的有偏随机游走。

考虑刚刚经过边(t,v)现在到达节点v的随机游走，游走的下一步由从v出发的所有边(v,x)的转移概率决定，这些概率与边的权重成正比（非加权图中所有边的权重为1）。边(v,x)的权重会根据节点t和x间的最短距离d_tx被p和q所调整：

• 如果d_tx = 0，将边的权重乘以1/p。在上图中，d_tt = 0。参数p影响返回到刚刚离开的节点的可能性。当p < 1时，更有可能回退一步；当p > 1时反之。
• 如果d_tx = 1，边的权重保持不变。在上图中，d_tx1 = 1。
• 如果d_tx = 2，将边的权重乘以1/q。在上图中，d_tx2 = 2。参数q决定随机游走是朝近处移动（q > 1）还是朝远处移动（q < 1）。

请注意，d_tx一定是{0, 1, 2}中的一个。

通过这两个参数，Node2Vec提供了一种在随机游走期间权衡探索（Exploration）和开发（Exploitation）的方式，从而能够产生从同质性到结构等效性的一系列表示。

2. 节点嵌入

从随机游走获取的节点序列会作为输入进入Skip-gram模型。Node2Vec基于预测误差使用 SGD来调整模型参数，并且通过负采样（Negative Sampling）和二次采样（Subsampling）等技术进行优化。

特殊说明

• Node2Vec的结果与边的方向无关。

语法

• 命令：algo(node2vec)
• 参数：

示例

文件回写

algo(node2vec).params({
  walk_length: 10,
  walk_num: 20,
  p: 0.5,
  q: 1000,
  buffer_size: -1,
  window_size: 5,
  dimension: 20,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}).write({
  file:{
    filename: 'embeddings'
}})

属性回写

algo(node2vec).params({
  walk_length: 10,
  walk_num: 20,
  p: 0.5,
  q: 1000,
  buffer_size: -1,
  window_size: 5,
  dimension: 20,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}).write({
  db:{
    property: 'vector'
}})

直接返回

algo(node2vec).params({
  walk_length: 10,
  walk_num: 20,
  p: 0.5,
  q: 1000,
  buffer_size: -1,
  window_size: 5,
  dimension: 20,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}) as embeddings
return embeddings

流式返回

algo(node2vec).params({
  walk_length: 10,
  walk_num: 20,
  p: 0.5,
  q: 1000,
  buffer_size: -1,
  window_size: 5,
  dimension: 20,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}).stream() as embeddings
return embeddings