✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

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