本人UCAS课程作业，未经允许不得转载！ 本人UCAS课程作业，未经允许不得转载！ 本人UCAS课程作业，未经允许不得转载！

# 引言

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

为了构造用于图数据挖掘的特征表示，图嵌入将节点映射到低维空间，生成保留原始图中某些重要信息的低维向量。目前，图嵌入不仅在节点分类、链接预测、节点聚类、可视化等复杂网络上的机器学习任务中获得成功，还广泛用于社交影响力建模、内容推荐等现实任务。早期的图嵌入算法主要用于数据降维，通过邻域关系构建相似度图，将节点嵌入低维向量空间，并保持相连节点向量的相似性。这类方法通常时间复杂度高，很难扩展到大型图上。近年来，图嵌入算法转向扩展性强的方法。例如，矩阵分解方法使用邻接矩阵的近似分解作为嵌入；随机游走法将游走序列输入到 Skip-Gram生成嵌入。这些方法利用图的稀疏性降低了时间复杂度。

为了适应更好的下游任务，好的嵌入方法需要满足更多的要求。目前主要的挑战有：

（1）需要确保嵌入很好地描述了图的属性。它们需要表示图拓扑、节点连接和节点邻域。预测或可视化的性能取决于嵌入的质量。

（2）网络的大小不应降低嵌入过程的速度。图表通常很大，如一个普通的社交网络就可能拥有数百万人的交互，因此好的嵌入方法需要在大图上表现高效。

（3）较长的嵌入维度能保留更多信息，但同时会带来更高的时间和空间复杂度，用户需要根据需求做出权衡。

# 图嵌入

为了将图从原始图空间转变为嵌入空间，可以采用不同的模型来合并不同类型的信息，常用的模型主要包括矩阵分解、随机游走、深度神经网络。

# 基于矩阵分解的图嵌入

邻接矩阵通常用来表示图的结构，其中每一列和每一行代表一个节点，矩阵项表示节点之间的关系。可以简单地使用行向量或列向量作为节点的向量表示，但形成的表示空间是N维的，其中N是节点的总数。图嵌入旨在学习网络的低维向量空间，最终是找到一个低秩空间来表示网络。而矩阵分解方法与学习原始矩阵的低秩空间具有相同的目标，在一系列矩阵分解模型中，奇异值分解（SVD）由于其对低秩近似的最优性而常用于图嵌入，非负矩阵分解因其作为加法模型的优点而经常被使用。

局部线性映射（locally linear embedding，LLE）将每个节点表示为相邻节点的线性组合，构造邻域保持映射。具体实现分为三步：（1）以某种度量方式（如欧氏距离）选择 k 个邻近节点；（2）由 k 个近邻线性加权重构节点，并最小化节点重建误差获得最优权重；（3）最小化最优权重构建的目标函数生成Y。但是，该模型对k值的选择十分敏感，对最终的降维结果有极大影响。

拉普拉斯特征映射（Laplacian eigenmaps，LE）与 LLE 相似，也是从局部近似的角度构建数据之间的关系。LE 使用邻接矩阵建立包含局部结构信息的嵌入表示，并要求相连节点在嵌入空间中尽可能地靠近。

LE 的目标函数强调权值大的节点对，弱化权值小的节点对，导致原始图中的局部拓扑结构被破坏。为了增强图嵌入的局部拓扑保持性，柯西图嵌入（Cauchy graph embedding，CGE）引入距离的反函数来保持节点在嵌入空间中的相似关系，相比LE，CGE的目标函数更加强调短距离，即确保局部越邻近的节点在嵌入空间的距离越接近。

针对当前对动态图分析的需求，出现了更为通用的基于矩阵分解的动态图嵌入方法，DANE采用分布式框架：离线部分，采用最大化相关性的方法，引入 和 使拓扑嵌入 和特征嵌入 投影后的相关性最大化，捕捉图结构和节点属性的依赖关系，然后将前d个特征向量进行拼接，保持 和 在表示上一致；在线部分，使用矩阵摄动理论更新嵌入的特征值和特征向量。在t时刻，DANE对拓扑结构和节点属性进行谱图嵌入；在t+1时刻，DANE使用矩阵摄动理论更新 和 生成新的嵌入。

# 基于随机游走的图嵌入

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

DeepWalk使用随机游走来生成嵌入，随机游走从选定的节点开始，然后从当前节点移动到随机邻居，并持续指定的步数。其流程包含三步如图2所示。

（1）采样：通过随机游走对图进行采样。从每个节点执行很少的随机游走。作者表明，从每个节点执行32到64次随机游走就足够了，作者表明，良好的随机游走的长度约为40步。

（2）训练skip-gram：随机游走与word2vec方法中的句子相当。 Skip-gram 网络接受随机游走中的一个节点作为one-hot向量作为输入，并最大化预测邻居节点的概率。它通常被训练来预测大约20个邻居节点（左边10个节点，右边10个节点）。

（3）计算嵌入：嵌入是网络隐藏层的输出。 DeepWalk 计算图中每个节点的嵌入。

