第三章、节点嵌入 Node Embedding

图表示学习（Graph Representation Learning）图表示学习减轻了每次进行特征工程的需要。传统机器学习对于输入的图信号会进行一系列的特征提取工作，如第二章所示。而图表示学习则是淡化了特征提取工作。图表示学习的目标：对图机器学习希望得到一个高效，且任务独立的特征学习方法。Embedding作用：将节点映射到一个embedding空间中。下面是embedding的性质和作用：网络

叫我阿明

13497人浏览 · 2021-09-15 21:59:51

叫我阿明 · 2021-09-15 21:59:51 发布

笔记总目录

课程为斯坦福大学CS224W 2021年冬季课程。

B站视频

斯坦福大学CS224W silide 03-nodeemb

图表示学习（Graph Representation Learning）

图表示学习减轻了每次进行特征工程的需要。传统机器学习对于输入的图信号会进行一系列的特征提取工作，如第二章所示。而图表示学习则是淡化了特征提取工作。

图表示学习的目标：对图机器学习希望得到一个高效，且任务独立的特征学习方法。

Embedding

作用：将节点映射到一个embedding空间中。

下面是embedding的性质和作用：

网络中相似的节点，在Embedding空间中也是相似的。
潜在地被用来作为下游的预测
编码网络信息

下图为网络embedding的实例。网络中节点在embedding之后被映射到2维空间上，其中网络中性质相似的节点，在2D空间中坐标临近。

节点嵌入：编码和解码

给定一个图 $G$ , $V$ 是顶点集， $A$ 是图邻接矩阵，为了简化问题，不考虑节点特征和其他的额外信息。

节点嵌入：

如下图所示

上图的目的是为了让embedding空间中的相似性近似图中的相似性，其中embedding空间一般是D维空间，相似性可以用向量 $z_u$ 和 $z_v$ 的内积来衡量。如下图所示，节点在图中国的相似性等于节点embedding之后的相似性，不过节点在图中的相似性需要定义。

Node Embedding涉及到的过程:

编码（Encoder）：将节点映射到embedding空间
在映射的过程中需要定义原始图中的节点相似性，以保证映射后的节点相似性有个优化目标。
解码（Decoder）：将embedding空间中的节点集映射为相似性得分。
优化编码参数以解码得分满足下式，其中解码得分使用内积的形式。

两个重要的部分：
Encoder：将每一个节点都映射为一个低维的向量。

相似性函数或解码：刻画向量空间的关系如何映射到网络空间中。

浅编码（Shallow Embedding）

最简单的编码方式：仅仅是一个嵌入查找，即一个编码集中找一个作为节点的编码。

$\mathrm{ENC(}v)=\mathbf{z}_v=\mathbf{Z}\cdot v$

其中 $\mathbf{Z}\in \mathbb{R}^{d\times |\nu |}$ 是一个矩阵，每一列是一个节点编码。 $v\in \mathbb{I}^{|\nu |}$ 是一个指示向量，指示节点 $v$ 处为1，其他为零，这个指标集的维数为 $|\nu |$ ，即节点个数。

最简编码处理方式：每个节点被分配一个唯一的Embedding vector，我们可以直接优化每个节点的嵌入向量。大致做法为先优化整个embedding矩阵，然后使用指示向量获得所需节点的Embedding。下图为浅编码的框架总结：

如何定义节点相似性

定义节点相似性的可能猜想，如果节点是相似的那么

两个节点是连接的？
有共享邻居节点？
有相似的结构表示？

后面将会用随机游走算法（random walks）来定义图节点的相似性，然后优化编码方式以近似图节点的相似结果。

节点嵌入的注意事项：

学习节点嵌入是一个无监督/自监督的方法
1. 不使用节点标签
2. 不使用节点特征
3. 节点嵌入的目的是直接估计节点的坐标以保证图结构的一些方面被保留
这些嵌入是任务独立的
1. 他们并不是针对一个特定的任务来训练，所以能够在其他任务中使用。

符号说明:

        向量 $z_u$ ：节点 $u$ 的embedding，这是我们要找的。
        概率 $P\left( v\mid \mathbf{z}_u \right)$ ：表示从节点 $u$ 出发以随机游走的方式访问到节点 $v$ 的概率.
        下面两个分线性函数被用来生成预测概率：
        Softmax函数：将K个实值组成的向量变成一个和为1的由K个概率组成的概率向量：

$\sigma (z)_i=\frac{e^Zi}{\sum_{j=1}^K{e^{Z_j}}}$

