概述
Struc2Vec 图嵌入算法最早发表在 SIGMOD 2017 年的会议上,字面意思是“结构到向量”。该算法描述了一种从图生成节点向量并保留图结构(即拓扑结构相似性)的框架。虽然 Node2Vec 图嵌入算法的结果也能在一定程度反映节点间的结构相似性,但仅局限在游走步数内;而结构相似的节点在网络中也许相距较远,Struc2Vec 图嵌入结果则能保证其在嵌入空间的距离是靠近的。
一般地,如果下游任务(如分类)更看重节点的同质性特征,Node2Vec 图嵌入算法可以满足要求;但如果下游任务是想利用节点局部拓扑结构的相似性,Struc2Vec 图嵌入算法则更合适。
算法的相关资料如下:
- L. Ribeiro, P. Saverese, D. Figueiredo, struc2vec: Learning Node Representations from Structural Identity (2017)
基本概念
结构性身份
在一个网络中,通常可以根据节点在网络中的功能将节点划分为不同类别,即结构性身份(Structural Identity);发挥相似功能的节点就可以被划分到同一类别,即具有结构相似性。例如,在一个公司社交网络中,所有实习生的角色是类似的。
结构相似性是指两个节点的邻域拓扑结构是近似同构或对称的。例如,下图中的节点 u
和 v
具有结构相似性:它们的节点度分别为 5 和 4,分别连接 3 个和 2 个三角形,并且都是通过其他两个节点(d
和 e
,x
和 w
)连接到剩余网络。然而,它们在网络中可能相距很远,既不直接相连也没有共同邻居。
Struc2Vec 核心思想
通过类似于 Node2Vec 的随机游走产生序列时,如果两个节点的游走序列相似,它们的嵌入结果也会比较接近。很容易想到的是,在图上位置比较靠近的节点更容易产生相似的游走序列,而相距较远(超过游走深度)的节点几乎不可能产生相似的游走序列,即使它们有相似的结构。
Struc2Vec 克服了这一局限性,它的核心思想如下:
- 忽略节点和边的属性以及它们在网络中的位置来评估节点间的结构相似性,仅考虑节点的局部结构。
- 建立一个分层结构来衡量节点的结构相似性:在最底层,结构相似性仅取决于节点度;在最高层,结构相似性取决于整个网络的信息。
- 节点随机游走得到游走序列,游走序列相似的两个节点具有相似的结构。
Struc2Vec 工作框架
1. 计算结构相似度
两个节点的结构相似度的直观评判标准是:如果两个节点的度相同,它们在结构上是相似的;如果两个节点的邻居的度也相同,它们的结构相似度就更高了。
令 Rk(u) 是图中节点 u 的第 k 跳邻居集合(0 ≤ k ≤ 图的直径),s(S) 是节点集合 S 的有序度序列,示例如下:
当节点 u、v 都存在第 k 跳邻居时,定义 fk(u,v) 为 u、v 间 k 跳邻域(所有与节点相距小于等于 k 步的节点集合)的结构距离(Structural Distance):
其中 g() ≥ 0 是计算两个序列间距离的函数。对于节点 u、v 来说,序列 s(Rk(u)) 和 s(Rk(v)) 的长度可能是不同的。比较不同长度的序列距离可采用动态时间规整(Dynamic Time Wrapping,简称 DTW),或其他可行方法。如果节点 u、v 的 k 跳邻域是同构的,则 fk-1(u,v) = 0。
2. 构建带权多层图
对于图 G = (V,E),按以下描述构建一个带权多层图 M:
M 的第 k 层是由节点集合 V 组成的带权无向完全图,其中每对节点 u、v 间的边权重与它们之间的结构距离成反比,定义如下:
请注意,只有当 fk(u,v) 有定义时,u、v 间的边才有定义。
对于第 k 层的每个节点 u,使用有向边分别将其与第 k+1 层和第 k-1 层的节点 u 相连,边权重定义如下:
其中 Γk(u) 是与 u 相连且权重大于第 k 层平均边权重的边数量。Γk(u) 实际上能衡量第 k 层节点 u 与其他节点间的相似度。请注意,如果节点 u 在第 k 层有很多相似节点,则需要更大的邻域(k 越大,邻域越大)来准确地描述节点 u 的结构性身份。
3. 为节点生成上下文
节点在带权多层图 M 中进行随机游走来生成结构性的上下文,也就是节点序列。每次的随机游走都从第 0 层出发,当到达 uk 的位置时,选择下一步游走位置的规定如下:
- 首先决定节点留在第 k 层还是跳到别层,留在当前第 k 层的概率由参数
stay_probability
(下图中用p
表示)控制。 - 如果留在第 k 层,uk 跳到各邻居节点的概率与它们之间边权重成正比;也就是说,节点倾向于跳到与自身结构相似度更高的节点。
- 如果跳到别层,即 uk+1 或 uk-1 的位置的概率也与它们之间边权重成正比。
4.语言模型训练
Struc2Vec 使用 Word2Vec 的 Skip-Gram 模型学习得到图中节点的嵌入向量。
关于 Skip-gram 模型,请阅读文档—— Skip-gram 模型 和 Skip-gram 模型优化
特殊处理
孤点、不连通图
孤点没有邻居节点,从 1 跳邻域开始,就无法计算孤点与其他节点间的结构距离。因此,带权多层图从第 1 层往上的每一层,孤点与其他节点间都不存在边或边权重极小。
图的连通性不影响节点的结构相似性,结构相似性高的两个节点可能位于不同的连通分量。
自环边
Struc2Vec 图嵌入算法对自环边的处理与节点度算法 algo(degree)
相同,都是每条自环边计算两次。
有向边
Struc2Vec 图嵌入算法的结果与边的方向无关。
命令和参数配置
- 命令:
algo(struc2vec)
params()
参数配置如下:
名称 | 类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
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 | 采样窗口大小,在窗口中心左边和右边各采样 window_size 个节点 |
dimension | int | / | >=1 | 节点嵌入向量的维度 |
learning_rate | float | / | (0,1) | 初始学习率,每次迭代后学习率都会降低,直至减到 min_learning_rate |
min_learning_rate | float | / | (0,learning_rate ) |
最小学习率 |
min_frequency | int | / | >=0 | 出现次数小于该值的节点将被模型舍弃,<=1 时保留全部节点 |
sub_sample_alpha | float | / | / | 二次采样策略中的阈值,小于等于 0 时不进行二次采样 |
resolution | int | / | >=1 | 如 10、100 |
neg_num | int | / | >=0 | 负采样时的负样本数量,建议 0~10 |
loop_num | int | / | >=1 | 训练迭代轮数 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
示例:在全图进行 Struc2Vec 图嵌入
algo(struc2vec).params({
walk_length: 3,
walk_num: 2,
k: 2,
stay_probability: 0.5,
window_size: 5,
dimension: 5,
learning_rate: 0.025,
min_learning_rate: 0.00025,
min_frequency: -1,
sub_sample_alpha: -1,
resolution: 2,
neg_num: 0,
loop_num: 2,
limit: -1
}) as results
return results
算法执行
任务回写
1. 文件回写
配置项 |
各列数据 |
---|---|
filename | _id ,embedding_result |
2. 属性回写
算法不支持属性回写。
3. 统计回写
算法无统计值。
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 各点及其图嵌入结果 | _uuid , embedding_result |
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 各点及其图嵌入结果 | _uuid , embedding_result |
实时统计
算法无统计值。