✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值
概述
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*。Rk(u) 表示图中距离节点 u 恰好 k ∈ [0, k*] 跳的节点集合,s(S) 表示节点集合 S ⊂ V 的有序度数序列。以下是一个示例:

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

其中函数 g() ≥ 0 用来计算两个度序列之间的距离。请注意,随着 k 增大,fk(u,v) 是递增的,并且仅当 u 和 v 都有 k 跳邻居时才有定义。
为了计算序列 s(Rk(u)) 和 s(Rk(v)) 之间的距离(两个序列的大小可能不同),可以采用动态时间规整(DTW)或其他适用的函数。请注意,如果节点 u 和 v 的 k 跳邻域是同构的,则 fk-1(u,v) = 0。
2. 构建多层加权图
Struc2Vec 构建一个多层加权图 M 来反映节点间的结构相似性,其中第 k 层使用节点的 k 跳邻域来定义。
M 的每层都是一个完全无向加权图,节点集为 V,因此有 条边。第 k 层节点 u 和 v 之间的边权重与它们的结构距离成反比,计算方式如下:

请注意,只有当 fk(u,v) 有定义时,u、v 间的边才有定义。
层之间通过有向边相连。每个节点与它在上一层和下一层(如果有的话)的对应节点相连,层之间的边权重如下:

其中 Γk(u) 表示在第 k 层与节点 u 相连的、权重大于该层平均边权重的边数量。Γk(u) 实际上衡量了节点 u 与第 k 层中其他节点的相似性。如果节点 u 在第 k 层有许多相似节点,则需要转移到更高的层才能准确地描述它的结构身份。
3. 为节点生成上下文
Struc2Vec 使用随机游走生成节点序列来确定给定节点的上下文。
考虑在图 M 中进行的有偏随机游走。游走从每个节点在第 0 层的对应节点开始,当到达第 k 层的节点 u(表示为 uk)时,随机游走首先决定是(1)留在当前层,还是(2)跳到别层:
(1) 以大小为 q
的概率留在当前层:移动到节点 vk 的概率与 wk(u,v) 的大小成正比。请注意,随机游走倾向于访问与当前节点在结构上更相似的节点。
(2) 以大小为 1-q
的概率跳到别层:移动到节点 uk+1 或 uk-1 的概率与 wk(uk,uk+1) 和 wk(uk,uk-1) 的大小成正比。请注意,在这种情况下,节点 u 在随机游走序列中只记录一次。

随机游走具有固定且相对较短的深度(步数),并且该过程会重复一定次数。
4.模型训练
从随机游走获取的节点序列会作为输入进入 Skip-gram 模型。Struc2Vec 基于预测误差使用 SGD 来调整模型参数,并且通过负采样(Negative Sampling)和二次采样(Subsampling)等技术进行优化。
特殊说明
- 在考虑节点度时,自环边计算两次。
- Struc2Vec 的结果与边的方向无关。
语法
- 命令:
algo(struc2vec)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 是 | 指定游走起点的 ID/UUID;忽略表示指定全部点 |
walk_length | int | ≧1 | 1 |
是 | 每次游走的深度,即访问的节点数量 |
walk_num | int | ≧1 | 1 |
是 | 从每个指定节点开始的游走次数 |
k | int | [1,10] | / | 否 | 构造的带权多层图的层数,不能超过图的直径 |
stay_probability | float | (0,1] | / | 否 | 留在当前层游走的概率 |
window_size | int | ≥1 | / | 否 | 上下文的最大长度 |
dimension | int | ≥1 | / | 否 | 嵌入向量的维度 |
loop_num | int | ≥1 | / | 否 | 训练迭代轮数 |
learning_rate | float | (0,1) | / | 否 | 模型训练的初始学习率,学习率会在每次训练迭代后逐渐减小,直至达到 min_learning_rate |
min_learning_rate | float | (0,learning_rate ) |
/ | 否 | 在训练过程中逐渐减小的学习率的最小阈值 |
neg_num | int | ≥0 | / | 否 | 每个正样本对应的负样本数量,建议设置在 0 到 10 之间 |
resolution | int | ≥1 | 1 |
是 | 用于提高负采样效率的参数;较高的值能提供更接近原始噪声分布的近似分布;建议设置为 10、100 等 |
sub_sample_alpha | float | / | 0.001 |
是 | 影响高频节点下采样概率的因素;较高的值会增加这种概率;设置 ≤0 的值表示不应用二次采样 |
min_frequency | int | / | / | 否 | 在训练“语料库”中出现次数低于此阈值的节点将被排除在“词汇表”之外,并在嵌入训练中被忽略;设置 ≤0 的值表示保留所有节点 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
文件回写
配置项 | 回写内容 |
---|---|
filename | _id ,embedding_result |
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'
}})
属性回写
配置项 | 回写内容 | 回写至 | 数据类型 |
---|---|---|---|
property | embedding_result |
点属性 | string |
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'
}})
直接返回
别名序号 | 类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其嵌入结果 | _uuid , embedding_result |
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
流式返回
别名序号 | 类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其嵌入结果 | _uuid , embedding_result |
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