有很多的叫法，GRL, NRL, GE（graph embedding）等等，感觉都是得到图的嵌入表示。

deepwalk

原理

从每一个节点出发，每次随机从邻居中选择一个作为下一个节点

node2vec

原理

deepwalk和LINE分别倾向于DFS和BFS，而node2vec则是使用了权重作为概率，介于DFS和BFS之间。

主要分为三部分：

计算基于边的转移概率：这里是上一个点不是起始点需要用的。

下图的意思是，从t出发，到达v之后，再往其他位置走的概率如下公式。（前面至少两个点才能用这个，起始点的话就只能用权重做归一化了）。感觉参考一的这个公式有点问题，下面是自己改的。

\[\left[P(\text { transform } \mid(t, v))=\alpha_{p q}(t, x) * w_{v, x} \quad \text { for } x \in N(v)\right] \]

\[\alpha_{p q}(t, x)=\left\{\begin{array}{ll} \frac{1}{p}= & \text { if } d_{t x}=0 \\ 1= & \text { if } d_{t x}=1 \\ \frac{1}{q}= & \text { if } d_{t x}=2 \end{array}\right. \]

基于节点的转移概率：对于起始点而言，将该节点的每一条边的权重归一化，作为走那边的概率。

alias取样：需要对每一个节点和边都生成accept和alias列表。节点的alias tables其实意义不大，主要是边的，最后取样。这个取样，其实就是依据概率，看你走那条边。

个人觉得，其实不用这个算法也可以，就轮盘赌，挨着比大小，就是复杂度高很多，而且一些图的节点比较多。

取样完成后使用skip-gram算法对walks进行嵌入，参考一中用gensim中的word2vec。

alias算法—一种\(O(1)\)的采样算法

个人感觉跟之前学的轮盘赌算法差不多，alias牺牲空间，换来时间，但是实际计算accept和alias的时候任然是$O(N) $

第一幅图代表一个概率轮盘，一般来说，我们需要生成一个0到1的随机数，判断在哪个区间，从而得到取样结果，也就是命中的那一块。

依次遍历复杂度为\(O(N)\), 二分法复杂度为\(O(log(N))\)

alias算法按照下面的公式，这里N=4，先归一化，然后乘以区域个数。之后，切割矩形，保证每一个柱子的大小为1，并且只能由最多之前的两块合成一个，得到下图，可以任意拼凑，满足条件即可。

\[\frac{p_{i} * N}{\sum_{k=1}^{k=N} p_{k}} \]

Accept就是原本该块留下来的面积，alias对应的是另一种颜色区域的编号。

第一次学习的时候感觉不可思议，后面看看确实是那么回事，可以找找证明。

实现

参考一中非常详细

参考

GraphEmbedding - Node2vec 图文详解_BITDDD小栈-CSDN博客_node2vec

alias算法的图很好

Alias Method:时间复杂度O(1)的离散采样方法 - 知乎 (zhihu.com)