图嵌入模型

图是复杂系统中常用的信息载体，可以表示现实中许多复杂关系，如社交网络、犯罪网络、交通网络等。图结构作为一种非欧几里德数据，很难直接应用卷积神经网络和循环神经网络。

为了构造用于图数据挖掘的特征表示，图嵌入将节点从高纬度空间映射到低维空间，生成保留原始图中某些重要信息的低维向量。（将图节点或者子图转换为向量）。主要应用于网络重构、系欸但分类、链接预测、聚类、异常检测和可视化。

定义

静态图：节点和边不随时间变化

动态图：按时间分布一系列演化图

一阶相似性：节点之间的成对邻近度，两个节点之间直接相连

二阶相似性：节点邻域结构的相似度，两个节点由相同的邻居

图嵌入：将每个节点映射成低微向量表示，保留原始图中某些关键信息

图嵌入分类

分为节点嵌入和整图嵌入

节点嵌入：将原始图上每个节点通过嵌入得到一个向量表达。可用于简单任务，如判断两个节点的相似性。

整图嵌入：将整张图通过嵌入得到一个向量表示。用于比较两个图的相似性。

图嵌入模型分类

基于矩阵分解的图嵌入

通过分解节点关系矩阵获得低维嵌入。不同的关系矩阵采用的分解方法不同 ，例如邻接矩阵通常使用奇异值分解（SVD）的方法生成节点嵌入，而属性矩阵通常使用特征值分解的方法。

静态图嵌入

基于矩阵分解的静态图嵌入模型对节点关联信息矩阵和属性信息矩阵进行特征分解，然后将分解得到的属性嵌入和结构嵌入进行融合，生成节点的低维嵌入表示

局部线性映射LLE将每个节点表示为相邻节点的线性组合，构造邻域保持映射。具体实现分为三步：

• 以某种度量方式选择k个邻接节点
• 由k个近邻线性加权重构节点，并最小化节点重建误差获得最优权重
• 最小化最优权重构建的目标函数生成Y

动态图嵌入

基于矩阵分解的动态图方法利用特征分解构造图的高阶相似度矩阵，然后利用矩阵摄动理论更新图的动态信息。DANE采用分布式框架：离线部分，采用最大化相关性的方法捕捉图结构和节点属性的依赖关系在线部分，使用矩阵摄动理论更新嵌入的特征值和特征向量。

基于随机游走的图嵌入

基于随机游走的图嵌入方法将节点转化为词，将随机游走序列作为句子，利用Skip-Gram 生成节点的嵌入向量。随机游走法可以保留图的结构特性，并且在无法完整观察的大型图上仍有不错的表现。

静态嵌入：基于随机游走的静态图嵌入模型通过随机游走获得训练语料库，然后将语料库集成到 Skip-Gram 获得节点的低维嵌入表示。

Deepwalk使用随机游走对节点进行采样，生成节点序列，再通过 Skip-Gram 最大化节点序列中窗口范围内节点之间的共现概率

Deepwalk不仅在数据量较少时有较好的表现，还可以扩展到大型图的表示学习。由于优化过程中未使用明确的目标函数，使得模型保持网络结构的能力受到限制。

node2vec在Deepwalk的基础上，引入有偏的随机游走，增加邻域搜索的灵活性，生成质量更高、信息更多的嵌入表示。通过设置 p 和 q 两个参数，平衡广度优先搜索和深度优先搜索策略，使生成的嵌入能够保持社区结构等价性或邻域结构等价性。

基于随机游走的动态图嵌入

CTDNE利用时间随机游走从连续型动态图中学习包含时间信息的嵌入表示，CTDNE 采用的时间随机游走与静态图方法相似，但约束每个随机游走符合边出现的时间顺序，即边的遍历必须按照时间递增的顺序，由于每条边包含多个时间戳，使得同一节点可能在游走中出现多次。

基于自编码器的图嵌入

自编码器使隐藏层学习到的表示维度小于输入数据，即对原始数据进行降维。基于自编码器的图嵌入方法使用自编码器对图的非线性结构建模，生成图的低维嵌入表示(SDNE)。

基于自编码器的静态图嵌入

基于自编码器的图嵌入方法起源于使用稀疏自编码器的 GraphEncoder。其基本思想是将归一化的图相似度矩阵作为节点原始特征输入到稀疏自编码器中进行分层预训练，使生成的低维非线性嵌入可以近似地重建输入矩阵并保留稀疏特性。

基于自编码器的动态图嵌入

基于自编码器的动态图方法将每个时刻训练的参数作为下一时刻自编码器的初始值，从而在一定程度上保持生成嵌入的稳定性，提高模型的计算效率。

基于图神经网络的图嵌入

图神经网络（GNN）是专门处理图数据的深度模型，其利用节点间的消息传递来捕捉某种依赖关系，使生成的嵌入可以保留任意深度的邻域信息。

基于图神经网络的静态图嵌入

基于 GNN的静态图模型聚合节点邻域的嵌入并不断迭代更新，利用当前的嵌入及上一次迭代的嵌入生成新的嵌入表示。

• GraphSAGE 不是为每个节点训练单独的嵌入，而是通过采样和聚合节点的局部邻域特征训练聚合器函数，同时学习每个节点邻域的拓扑结构及特征分布，生成嵌入表示。
• 图注意力网络（graph attention network，GAT）在 GCN 的基础上引入注意力机制，对邻近节点特征加权求和，分配不同的权值。

基于图神经网络的动态图嵌入

基于 GNN的动态图模型通常在静态图模型的基础上，引入一种循环机制更新网络参数，实现动态过程的建模，使生成低维嵌入可以有效保留图的动态演化信息。

• DyRep将动态图嵌入假设为图的动态（拓扑演化）和图上的动态交织演化（节点间的活动）的中介过程。
• DySAT通过邻域结构和时间两个维度的联合自注意力来计算节点嵌入，结构注意力块通过自注意聚集和堆叠从每个节点局部邻域中提取特征。