本文是一篇计算机论文范文，本文对现有的GTs进行了改进并提出了EHDGT、MAEGT两个新的模型。
第一章引言
1.1研究背景与意义
图结构数据在现实世界中广泛存在，如社交网络、知识图谱等。图结构数据的复杂性和丰富性使其在理解和分析复杂关系的问题上具有独特优势。图表示学习旨在将节点、边乃至整个图转化为低维向量表示，从而实现对图结构数据的有效分析和挖掘。图G由节点V和连接节点的边E所构成，通常记为G=(V,E)。其中V={v1,v2,⋯,vn}代表节点集合，E={e1,e2,⋯,em}代表边集合。通常节点也被称为顶点或者交点，边也被称为链接或者弧。通用的图表示是一个五元组：G(V,E,A,X,D)，其中，A∈ℝn×n代表图G的邻接矩阵，X∈ℝn×d代表节点的特征矩阵，D∈ℝn×n代表度矩阵，n和d分别代表节点的数量和节点的特征维度[1]。
图神经网络（Graph Neural Network,GNN）[2]是一种被广泛认可的图表示学习工具，GNN通过构建多层模型，每一层在前一层的基础上通过消息传递机制[3]聚合局部邻域信息并且生成新的节点表示。尽管已经提出了许多不同的消息传递策略，但GNN仍存在一些局限性，其中包括有限表达能力[4-5]，过平滑[6]以及过挤压[7]等已知的问题。过平滑表现为所有节点表示在经过足够多的层之后变得过于相似而难以区分；而过挤压意味着远距离节点的消息无法进行有效传播，因为太多的消息被压缩到一个固定长度的向量中。因此，为了缓解这些问题，设计超越邻域聚合的新体系结构就显得至关重要[8]。
经过多年的发展，Transformer模型[9]及其变体已成功应用于三个最流行的人工智能领域：自然语言处理，计算机视觉和音频处理。Transformer通过并行化计算能够提升处理大规模数据的效率，并且在捕获全局信息方面更强，归纳偏差更小，因此在许多任务中表现出色[10]。此外，最近几年也出现了许多用于处理图数据的Transformer变体，它们被统称为GTs。GTs在许多应用中表现出了与GNN相媲美甚至更优越的性能[11]。
1.2国内外研究现状
1.2.1 Graph Transformer架构
Graph Transformer作为图结构数据建模领域一个较新的研究方向，引起了广泛的关注。现有的Graph Transformer架构可以分为两大类：第一类考虑将图的信息融入到Transformer中，赋予其对图数据的理解和处理能力，使得Transformer能够在图领域展现出更强大的性能；第二类架构则致力于将GNN与Transformer进行结合，充分发挥两者的优势，以实现对图数据更加全面的分析和建模[12]。Graph Transformer架构对比如表1-1所示。
第二章基础知识
2.1图表示学习
图表示学习，又称为图嵌入，其核心是找到一种映射函数，将复杂的图结构数据转换为低维向量表示。这些向量表示既要尽可能保留图的结构信息，如节点间的连接关系、邻居信息等，也要反映图的语义信息，如节点在图中的角色、功能等。在实际应用中，图表示学习具有非常多的意义。首先，与传统的手动特征工程不同，图表示学习能自动提取图中的关键特征，大幅提高了效率。其次，将高维图数据转换为低维向量表示，可以减少计算的复杂度，进而使问题更易于处理。此外，学习到的表示具有很强的通用性和灵活性，能够与多种机器学习和深度学习算法相结合，并可以应用于节点分类、链接预测以及图分类等多种不同的任务。这些特点使得图表示学习在现实世界中得到了广泛的应用。例如，在社交网络中用于好友和内容推荐，在知识图谱中进行实体链接和关系预测等。
综上所述，图表示学习凭借其强大的功能和广泛的应用前景，已经成为人工智能领域中一个极为重要的研究方向。它为我们处理和理解复杂的图结构数据提供了有力的工具，为解决各种实际问题带来了新的思路和方法。
2.2图神经网络
GNN和CNN在处理数据的方式和适用场景上存在显著差异。CNN主要用于处理规则的网格数据，如图像和视频，这类数据具有固定的邻域结构，可通过滑动卷积核来提取空间或时间上的局部特征。然而，图数据的拓扑结构通常不规则且具有复杂的连接关系，使得CNN难以直接应用于这类数据。GNN是一类专为处理图数据而设计的深度学习模型。如图2-1所示，它通过消息传递机制不断地更新并生成更为丰富的表示。接下来将对一些常见的GNN进行介绍。
第三章 融合 GNN 的 Graph Transformer ........................... 30
3.1 问题描述 .................................. 30
3.2 EHDGT模型的设计与实现 .................... 30
第四章 混合注意力机制的 Graph Transformer ...................... 43
4.1 问题描述 ................................ 43
4.2 MAEGT模型的设计与实现 ....................... 43
第五章 总结与展望 .............................. 57
5.1 总结 .......................................... 57
5.2 展望 ...................................... 58
第四章混合注意力机制的Graph Transformer
4.1问题描述
Transformer通过注意力机制能够更有效地建模节点之间的关系。因此，在将GNN和Transformer相结合的GTs架构中，使用Transformer替代GNN在理论上可能会带来更好的效果。然而，传统Transformer采用的是全连接的注意力机制，这种机制的计算复杂度随着节点数量的增加呈平方级增长，如果一个模型同时运用了多个Transformer，那么这将会致使它们在处理规模更大的图时，面临更为严峻的挑战。在不同级别的图任务中，图的外部信息，即不同样本之间的相关性，扮演着非常重要的角色。然而，现有的模型往往忽视这些信息，进而影响了它们的表达能力。针对图的多标签分类问题而言，通常使用二元交叉熵（BCE）损失函数来优化模型。但是原始的BCE损失无法针对不同任务进行调整，也无法有效解决正负样本不平衡问题，导致模型的效果不能达到预期。
第五章总结与展望
5.1总结
图结构数据在现实世界中非常常见，图表示学习旨在将这些图结构数据转化为低维的向量表示，这些学习到的表示能够帮助我们更好地分析其中隐藏的复杂关系，为后续的各种任务提供有力的支持。Graph Transformer是一种基于Transformer架构的图表示学习方法，凭借其出色的性能，越来越受到图领域研究者的关注。但是，大多数GTs在局部特征学习、边特征利用、计算复杂度等方面存在不足，这些问题限制了其在某些复杂图任务中的应用。为此，本文对现有的GTs进行了改进并提出了EHDGT、MAEGT两个新的模型。本文的主要工作总结如下：
（1）EHDGT受到Rampášek等人[13]的启发，采用了GNN和Transformer相结合的方式进行构建。具体来说，该模型引入了边级别的随机游走位置编码对原始图进行增强，经过增强后的图将分别作为GNN和Transformer的输入。传统的GNN只能从直接邻居处聚合消息，这在一定程度上限制了其表达能力。为此，引入了子图增强GNN，即使用GNN对输入图的局部子图而不是原图进行编码。标准的Transformer没有将边纳入考虑，而这些边特征对于图的表示和理解非常重要。针对这一问题，对Transformer进行了改进，使其可以更加全面地建模到节点之间的相关性。最后，为了更好地平衡局部和全局的特征，将每个GNN层与Transformer层的输出进行动态融合。实验结果表明，EHDGT在多个广泛且具有代表性的数据集上表现出色，展现出了强大的竞争力。
（2）由于单一的注意力机制无法全面建模图数据，因此提出了一种混合注意力机制的方法MAEGT。具体来说，在Transformer全局注意力机制的基础上引入了局部注意力、外部注意力和线性注意力。局部注意力使用Transformer对输入图的局部子图进行处理，这可以看作是对EHDGT中子图增强GNN的进一步改进；外部注意力通过共享的参数（外部单元）隐式地考虑了样本之间的共性特征，而现有的Transformer往往忽略了这些信息；线性注意力相对于具有二次复杂度的全局注意力来说具有更高计算效率，因为它不用计算每对节点之间的注意力。多标签分类任务通常使用二元交叉熵损失函数，但它无法根据不同的任务进行调整也不能解决正负样本不平衡的问题，因此引入了非对称多项式损失。在多个数据集上的实验结果表明，MAEGT能够在效率与性能之间取得良好的平衡。
参考文献（略）