DeepWalk方法随机执行随机游走，这意味着嵌入不能很好地保留节点的局部邻域。Node2vec方法解决了这个问题。Node2vec是DeepWalk的改进版，在随机游走方面差异很小。它具有参数P和Q。参数Q定义随机游走发现图的未发现部分的可能性有多大，而参数P定义随机游走返回到前一个节点的可能性有多大。参数P控制节点周围微观视图的发现。参数Q控制较大邻域的发现。它推断出社区和复杂的依赖关系。

如图3所示为Node2vec中随机游走步骤的概率，从红色节点迈出了绿色节点的一步，返回红色节点的概率为1/P，而前往与前一个（红色）节点未连接的节点的概率为1/Q，前往红色节点邻居的概率为1。

Graph2vec基于使用skip-gram网络的doc2vec方法的思想，它在输入上获取文档的ID，并经过训练以最大化从文档中预测随机单词的概率，由于任务是预测子图，因此具有相似子图和相似结构的图具有相似的嵌入。如图4所示，Graph2vec方法包含三个步骤。

（1）对图中的所有子图进行采样并重新标记。子图是出现在所选节点周围的一组节点，子图中的节点距离不超过选定的边数。

（2）训练skip-gram模型。图表与文档类似。由于文档是单词的集合，因此图是子图的集合。在此阶段，训练skip-gram模型。它经过训练以最大化预测输入图中存在的子图的概率。输入图作为one-hot向量提供。

（3）通过在输入处提供图ID作为one-hot向量来计算嵌入，嵌入是隐藏层的结果。

# 基于图神经网络的图嵌入

GCN通常应用于固定图的直推式表示学习，GraphSAGE将其扩展到归纳式无监督学习的任务中，利用节点特征（例如文本属性、节点度）学习不可见节点的嵌入表示。如图5所示，GraphSAGE不是为每个节点训练单独的嵌入，而是通过采样和聚合节点的局部邻域特征训练聚合器函数，同时学习每个节点邻域的拓扑结构及特征分布，生成嵌入表示。相比GCN，GraphSAGE使用无监督损失函数强制邻近节点具有相似表示，远距离节点具有不同的表示。在给定下游任务的情况下，GraphSAGE能够替换或增加相应的目标函数，进行有监督或半监督学习，提升模型的灵活性；训练过程执行分批次训练，提升模型的收敛速度。

如图6所示，图注意力网络（graph attention network，GAT）在GCN的基础上引入注意力机制，对邻近节点特征加权求和，分配不同的权值。针对单个节点，GAT使用self-attention获得注意力系数，使用masked-attention将注意力分配到节点 i的邻域，使用multi-head attention生成节点嵌入。

注意力参数全图共享，大幅减少了参数占用的存储空间，同时GAT对所有邻居节点进行采样，较GraphSAGE得到的嵌入更具表征性。GAT的缺点在于使用二阶以上邻居时，容易导致过度平滑。

# 总结与讨论

图嵌入可以解释为生成图数据的向量表示，用于洞察图的某些特性。表1归纳了主要图嵌入的模型策略，同时总结了每种模型的缺陷。

表1 模型策略归纳

现阶段的主要任务依然是提升模型对大规模和复杂图数据的扩展性、创新模型方法和提高下游任务性能。

个人认为面向特定任务的嵌入仍具有较强的研究意义，大部分图嵌入模型生成的结果将用于节点分类、链接预测、可视化等多个任务。但对于具体的下游任务，不同的图嵌入模型对下游任务具有不同的效果，面向任务的嵌入模型可以只关注一个任务，并充分利用与该任务相关信息来训练模型。

本人UCAS课程作业，未经允许不得转载！ 本人UCAS课程作业，未经允许不得转载！ 本人UCAS课程作业，未经允许不得转载！

参考文献：

[0] Graph Neural Nets Explained: Summary of different graph embedding methods. | by Manish Chablani | Medium

[1] 袁立宁, 李欣, 王晓冬, & 刘钊. (2022). 图嵌入模型综述. Journal of Frontiers of Computer Science & Technology, 16(1).

[2] Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500), 2323-2326.

[3] Belkin, M., & Niyogi, P. (2001). Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems, 14.

[4] Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710).

[5] Grover, A., & Leskovec, J. (2016, August). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 855-864).

[6] Narayanan, A., Chandramohan, M., Venkatesan, R., Chen, L., Liu, Y., & Jaiswal, S. (2017). graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv:1707.05005.

[7] Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive representation learning on large graphs. Advances in neural information processing systems, 30.

[8] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2017). Graph attention networks. arXiv preprint arXiv:1710.10903.

[9] Cai, H., Zheng, V. W., & Chang, K. C. C. (2018). A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE transactions on knowledge and data engineering, 30(9), 1616-1637.

[10] Cui, P., Wang, X., Pei, J., & Zhu, W. (2018). A survey on network embedding. IEEE transactions on knowledge and data engineering, 31(5), 833-852.