概述
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)意味着它们的邻域拓扑是同构或对称的。具有相似功能的节点与其邻居节点之间具有相似的连接关系。
![](https://img.ultipa.cn/2021-12-23-14-50-13-struc2vec-network.png)
如图所示,节点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的有序度数序列。以下是一个示例:
![](https://img.ultipa.cn/draw/draw_88cfae112dee41fc92f1109b9d279048.jpg?v='1693276088404')
fk(u,v)表示考虑k跳邻域(所有距离小于或等于k的节点)时,u和v之间的结构距离(Structural Distance):
![](https://img.ultipa.cn/2022-08-31-09-45-06-fk.jpg)
其中函数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之间的边权重与它们的结构距离成反比,计算方式如下:
![](https://img.ultipa.cn/2022-08-31-10-20-44-wk.jpg)
请注意,只有当fk(u,v)有定义时,u、v间的边才有定义。
层之间通过有向边相连。每个节点与它在上一层和下一层(如果有的话)的对应节点相连,层之间的边权重如下:
![](https://img.ultipa.cn/img/2023-01-12-15-54-37-weight.jpg)
其中Γ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在随机游走序列中只记录一次。
![](https://img.ultipa.cn/draw/draw_b8c83622d5104488aa8657ab14e02cfb.jpg?v='1693299298592')
随机游走具有固定且相对较短的深度(步数),并且该过程会重复一定次数。
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 | ≥2 | / | 否 | 嵌入向量的维度 |
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