Deepwalk，Node2vec算法原理生动理解（图文）

Deepwalk算法原理详解

DeepWalk算法之所以能够有效地学习节点的低维表示，是因为它利用了本质上与自然语言处理相同的思路：图是一种高维数据，很难直接处理，但是可以将其映射到低维空间中，这样可以更好地进行处理

DeepWalk算法的核心是随机游走过程。该过程从某个节点开始，依次按照一定的策略，选择这个节点的邻居节点进行移动，最终形成一个游走路径。重复执行该过程，就可以得到一系列游走路径，这些路径就是DeepWalk算法中的“句子”。Word2Vec对“句子”进行学习，得到每个节点的低维表示

DeepWalk算法的基本原理

1、生成节点邻接矩阵A

2、从一个初始节点开始，按照随机游走策略，不断移动到与它邻接的节点
我们假设随机游走的长度为4，并且从A节点开始游走：

第一步：A——B

第二步：A——B——C

第三步：A——B——C——D

这样我们就得到了一个随机游走序列A——B——C——D（请注意游走是随机的，完全有可能从A到B，再从B又回到A）

3、重复上面的步骤生成多个游走路径，这些路径就是DeepWalk算法中的“句子”

4、利用Word2Vec模型，对“句子”进行学习，得到每个节点的低维表示，即嵌入向量
假如图中有10000个顶点，那么我们将每个顶点用长度10000的向量表示，顶点1表示为[1，0，0，0，…]，顶点2表示为[0，1，0，0，…]

在上图中，输入为某个顶点，通过10000xh的W1矩阵，变成了长度为h的向量，再通过hx10000的W2矩阵变回长度为10000的向量

我们的目标是输入一个顶点，输出的结果中对应的与输入顶点关系密切的位置的得分较高。
在序列A——B——C——D中，输入A节点时，希望输出向量的第2，3，4维度的得分较高。
通过deepwalk得到了许多的游走序列，也就是句子，这就是我们的训练集。
观察图中，Input的第一个维度只与W1的第一行进行了线性计算，意思是W1的第一行提取了Input输入的第一个维度信息（也就是顶点1），所以顶点1的低纬度向量表示即为W1的第一行。

Deepwalk特点

1、首个将深度学习和自然语言处理的思想用于图机器学习

2、在稀疏标注节点分类场景下，嵌入性能卓越

3、DeepWalk算法不能捕获节点的全局结构信息

4、DeepWalk算法基于随机游走，对于大图，这个方法可能会带来较高的计算复杂度

5、DeepWalk算法依赖于节点的邻居关系，在节点之间存在高度长距离的图上时，DeepWalk效果可能不佳

6、无监督，仅编码图的连接信息，没有利用节点的属性特征

7、没有真正用到神经网络和深度学习

Node2Vec算法原理详解

Node2Vec算法的基本原理

相较于Deepwalk，Node2Vec中节点的游走不再是无偏的随机游走，而是根据p和q的参数来影响节点的游走：（看图！）

假设A是上一个节点，B是当前节点，那么B现在有四条路可以选择：A，H，C，J
对于A：相当于是返回，我们设置其概率为1/p，受参数p的影响
对于H：相当于是徘徊，因为A到B和A到H的距离都是相等的，，设置概率为1
对于C和J：相当于是远离，它们朝着离A更远的方向离去，设置概率为1/q，受参数q的影响

当q值较小时，类似于深度优先搜索算法（DFS），用于探索相邻的节点
当p值较小时，类似于广度优先搜索算法（BFS），用于探索结构功能相似的节点

DeepWalk是Node2Vec在p=1, q=1的特例

Node2Vec特点

1、通过调节p、q值，实现有偏随机游走,探索节点社群、功能等不同属性

2、首次把节点分类用于Link Prediction

3、可解释性、可扩展性好,性能卓越

4、需要大量随机游走序列训练。弱水三千取一瓢,管中窥豹

5、距离较远的两个节点无法直接相互影响。看不到全图信息(图神经网络)

6、无监督,仅编码图的连接信息,没有利用节点的属性特征(图卷积)

7、没有真正用到神经网络和深度学习