Sigmoid函数：是一个S形状的函数，能够将实值映射成(0,1)区间的值，此函数写作:

$S(x)=\frac{1}{1+e^{-x}}$

随机游走：给定一个图 $G$ 和一个开始节点 $v$ ，我们随机挑选这个节点的邻居节点 $v_{u_i}$ ，然后移到这个邻居节点 $v_{u_i}$ ，以这个邻居节点作为开始点重复这个过程。到达一定次数之后这个过程结束。在整个过程中访问的节点序列就是图上的随机游走。如下图所示：

随机游走嵌入： $\mathbf{z}_{u}^{\mathrm{T}}\mathbf{z}_v$ 表示 $u$ 和 $v$ 同时出现在图的随机游走过程的概率。

随机游走Embedding的执行步骤：

用随机游动策略 $R$ 估计从节点 $u$ 开始的随机游走中访问节点 $v$ 的概率。

2.优化这些embedding来编码随机游走统计参数。用embedding 空间中的相似性（这个相似性需要专门的二元函数来计算，如简单的内积）来编码节点经过随机游走算法得出来的”相似性“.

随机游走算法的好处：

表达性强。灵活且随机的节点相似性定义能够整合节点局部和全局的邻居信息。
1. 一个朴素的认知：如果从节点 $u$ 开始的随机游走过程以高概率访问到节点 $v$ ，那么节点 $u$ 和节点 $u$ 有“很强的关系“，他们是相似的。
高效。在训练过程中不需要考虑所有的节点对，仅仅需要考虑在随机游走过程中出现的节点对。

无监督特征学习：

目的。在d维空间中，找到能够保存图节点相似性的节点嵌入。
思路。在embedding空间中临近的节点在网络中连接的紧密。
给定一个节点，如何定义节点中连接紧密的节点？
1. $N_R\left( u \right)$ 表示以随机游走策略 $R$ 取得的节点 $u$ 的邻居。

Feature Learning as Optimization

给定一个图 $G\left( V,E \right)$
目标。学习一个映射 $f:u\rightarrow \mathbb{R}^d:f(u)=\mathbf{z}_u$ .
Log-likelihood 目标：

$\mathop {\max} \limits_{f}\sum_{u\in V}{\log}P\left( N_{\mathrm{R}}(u)\mid \mathbf{z}_u \right)$

4.给定节点 $u$ ，我们想要在随机游走过程中取得的邻居节点集 $N_R\left( u \right)$ 中学习节点预测特征表示。

随机游走优化过程：

大致思路：

用随机游走策略 $R$ 以节点 $u$ 作为起始点执行一个短的且固定长度的随机游走过程。
$N_R\left( u \right)$ 表示 $u$ 的随意游走访问的节点集； $N_R\left( u \right)$ 是一个多重集（multiset），即存在重复值。这符合随机游走过程的，因此很可能对某一个节点访问多次。
优化embedding是通过对给定的节点 $u$ 预测他的随机游走邻居 $N_R\left( u \right)$ 来实现

$\mathop {\max} \limits_{f}\sum_{u\in V}{\log}\mathrm{P}\left( N_{\mathrm{R}}(u)\mid \mathbf{z}_u \right) \Longrightarrow Maximum\,\,likelihood\,\,objective$ . (1)

等价于：

$\mathcal{L}=\sum_{u\in V}{\sum_{v\in N_R(u)}{-}}\log \left( P\left( v\mid \mathbf{z}_u \right) \right)$ . (2)

这里（1）变成（2）仅仅是将集合写成单个元素点的形式。

Intuition: 优化嵌入 $z_u$ 来最大化似然co-occurrences随机游走。

使用softmax函数来参数化 $P\left( v\mid \mathbf{z}_u \right)$

$P\left( v\mid \mathbf{z}_u \right) =\frac{\exp \left( \mathbf{z}_{u}^{\mathrm{T}}\mathbf{z}_v \right)}{\sum_{n\in V}{\exp}\left( \mathbf{z}_{u}^{\mathrm{T}}\mathbf{z}_n \right)}$

为什么使用softmax：我们希望节点 $v$ 是所有N个节点中与节点 $u$ 最相近的，而 $\sum_i{\exp \left( x_i \right)}\approx \underset{i}{\max}\,\,\exp \left( x_i \right)$ ,即与节点 $u$ 最相近的占主导。

