图上的机器学习系列-聊聊struc2vec

前言

本篇继续我们的Graph Embedding之旅。以往我们生成的节点向量保留的一个特征是节点之间的距离，基于随机游走的这一类方法生成的节点距离往往是图上空间位置上的相近。现实世界中，网络中的节点往往还有一个特征就是其在网络结构上的位置角色，类似于下图中u,v这两个节点，它们在结构上的作用很相似，但如果基于随机游走的方法来进行embedding表示，无法将其映射为相似的账号。对传统复杂网络领域有所了解的同学也会联想到边介数、点介数这样的特征，它们刻画的也是节点或边在整个网络中的作用与影响力。

因此，今天我们将要介绍的这个struc2vec方法要刻画的就是这类节点的向量化表达，参考的论文为《struc2vec: Learning Node Representations from Structural Identity》。

----广告时间，欢迎关注本人公众号

算法思路消化

事实上，struc2vec可归属为deepwalk一类的方法，其最核心的方法仍然是先生成节点的序列，然后使用SkipGram来进行向量化求解。到目前为止，我们看到deepwalk发布以来，node2vec，metapath2vec，struc2vec都是遵循了其基本思想！也许这就是影响力吧，能对后人产生深远的影响，这种价值真是挺大的。话说回来，这些方法的差异点无非在于生成节点序列化的过程怎么操作，以便实现不同的关注重点。下面让我们带着问题来消化一下struc2vec。

struc2vec怎样度量节点的相似性？
创新性来了，本方法将节点之间的相似性进行了分层（hierarchy），用下面的计算方法来定义了第k层（也叫第k跳距离上）上u,v两个节点的相似性。

其中s()是一个排过序的度数序列，例如第k跳的路径上依次经过了v1,v2…vk节点，其节点度数分别为d1,d2…dk，排序后的序列为d1’,d2’…dk’，那么s() = (d1’, d2’… dk’)。那么计算上面的相似性的任务就依赖于g这个函数怎样计算不同节点度序列的距离。
作者采用了一种叫做Dynamic Time Warping的方法。

最后，值得一提的是，作者说虽然论文中采用了这种相似性计算方法，但如果使用者有其它的方法，也是可以采用本论文的框架来计算的。这就使得该方法有了一定的可定制性。

struc2vec怎样设计随机游走的策略，以便得到它自己的节点序列？
为了让生成的节点序列能捕捉到节点的结构性特征，作者同样设计了一个很巧妙的构思——构造一个分层的加权图。我根据论文的内容画了一个示意图如下所示：

不同层级的边权重也有一个定义：

生成这个分层的图，最终还是为了生成节点的随机游走序列。因为这里有不同的layer，所以游走的过程会有几种：保留在本layer内游走，向上到k+1层，向下到k-1层。与前人的思想类似，设计几种游走的概率值（基于边的权重）：
1）首先以概率q留在同一个layer内，然后在该层上进行下述概率游走：

2) 以概率q来跨层，且向上、向下的概率也不同：

struc2vec使用skipgram的过程有什么不同吗？
有了节点序列后，以往的方法就是直接使用word2vec中的skipgram方法了！那本文的struc2vec有什么不同吗？
答案是：并没有！所以，如果你之前看懂了deepwalk，那么这个问题就已经转变成已有的知识了。看吧，这就是知识的积累性，知道的越多，面临新问题时需要的增量知识其实是递减的。

 小结

struc2vec致力于刻画节点在网络结构上的相似性，采用了与deepwalk一致的思想。但为了生成节点的随机序列，本方法先构造了一个分层的图，通过定义节点之间的相似度来刻画边的权重，然后基于权重进行随机游走。最后也使用了skipgram进行节点向量化表示。

参考资料

1. 提出struc2vec的论文《struc2vec: Learning Node Representations from Structural Identity》