Deepwalk 主要思想是利用随机游走产生序列，当成句子输入到word2vec学习到特征。

Node2vec 改进了Deepwalk中随机游走，使得嵌入得到功能角色信息，具体做法是利用BFS和DFS。

Graph Embeddings 基于匿名随机游走学习到子图的一些结构信息，从而得到图嵌入向量。

辅助资料：

Node2Vec【图神经网络论文精读】 哔哩哔哩 bilibili

图表示学习的作用(Graph Representation Learning)

图表示学习的思想（embebding）

图表示学习的思想是将图的信息镶嵌到d维空间上，获取特征，同时保持相似性

example：

Node Embeddings

1、目标：找个一个相似性函数

2、Node Embedding过程

第一步：encoder，找到 $z_v^Tz_u$

第二步：定义节点相似性函数（测量原来图上节点位置的相似性）

第三步：decoder，度量 $z_v^Tz_u$

3、两个关键点

Encoder：找到映射空间

Decoder：找到Decoder使得计算映射后的特征和原空间的特征相似性保持一致

Shallow Encoding（最简单的思想）

1、找到一个矩阵，将节点进行one-hot编码，利用矩阵相乘进行映射

2、思路如下

若有1w个节点， $Z$ 矩阵则有1w列

每一个节点都看出一个单独的任务，毫无关联，对应word2vec中的one-word model

DeepWalk

1、加入相似信息

在Shallow Encoding中，节点的相似信息没有被用上，Deepwalk加入了节点的相似信息，那么节点的相似信息如何定义？

are linked？

share neighbors？

have similar “structural roles”？

在本节，我们将介绍利用random walk进行节点相似性定义

2、Note on Node Embedings（注意）

DeepWalk是无监督或者自监督的学习方式， 即我们将不使用节点的标签，不使用节点的特征，只使用节点的相似性，这个方式是适用于任何任务上的。

Base on random walks

随机游走的主要思想： 利用随机游走产生的序列，节点当成单词，形成句子，投入到word2vec，利用word2vec中的skip-gram模型进行embedding

step1：定义步长R，进行随机游走

step2：基于one-hot进行编码

step3：投入到wrod2vec进行embedding

1、定义一些符号

2、Random Walk思想

在图上从某个点开始，随机游走K步

3、节点相似度定义

在Random Walk中，节点相似度定义为： 从某点出发随机游走得到的集合，该集合中的节点具有相似性。

利用概率估计，预测从 $u$ 出发，R步所能走过的节点的概率

$u$ 和 $v$ 之间的相似性类似于夹角，定义为上述所说的概率。对应模型为word2vec中的Skip-Gram利用中心词预测上下文。

4、为什么进行随机游走？

两个原因：

灵活的随机定义包含两个局部的节点相似性和高阶邻域信息

有效性：无须进行任何训练，只需要考虑在随机游走中共现的节点

因而随机游走是 一种自监督学习方法

5、定义优化目标

给定一个图G，定义映射函数 $f$ （一个矩阵），目标为在定义域为 $f$ 中搜索 $\sum_{u \in V} \log \mathrm{P}\left(N_{\mathrm{R}}(u) \mid \mathbf{z}_{u}\right)$

优化目标等同于优化：

概率定义为softmax即相当于 $|V|$ 类分类任务， $|V|$ 为节点数：

运算量过大

主要原因是下面的正则项:

7、一些加速的方法

也是word2vec中的加速方法。

负采样：相比于利用全图节点进行正则项计算，负采样只采用某些节点进行计算，丢失一些准确率，但保证了速度，具体参考 1402.3722.pdf (arxiv.org)

8、反向传播（梯度下降法）

定义了优化函数，我们将利用随机梯度下降法进行优化。

根据word2vec的原理，DeepWalk只用到了节点在图上位置的信息，利用one-hot编码进行降维得到节点嵌入。

这样做的缺点是，没有利用其他信息，如节点间的链接权重，节点本身的特征等 。

此外DeepWalk用的是随机游走，无法看到整张图的信息，随机游走的随机性可能无法很好的表示局部信息。

只能反映相邻节点的社群相似信息，无法反映节点的功能角色相似信息。

Node2vec

为了解决随机游走无法看到整张图的信息，作出改进，把随机游走改为有偏游走。

1、利用偏向游走

BFS(宽度优先)：局部游走

