概述

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