当前位置：首页 > news >正文

图神经网络_图嵌入_Struc2Vec

news 来源：原创 2025/5/16 11:27:12

0 背景

之前的node embedding方式，都是基于近邻关系，但是有些节点没有近邻，也有结构相似性。如图中的u、v节点。
struc2vec算法适用于捕获结构相似性。
在这里插入图片描述

1 相似度（距离）计算

1.1 公式

$f_k(u,v) = f_{k-1}(u,v)+g(s(R_k(u),sR_k(v))),k\ge 0 \space and \space |R_k(u)|,|R_k(v)|>0$

$\begin{aligned} & f_k(u,v) \ 表示u、v节点的k跳邻居相似性； \\ & R_k(u) \ 表示节点u的k跳邻居节点集合； \\ & S(s) \ 表示集合s度的有序集合；\\ & g(D_1,D_2) \ 是度量两个序列的函数，比较常用的有DTW算法 \end{aligned}$

1.2 示例

在这里插入图片描述

其中距离函数 g 的计算方法为：

2 DTW动态时间规整算法

2.1 应用

DTW最初用于识别语音的相似性。

2.2 举个栗子

我们用数字表示音调高低。例如：某个单词发音的音调为1-3-2-4。现在有两个人说这个单词，一个人在前半部分拖长，其发音为1-1-3-3-2-4；另一个人在后半部分拖长，其发音为1-3-2-2-4-4。

因为两个序列代表同一个单词，so we hope 1-1-3-3-2-4 和 1-3-2-2-4-4 两个序列的距离距离小，相似度高，识别为同一单词的概率大。

2.3 传统算法——欧氏距离

S = |A(1)-B(1)| + |A(2)-B(2)| + |A(3)-B(3)| + |A(4)-B(4)| + |A(5)-B(5)| + |A(6)-B(6)|
= |1-1| + |1-3| + |3-2| + |3-2| + |2-4| + |4-4|
= 6

在这里插入图片描述

2.4 DTW动态时间规整算法

核心思想：允许序列的点与另一序列的多个连续的点相对应。

如下图：B(1)与A(1)、A(2)相对应，B(2)与A(3)、A(4)相对应，A(5)与B(3)、B(4)相对应，A(6)与B(5)、B(6)相对应。

在这里插入图片描述

S = |A(1)-B(1)| + |A(2)-B(1)| + |A(3)-B(2)| + |A(4)-B(2)| + |A(5)-B(3)| + |A(5)-B(4)| + |A(6)-B(5)| + |A(6)-B(6)| 
= |1-1| + |1-1| + |3-3| + |3-3| + |2-2| + |2-2| + |4-4| + |4-4|
= 0

2.5 图示

在这里插入图片描述

灰色线表示传统的欧氏距离
红色线表示DTW算法距离

2.6 步骤

计算两个序列各个点之间的距离矩阵。
寻找一条从矩阵左上角到右下角的路径，使得路径上的元素和最小。

2.7 特点

非线性对齐：DTW 允许序列在时间轴上进行不同速率的对齐，能够处理局部时间伸缩。
适应性强：DTW 不要求输入序列长度相同，且能够容忍输入序列的平移、缩放和局部错位。
计算复杂度：DTW 的计算复杂度通常为 (O(mn))，其中 (m) 和 (n) 分别是两条序列的长度。

2.8 应用

语音识别：DTW 可以通过对齐不同的发音序列来识别用户的语音。
手写识别：DTW 可用于比较手写笔迹和已知字符模式之间的相似度。
金融分析：DTW 可用于识别股票价格或其他金融数据的时间序列模式。
生物信息学：DTW 可用于比较基因序列的相似性，尤其是在基因组学中用于比较不同个体的基因表达模式。

3 多层带权重图

在这里插入图片描述

其中：w_0(a,b)、w_1(a,b) 分别表示0、1层（跳）a、b两节点权重；w(e_0,e_1)表示跨层（不同跳）节点，计算公式分别为：
$\begin{aligned} & w_k(a,b) = e^{-f_k(a,b)} \\ & w(u_k,u_{k-1}) = 1 \\ & w(u_k,u_{k+1}) = log(\Gamma_k(u)+e) \\ & 其中: \Gamma_k(u) = \sum_{v∈V}1(w_k(u,v)>\bar w_k) \\ & 举个栗子: \Gamma_0(e) = w_0(e,a),w_0(e,b),w_0(e,c),w_0(e,d)>\bar w_k \end{aligned}$

4 定点采样序列

在这里插入图片描述

下一次采样时，有p的概率在本层游走，有1-p的概率在上下游切换。

在本层游走：
$p_k(u,v) = \frac{e^{-f_k(u,v)}}{Z_k(u)}$
其中，Z_k的计算方式为：
$Z_k(u) = \sum_{v∈V,v≠u}e^{-f_k(u,v)}$
上下层切换：
$\begin{aligned} & p_k(u_k,u_{k+1}) = \frac{w(u_k,u_{k+1})}{w(u_k,u_{k+1})+w(u_k,u_{k-1})} \\ & p_k(u_k,u_{k-1}) = 1- p_k(u_k,u_{k+1}) \\ & \text{不难发现前往下一层的概率更大} \end{aligned}$

5 使用skip-gram生成embedding

在采用 4定点采样序列中游走的方法得到节点序列后，使用skip-gram方法生成embedding。

Word2Vec提供了两种模型架构：CBOW 和 Skip-gram。

CBOW模型：通过上下文词预测目标词。
Skip-gram模型：通过目标词预测上下文词。

Skip-gram模型在处理低频词时表现得更好，因此被广泛应用于各种自然语言处理任务。

6 实验效果

在这里插入图片描述

struc2vec算法在捕获结构相似性上有很好的效果。

适用性分析：适用于节点分类中，结构标识比邻居标识更重要时。

0 背景

1 相似度（距离）计算

1.1 公式

1.2 示例

2 DTW动态时间规整算法

2.1 应用

2.2 举个栗子

2.3 传统算法——欧氏距离

2.4 DTW动态时间规整算法

2.5 图示

2.6 步骤

2.7 特点

2.8 应用

3 多层带权重图

4 定点采样序列

5 使用skip-gram生成embedding

6 实验效果

相关文章：