最优化随机游走嵌入等于找到使 $\mathcal{L}$ 最小的 $z_u$ ，即是的在图中与节点 $v$ 最相似的节点在embedding空间中内积最大使得 $P\left( v\mid \mathbf{z}_u \right) \approx 1$ .但是这个双重求和的时间复杂度为 $O\left( \left| V \right|^2 \right)$ .

下面借用负采样[1]来降低复杂度问题，具体推导过程"负采样推导过程"。

有两个关于负样本的个数k的考量

更高的k表示着更好的鲁棒性
更高的k表示着越偏向于负样本，即得出的参数偏向于保证图结构中不相似的点，在embedding空间中不临近，但是不一定保证相似的点更加靠近。在实际中一般将k取为5-20.

在取得目标函数之后采用梯度或随机梯度下降法来解优化函数。梯度下降是使用所有样本来计算梯度，计算时间长，计算量大。随机梯度下降是使用一个样本来计算梯度，时间消耗短，但是梯度计算的随机性大；一般采样mini-batch梯度下降，即梯度和随机梯度的一个折中，主要思想是从样本中抽样一定数量样本进行梯度计算。此外梯度下降使用反向传播算法来更新参数值。

随机游走算法的总结：

对图中每一个节点都执行一次short fix-length 随机游走。
经过随机游走计算每个节点的随机游走邻居多重集合 $N_R\left( u \right)$ ， $N_R\left( u \right)$ 存放的是从节点开始经过随机游走算法得到的重复样点集。
用随机梯度下降法优化embedding（使用负样本来简化计算）

$\mathcal{L}=\sum_{u\in V}{\sum_{v\in N_R(u)}{-}}\log \left( P\left( v\mid \mathbf{z}_u \right) \right)$

如何执行随机游走

到目前为止，我们讨论了对于给定的随机游走策略，如何优化所需的embedding.但是并没有说明如何执行随机游走算法！最简单的想法：对每一个节点执行定长，无偏随机游走，即DeepWalk from Perozzi et al., 2013,但是这种执行方式好像不太好，有局限性。这有个扩展Perozzi et al. 2014.

Node2vector

目标：相似的网络邻居经过节点嵌入之后他们在特征空间的坐标也是临近的。
我们将这个目标建模为最大似然优化问题，且与后续的预测任务相互独立。
Key observation: 如果节点 $u$ 有灵活的网络邻域概念 $N_R\left( u \right)$ ，那么将会对更加丰富的节点嵌入。
开发2阶有偏随机游走策略来生成节点 $u$ 的网络邻域 $N_R\left( u \right)$ . 参考Grover et al. 2016.

有偏游走：

思路：使用灵活、有偏能够平衡网络中的局部和全局概念。

下面说明两个经典的定义节点 $u$ 的网络邻域 $N_R\left( u \right)$ 的算法，即广度优先搜索和深度优先搜索：

两种方法的特点：

BFS：关注节点邻居的微观结构
DFS：关注节点邻居的宏观结构

下面介绍对于BFS和DFS两个重要的参数

参数应用：使用有偏的2阶随机游走研究网络邻居。如下图

随机游走在边 $\left( S_1,W \right)$ 上穿梭，现在从 $S_1$ 回到 $W$
从内部看， $W$ 的邻居节点只能是 $S_1$ , $S_2$ , $S_3$ , 且 $W$ 到 $S_1$ , $S_2$ ,的距离相等，到 $S_3$ 的距离远于 $S_1$ .

Key idea: 记住游走过程的上一个节点。

随机游走在 $\left( S_1,W \right)$ 上游荡，现在在 $W$ 节点处，下一步怎么走？（其中 $p,q$ 是前面提到的模型转换概率）答：使用BFS和DFS算法

BFS和DFS算法在随机游走的性质是什么？参数 $p,q$ 应该怎么选择？

BFS选择较小的 $p$ . 我的理解是因此BFS在随机游走中主要关注邻居的微观结构，不偏向于走的太远，所以更可能走重复的路径。
DFS选择较小的 $q$ . 我的理解是因为DFS在随机游走中主要关注邻居的宏观结构，希望走的很深，很远，所以要避免走重复的路径，尽可能去距出发节点较远的点。

随机游走算法步骤：

计算随机游走的两个概率参数 $p,q$ .
对每一个节点模拟 $r$ 次长度为 $l$ 随机游走.
用随机梯度下降法优化ndoe2vec目标函数。

上述算法的特点：

线性时间复杂度
所有的3个步骤都可以独立并行计算。

