一文梳理图嵌入 (Graph Embedding)

Coggle数据科学 2023-09-15

357

图嵌入

本节内容主要参考自：

A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications [cai2018comprehensive]
Graph Embedding Techniques, Applications, and Performance: A Survey [goyal2018graph]
Representation Learning on Graphs: Methods and Applications [hamilton2017representation]

使用邻接矩阵的网络表示存在计算效率的问题，邻接矩阵使用的存储空间表示一个图，随着节点个数的增长，这种表示所需的空间成指数增长。同时，在邻接矩阵中绝大多数是 0，数据的稀疏性使得快速有效的学习方式很难被应用。

网路表示学习是指学习得到网络中节点的低维向量表示，形式化地，网络表示学习的目标是对每个节点学习一个实值向量，其中表示向量的维度。经典的 Zachary's karate club 网络的嵌入可视化如下图所示：

Random Walk

基于随机游走的图嵌入通过使得图上一个短距的随机游走中共现的节点具有更相似的表示的方式来优化节点的嵌入。

DeepWalk

DeepWalk [^perozzi2014deepwalk] 算法主要包含两个部分：一个随机游走序列生成器和一个更新过程。随机游走序列生成器首先在图中均匀地随机抽样一个随机游走的根节点，接着从节点的邻居中均匀地随机抽样一个节点直到达到设定的最大长度。对于一个生成的以为中心左右窗口为的随机游走序列，DeepWalk 利用 SkipGram 算法通过最大化以为中心，左右为窗口的同其他节点共现概率来优化模型：

DeepWalk 和 Word2Vec 的类比如下表所示：

node2vec

node2vec通过改变随机游走序列生成的方式进一步扩展了 DeepWalk 算法。DeepWalk 选取随机游走序列中下一个节点的方式是均匀随机分布的，而 node2vec 通过引入两个参数和，将宽度优先搜索和深度优先搜索引入了随机游走序列的生成过程。宽度优先搜索注重邻近的节点并刻画了相对局部的一种网络表示，宽度优先中的节点一般会出现很多次，从而降低刻画中心节点的邻居节点的方差，深度优先搜索反映了更高层面上的节点之间的同质性。

node2vec 中的两个参数和控制随机游走序列的跳转概率。假设上一步游走的边为，那么对于节点的不同邻居，node2vec 根据和定义了不同的邻居的跳转概率，控制跳向上一个节点的邻居的概率，控制跳向上一个节点的非邻居的概率，具体的未归一的跳转概率值如下所示：

其中，表示节点和之间的最短距离。为了获得最优的超参数和的取值，node2vec 通过半监督形式，利用网格搜索最合适的参数学习节点表示。

APP

之前的基于随机游走的图嵌入方法，例如：DeepWalk，node2vec 等，都无法保留图中的非对称信息。然而非对称性在很多问题，例如：社交网络中的链路预测、电商中的推荐等，中至关重要。在有向图和无向图中，非对称性如下图所示：

为了保留图的非对称性，对于每个节点设置两个不同的角色：源和目标，分别用和表示。对于每个从开始以结尾的采样序列，利用表示采样的节点对。则利用源节点预测目标节点的概率如下：

通过 Skip-Gram 和负采样对模型进行优化，损失函数如下：

其中，我们根据分布随机负采样个节点对，为采样的对的个数，为 sigmoid 函数。通常情况下，，即和的观测数量是不同的。模型利用 Monte-Carlo End-Point 采样方法随机的以为起点和为停止概率采样条路径。这种采样方式可以用于估计任意一个节点对之间的 Rooted PageRank 值，模型利用这个值估计由到达的概率。

Matrix Fractorization

GraRep

GraRep提出了一种基于矩阵分解的图嵌入方法。对于一个图，利用邻接矩阵定义图的度矩阵：

则一阶转移概率矩阵定义如下：

其中，表示通过一步由转移到的概率。所谓的全局特征包含两个部分：

捕获两个节点之间的长距离特征分别考虑按照不同转移步数的连接下图展示了情况下的强（上）弱（下）关系：

利用 Skip-Gram 和 NCE（noise contrastive estimation）方法，对于一个阶转移，可以将模型归结到一个矩阵的分解问题：

其中，和的每一行分别为节点和的表示，，为负采样的数量，为图中边的个数。

之后为了减少噪音，模型将中所有的负值替换为 0，通过 SVD（方法详情见参见之前博客）得到节点的维表示：

最终，通过对不同的表示进行拼接得到节点最终的表示。

HOPE

HOPE对于每个节点最终生成两个嵌入表示：一个是作为源节点的嵌入表示，另一个是作为目标节点的嵌入表示。模型通过近似高阶相似性来保留非对称传递性，其优化目标为：

其中，为相似矩阵，和分别为源节点和目标节点的向量表示。下图展示了嵌入向量可以很好的保留非对称传递性：

对于有多种可选近似度量方法：Katz Index，Rooted PageRank（RPR），Common Neighbors（CN），Adamic-Adar（AA）。这些度量方法可以分为两类：全局近似（Katz Index 和 RPR）和局部近似（CN 和 AA）。

算法采用了一个广义 SVD 算法（JDGSVD）来解决使用原始 SVD 算法计算复杂度为过高的问题，从而使得算法可以应用在更大规模的图上。

Meta Paths

matapath2vec

matapath2vec提出了一种基于元路径的异构网络表示学习方法。在此我们引入 3 个定义：

