RandomWalk在GraphEmbedding中的应用
从某个节点的邻居中随机挑选一个节点作为下一跳节点的过程称为随机游走(Random Walk，下文简称游走)，多次重复游走过程可产生游走序列。
随机游走负责对图进行采样，获得图中节点与节点的共现关系。产生的序列可以作为训练样本输送到模型(如word2vec)中进行训练，进而得到图上节点嵌入向量，即embedding。
图上游走特点：“多快好省”
多：游走产生序列蕴含信息丰富
图上节点可以用从它出发的游走序列来描述，每个节点游走到达的节点集合不完全相同。 从一个节点出发得到的游走序列既包含该节点的本地邻居，又包含高阶邻居。
快：游走生成序列速度快、训练模型快
游走过程可并行化:可以同时从不同顶点出发进行一定⻓度的游走生成序列。
直接从游走序列采样节点对训练模型，极大节省在全图采样节点对的时间。
好：图上游走方法科学有效
随机游走序列中节点共现与句子中单词共现均服从幂律分布，可通过word2vec(多使用skip-gram)求解 得到图上节点Embedding。
省：可持续迭代、节省重复训练成本
网络的演化通常是局部的点和边的变化，在网络演化过程中只需要对有变动的节点重新生成随机游走序 列，大大节省对整个图上节点重新生成游走序列的时间。
随机游走策略介绍
游走的关键问题在于如何选择下一跳节点，即选点策略。
选点策略具体可以用转移概率来表示，我们通常按转移概率是否相等可以将游走分为无权(unbias)和 加权(bias)两类。 Knightking对游走进行更为详细的划分:
http://madsys.cs.tsinghua.edu.cn/publications/SOSP19-yang.pdf
本文将按从简单到复杂、从通用到特殊的思路来介绍常用的游走策略，读者可以自行思考所属类别。
uniform：一视同仁的游走
uniform的特点是邻居节点集合中每个节点被选中的概率相等，转移概率为1/节点出度数。
frequency：带权重的游走
frequency的特点是邻居节点集合中每个节点被选中的概率与节点边的权值正相关，转移概率为归一化后的边权重。
https://arxiv.org/abs/1403.6652
markov：克制的游走
markov的特点是节点每次游走时以概率p停留在本节点，以概率1-p跳转至邻居节点，可缓解经若干跳到达的节点距离初始节点较远的现象。
Learning of Multimodal Representations With Random Walks on the Click Graph
dynamic：温故知新的游走
dynamic的特点是需要结合访问过节点的信息来选择下一跳节点。 node2vec使用一种二阶动态随机游走策略:通过调节参数p和q来控制游走倾向于DFS还是BFS。
https://cs.stanford.edu/~jure/pubs/node2vec-kdd16.pdf
metapath：带先验的游走
在异构图上进行随机游走需要考虑节点异构性质。如果不考虑节点异构性，节点游走概率更容易倾向于选中邻居节点类型占比大的节点，导致训练出的节点embedding将倾向于占比较大的节点类别 embedding。
metapath的特点是在异构图上提供有效游走路径。在某条固定的路径下，节点的下一跳节点类型已经确定，只在该类型的邻居节点集合中选取一个节点。
https://ericdongyx.github.io/papers/KDD17-dong-chawla-swami-metapath2vec.pdf
just：平衡同质边和异质边数的游走
metapath策略存在获取困难、无法保证有效性的情况，导致产生的游走路径训练出的embedding效果 不佳。
Just的思想是节点以p^L的次方跳转至同类型的邻居节点(其中p为停留概率，L表示连续相同节点类 型⻓度)，否则跳转至其他类型的邻居节点。
为使跳转类型更丰富，下一跳跳转的节点类型尽量与最近几次跳转访问到的节点类型不同。
struc：根据结构信息重新定义邻居的游走
前文提到的几种游走策略直接从节点的邻居节点采样节点，节点间存在连通路径是节点相似的必要条件。
结构化随机游走则是根据节点的结构相似性重新定义节点的”邻居节点“，如果两个节点在局部具有类 似的拓扑结构，那么这两个节点也可以是相似节点。
腾讯云开发者
