STRUC2VEC（图结构→向量）论文方法解读

STRUC2VEC

原文：struc2vec: Learning Node Representations from Structural Identity

捕捉节点在网络中的结构信息，将它表达成一个高维向量，需要考虑以下两个相关的性质：

1. 不同节点的表达之间的距离（也就是高维向量之间的距离）应该跟他们的结构之间的相似度高度相关。
2. 节点的这种结构表达，不应该依赖于节点或者边的属性以及它们的标签。节点的结构信息应该跟他们在网络中的位置不相关。

STRUC2VEC的基本步骤：

1. 在不同的邻域大小下，比较图中的每个节点之间的结构相似度。

   产生一个结构相似度度量的多层模型（hierarchy）。

2. 构造一个带权的多层图，网络中所有的节点都会出现在每一层，每一层都会和度量结构相似度的多层模型（hierarchy）的每一级相对应。然后带权多层图的边的权重和该边相关的节点对之间的距离成反比。

3. 使用上述的多层图生成每个节点的上下文。用带偏的 random walk 来生成多层图的节点序列。

4. 使用某种技术，通过节点序列给出的上下文来学习潜在表达

第一步：度量结构相似度

• $R_k(u)$表示了节点$u$的$k$级邻域。

• $s(S)$则表示节点的集合$S \subset V$的度数序列。

• $g(D_1,D_2)$度量了两个度数序列$D1,D2$之间的距离

• $f_k(u,v)$表示了$u,v$两节点之间，$k$级邻域（距离小于等于$k$的节点和所有它们之间的边）的结构距离。

  $f_k(u,v) = f_{k-1}(u,v) + g(s(R_k(u)), s(R_k(v)))$

  $f_{-1} = 0$

  上述定义表达的是一个递归的过程，把问题转换成了如何定义两个节点集合之间的距离，也就是$g(\cdot)$该如何计算。

• 文章使用了 Dynamic Time Warping(DTW)来度量两个度数序列之间的距离。

  序列 A 和 B，其中，$a \in A$，$b \in B$，那么$a, b$之间的距离定义为：$d(a, b) = \frac{max(a, b)}{min(a, b)} - 1$，当$a=b$时，他们的距离也就是 0。然后两个序列之间的距离，也就是所有$a,b$组合之间的距离和。

  其他方案也可以用在该框架下，感觉这里的时间复杂度相对较高，可以有替换的方案。VIGOR 论文中提到的方法？

第二步：构造上下文图（context graph）

• 构造一个带权的多层图$M$。层数由$0到k^*$，其中$k^*$表示的是图的直径，也就是原始图$G=(V,E)$中节点之间的最远距离。

• 第$k$层图表达的是节点之间$k$级邻域的相似度度量。

• 故而$M$的每一层都是一个完全图，都会有$n=|V|$个节点，边的数量是$n(n-1)$，边的权重的定义：

  $$w_k(u,v) = e^{-f_k(u,v)},k=0,…,k^*$$

  当然，只有$f_k$定义了，边才能被定义。

• 因为$f_k(u,v)$最小是 0，那么边的权重$w_k(u,v)$的取值范围是$(0,1]$，当等于 1 时，代表两个节点结构相同。

• 不同层级之间，通过有向边连接，在$k$层的每个节点都会跟$k-1$层和$k+1$层的相同节点用有向边连接，边的权重定义：

  $$w(u_k,u_{k+1})=log(\Gamma_k(u)+e), k=0,…,k^∗−1$$

  $$w(u_k,u_{k-1})=1,k=1,…,k^∗$$

  • 其中$\Gamma_k(u)$代表了指向节点$u$的权重大于$k$层图平均权重的边的数量：$\Gamma_k(u)=\sum_{v \in V} \mathbb{1}(w_k(u,v) > \overline{w_k})$，也就是度量了该节点$u$和第$k$层其他节点之间的相似度。
  • 而$\overline{w_k} = \sum_{(u,v)\in \begin{pmatrix} V \\ 2 \\ \end{pmatrix} }w_k(u,v)/\begin{pmatrix} n \\ 2 \end{pmatrix}$

第三步：生成节点的上下文

利用$M$生成节点的上下文的过程：带偏的随机游走（biased random walk）。

• 首先需要决定，随机游走的这一步，是留在当前层还是换层

• 有一定概率$q$，留在当前层，假设留在当前层，那么从节点$u$走到$v$的概率（权重越大，概率越高，也就是更容易走到相似节点上）：

  p_k(u,v) = \frac{e^{-f_k(u,v)}}{Z_k(u)}$$，$$Z_k(u)=\sum_{v \in V, v ≠ u} e^{-f_k*(u,v)}

• 假设在另一半概率上$1-q$，换层，换到$k+1$的概率定义：

  $$p_k(u_k, u_{k+1}) = \frac{w(u_k, u_{k+1})}{(u_k, u_{k+1})+(u_k, u_{k-1})}$$

  而换到$k-1$层的概率：

  $$p_k(u_k, u_{k-1}) = 1 - p_k(u_k, u_{k+1})$$

• 当节点走到$k+1$层时，产生的 context 可能只是前$k$层产生的 context 的一个子集，所以这种情况下，并不没有贡献

• 每次随机游走从第 0 层开始，游走步数都是一个固定的，较小的值，然后随机游走会在同一个节点上重复多次，产生多个独立的游走

第四步：学习语言模型

通过 word embedding 的方法，对第三步生成的随机游走结果，生成高维向量。

文章使用了Skip-Gram[^1]。

[^1]: Mikolov, Tomas, et al. "Efficient estimation of word representations in vector space." arXiv preprint arXiv:1301.3781 (2013).