struc2vec - Learning Node Representations from Structural Identity

众里寻他千百度

概述

struc2vec是KDD 2017年的关于图表示学习的一个模型。在图表示学习中,节点表示的学习主要依赖于临近性与同构性,前者是指距离越近的节点得到的表示也应该相互靠近,后者是指结构相似的节点得到的表示也应该相互接近。与DeepWalknode2vec这类通过模仿DFS/BFS来权衡同构性/邻近性不同,struc2vec试图通过直接定量地挖掘图中节点的结构来得到更多保存图中“同构性”的表示。

模型概览

为了让模型尽可能多地保存节点之间结构信息,作者认为应当在设计模型的过程中着重注意以下两点:

  1. 表示之间的距离应该与节点结构相似性高度相关;
  2. 表示的学习不应当依赖于任何节点或者边的属性,包括节点的类别。

按照以上两点理念,作者将struc2vec设计为下列四大步骤:

  1. 定量描述图中节点的结构相似性,同时由考虑“邻域”的大小自然地划分为不同的层次;
  2. 由第一步中得到的信息构造多层加权图,图中每一层与第一步中的不同“邻域”形成的层次相对应;
  3. 通过第二步中构造的多层加权图,随机游走得到每一节点的上下文信息;
  4. Skip-Gram模型对游走序列进行学习,得到节点表示。

由此可知,上述步骤中较为独特和关键的为第一、二步,详述见下。

结构相似性

struc2vec中结构相似性的目的是不依赖于图中节点和边的属性来定量描述节点的结构相似性。直观地说,如果两个节点的度相近则他们之间的结构相似度也应该高,而如果这两个节点的邻居节点的度也是相同,则他们之间的结构相似度也应该更高。
记$$G=(V, E)$$表示无向无权图,其中$$V$$表示节点集合,$$E$$表示边集合,$$n=\vert V\vert$$表示图的节点数,$$k^*$$表示图的直径。记$$R_k(u)$$表示图$$G$$中距离节点$$u$$为$$k$$的节点集合,其中$$k\ge0$$。记$$\mathrm{s}(S)$$表示节点集合$$S\subset V$$的有序度序列。
进而,我们就可以在上述概念上定义结构相似性。具体来说,定义函数$$\mathrm{f}_k(u, v)$$,该函数用来衡量节点$$u$$和$$v$$之间的结构相似性,该结构相似性考虑的范围为$$k$$,即与节点$$u$$或$$v$$距离小于等于$$k$$的节点才会被考虑。函数$$\mathrm{f}_k(u, v)$$定义如下:
$$
\mathrm{f}k(u, v) = \mathrm{f}{k-1}(u, v) + \mathrm{g}(\mathrm{s}(\mathrm{R}_k(u)),\mathrm{s}(\mathrm{R}_k(v))),\ k\ge0\text{ and } \vert\mathrm{R}_k(u)\vert, \vert\mathrm{R}_k(v)\vert >0
$$
其中,函数$$\mathrm{g}(D_1, D_2)\ge0$$是衡量两个度序列$$D_1$$和$$D_2$$距离的函数,并且$$\mathrm{f}_{-1}=0$$。由上述$$\mathrm{f}_k(u, v)$$的定义可知,该函数是非减函数,并且只有在节点$$u$$和$$v$$存在距离为$$k$$的邻居节点时才有定义。
接着就要确定比较两个度序列的函数$$\mathrm{g}(\cdot, \cdot)$$了。首先,对于度序列$$\mathrm{s}(\mathrm{R}_k(u))$$和$$\mathrm{s}(\mathrm{R}_k(v))$$,他们可能大小不一致,且序列元素可能是$$[0, n-1]$$内元素的任意组合。在本文中,作者使用Dynamic Time Warping (DTW)来作为该函数,并针对图的某些特性进行了定制化。

多层加权图

多层加权图的构造是为了更准确地表达节点之间的结构相似度。由上述记法,将$$G=(V, E)$$记为原始图,$$k^$$记为图直径。用$$M$$表示构造的多层图,而第$$k$$层图即是通过节点和与之距离为$$k$$的邻居节点构成的图。
每一层$$k=0, \cdots, k^
$$都是定义在节点集合$$V$$上面的无向有权完全图,即共有$$n \choose 2$$个边。而边的权重通过下式得出:
$$
\mathrm{w}_k(u, v) = e^{-\mathrm{f}_k(u, v)}, k=0,\cdots,k^
$$
其中函数$$\mathrm{w}_k(u, v)$$只有在$$\mathrm{f}_k(u, v)$$有定义处才有定义,且该函数的值小于等于$$1$$。当$$\mathrm{f}_k(u, v)$$越小时,$$\mathrm{w}k(u, v)$$越大。并且与节点$$u$$结构相似的节点在不同层次的图中的边权都会更大些。
每一个节点都与相邻层次的图中对应节点相连(如果存在的话),记在第$$k$$层图中的节点为$$u\in V$$,第$$k-1$$层中对应的节点为$$u
{k-1}$$,第$$k+1$$层中对应的节点为$$u_{k+1}$$。则如下定义各个节点之间的权重:
$$
\mathrm{w}(u_k, u_{k+1}) = \mathrm{log}(\mathrm{\Gamma}_k(u)+e),\ k=0,\cdots,k^
-1
$$
$$
\mathrm{w}(u_k, u_{k-1}) = 1,\ k=1,\cdots,k^*
$$
其中,$$\mathrm{\Gamma}_k(u)$$定义为:
$$
\mathrm{\Gramma}k(u)=\sum{v\in V}\mathrm{1}(\mathrm{w}_k(u, v)>\hat(w)_k)
$$
其中,$$\hat(w)k=\frac{\sum{(u, v)\in{V \choose 2}}\mathrm{w}_k(u, v)}{n \choose 2}$$.

其他

由上述多层加权图的构造过程,我们可以知道,该多层加权图也可以被当作一个巨大的有向有权图,之后作者又详细讨论了如何在这张图上进行采样的算法。其中涉及到一些更细节的游走策略,在此不再赘述。最后作者也介绍了下语言模型的学习过程。

参考资料

struc2vec: Learning Node Representations from Structural Identity

0%