论文阅读|struc2vec: Learning Node Representations from Structural Identity
文章目录
Abstract
struc2vec 使用层次结构来衡量不同尺度的节点相似性，并构建一个多层图来编码结构相似性并为节点生成结构上下文。
Introduction
确定节点结构身份的最常见的实用方法是基于距离或递归。 在前者中，利用节点邻域的距离函数来测量所有节点对之间的距离，然后执行聚类或匹配以将节点放入等效类 。 后者中，构建关于相邻节点的递归，然后迭代展开直到收敛，最终值用于确定等效类 。
领域相似的结点具有结构相似性，但距离比较远的这样的结点就不具有相似性。如上图结点u和v。
DeepWalk和Node2vec在结构等效性任务中表现很差，因为现在的 网络都具有很强的同质性。
struc2vec的具体过程如下：
- 独立于节点和边属性以及它们在网络中的位置来评估节点之间的结构相似性。 因此，具有相似局部结构的两个节点将被视为独立于其邻域中的网络位置和节点标签。 我们的方法也不需要连接网络，并在不同的连接组件中识别结构相似的节点。
- 建立层次结构来衡量结构相似性，允许对结构相似性的含义逐渐提出更严格的概念。 特别是在层次结构的最底层，节点之间的结构相似度仅取决于它们的度数，而在层次结构的顶部，相似性取决于整个网络（从节点的角度来看）。
- 为节点生成随机上下文，这些节点是结构相似节点的序列，通过遍历多层图（而不是原始网络）的加权随机游走观察到。 因此，经常出现在相似上下文中的两个节点可能具有相似的结构。
对比算法：DeepWalk，Node2vec，RolX。
Related Work
DeepWalk：若两个节点的距离（即跳数）大于Skip-Gram的窗口大小，这种结构相似就被忽略了。
sub-graph2vec：使用邻居节点生成上下文，结构上非常相似（但未通过测试）且具有非重叠邻居的两个节点在空间上可能并不接近。
RolX：···
Strcu2vec
步骤：
- 确定不同邻域大小的图中每个顶点对之间的结构相似性。 这在节点之间结构相似性的度量中引入了层次结构，提供了更多信息来评估层次结构的每个级别的结构相似性。
- 构建一个加权的多层图，其中网络中的所有节点都存在于每一层中，每一层对应于衡量结构相似性的层次结构的一个级别。此外，每层内每个节点对之间的边权重与其结构相似性成反比。
- 使用多层图为每个节点生成上下文。特别是，使用有偏随机游走来生成节点序列。这些序列可能包括结构更相似的节点。
- 应用一种技术从节点序列给定的上下文中学习潜在表示，例如，SkipGram。
Measuring structural similarity
G=（V，E）， R k ( u ) 表 示 距 离 结 点 u 为 k 的 结 点 集 R_k(u)表示距离结点u为k的结点集 Rk?(u)表示距离结点u为k的结点集
s ( S ) 表 示 结 点 集 合 S � V 的 有 序 度 数 序 列 s(S)表示结点集合S�V的有序度数序列 s(S)表示结点集合S�V的有序度数序列
通过比较节点u和v间距离为k的环路有序度序列，可以施加层次结构来测量结构相似性。特别地，当考虑它们的 k 跳邻域（距离小于或等于 k 的所有节点以及它们之间的所有边）时，让
f
k
(
u
,
v
)
f_k(u,v)
fk?(u,v)表示 u 和 v 之间的结构距离。 特别地，定义：
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)),s(R_k(v))),k \geq\;0 \quad and |R_k(u)|,|R_k(v)| \geq\ 0;
fk?(u,v)=fk?1?(u,v)+g(s(Rk?(u)),s(Rk?(v))),k≥0and∣Rk?(u)∣,∣Rk?(v)∣≥?0;
其中
g
(
D
1
,
D
2
)
≥
??
0
g(D_1,D_2) \geq\; 0
g(D1?,D2?)≥0表示度数序列
D
1
,
D
2
D_1,D_2
D1?,D2?之间的距离，且
f
?
1
=
0
f_{-1}=0
f?1?=0，
f
k
(
u
,
v
)
f_k(u,v)
fk?(u,v)是递增的，当且仅当节点u和节点v之间距离不小于k。若u和v之间是同构的，并且u映射到v，则
f
k
?
1
(
u
,
v
)
=
0
f_{k-1}(u,v)=0
fk?1?(u,v)=0。
采用DTW（Dynamic Time Warping）来测量两个有序度序列之间的距离，它可以很好地处理不同大小的序列并且松散地比较序列模式。使用它的原因是它惩罚了两个节点的度数都比较小时两者的差异。给定序列元素的距离函数
d
(
a
,
b
)
d(a,b)
d(a,b)，DTW匹配每个元素
a
∈
A
,
b
∈
B
a∈A,b∈B
a∈A,b∈B，使得匹配元素之间的距离总和最小化。采用以下距离函数：
d
(
a
,
b
)
=
m
a
x
(
a
,
b
)
m
i
n
(
a
,
b
)
?
1
d(a,b)=\frac{max(a,b)}{min(a,b)}-1
d(a,b)=min(a,b)max(a,b)??1
当a=b时，则
d
(
a
,
b
)
=
0
d(a,b)=0
d(a,b)=0。
Constructing the context graph
构建层次带权图
k
?
k^*
k?表示网络的直径。每层
k
=
0
,
.
.
.
,
k
?
k=0,...,k^*
k=0,...,k?由一个带节点集V的加权无向图形成，一层中两个节点之间的边权重由下式给出：
w
k
(
u
,
v
)
=
e
?
f
k
(
u
,
v
)
,
k
=
0
,
.
.
.
,
k
?
w_k(u,v)=e^{-f_k(u,v)},k=0,...,k^*
wk?(u,v)=e?fk?(u,v),k=0,...,k?
第k层的节点u会连接到第k+1层和第k-1层。层间的边权重如下：
w
(
u
k
,
u
k
+
1
)
=
l
o
g
(
Γ
k
(
u
)
+
e
)
,
k
=
0
,
.
.
.
,
k
?
?
1
w(u_k,u_{k+1})=log(\Gamma_k(u)+e),k=0,...,k^*-1
w(uk?,uk+1?)=log(Γk?(u)+e),k=0,...,k??1
w ( u k , u k ? 1 ) = 1 , k = 1 , . . . , k ? w(u_k,u_{k-1})=1,k=1,...,k^* w(uk?,uk?1?)=1,k=1,...,k?
其中
Γ
k
(
u
)
\Gamma_k(u)
Γk?(u)是与u相关且权重大于第k层中完整的平均边权重的边数，如下
Γ
k
(
u
)
=
∑
v
∈
V
1
(
w
k
(
u
,
v
)
>
w
k
￣
)
\Gamma_k(u)=\sum_{v∈V}1(w_k(u,v)>\overline{w_k})
Γk?(u)=v∈V∑?1(wk?(u,v)>wk??)
其中
(
w
k
)
￣
=
∑
u
,
v
∈
(
V
2
)
w
k
(
u
,
v
)
/
(
V
2
)
\overline{(w_k)}=\sum_{u,v∈ \begin{pmatrix}V \\ 2\end{pmatrix}} w_k(u,v)/ \begin{pmatrix} V \\ 2 \end{pmatrix}
(wk?)?=∑u,v∈(V2?)?wk?(u,v)/(V2?)。
Γ k ( u ) \Gamma_k(u) Γk?(u)度量了节点u与第k层其他节点的相似性。若当前层中有许多相似的节点，那么它应该更改层以获得更细化的上下文，通过向上移动一层，相似节点的数量只会减少，最后，log函数只是减少了给定层中与u相似的节点的数量。
Generating context for nodes
采样获取顶点序列
请注意，M 完全不使用标签信息来捕获 G 中节点之间结构相似性的结构。 与之前的工作一样，struct2vec 使用随机游走生成节点序列来确定给定节点的上下文。 特别是，我们考虑了一个有偏随机游走，它在 M 周围移动，根据 M 的权重做出随机选择。在每一步之前，随机游走首先决定是改变层还是在当前层上游走（概率 q > 0 随机游走留在当前层）。
鉴于它将留在当前层，在第k层从节点u游走至节点k的概率为
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
(
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)是第k层中顶点u的归一化因子。
随机游走以概率 1 -q 决定改变层，并以与边权重成正比的概率移动到第 k + 1 层或第 k - 1 层（层允许）中的相应节点。
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
)
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})
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?)
注意每次游走至一个层时，它都会将当前顶点作为其上下文的一部分，独立于该层。因此，顶点 u 可能在第 k 层具有给定的上下文（由该层的结构相似性确定），但在第 k + 1 层具有该上下文的子集，因为随着我们移动到更高层，结构相似性不会增加。 跨层的分层上下文的概念是所提出方法的基本方面。
最后，对于每个节点 u ∈ V ，在第 0 层对应的顶点开始随机游走。随机游走有固定且相对较短的长度（步数），并且该过程重复一定次数，从而产生多个独立的游走（即节点u 的多个上下文）。
Learning a language model
语言模型学习 Skip-Gram
Hierarchical Softmax（分层Softmax），使用二元分类器树计算条件符号概率。
对于每个节点
v
j
∈
V
v_j∈V
vj?∈V,分层Softmax在分类树中分配一个特定的路径，由一组树结点
n
(
v
j
,
1
)
,
n
(
v
j
,
2
)
,
.
.
.
,
n
(
v
j
,
h
)
，
其
中
n
(
v
j
,
h
)
=
v
j
n(v_j,1),n(v_j,2),...,n(v_j,h)，其中n(v_j,h)=v_j
n(vj?,1),n(vj?,2),...,n(vj?,h)，其中n(vj?,h)=vj?。在这些设置中，我们有
P
(
v
j
∣
v
i
)
=
∏
k
=
1
h
C
(
n
(
v
j
,
k
)
,
v
i
)
P(v_j|v_i)=\prod _{k=1}^hC(n(v_j,k),v_i)
P(vj?∣vi?)=k=1∏h?C(n(vj?,k),vi?)
其中C是存在于树中每个节点的二元分类器。请注意，由于 Hierarchical Sofmax 在二叉树上运行，我们有$ h = O(log |V|)$。
Complexity and optimizations
O ( k ? n 3 ) O(k*n^3) O(k?n3)
优化如下：
减少度序列的长度（OPT1）。通过度数频次统计来压缩有序度数序列。令
A
‘
和
B
‘
A^`和B`
A‘和B‘分别表示A和B的压缩度序列。由于
A
′
和
B
′
的
元
素
是
元
组
，
按
如
下
方
式
调
整
D
T
W
成
对
距
离
函
数
。
A'和B'的元素是元组，按如下方式调整DTW成对距离函数。
A′和B′的元素是元组，按如下方式调整DTW成对距离函数。
d
i
s
t
(
a
,
b
)
=
(
m
a
x
(
a
0
,
b
0
)
m
i
n
(
a
0
,
b
0
)
?
1
)
m
a
x
(
a
1
,
b
1
)
dist(a,b) = (\frac{max(a_0,b_0)}{min(a_0,b_0)} - 1)max(a_1,b_1)
dist(a,b)=(min(a0?,b0?)max(a0?,b0?)??1)max(a1?,b1?)
其中
a
=
(
a
0
,
a
1
)
和
b
=
(
b
0
,
b
1
)
a=(a_0,a_1)和b=(b_0,b_1)
a=(a0?,a1?)和b=(b0?,b1?)分别是
A
0
和
B
0
A_0和B_0
A0?和B0?中的元组；
a
0
,
b
0
a_0,b_0
a0?,b0?是度数；
a
1
和
b
1
a_1和b_1
a1?和b1?是出现的次数。
减少成对相似度计算的次数（OPT2）。
对于每个级别k，将每个节点的成对相似对计算的数量限制为 O ( l o g n ) O(logn) O(logn)。令 J u 表 示 为 M 中 将 成 为 节 点 u 的 邻 居 节 点 集 J_u表示为M中将成为节点u的邻居节点集 Ju?表示为M中将成为节点u的邻居节点集，这对于每个级别都是相同的。 J u J_u Ju?应该具有在结构上与u最相似的节点。为了确定 J u J_u Ju?，选取度数与u最相似的节点。可以通过对网络中所有节点的有序度数序列（对于节点u的度数）执行二分搜索，并在搜索完成后在每个方向上取 l o g n logn logn个连续节点，来进行有效计算。计算所有节点的 J u J_u Ju?具有复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。
减少层数（OPT3）
评估两个节点之间结构相似性的重要性随着k的增大而降低。当 k 接近 k ? k^* k? 时，环的度数序列的长度变得相对较短，因此 f k ( u , v ) f_k (u,v) fk?(u,v) 与$f_{k-1}(u,v) $没有太大区别。 因此，我们将 M 中的层数限制为一个固定常数 k ‘ < k ? k^` < k^* k‘<k? ，捕获用于评估结构相似性的最重要的层。 这显然降低了构建 M 的计算和内存要求。
Experimental Evaluation
B ( h , k ) B(h,k) B(h,k)表示为 ( h , k ) (h,k) (h,k)杠铃图，它们都由两个完整的图 K 1 , K 2 K_1,K_2 K1?,K2?（每个都含有h个节点）组成，且由长度为k的路径图P连接。两个节点 b 1 ∈ V ( K 1 ) 和 b 2 ∈ V ( k 2 ) b_1∈V(K_1)和b_2∈V(k_2) b1?∈V(K1?)和b2?∈V(k2?)作为桥梁。使用 p 1 , . . . , p 2 表 示 V ( P ) p_1,...,p_2表示V(P) p1?,...,p2?表示V(P)， 连 接 b 1 和 p 1 , b 2 和 p k 连接b_1和p_1,b_2和p_k 连接b1?和p1?,b2?和pk?，从而连接三个图。
图表示学习结果如下（着色相同的节点即是算法表示学习得到的具有相似结构的节点）：
构建关于karate_club的镜像图，从而验证各算法的节点相似度，并对相应节点进行匹配。
实验数据集：karate_club、Brazilian air-trafc network、American air-trafc network、European air-trafc network
对比算法：deepwalk，node2vec，struc2vec（opt1|opt2|opt3）
评估指标：单标签准确度（0/1，准确率）
参考文献
论文：struc2vec: Learning Node Representations from Structural Identity