struc2vec: Learning Node Representations from Structural Identity
学习指导
struc2vec是一种图嵌入算法，用于生成节点的嵌入表示，和DeepWalk一样。但是DeepWalk倾向于保留节点的共现信息，而struc2vec倾向于保留节点的结构角色。
什么是结构角色
所谓的角色，就是你在社会中和他人的关系，比如你的角色是子女，就是你和你的父母的关系，你的角色是员工，就是你和老板的关系。在图中，一个节点的结构角色就是它和其他节点的连接关系，在struc2vec中，忽略与其连接节点的属性，也就是说所有的节点一视同仁，那么使用度就能直观的表示节点的结构角色，更进一步，我们考察节点邻居节点的度，可以进一步评价节点的结构角色（比如两个人的子女数量相同，那么我们认为两个人的角色相近，此时可以可以进一步考察两人子女的子女来区分两人的角色。）
如上图，节点u和节点v就具有相似的结构角色
思路
节点嵌入的本质就是设计一种距离度量（向量），来度量节点与节点之间的“相似度”（也就是距离），由于这个过程会把节点从图结构放到向量空间中，所以叫做“嵌入”。在Deepwalk中，我们把“节点共现”作为度量节点之间距离的依据，其本质就是节点在图中的距离（两个节点之间最短路的长度）。在struc2vec中，我们试图使用节点的结构角色作为距离度量的依据。
秉持着把不熟悉的问题转换成熟悉的问题的原则，我们可以用原图的节点构造新图，在新图中，我们把结构角色相似的节点用边直接连接，那么整个问题就可以用我们熟悉的DeepWalk算法解决了。
如何度量结构相似度
- \(R_k(v)\) 表示与节点v相距k跳的节点集
- 对 \(R_k(v)\) 中节点按度排序，得到度序列 \(s(R_k(v))\)
定义考虑节点在k跳邻域下的结构距离：
\[\begin{gathered} f_k(u, v)=f_{k-1}(u, v)+g\left(s\left(R_k(u)\right), s\left(R_k(v)\right)\right), \\ k \geq 0 \text { and }\left|R_k(u)\right|,\left|R_k(v)\right|>0 \end{gathered} \]其中，\(g(\cdot, \cdot)\) 是度量两个序列的函数，比较常用的有DTW算法。
在DTW中，我们使用以下函数度量两个数的距离：
\[d(a, b)=\frac{\max (a, b)}{\min (a, b)}-1 \]这样，\(d(10000,10001)\) 和 \(d(1,2)\) 的距离将有很大的差别，距离说明，如果老板A有10000个员工，老板B有10001个员工，那么他们的角色几乎一样，但是如果老板A有1个员工，老板B有2个员工，那么我们就不能说他们两个角色完全一样，因为增量和总量的比例太大了。
使用结构距离构造新图
我们构造一个多层的图，每一层包含原图中所有节点，第k对应原图中考虑k跳邻居的结构距离，也就是 \(f_k\)，新图总共 \(k^*层\)，其中 \(k^*\) 是原图的直径。
新图是带权图，第k层中，节点u与节点v之间边的权重为
\[w_k(u, v)=e^{-f_k(u, v)}, \quad k=0, \ldots, k^* \]这就是结构相似度，结构距离越小，结构相似度越大。
在不同的层之间，我们把对应的节点用带权有向边连接，也就是把第k层的节点u和第k+1层的节点u连接，节点权重为：
\[\begin{aligned} & w\left(u_k, u_{k+1}\right)=\log \left(\Gamma_k(u)+e\right), \quad k=0, \ldots, k^*-1 \\ & w\left(u_k, u_{k-1}\right)=1, \quad k=1, \ldots, k^* \end{aligned} \]其中，\(\Gamma_k(u)=\sum_{v \in V} \mathbb{1}\left(w_k(u, v)>\overline{w_k}\right)\)，\(\bar{w}_k=\sum_{(u, v) \in \mathcal{E}_k} w_k(u, v) /\left(\begin{array}{l}N \\ 2\end{array}\right)\)。
有偏随机游走
struc2vec中，我们采用有偏随机游走生成随机游走序列。
假设当前随机游走停留在第k层的节点u。
首先，我们以概率q停留在当前层，以概率1-q前往其他层。
停留当前层：从节点u游走到节点v的概率为
\[p_{k}(u, v) = \frac{e^{-f_{k}(u, v)}}{Z_{k}(u)} \]\[Z_{k}(u)=\sum_{\substack{v \in V \\ v \neq u}} e^{-f_{k}(u, v)} \]跳到其他层：
\[\begin{array}{l} p_{k}\left(u_{k}, u_{k+1}\right)=\frac{w\left(u_{k}, u_{k+1}\right)}{w\left(u_{k}, u_{k+1}\right)+w\left(u_{k}, u_{k-1}\right)} \\ p_{k}\left(u_{k}, u_{k-1}\right)=1-p_{k}\left(u_{k}, u_{k+1}\right) \end{array} \]Skip-Gram算法
获得了随机游走序列后，我们就能用Skip-Gram算法生成节点的嵌入表示了，详见【论文阅读】DeepWalk Online Learning of Social Representations。
复杂度与优化
DTW算法复杂度为 \(O(l^2)\)，其中，\(l\) 是最长序列的长度，使用FastDTW可以把时间复杂度降到 \(O(l)\)。
优化1：减少度序列的长度。
由于度序列中有很多度可能是重复的，我们可以用二元组表示度序列，其中一个表示度，另一个表示度出现的频数，对于压缩后的序列A'和B'，DTW度量如下：
\[\operatorname{dist}(\boldsymbol{a}, \boldsymbol{b})=\left(\frac{\max \left(a_{0}, b_{0}\right)}{\min \left(a_{0}, b_{0}\right)}-1\right) \max \left(a_{1}, b_{1}\right) \]其中 \(\boldsymbol{a}=\left(a_{0}, a_{1}\right)\) 和 \(\boldsymbol{b}=\left(b_{0}, b_{1}\right)\)。
优化2：减少相似度计算次数
在计算结构相似度的时候，我们对所有节点对进行了计算，但事实上，如果两个节点的结构相似度很低，那么有偏随机游走几乎不可能连续经过这两个节点，那么我们也不用计算这两个节点的结构相似度。
我们假设节点u的邻居是 \(J_u\)，那么我们首先在度序列中找到和节点u的度最相近的节点（二分查找），然后取连续的log n个节点，只计算节点u和这log n个节点的相似度。
优化3：减少层数。
层数越大的层，对于相似度的影响越小，所以我们不需要太多层。
标签：struc2vec,Node,right,角色,Learning,结构,节点,left From： https://www.cnblogs.com/yangxuanzhi/p/17158860.html