0 背景
之前的node embedding方式，都是基于近邻关系，但是有些节点没有近邻，也有结构相似性。如图中的u、v节点。
struc2vec算法适用于捕获结构相似性。
1 相似度（距离）计算
1.1 公式
f k ( u , v ) = f k − 1 ( u , v ) + g ( s ( R k ( u ) , s R k ( v ) ) ) , k ≥ 0 a n d ∣ R k ( u ) ∣ , ∣ R k ( v ) ∣ > 0 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 fk(u,v)=fk−1(u,v)+g(s(Rk(u),sRk(v))),k≥0 and ∣Rk(u)∣,∣Rk(v)∣>0
f k ( u , v ) 表示 u 、 v 节点的 k 跳邻居相似性； R k ( u ) 表示节点 u 的 k 跳邻居节点集合； S ( s ) 表示集合 s 度的有序集合； g ( D 1 , D 2 ) 是度量两个序列的函数，比较常用的有 D T W 算法 \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} fk(u,v) 表示u、v节点的k跳邻居相似性；Rk(u) 表示节点u的k跳邻居节点集合；S(s) 表示集合s度的有序集合；g(D1,D2) 是度量两个序列的函数，比较常用的有DTW算法
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)表示跨层（不同跳）节点，计算公式分别为：
w
k
(
a
,
b
)
=
e
−
f
k
(
a
,
b
)
w
(
u
k
,
u
k
−
1
)
=
1
w
(
u
k
,
u
k
+
1
)
=
l
o
g
(
Γ
k
(
u
)
+
e
)
其中
:
Γ
k
(
u
)
=
∑
v
∈
V
1
(
w
k
(
u
,
v
)
>
w
ˉ
k
)
举个栗子
:
Γ
0
(
e
)
=
w
0
(
e
,
a
)
,
w
0
(
e
,
b
)
,
w
0
(
e
,
c
)
,
w
0
(
e
,
d
)
>
w
ˉ
k
\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}
wk(a,b)=e−fk(a,b)w(uk,uk−1)=1w(uk,uk+1)=log(Γk(u)+e)其中:Γk(u)=v∈V∑1(wk(u,v)>wˉk)举个栗子:Γ0(e)=w0(e,a),w0(e,b),w0(e,c),w0(e,d)>wˉk
4 定点采样序列
下一次采样时，有p的概率在本层游走，有1-p的概率在上下游切换。
在本层游走：
p
k
(
u
,
v
)
=
e
−
f
k
(
u
,
v
)
Z
k
(
u
)
p_k(u,v) = \frac{e^{-f_k(u,v)}}{Z_k(u)}
pk(u,v)=Zk(u)e−fk(u,v)
其中，Z_k的计算方式为：
Z
k
(
u
)
=
∑
v
∈
V
,
v
≠
u
e
−
f
k
(
u
,
v
)
Z_k(u) = \sum_{v∈V,v≠u}e^{-f_k(u,v)}
Zk(u)=v∈V,v=u∑e−fk(u,v)
上下层切换：
p
k
(
u
k
,
u
k
+
1
)
=
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
)
不难发现前往下一层的概率更大
\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}
pk(uk,uk+1)=w(uk,uk+1)+w(uk,uk−1)w(uk,uk+1)pk(uk,uk−1)=1−pk(uk,uk+1)不难发现前往下一层的概率更大
5 使用skip-gram生成embedding
在采用 4定点采样序列中 游走的方法得到节点序列后，使用skip-gram方法生成embedding。
Word2Vec提供了两种模型架构：CBOW 和 Skip-gram。
- CBOW模型：通过上下文词预测目标词。
- Skip-gram模型：通过目标词预测上下文词。
Skip-gram模型在处理低频词时表现得更好，因此被广泛应用于各种自然语言处理任务。
6 实验效果
struc2vec算法在捕获结构相似性上有很好的效果。
适用性分析：适用于节点分类中，结构标识比邻居标识更重要时。
