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

概述

Struc2Vec 代表"结构到向量"。该算法生成的节点向量能保留图的内在结构，即拓扑相似性，是一个革命性的图嵌入技术。

• L. Ribeiro, P. Saverese, D. Figueiredo, struc2vec: Learning Node Representations from Structural Identity (2017)

尽管 Node2Vec 能够在某种程度上捕获节点间的结构相似性，但它受其生成过程中使用的随机游走深度所限制。与之不同，Struc2Vec 在其框架中克服了这一限制，能够确保具有相似结构特征的节点在嵌入空间中有靠近的表示。

选择使用 Node2Vec 或 Struc2Vec 时，要考虑下游任务的性质：

• Node2Vec 适用于优先考虑节点同质性、捕获属性和连接相似性的任务。
• Struc2Vec 在需要关注局部拓扑相似性、保留节点之间结构关系的任务中表现出色。

基本概念

结构相似性

在各种网络中，节点往往具有承担特定的功能或角色的结构身份（Structural Identity）。发挥类似功能的节点自然属于同一类，表示它们具有结构相似性。例如，在公司的社交网络中，所有的实习生具有相似的角色。

节点之间的结构相似性（Structural Similarity）意味着它们的邻域拓扑是同构或对称的。具有相似功能的节点与其邻居节点之间具有相似的连接关系。

如图所示，节点 u 和 v 在结构上是相似的（度数分别为 5 和 4，分别连接到 3 和 2 个三角形，都通过 2 个节点连接到网络的其余部分）。然而，它们之间没有直接相连，也没有共同邻居，甚至在网络中可能相隔很远。

当节点之间的距离超过随机游走的深度时，就很难使用 Node2Vec 等方法为它们生成类似的表示。Struc2Vec 算法有效地解决了这个问题。

Struc2Vec 框架

1. 计算结构相似性

关于结构相似性，直观评判标准是：如果两个节点的度相同，它们在结构上是相似的；如果两个节点的邻居的度也相同，它们的结构相似性就更高了。

考虑一个无向无权图，表示为 G = (V, E)，其直径表示为 k*。R_k(u) 表示图中距离节点 u 恰好 k ∈ [0, k*] 跳的节点集合，s(S) 表示节点集合 S ⊂ V 的有序度数序列。以下是一个示例：

f_k(u,v) 表示考虑 k 跳邻域（所有距离小于或等于 k 的节点）时，u 和 v 之间的结构距离（Structural Distance）：

其中函数 g() ≥ 0 用来计算两个度序列之间的距离。请注意，随着 k 增大，f_k(u,v) 是递增的，并且仅当 u 和 v 都有 k 跳邻居时才有定义。

为了计算序列 s(R_k(u)) 和 s(R_k(v)) 之间的距离（两个序列的大小可能不同），可以采用动态时间规整（DTW）或其他适用的函数。请注意，如果节点 u 和 v 的 k 跳邻域是同构的，则 f_k-1(u,v) = 0。

2. 构建多层加权图

Struc2Vec 构建一个多层加权图 M 来反映节点间的结构相似性，其中第 k 层使用节点的 k 跳邻域来定义。

M 的每层都是一个完全无向加权图，节点集为 V，因此有 $\frac{\mathrm{|V|*(|V|-1)}}{2}$ 条边。第 k 层节点 u 和 v 之间的边权重与它们的结构距离成反比，计算方式如下：

请注意，只有当 f_k(u,v) 有定义时，u、v 间的边才有定义。

层之间通过有向边相连。每个节点与它在上一层和下一层（如果有的话）的对应节点相连，层之间的边权重如下：

其中 Γ_k(u) 表示在第 k 层与节点 u 相连的、权重大于该层平均边权重的边数量。Γ_k(u) 实际上衡量了节点 u 与第 k 层中其他节点的相似性。如果节点 u 在第 k 层有许多相似节点，则需要转移到更高的层才能准确地描述它的结构身份。

3. 为节点生成上下文

Struc2Vec 使用随机游走生成节点序列来确定给定节点的上下文。

考虑在图 M 中进行的有偏随机游走。游走从每个节点在第 0 层的对应节点开始，当到达第 k 层的节点 u（表示为 u_k）时，随机游走首先决定是（1）留在当前层，还是（2）跳到别层：

(1) 以大小为 q 的概率留在当前层：移动到节点 v_k 的概率与 w_k(u,v) 的大小成正比。请注意，随机游走倾向于访问与当前节点在结构上更相似的节点。

(2) 以大小为 1-q 的概率跳到别层：移动到节点 u_k+1 或 u_k-1 的概率与 w_k(u_k,u_k+1) 和 w_k(u_k,u_k-1) 的大小成正比。请注意，在这种情况下，节点 u 在随机游走序列中只记录一次。

随机游走具有固定且相对较短的深度（步数），并且该过程会重复一定次数。

4.模型训练

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

特殊说明

• 在考虑节点度时，自环边计算两次。
• Struc2Vec 的结果与边的方向无关。

语法

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

示例

文件回写

algo(struc2vec).params({
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  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(struc2vec).params({
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  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(struc2vec).params({
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  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(struc2vec).params({
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  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