其他的随机游走算法：

Different kinds of biased random walks:
1. Based on node attributes
2. Based on learned weights
Alternative optimization schemes
1. Directly optimize based on 1-hop and 2-hop random walk probabilities
Network preprocessing techniques
1. Run random walks on modified versions of the original network

Node2vec总结

核心思想:嵌入节点，使嵌入空间的距离反映原网络中节点的相似性。
节点相似度的不同概念:
1. Naïve: 2节点连接时相似
2. 邻域重叠(在第二讲中涉及)
3. 随机游走方法

总的来看随机游走算法在大多数情况下拥有比较好的性能。

Embedding Entire Graphs

目标：将子图或者整张图嵌入embedding空间。Graph embedding： $z_G$ .

任务：

分类有毒和无毒的分子
识别异常图。

方式一

最简单的方法：使用上面的节点嵌入方式得到所有的节点嵌入；然后对所有的节点嵌入求合或者求平均（被Duvenaud et al., 2016用来做分子分类）：

$\mathbf{z}_{\boldsymbol{G}}=\sum_{v\in G}{z_v}$

方式二

引入一个虚拟节点然后执行一个标准的图节点嵌入，将求得的虚拟节点嵌入作为整个图的嵌入（proposed by Li et al., 2016 as a general technique for subgraph embedding）。

方式三

匿名随机游走（Anonymous walk embeddings，Anonymous Walk Embeddings, ICML 2018 ）

匿名游走中的状态对应于我们在随机漫步中第一次访问该节点的索引。

匿名随机游走例子：

Step 1: node A $\Longrightarrow$ node 1

Step 2: node B $\Longrightarrow$ node 2 (different from node 1)

Step 3: node C $\Longrightarrow$ node 3 (different from node 1, 2)

Step 4: node B $\Longrightarrow$ node 2 (same as the node in step 2)

Step 5: node C $\Longrightarrow$ node 3 (same as the node in step 3)

Random walk2表示了同样的匿名随机游走结果。

游走内容 $w_i$ 的数量的大小与游走的路径长度有关。如游走长度为3，游走内容 $w_i$ 的数量为5：

$w_1=111,w_2=112,w_3=121,w_4=122,w_5=123$

匿名游走的简单使用：

设置随机游走的路径长度为 $l=3$
按照上面的图表得到，随机游走的内容最多为5，因此我们可以都得一个5维的向量。
$\boldsymbol{Z}_G[i]$ 表示 $w_i$ 在整个匿名游走的过程出现的概率。

随机游走的采样

抽样匿名游走：独立的生成集合数量为 $m$ 的随机walks。
将图表示成这个集合上的概率分布

存在一个关键问题：我们应该采样多少次，即随机游走数量 $m$ 应该为多少？

New idea：learn walk embeddings

不同于简单的将游走发生的次数作为不同游走的表示，这节学习匿名游走 $w_i$ 的嵌入 $z_i$ .

学习图嵌入 $Z_G$ 的同时学习所有匿名游走的嵌入 $z_i$ $Z=\left\{ z_i:i=1...\eta \right\}$ ,其中 $\eta$ 表示采样随机游走的个数。

如何嵌入walks？

思路：要得要嵌入walks要解决预测walks的任务，即给出一定数量某个节点的walks，然后利用这些walks预测下一步的walk（Anonymous Walk Embeddings, ICML 2018）。

步骤如下：

以节点 $u$ 原点执行T次长度为 $l$ 的随机游走得到 $N_R(u)=\left\{ w_{1}^{u},w_{2}^{u}...w_{T}^{u} \right\}$ .
利用采样得到的采样点，预测在 $\varDelta size$ 窗口内发生的walks（例如，给定 $w_1$ , $w_3$ , $\varDelta size=1$ 预测 $w_2$ )
估计匿名游走 $w_i$ 的嵌入 $z_i$ ， $\eta$ 是所有可能的游走嵌入数目

下面结合Anonymous Walk Embeddings, ICML 2018对上面一些我认为难理解的部分进行解释：

关于 $N_R\left( u \right)$ 的解释。 $N_R\left( u \right)$ 是以节点 $u$ 开始的匿名随机游走所有元素的集合。目标函数中的 $w_t$ 就是 $N_R\left( u \right)$ 中的元素。下图为使用 $w_1, w_2, w_3$ 来预测 $w_4$ 出现的概率，并计算出 $w_1, w_2, w_3, w_4$ 和图 $G$ 的嵌入。