struc2vec: Learning Node Representations from Structural Identity

• PDF文件

学习指导

struc2vec是一种图嵌入算法，用于生成节点的嵌入表示，和DeepWalk一样。但是DeepWalk倾向于保留节点的共现信息，而struc2vec倾向于保留节点的结构角色。

什么是结构角色

所谓的角色，就是你在社会中和他人的关系，比如你的角色是子女，就是你和你的父母的关系，你的角色是员工，就是你和老板的关系。在图中，一个节点的结构角色就是它和其他节点的连接关系，在struc2vec中，忽略与其连接节点的属性，也就是说所有的节点一视同仁，那么使用度就能直观的表示节点的结构角色，更进一步，我们考察节点邻居节点的度，可以进一步评价节点的结构角色（比如两个人的子女数量相同，那么我们认为两个人的角色相近，此时可以可以进一步考察两人子女的子女来区分两人的角色。）

如上图，节点u和节点v就具有相似的结构角色

思路

节点嵌入的本质就是设计一种距离度量（向量），来度量节点与节点之间的“相似度”（也就是距离），由于这个过程会把节点从图结构放到向量空间中，所以叫做“嵌入”。在Deepwalk中，我们把“节点共现”作为度量节点之间距离的依据，其本质就是节点在图中的距离（两个节点之间最短路的长度）。在struc2vec中，我们试图使用节点的结构角色作为距离度量的依据。

秉持着把不熟悉的问题转换成熟悉的问题的原则，我们可以用原图的节点构造新图，在新图中，我们把结构角色相似的节点用边直接连接，那么整个问题就可以用我们熟悉的DeepWalk算法解决了。

如何度量结构相似度

• 表示与节点v相距k跳的节点集
• 对 中节点按度排序，得到度序列

定义考虑节点在k跳邻域下的结构距离：

其中， 是度量两个序列的函数，比较常用的有DTW算法。

在DTW中，我们使用以下函数度量两个数的距离：

这样， 和 的距离将有很大的差别，距离说明，如果老板A有10000个员工，老板B有10001个员工，那么他们的角色几乎一样，但是如果老板A有1个员工，老板B有2个员工，那么我们就不能说他们两个角色完全一样，因为增量和总量的比例太大了。

使用结构距离构造新图

我们构造一个多层的图，每一层包含原图中所有节点，第k对应原图中考虑k跳邻居的结构距离，也就是 ，新图总共 ，其中 是原图的直径。

新图是带权图，第k层中，节点u与节点v之间边的权重为

这就是结构相似度，结构距离越小，结构相似度越大。

在不同的层之间，我们把对应的节点用带权有向边连接，也就是把第k层的节点u和第k+1层的节点u连接，节点权重为：

其中， ， 。

有偏随机游走

struc2vec中，我们采用有偏随机游走生成随机游走序列。

假设当前随机游走停留在第k层的节点u。

首先，我们以概率q停留在当前层，以概率1-q前往其他层。

停留当前层：从节点u游走到节点v的概率为

跳到其他层：

Skip-Gram算法

获得了随机游走序列后，我们就能用Skip-Gram算法生成节点的嵌入表示了，详见【论文阅读】DeepWalk Online Learning of Social Representations。

复杂度与优化

DTW算法复杂度为 ，其中， 是最长序列的长度，使用FastDTW可以把时间复杂度降到 。

优化1：减少度序列的长度。

由于度序列中有很多度可能是重复的，我们可以用二元组表示度序列，其中一个表示度，另一个表示度出现的频数，对于压缩后的序列A'和B'，DTW度量如下：

其中 和 。

优化2：减少相似度计算次数

在计算结构相似度的时候，我们对所有节点对进行了计算，但事实上，如果两个节点的结构相似度很低，那么有偏随机游走几乎不可能连续经过这两个节点，那么我们也不用计算这两个节点的结构相似度。

我们假设节点u的邻居是 ，那么我们首先在度序列中找到和节点u的度最相近的节点（二分查找），然后取连续的log n个节点，只计算节点u和这log n个节点的相似度。

优化3：减少层数。

层数越大的层，对于相似度的影响越小，所以我们不需要太多层。