struct2vec笔记

2022-03-07

struct2vec

kdd2017

struc2vec使用层次结构在不同尺度上度量节点相似性，并构建一个多层图来编码结构相似性并为节点生成结构上下文。大多数真实网络中的许多节点特征都表现出很强的同质性，如果隔得比较远的两个节点有相似的结构的话，用deepwalk和node2vec这种表示学习方法是不能够刻画出他们的结构相似性的。

struct2vec的思想：

评估节点之间的独立于节点和边缘的结构相似性以及它们在网络中的位置。将考虑具有相似的局部结构的两个节点，独立于网络的位置以及节点的在邻居中的标签。我们的方法也不需要网络连接，并且在不同连接的组件中识别结构相似的节点。
在层次结构的底部，节点之间的结构一致性只取决于他们的度，在层次结构的顶部，相似性取决于整个网络（从节点的角度来看）
为节点生成随机上下文，节点是通过遍历加权随机游走历多层图观察到的结构相似的节点序列（而不是原来的网络）。使用随机采样的方式来获取上下文，如果两个节点经常出现在相同的上下文中，表明他们有相类似的结构特征。

构建显式捕获结构身份的表示是一个相对正交的问题，它没有得到多少的关注。

好的反应节点的结构特征的方法必须满足以下两个特征：

嵌入空间的距离得能够反映出节点之间的结构相似性，两个局部拓扑结构相似的节点在嵌入空间的距离应该相近。
节点的结构相似性不依赖于节点或者边的属性甚至是节点的标签信息。

strcut2vec包含以下四个步骤：

对于不同大小的邻域，确定图中每个节点对之间的结构相似性。这在节点之间的结构相似度度量中引入了一个层次结构，提供更多的信息来评估层次结构的每个层次的结构相似性。
构造一个加权多层图，其中网络中的所有节点都出现在每一层中，每一层对应于衡量结构相似度的层次水平。此外，每一层内每个节点对之间的边权值与其结构相似性成反比。
使用多层图可以为每个节点生成上下文。特别地，利用多层图上的有偏随机游走来生成节点序列。这些序列很可能包括在结构上更相似的节点。
应用一种技术，从由节点序列给出的上下文中学习潜在的表示。

1. 测定结构相似性

如果两个节点具有相同的度的话，他们的结构是相似的，但是如果邻居也有相同的度的话，他们结构上就更相似。

$G=(V,E)$表示无向无权网络，$n=|V|$表示的是节点个数，$K^*$表示直径。$R_k(u)$表示的是G中距离（跳数）的节点集正好是k≥0。$R_1(u)$表示的就是节点u的邻居。$s(S)$对某个节点集合V中的节点按照度的大小从小到大顺序排序后的序列。

$f_k(u,v)$为考虑两个节点的k跳邻居时（小于等于k跳的所有邻居均要考虑），两个节点的结构距离：

$f_{k}(u, v)=f_{k-1}(u, v)+g\left(s\left(R_{k}(u)\right), s\left(R_{k}(v)\right)\right)$ $k \geq 0$ and $\left|R_{k}(u)\right|,\left|R_{k}(v)\right|>0$

其中$g(D_1,D_2)≥0$测量有序度序列D1和D2之间的距离并且$f_{-1}=0$。$f_k(u,v)$是一个单调不降的函数，并且这个函数只有在两个节点同时存在k跳邻居时才有定义。本文使用的时DTW的方法来处理两个序列之间的距离。DTW找到两个序列A和序列B之间的最佳比对，给定距离方程$d(a,b)$，DTW匹配每个$a∈A$和$b∈B$，从而使匹配元素之间的距离之和最小化。这里处理的A和B的序列元素表示度，所以采用方程：$d(a, b)=\frac{\max (a, b)}{\min (a, b)}-1$，如果a=b那么$d(a,b)=0$

2. 构造上下文图

上一步构造了一个多层加权图来编码节点之间的结构相似性。这一步中，根据这些信息构建一个多层的带权重网络M。其中M的第k层是由节点的k跳邻居所定义的。对于每一层，$k=0,...,k^*$，是一个带权重的完全图，有$n(n-1)/2$条边，每条边的权值定义为：$w_{k}(u, v)=e^{-f_{k}(u, v)}, \quad k=0, \ldots, k^{*}$

