BLOG

个人博客,记录学习与生活

[KDD2017]Struc2Vec

Published Aug. 7, 2020, 11:06 p.m. by kkk

1研究主题目的跟其它几篇论文相同,不再赘述问题。

核心思路

在图的低维表示中,让图中结构相同但是距离远的点也能靠得比较近(获取结构相似性)

比如在节点是世界城市的话,上海、香港、洛杉矶这些城市虽然隔得很远,但是应该是比较接近的。也是比较符合直觉的想法,重要的是怎么来实现这样的目的。

论文步骤

  1. 确定每个节点对的结构相似性
  2. 构建带权多层图
  3. 生成节点上下文
  4. 使用语言学习模型

具体策略

确定相似性

启发理念:具有相同度(图的概念,入度、出度,由于研究的是)的两个节点结构相似,各自的邻节点也具有相同度的话,两者结构会更相似。

对于一个无向、无权图$G=(V,E)$,节点数为$n$,直径为$k^*$,$R_k(u)$是与节点$u$距离为$k$的所有节点集合,$s(S)$是节点集合$S$的按顺序排列的度序列(即把各个节点的度数进行排序之后存储在一起)。

定义两节点个相似性为: $$ \begin{align} f_k(u,v) = &f_{k-1}(u,v) + g(s(R_k(u)), s(R_k(v))),\\ & k \ge 0 and \vert R_k(u)\vert, \vert R_k(v)\vert \gt 0 \end{align} $$ 解释:将相似度按邻节点与中心节点距离分层,外层相似性等于内层相似性(等式右边第一部分)加上该层邻节点度序列的相似性(第二部分),其中第二部分非负,也就是外层相似性是大于等于内层相似性的。

对于度序列相似性$g()$, 采用的是动态时序调整(DTW),比较两个序列$A,B$,对于同等长度的序列,对应位置的元素组成一对,长度不等的序列先进行一定放缩之后再组成元素对(实际通过动态规划),对每对元素$a\in A, b\in B$,定义距离为: $$ d(a, b) = \frac{\max(a,b)}{\min(a,b)} - 1 $$ 而两序列相似性则是所有元素对距离之和,即: $$ g(A,B) = \sum_{(a,b)\in (A, B)} d(a, b) $$ 注:两者相似度越大,$g(A,B)$越小,即$f_k(u,v)$越小

构造图

接下来是构造图,将上述求得的相似性编码到图中。由于涉及到$k^\ast$层相似度,建立的图具有$(k^\ast + 1)$层,分别是$0, 1, \cdots, k^\ast$,每层是带权、无向、完全图,每两个点间权重计算公式为: $$ w_k(u,v) = e^{-f_k(u,v)}, \, k=0,\cdots, k^* $$ 注:$f_k(u,v)$有定义$w_k(u,v)$才有定义,并且成反比,结合前面的注,权重$w_k(u,v)$越大,则两节点相似度越大

另外,对于这些不同层的图,采用有向带权边进行连接对应的节点,如第$k$层的节点$u$,将与第$k+1, k-1$层的节点$u$相连,权重设置如下: $$ w(u_k, u_{k+1}) = \log(\Gamma(u)+e),\, k=0,\cdots, k^*-1 $$

$$ w(u_k, u_{k-1}) = 1, \, k=1,\cdots, k^* $$

其中$\Gamma(u)$等于在第$k$层图中,与$u$有边且权重大于该层平均权重的节点数量,描述了在该层中$u$与其它节点的相似程度。

注:在构造的多层图中,从下到上,每层相似的节点数量是越来越少的。

生成上下文序列

即采样操作,与DeepWalk同采取随机游走,在同层的图内游走的概率为$q$,向不同层的图游走的概率为$1-q$

向同层内节点$v$游走的概率为: $$ p_k(u,v) = \frac{e^{-f_k(u,v)}}{Z_k(u)} $$ $Z_k(u)$为标准化因子: $$ Z_k(u) = \sum_{u\in V, v\ne u} e^{-f_k(u,v)} $$ 该设置使得会更偏向于与自己具有更高相似性的节点,使得采样的上下文序列更有效率。有向不同层游走的概率为: $$ 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}) $$

于是,对于每个节点$u$,在第0层图内开始游走,达到最大游走长度时结束,每个节点进行重复多次游走,于是得到了节点的上下文序列。

利用语言模型

上一步获取的上下文序列,输入到Skip-gram中即可学习到图中每个节点的低维表示,即为最终结果。

该方法的复杂度和一些优化策略

计算序列相似度时使用了DTW,传统的DTW复杂度是$O(l^2)$,$l$是最大序列长度,FastDTW2可优化到$O(l)$,由于邻节点度序列长度$\vert s(R_k(u))\vert \le min(d^k_{max}, n)$,于是计算第$k$层所有相似度距离的复杂度为$O(n^2 min(d^k_{max}, n))$,最终复杂度为$O(k^*n^3)$。

优化策略1(OPT1)

减少度序列长度,即减少了DTW的计算。具体做法是记录每个值出现的次数,将多个相同的度变成一个元组,如$a=(a_0,a_1)$,$a_0,a_1$分别是度的值和出现的次数,并调整距离计算: $$ dist(a,b) = (\frac{\max(a_0,b_0)}{\min(a_0,b_0)} - 1)max(a_1, b_1) $$

优化策略2(OPT2)

减少两两相似度计算的次数,减少到$O(logn)$,由于度差别很大的节点相似度自然就很大,游走的时候选择的概率也很小,这些计算其实是多余的。将图上所有节点的度按序排列,然后进行二叉搜索,只计算每个方向上连续的$O(logn)$个节点相似度。

优化策略3(OPT3)


减少层数,改为固定数量,以适用更大的网络。

效果

在Barbell Graph中,如下图(a),分别通过Rolx,Deepwalk,node2vec,struct2vec和三种优化的struct2vec,可以看出效果很显著,是唯一能将两边蓝色节点聚合在一起的方法,证明其思路、方法的可行性,只不过实施起来计算度偏高,可能不适用大规模图,或者作为子图的处理手段。



  1. Ribeiro L F R, Saverese P H P, Figueiredo D R. struc2vec: Learning node representations from structural identity[C]//Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017: 385-394. 

  2. S Salvador and P Chan. 2004. FastDTW: Toward accurate dynamic time warping in linear time and space. InWorkshop on Min. Temp. and Seq. Data, ACM SIGKDD. 


Share this post
< Pre: [KDD2018]Airbnb Embedding Pos: [KDD2015]PTE >
1283 comments
Similar posts
Add a new comment