异构网络（(Heterogeneous information network，HIN） 可以定义为一个有向图，一个节点类型映射和一个边类型映射，其中对于有，有，且。
网络模式（Network schema） 定义为，为一个包含节点类型映射和边映射异构网络的的元模板。
元路径（Meta-path） 定义为网络模式上的一条路径，形式为。

下图展示了一个学术网络和部分元路径：

其中，APA 表示一篇论文的共同作者，APVPA 表示两个作者在同一个地方发表过论文。

metapath2vec 采用了基于元路径的随机游走来生成采样序列，这样就可以保留原始网络中的语义信息。对于一个给定的元路径模板，第步的转移概率为：

其中，，表示节点类型为的邻居。之后，则采用了类似 DeepWalk 的方式进行训练得到节点表示。

HIN2Vec

HIN2Vec提出了一种利用多任务学习通过多种关系进行节点和元路径表示学习的方法。模型最初是希望通过一个多分类模型来预测任意两个节点之间所有可能的关系。假设对于任意两个节点，所有可能的关系集合为。假设一个实例和包含两种关系：和，则对应的训练数据为。

但实际上，扫描整个网络寻找所有可能的关系是不现实的，因此 HIN2Vec 将问题简化为一个给定两个节点判断之间是否存在一个关系的二分类问题，如下图所示：

模型的三个输入分别为节点和，以及关系。在隐含层输入被转换为向量和。需要注意对于关系，模型应用了一个正则化函数使得的向量介于和之间。之后采用逐元素相乘对三个向量进行汇总。在最后的输出层，通过计算得到最终的预测值。

在生成训练数据时，HIN2Vec 采用了完全随机游走进行节点采样，而非 metapath2vec 中的按照给定的元路径的方式。通过随机替换中的任何一个可以生成负样本，但当网络中的关系数量较少，节点数量远远大于关系数量时，这种方式很可能产生错误的负样本，因此 HIN2Vec 只随机替换，保持不变。

Deep Learning

SDNE

SDNE提出了一种利用自编码器同时优化一阶和二阶相似度的图嵌入算法，学习得到的向量能够保留局部和全局的结构信息。SDNE 使用的网络结构如下图所示：

对于二阶相似度，自编码器的目标是最小化输入和输出的重构误差。SDNE 采用邻接矩阵作为自编码器的输入，，每个包含了节点的邻居结构信息。模型的损失函数如下：

由于网络的稀疏性，邻接矩阵中的非零元素远远少于零元素，因此模型采用了一个带权的损失函数：

其中，表示按位乘，，如果则否则。

对于一阶相似度，模型利用了一个监督学习模块最小化节点在隐含空间中距离。损失函数如下：

最终，模型联合损失函数如下：

其中，为 L2 正则项。

DNGR

DNGR提出了一种利用基于 Stacked Denoising Autoencoder（SDAE）提取特征的网络表示学习算法。算法的流程如下图所示：

模型首先利用 Random Surfing 得到一个概率共现（PCO）矩阵，之后利用其计算得到 PPMI 矩阵，最后利用 SDAE 进行特征提取得到节点的向量表示。

对于传统的将图结构转换为一个线性序列方法存在几点缺陷：

采样序列边缘的节点的上下文信息很难被捕捉。很难直接确定游走的长度和步数等超参数，尤其是对于大型网络来说。受 PageRank 思想影响，作者采用了 Random Surfing 模型。定义转移矩阵，引入行向量，第个元素表示通过步转移之后到达节点的概率。为一个初始向量，其仅第个元素为 1，其它均为 0。在考虑以的概率返回初始节点的情况下有：

在不考虑返回初始节点的情况下有：

直观而言，两个节点越近，两者的关系越亲密，因此通过同当前节点的相对距离来衡量上下文节点的重要性是合理的。基于此，第个节点的表示可以用如下方式构造：

其中，是一个衰减函数。

利用 PCO 计算得到 PPMI 后，再利用一个 SDAE 进行特征提取。Stacking 策略可以通过不同的网络层学习得到不同层级的表示，Denoising 策略则通过去除数据中的噪声，增加结果的鲁棒性。同时，SNGR 相比基于 SVD 的方法效率更高。

Others

LINE

LINE提出了一个用于大规模网络嵌入的方法，其满足如下 3 个要求：

同时保留节点之间的一阶相似性（first-order proximity）和二阶相似性（second-order proximity）。可以处理大规模网络，例如：百万级别的顶点和十亿级别的边。可以处理有向，无向和带权的多种类型的图结构。给定一个无向边，点和的联合概率如下：

其中，为节点的低维向量表示。在空间上，分布的经验概率为，其中。通过最小化两个分布的 KL 散度来优化模型，则目标函数定义如下：

需要注意的是一阶相似度仅可用于无向图，通过最小化上述目标函数，我们可以将任意顶点映射到一个维空间向量。

二阶相似度既可以用于无向图，也可以用于有向图。二阶相似度假设共享大量同其他节点连接的节点之间是相似的，每个节点被视为一个特定的上下文，则在上下文上具有类似分布的节点是相似的。在此，引入两个向量和，其中是做为节点的表示，是做为上下文的表示。对于一个有向边，由生成上下文的概率为：

其中，为节点或上下文的数量。在此我们引入一个参数用于表示节点的重要性程度，重要性程度可以利用度或者 PageRank 算法进行估计。经验分布定义为，其中为边的权重，为节点的出度。LINE 中采用作为节点的重要性，利用 KL 散度同时忽略一些常量，目标函数定义如下：

LINE 采用负采样的方式对模型进行优化，同时利用 Alias 方法加速采样过程。