cs224w课程学习笔记-第3课

前言

为什么要做节点嵌入,节点嵌入可以揭示节点间的相似性;可以编码网络信息;可以用于更多下游应用.且节点嵌入是非监督或自监督的方法,无需要节点的标签,特征,仅估计节点的一组坐标变可实现原网络结构信息的保留.节点嵌入过程基本独立与实际任务,不同任务其嵌入是通用的.

一、嵌入原理

嵌入的目标是嵌入后的两个节点其相似性应该与嵌入前一致;对目标的分解,其嵌入步骤如下图:

1. 编码:将节点映射到嵌入空间中
2. 定义一个相似性函数衡量原图的相似性
3. 解码:计算嵌入后的相似分数
4. 优化目标得到:嵌入前后的相似性尽可能一致

由上述步骤,可以看到其核心是编码与构建相似性函数,解码可以将两个节点嵌入向量点积即可得.
简单的嵌入方法,一个节点一个嵌入向量,如Deep Walk,nodeo2vec.
在实际应用中,我们常常使用随机漫步来构建相似性函数,接下来介绍随机漫步原理

二、节点嵌入

1. 随机漫步

随机漫步原理如图所示,每一步随机选取相邻节点,重复该过程,直到漫步长度限制.

此时直觉上来讲,两个节点在随机漫步过程中一起出现的概率越大,两个节点的相似性越高.该关系表示为,以u为起点,漫步策略为R,其节点v出现的概率如下.实际相似性计算中不会计算起始节点外的所有节点相似性,而是计算其邻近点就好,这里的相邻点不局限于直接相连的节点,如果是直接相邻的那么就无法捕捉全局结构了.因此我们要先根据漫步策略确定其邻近点,然后统计.
若嵌入节点与嵌入前一致,其邻近点的出现概率也应与原节点接近,此时我们要计算嵌入后与相似性函数的一致性,则其总漫步概率越大越好,其目标函数如下所示:

其目标函数等价于取负,邻近集展开相加的函数.

但我们看到该目标函数的复杂度是$O(V{)}^2$,其核心是概率的分母很难计算.其分母可以通过负采样做近似计算.其k个节点一般从所有节点中随机选取.

处理好目标函数后,使用随机梯度下降进行寻优.
前面提到近邻点需要漫步策略去获得,漫步步伐太长过于复杂,过短全局信息又不够,最好是有一个可变步长的漫步策略,常用的如node2vec.

node2vec

可变的随机漫步包含了局部与全局的视野,其具体如下图所示,走一步,和走三步,其涉及范围显著不同.

抽象为数学参数为返回参数p,进出参数q,

其步骤如下

第2步以下图为例,以t为节点,漫步其邻近点,第一步到达W点的话,下一步W可以去往3个方向,返回t,去往s1,s2;返回的概率自然是1/p,s1是t的邻居节点为1,而s2两者均不是为1/p.

该算法的特点是

1. 计算边的转移概率：对于每条边 (u, v)，基于节点 u 和 v 的信息，计算出从节点 u 起点延伸出的边 (u, ⋅) 的行走概率。
2. 模拟从每个节点 u 开始的 k 次长度为 l 的随机游走。
3. 使用随机梯度下降法 (Stochastic Gradient Descent) 优化 node2vec 目标函数。

线性时间复杂度。
以上三个步骤均可独立进行并行化处理。

2. 矩阵分解

若节点u,v是相连的话,那么相似度一致性可以由相邻矩阵得到,由此目标函数也可转化为图示那样.


因此我们可以进一步通过矩阵的方式进行求解,下图所示的是Deepwalk方法的求解式子,前面的node2vec也可表达为这个形式,感兴趣的可以找找相关资料

三、图嵌入

1. 图嵌入最简单的方法就是将所有节点嵌入加起来
2. 建立一个虚拟的节点代表图,然后对虚拟节点进行嵌入
   如下图,还可对图分层进行嵌入
   

四、嵌入应用与局限

1. 应用

需要注意的是边的任务,需要根据节点的嵌入做一个处理

2. 局限

1. 本课程介绍的嵌入方法无法作用于不在训练集中的节点,也无法应用于新图.
2. 无法捕捉结构的相似性,如下图所示.
3. 无法利用上节点,边,图的特征,需使用深度表征学习或GNN
   

五、总结

本课程介绍了传统的节点嵌入方法,其核心思想是随机漫步,结合上相邻矩阵还可以使用矩阵分解的方式进行求解.最后根据节点嵌入可得到图嵌入与边嵌入,目前传统嵌入方法还是有较多的局限性的,因此一个嵌入方法不是所有的场景都能很好的适配(比如方法node2vec在节点预测表现要比边预测好),主要是要根据自己的应用需求匹配合适的相似性.