这个式子的意思是当任意两个节点的结构相似性越大，其权重越大。

使用有向边连接层与层，对于第k层的任意节点$u_k$，都有有向边$(u_k,u_{k-1})$和$(u_k,u_{k+1})$，权重分别为：

$w\left(u_{k}, u_{k+1}\right)=\log \left(\Gamma_{k}(u)+e\right), \quad k=0, \ldots, k-1$ $w\left(u_{k}, u_{k-1}\right)=1, \quad k=1, \ldots, k$

其中$\Gamma_k(u)$表示第k层中，所有指向u的边中权重大于该层平均权重的数量。

$\Gamma_{k}(u)=\sum_{v \in V} 1\left(w_{k}(u, v)>\overline{w_{k}}\right)$

$ =_{(u, v) ( \[\begin{array}{l}V \\ 2\end{array}\] )} w_{k}(u, v) /( \[\begin{array}{l}n \\ 2\end{array}\]

)$表示所有边权重的平均值，$k(u)$实际上表示了第k层中，有多少是与节点u相似的，如果u与很多节点都相似，说明此时一定处于低层次，考虑的信息太少了，那么$k(u)$将会很大，也就是$w(u_k,u{k+1})>w(u_k,u{k-1})$，对于这种情况，就不适合将本层的节点作为上下文了，应该考虑跳到更高的层去找上下文，所以去更高层的权重更大。

M有$nk^*$个节点，最多有$k^{*}\left(\begin{array}{l}n \\ 2\end{array}\right)+2n(k^*-1)$权重边。

3. 为节点生成上下文

上一步讲的多层网络M的构建是为了寻找合适的上下文，而寻找上下文的方式与deepwalk一样是采用随机游走的方式。M在完全没有使用标签信息的情况下捕获在G中节点的结构相似性。特别的，考虑一个有偏的随机游走，在M周围移动，根据M的权重来随机选择。在每一步之前，随机行走首先决定它将改变层还是在当前层上行走（随概率q>0计算，随机游走保持在当前层中）。

考虑到它将保留在当前的一层中，在第k层中，从节点u步进到节点v的概率为：

$p_{k}(u, v)=\frac{e^{-f_{k}(u, v)}}{Z_{k}(u)}$

分母是归一化因子$Z_{k}(u)=\sum_{v \in V \atop v \neq u} e^{-f_{k}(u, v)}$

请注意，随机游走将更倾向于转移到在结构上更类似于当前顶点的节点上，从而避免与它具有非常不接近的结构相似性的节点。因此，节点的u∈V的上下文很可能具有结构相似的节点，独立于它们的标签和在原始网络G中的位置。

如果跳层，同样分为两个方向，概率也跟边的权重有关，

$p_{k}\left(u_{k}, u_{k+1}\right)=\frac{w\left(u_{k}, u_{k+1}\right)}{w\left(u_{k}, u_{k+1}\right)+w\left(u_{k}, u_{k-1}\right)}$ $p_{k}\left(u_{k}, u_{k-1}\right)=1-p_{k}\left(u_{k}, u_{k+1}\right)$

请注意，每次游走在一个层中行走时，它都将当前顶点作为其上下文的一部分，独立于该层。，一个顶点u在第k层中可能有一个给定的上下文（由该层的结构相似性决定），但是在k+1层有这个上下文的子集，因为结构上的相似性不能随着我们移动到更高的层次而增加。是一个跨层的层次上下文的概念，它是所提出的方法的一个基本方面。

最后，对于每个节点u∈V，我们在第0层中对应的顶点开始随机游走。

注意到当层数越高，因为考虑的邻域更广，节点间的结构相似性计算越苛刻，因此在底层计算出两个节点结构相似的，在高层则不一定相似，并且高层很多节点之间的 $f_k(u,v)$ 可能根本没有定义。这就导致如果随机游走在某个节点u跳到了更高的层，那么在随机游走的序列中，其左边的节点是k层，而右边的节点是k+1层的。而左右两边的取值范围是不同的。换言之，某个节点可能会出现在左边，但不会出现在右边，因为虽然它跟中间那个节点u在k层是相似的，但在k+1层可能无定义或者 $f_{k+1}(u,v)$ 太大导致随机游走在k=1层走到这个节点的概率几乎可以忽略。