DFS(深度优先)：深度游走

2、策略比较

当从t走到V后，再选取下一个节点的时候，有两种倾向。

返回上一个节点或者走到上一个节点的邻居

远离上一个节点

当我们定义p很小时，我们更 倾向回到上一个节点 ，这就是BFS，会在局部中游走。

当我们定义q很小时，我们更 倾向远离上一个节点 ，这就是DFS，会在全局中游走。

基于任务各有好处：

BFS：局部视野

DFS：全局视野

3、二阶随机游走

在Deepwalk中，是一阶随机游走，即选取节点的策略仅取决于当前的节点。

在Node2vec中，采用的是二阶随机游走， 即选取的节点策略取决于当前节点同时也取决于上一个节点

4、技术细节

Step1(关键一步)、计算随机游走的概率，形成概率表， 降低游走采样的时间复杂度 ，降为线性时间。

Step2、模拟随机游走。

Step3、基于随机梯度下降法进行优化。

Node2vec向量嵌入包含了节点的语义信息（相邻社群和功能角色）

语义相似的节点，向量嵌入的距离也近。

在DeeoWalk完全随机游走的基础上，Node2vec增加了p、q参数，实现有偏随机游走。

不同的p、q参数组合，对应了不同的探索范围和节点语义。

DFS深度优先搜索， 相邻的节点，向量嵌入距离相近 。

BFS广度优先搜索， 相同功能角色的节点，向量嵌入距离相近 。

DeepWalk是Node2Vec在p=1，q=1的特例。

其他游走策略

可以使用节点的属性，节点的权重等。

Graph Embeddings

对图或者子图进行Embeddings，用于一些图分类任务上。

1、方法1

将图上的节点嵌入向量平均化，得到图的向量。

2、方法2

引入一个虚拟节点表示子图，然后对虚拟节点进行node2vec

3、方法3（匿名随机游走）

匿名随机游走，顾名思义将节点匿名，从index=1开始走，遇到新的节点则加1并标记上index，遇到之前遇到过的节点则设置为第一次出现时的index。如下图的例子。

A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ B $\rightarrow$ C：则为1 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 2 $\rightarrow$ 3

C $\rightarrow$ D $\rightarrow$ B $\rightarrow$ D $\rightarrow$ B：则和上式一样1 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 2 $\rightarrow$ 3。

这说明这两条随机游走有相似的结构，相似的子图

A $\rightarrow$ B $\rightarrow$ A $\rightarrow$ B $\rightarrow$ D：则为1 $\rightarrow$ 2 $\rightarrow$ 1 $\rightarrow$ 2 $\rightarrow$ 3

匿名随机游走产生的pattern，即不同的链和路径长成指数增长关系，如路径长为3的匿名游走，根据组合数可以得到pattern有5个。

简单使用匿名随机游走，进行Graph Embeddings

记录所有长度为 $l$ 的匿名随机游走

将图表示为这些匿名游走的分布

想法和Traditional Embeddings中的Graphlet Degree Vector差不多，统计所有长度为 $l$ 的匿名随机游走的pattern，然后将图表示为这些pattern的频数或概率。

example：

设定 $l=3$

假设w_i分别在图中出现的频数为30,10,5,10,20。归一化后得到w_i在图中出现的概率。

将第i个pattern记作 $w_i$

这样的做法会使得时间复杂度上升，因为长度l和pattern个数成指数关系。

解决的方法：用采样

独立地采样m条随机游走路径来近似匿名游走pattern

用这些采样得到的随机游走路径的概率分布来表示图

4、其他idea：Learn Walk Embeddings

不简单地用每次游走出现的次数的分数来表示匿名游走，而是学习匿名游走 $w_i$

具体来说：

就是将所有的匿名游走的embeddings $z_i$

如何进行embed walks？利用CBOW。输入了整张图的embeddings 说明和doc2vec类似（后续再具体学习）

具体过程如下：

输入整张图的 $Z_G$

从节点1开始，采样获取匿名随机游走， $w_1$

学习预测walks共现在 $t-\varDelta$

example： $\varDelta =1$

聚类/社区发现：聚类 $z_i$

节点分类：基于 $z_i$

边预测：通过定义两个节点之间的向量映射，得到边向量，再进行预测。

图预测：通过聚合节点embeddings或匿名随机游走获取的图 $z_G$