struc2vec: Learning Node Representations from Structural Identity
struc2vec是一种专注于网络structural identity的embedding算法，适合于无向无权图。
文中指出，大多数的graph embedding方法的想法是，如果两个节点有共同的neighbor节点，则它们有相似的representation。但问题在于neighborhood是一个非常local 的概念，如果两个节点在neighborhood的结构上是相似的，但这两个节点离得很远，就不会有相似的representation。
（大多数的graph embedding方法更关注homophily，而struc2vec可以有效挖掘structural identity。其实node2vec已经同时考虑了homophily和structural identity，但是node2vec的局限性在于，当两个节点的距离（节点之间的跳数）超过了Skip-Gram的window大小，就无法捕捉它们的structural identity了）
如上图中的节点u和v，它们有相似的local structure，但在网络中离得很远。它们的neighborhood没有共有的节点，很多graph embedding方法并不能捕捉这种结构相似性。
struc2vec的主要想法：
•能够发现两个节点在neighborhood结构上的相似性，即使它们位于网络的不同位置上，没有直接相连。
•构建一种hierarchy来度量structural similarity。
-在低 hierarchy层面上，节点的structural similarity仅仅依赖于它们的度。
-在高hierarchy层面上，节点的structural similarity依赖于整个网络结构。
•生成节点的context，放入language model(如Skip-Gram)来学习representation。
STRUC2VEC
学习节点的representation能够捕捉到节点的structural identity，一个好的方法应该具备以下两点：
•节点的representation之间的距离应该与节点的structural similarity高度相关。即两个节点有相似的structural identity，则它们之间的representation应该是相似的。
•节点的representation不依赖于节点属性、边属性和节点label。节点的structural identity独立于节点在网络中的位置，及时两个节点离得很远，但它们有相似的structural identity，也能够识别出来。
基于上面两点，提出了struc2vec算法，由四个步骤组成：
•对于不同的节点对，计算它们的结构相似度(structural similarity)，并以此产生一个hierarchy。
•构造一个带权重的多层图，network中的所有节点都被摆放在这个新的图的每一层中。每一层都对应structural similarity的一个hierarchy。
•利用多层图来产生节点的context。具体来说，使用biased random walk在多层图上产生节点序列。
•通过Skip-Gram等算法来从节点的context中学习representation。
Measuring structural similarity
如果两个节点的度相同，就认为它们具有一定的structural similarity，如果它们的neighbor也有相同的度，那么就认为它们的structural similarity更高了。
G=(V,E)表示无向无权图。n = |V|表示network中的节点数，k*表示图的直径。Rk(u)表示从节点u出发，恰好经过k跳能到达的节点集合。R1(u)表示u的neighbor节点集合，Rk(u)可以看作与u距离为k的环。s(S)表示对于子集S ⊂V，S集合中节点的有序的度序列。fk(u,v)表示u和v之间的structural distance(考虑它们的k-hop neighborhood，即所有的节点距离≤k以及所有其中的边)。
定义
g(D1,D2)≥0度量了有序的度序列D1和D2的距离。f-1 = 0。
fk(u,v)对于k是单调不减函数，并且在u和v在距离k有节点时才有定义。
s(Rk(u))和s(Rk(v))可以有不同的长度，本文使用DTW来衡量它们之间的距离。
定义距离函数
也就是说，fk(u,v)考虑了≤k的部分，等于考虑了≤k-1部分的fk-1(u,v)加上考虑恰好为k的距离g(s(Rk(u)),s(Rk(v)))。
DTW具体说明：
目标：衡量两个有序序列的距离。
具体步骤：
以序列A,B为例，A和B是有序的度序列，具体的，比如A = (1,1,2,8,10), B = (1,2,4,5)
将A和B分别水平和竖直排开，按照上面给出的d(a,b)的公式计算两两元素的距离。
根据上面的矩阵，计算A与B的距离，利用的是动态规划，每个位置的值如下(d(i,j)表示的是在上面那个矩阵对应位置的值)
计算得到，
那么序列A和序列B的距离为右上角的值3.2(越小越相似)，即g(A,B) = 3.2。
Constructing the context graph
定义多层图M，每一层k = 0,...,k*是节点集为V的带权无向完全图，一层中的两个节点之间的边权为
wk(u,v)≤1，等号当且仅当f(u,v)=0时取到。
与节点u在structural similarity上相似度高的节点，会在M的各层上有更大的边权。
上层(k比较大)偏向于考虑全局信息，下层(k比较小)偏向于考虑比较local的信息。
使用有向边将各层连接起来，第k层中的u节点和k+1层、k-1层中的u节点相连。
连接各层之间的边权为
其中
即第k层与u相连的边的边权大于平均边权的边的数量，
表示第k层的平均边权。
对于此处，τk(u)衡量了在第k层中，有多少节点和节点u的相似度比较高，如果τk(u)很大，说明当前层次比较低，那么w(uk,uk+1)就会比较大，倾向于向上层走。
Generating context for nodes
在多层图M上使用biased random walk来获得各节点的context。
在每一步，首先要决定random walk会走到其它层还是留在当前层，random walk会停留在当前层的概率为q>0。
假设random walk会留在当前层，在第k层从节点u到节点v的概率为
Zk(u)为正则化因子，
random walk会朝着有相似的structural similarity节点的方向。
有1-q的概率，random walk会离开当前层，到上层或下层对应的节点处，此时到上层和下层的概率分别是
对于每个节点，开启random walk时在第0层它对应的节点位置。
Learning a language model
获得random walk sequence后，使用Skip-Gram来生成representation，文中使用了Hierarchical Softmax优化。
Optimizations
OPT1
压缩有序的度序列长度，改为二元组序列(degree,counts)。
A'和B'表示压缩后的A和B，此时DTW距离函数为
a = (a0,a1), b = (b0,b1)为A'和B'中的二元组，a0和b0为度，a1和b1为出现的次数。
OPT2
相似度计算优化。
在一层中，如果两个节点的度数相差很大，就不太可能被random walk采样到，因此没必要计算。
只计算与顶点u的度数接近的顶点的距离。在顶点u对应的有序的度序列中进行二分查找，只计算查找路径上的顶点与u的距离。
OPT3
减少层数。
使用固定的k'层，k'<k*。
网友评论