TPAMI 2024 | 通过复制动态学习图注意力

文摘 2024-11-16 19:00 辽宁

点击下方“PaperEveryday”，每天获得顶刊论文解读
点击加入论文投稿、写作、阅读分享交流群

论文信息

题目：Learning Graph Attentions via Replicator Dynamics

通过复制动态学习图注意力

作者：Bo Jiang; Ziyan Zhang; Sheng Ge; Beibei Wang; Xiao Wang; Jin Tang

论文创新点

图复制器注意力（GRA）模型：提出了一种新的基于复制器动态的图注意力学习模型——图复制器注意力（GRA），该模型能够通过自监督的方式显式学习上下文感知和保留稀疏性的图注意力系数。
结构信息的融合：GRA模型能够充分利用图边缘的结构信息，通过注意力信息在不同边缘间的扩散/传播，捕捉边缘的上下文信息，而不是仅依赖于边缘或节点的特征，从而提高了图神经网络（GNNs）的性能。
理论和效率的双重优势：GRA不仅在理论上可以从能量最小化框架得到解释，而且在实际应用中具有高效的计算复杂度，类似于图卷积操作，可以简单高效地实现，并且能够有效缓解过平滑问题，提高模型在多个图学习任务上的表现。

摘要

图注意力（GA）旨在学习图边缘的注意力系数，在多种图学习任务中，GA在图神经网络（GNNs）上取得了令人印象深刻的性能。然而，现有的GA通常是根据边缘（或连接节点）的特征进行学习的，这未能完全捕捉边缘的丰富结构信息。一些最近的研究尝试将结构信息纳入GA学习中，但如何在GA学习中充分利用这些信息仍然是一个挑战。为了解决这一挑战，本工作提出了一个新的基于复制器动态模型的图注意力学习模型，称为图复制器注意力（GRA）。GRA的核心是我们基于复制器动态导出的稀疏注意力扩散，这可以明确地通过简单的自监督方式学习上下文感知和保留稀疏的图注意力。此外，GRA可以从能量最小化模型中得到理论解释。这为提出的GRA方法提供了更多的理论依据。在几个图学习任务上的实验表明，所提出的GRA方法在十个基准数据集上的有效性和优势。

关键字

图注意力网络
复制器动态
图扩散
图神经网络

I. 引言

图神经网络（GNNs）已被广泛研究用于图数据的表示和学习。例如，Kipf等人[1]提出了基于谱图卷积的一阶近似的图卷积网络（GCN）。Jiang等人[2]提出了一个统一的图学习-卷积网络（GLCN），用于联合优化图学习和图卷积模块。Klicpera等人[3]通过结合图卷积网络（GCN）和PageRank，提出了一种个性化传播神经预测（PPNP）的传播方案。Veliˇckovi´c等人[4]提出了一种无监督图嵌入方法Deep Graph Infomax（DGI）。Sergey等人[5]提出了一种通过特定能量函数实现图传播过程的新颖平衡聚合方法。众所周知，注意力机制已在神经网络中常用于增强学习能力。受此启发，设计了各种图注意力机制[6]-[12]。图注意力（GA）的目标是学习图边缘的注意力系数，如图1所示。由于其在执行许多图学习任务（如半监督学习、链接预测和图分类）方面的有效性，它已引起了越来越多的关注。例如，Veliˇckovi´c等人[6]提出了图注意力网络（GAT），旨在采用自注意力机制对每个边缘进行操作，并在加权图上进行消息传播。Wang等人[13]提出了异构图注意力网络（HAN），该网络结合了节点和语义级别的注意力，以同时学习节点和元路径的重要性。Ye和Ji[8]提出了SGAT，通过L0-范数正则化学习稀疏注意力。上述图注意力（GAs）通常利用自注意力机制和边缘（连接节点）内容特征来计算边缘的注意力系数。然而，众所周知，图数据包含边缘的丰富结构信息。例如，在现实世界的网络中，社区的“形状”通常包含彼此密集连接的节点。如文献[14]、[15]所示，鼓励将同一社区内的边缘分配更强的注意力，而不是不同社区之间的边缘。上述GAs[6]、[8]、[13]仅基于边缘的内容特征，因此未能充分利用GA学习中的边缘结构关系。

问题和相关工作为了解决上述问题，一些最近的工作尝试将结构信息纳入图注意力学习中[14]、[16]-[19]。主要流行的策略是首先将结构信息编码为节点描述符，然后将其与节点原始特征结合起来，以学习改进的注意力。例如，He等人[17]提出了图联合注意力网络（CAT），该网络同时结合节点特征和结构干预来计算图边缘的注意力系数。Zhang等人[14]提出了自适应结构指纹（ADSF）模型，该模型首先使用节点特征描述符编码局部结构细节，然后将其与节点原始内容特征结合起来，以学习最终的图注意力。Yang等人[18]提出了软序列与上下文注意力（SSCA），该模型可以自动发现最具辨识力的子结构，以优化邻域序列的顺序。显然，上述组合策略通常未能探索基于结构和节点特征的GA学习过程中的相关性。此外，通常不直接将边缘的结构信息表示为节点描述符。因此，如何充分利用边缘的丰富结构信息在图（边缘）注意力学习中仍然是图数据表示的核心挑战问题。众所周知，在普通的图卷积（GC）[1]、[20]基于图节点学习的图中，消息扩散（或传播）是捕获节点结构信息的核心机制。受此启发，自然提出了一个新问题：我们是否可以类似地为图（边缘）注意力学习设计一个GC类扩散，以利用边缘的丰富结构信息？这个问题的主要挑战有两个。C1：由于图注意力系数是为图边缘定义的，因此在本质上是结构稀疏的（如图1所示），因此在扩散过程中明确保留这种稀疏属性是必要的。这与普通的节点特征（或注意力）扩散[1]、[20]-[23]不同。C2：希望能够高效地实现图注意力扩散。最近，Wang等人[24]提出了多跳注意力图神经网络（MAGNA），该网络使用图扩散模型[25]进行图注意力学习。Chamberlain等人[26]将图神经网络视为偏微分方程的离散化，并提出了图神经扩散（GRAND）。然而，他们的图扩散模型[24]-[26]通常返回密集的图注意力，未能保留稀疏属性。因此，需要后处理稀疏化步骤[25]以获得最终的稀疏注意力，如图2（a）所示。然而，由于后处理稀疏化步骤与注意力学习独立，可能导致次优学习。此外，另一种可能的方法是首先构建线图[27]以表示边缘之间的邻接性，然后将边缘注意力学习重新表述为线图上的节点注意力学习。然而，这种方法通常需要高计算成本，特别是对于密集图。贡献。为了解决上述挑战C1-C2，本工作提出了一种新颖的图复制器注意力（GRA）用于图注意力学习，利用了一个新的复制器动态扩散模型[28]。我们GRA的核心优势有四个方面。首先，GRA可以通过在不同边缘之间扩散/传播注意力信息，充分利用边缘的结构信息。其次，GRA可以在其学习过程中自然保留图注意力的结构稀疏属性。因此，它不需要任何后处理稀疏化步骤，如图2所示。第三，GRA可以从能量最小化框架中得到理论解释。这进一步证明了GRA的自监督机制和稀疏属性。最后，类似于普通的图卷积[1]，GRA的计算基于（稀疏）邻接矩阵的乘积，因此可以高效实现。我们将GRA机制纳入GNNs，并提供了一个有效的图复制器注意力网络（GRAT）用于图学习任务。在十个数据集上的实验表明，所提出的GRAT模型在多个图学习任务上的有效性和优势。

II. 基于复制器动态学习图注意力

本节介绍了所提出的图复制器注意力网络（GRAT）的整个网络架构。我们将在第三节中进一步讨论我们的GRA。图3说明了所提出的GRAT的整体架构，主要包括i) 边缘自注意力，ii) 复制器注意力扩散和iii) 节点特征表示，如下所述。

A. 自注意力

设为输入属性图，其中表示节点，表示边缘。矩阵表示邻接矩阵，表示节点特征的集合。在GAT[6]中，它通过设计函数来计算每条边缘的注意力，如下所示：

其中表示特征转换矩阵，表示在图[6]上定义的softmax函数。表示亲和力函数。函数通常使用单层前馈神经网络定义，参数化为。在本工作中，我们计算函数，如下所示：

其中表示连接操作，表示一些非线性函数，如LeakyReLU。请注意，如果节点和\alpha_{ij} = 0\alphaA$具有相同的稀疏模式。

B. 通过复制器动态的注意力扩散

上述自注意力机制基于边缘自身的特征表示确定每条边缘的注意力，因此未能完全捕获边缘的结构关系。为了解决这个问题，我们开发了一种新的基于复制器动态的注意力扩散模型，以进一步捕获边缘的上下文信息。设为输入属性图，其中表示节点，表示边缘。设表示通过方程(1)计算的自注意力。然后，我们提出在图上扩散边缘注意力，如下所示：

其中，是度矩阵。参数是一个超参数，用于保留边缘自注意力项（方程(1)）。表示邻域归一化，定义为

。使用矩阵表示，方程(3)可以写成：

其中表示元素乘积。由于方程(3)是基于复制器动态模型[28]的规则导出的，因此在本文中，我们称为图复制器注意力（GRA）。备注：所提出的GRA模型的主要属性如下：

与常规图注意力（方程(1)）相比，GRA系数的每条边缘是通过聚合其相邻边缘的消息来学习的，因此在其学习过程中可以有效捕获上下文信息。GRA也可以从能量最小化的角度进行解释，如第三节所讨论的。
图注意力矩阵的固有稀疏属性在GRA学习中自然保留，即如果，则。这将在第三节进一步证明。
类似于图卷积[1]操作对于图节点学习，我们的GRA操作（方程(4)）具有简单的公式。复杂度分析：由于和都是稀疏矩阵，它可以被高效地实现为两个稀疏矩阵的乘积，即和。GRA的主要计算复杂度在于计算，大约是，其中表示边的数量，表示节点的数量。同时，在方程(4)中计算元素乘积和加法操作的复杂度是。因此，整体复杂度是，模型因此被高效实现。

C. 节点特征传播

基于图复制器注意力，然后将其纳入GNN的逐层消息传递，并进行节点信息传播，如下所示：

其中表示转换矩阵，表示非线性激活函数，如Softmax、ReLU等。为了稳定学习过程，我们也可以在这里采用多头策略[6]、[29]。

D. 实现

GRA基于逐层传播的完整实现总结在算法1中。图3显示了所提出的GRAT的整体架构。最后一层输出图节点的最终表示，用于下游学习任务，如聚类、半监督学习和可视化等。每层的最优层特定权重参数通过最小化某些损失函数（如交叉熵损失或自监督损失）通过Adam算法[1]进行优化。

III. 理论分析

在这一部分，我们展示所提出的GRA可以从能量最小化框架中得到理论解释。引理1。扩散方程(3)提供了以下问题的一步乘法解，

受限于，，以及如果则（方程(7)），

其中，，以及表示Frobenius范数。备注：方程(7)中的约束对于我们的边缘注意力传播是必要的，它们保证了注意力与原始输入对于所有边缘具有相同的稀疏模式，即如果图中断开节点和之间的连接，则。这是所提出的GRA的一个主要好处，与以前的注意力扩散方法[24]不同。上述方程(6,7)为所提出的GRA提供了直观的解释，其中第一项正则化项鼓励图上的注意力传播，而第二项拟合项表示在传播过程中保留基于原始特征的自注意力（方程(1)）。请注意，基于这种公式，我们可以推导出一些其他的图注意力学习的传播策略。例如，我们可以在拟合项中用L2,1/L1范数函数替换Frobenius范数来诱导一些鲁棒的注意力学习。这些可以在我们的未来工作中进行研究。引理1的证明。使用一些代数操作，问题方程(6)可以重写为

受限于，，以及如果则（方程(9)）。

设为注意力矩阵的第行。然后，使用矩阵公式，上述问题可以紧凑地重写为

受限于，，以及如果则。

其中，。这是一般的复制器动态问题[28]，可以通过乘法更新算法进行优化。具体来说，给定初始，可以推导出以下更新规则来解决上述问题：

其中。请注意，稀疏约束可以自然地在上述乘法更新规则中得到保证。同样，可以很容易地证明和的约束也可以在这个更新规则中得到保证。由于，这个更新的第一步（）变为：

这与我们的GRAT（方程(3)）相同。

A. 与相关工作的比较

本节讨论了我们的GRAT与其他相关的结构GAT变体的主要区别，包括图联合注意力网络（CAT）[17]、自适应结构指纹（ADSF）[14]、多跳注意力图神经网络（MAGNA）[24]和CaGAT[9]。首先，CAT和ADSF首先尝试将全局/局部结构信息编码为节点特征描述符，然后将它们与节点内容特征结合起来，以学习GNN的改进图注意力。相比之下，我们的GRAT方法采用复制器动态扩散策略来学习图边缘的结构感知注意力。它提出了一个更一般的学习方案。其次，我们的方法也与最近的基于扩散的注意力方法MAGNA[24]和CaGAT[9]不同。MAGNA在注意力矩阵上采用图扩散卷积（GDC）[25]，CaGAT采用张量乘积图扩散，计算成本高。然而，它们都没有考虑到结构化图的固有稀疏属性。此外，GDC[25]在其扩散过程中未能保留基于原始特征的注意力。相比之下，所提出的GRAT采用了特定的稀疏约束扩散模型，可以在其扩散过程中保持基于特征的注意力，并且可以简单实现。

IV. 实验

A. 数据集

对于传导学习任务，我们在六个基准数据集上测试我们的方法，包括三个引用网络（Cora、Citeseer、Pubmed）[30]，两个共同购买图（Amazon Computers和Amazon Photo）和一个共同作者图Coauthor Physics[31]。Cora、Citeseer和Pubmed[30]是评估GNNs在传导分类任务上广泛使用的数据集。Amazon Computers和Amazon Photo[31]是Amazon共同购买图的片段。这些数据集中的每个节点代表一个产品，边缘代表两个同时购买的产品。Coauthor Physics[31]是共同作者图数据，其中每个节点代表一个作者，边缘代表两个作者之间的共同作者关系。对于归纳学习任务，我们在Protein-Protein Interaction (PPI)[32]数据集上评估所提出的GRAT。它由24个对应不同人体组织的图组成。这些七个数据集的详细统计数据在表III中介绍。对于图分类任务，我们在包括一个生物信息学数据集（MUTAG）和两个社交网络（IMDB-BINARY和IMDB-MULTI）[33]的三个数据集上评估所提出的GRAT。MUTAG由188个平均每个图有17.9个节点的两类图组成。IMDB-BINARY是一个电影合作数据集，每个图平均有19.8个节点，所有图被分类为两个类别。IMDB-MULTI是IMDB-BINARY的多类别版本，所有图被分类为三个类别，每个图平均有13个节点。

B. 传导学习

我们在六个基准数据集上评估GRAT。对于所有数据集上的传导学习任务，随机选择每个类别的10个和20个标记节点作为训练集，其他每个类别的20个标记节点用作验证集。其余未标记的节点用于测试目的。在我们的实验中，我们随机生成十个不同的数据拆分，并报告所有数据集上的平均性能。此外，我们在Cora、Citeseer和Pubmed[30]数据集上提供与标准数据集拆分[6]的比较结果，即选择每个类别的20个节点作为标记节点，并为验证和测试选择500、1000个节点。结果是在10次运行中平均得到的。类似于标准GAT[6]的架构，我们采用两层架构，并使用多头机制。隐藏单元的数量设置为，其中是类别的数量。隐藏层的头数分别设置为。参数在方程(3)中对于所有数据集设置为0.43。训练的最大轮数是10000。如果验证集损失在100个轮次中没有下降，则停止训练，如以前工作[6]中建议的那样。网络权重矩阵通过Glorot初始化[34]进行初始化。我们通过最小化定义在标记节点上的交叉熵损失函数[1]、[6]来优化网络参数。我们将GRAT与其他一些GNNs进行比较，包括三个GCN模型，即GCN[1]、DropEdge[35]、GDEN[21]和五个基于注意力的GNNs，即GAT[6]、GAT-NetMF[17]、MAGNA[24]、SGAT[8]和CAT[17]。GAT-NetMF[17]是一种改进的GAT方法，首先通过NetMF[36]获得结构特征，然后使用GAT的消息传递机制进行图学习。比较方法的结果是通过运行作者提供的代码并根据工作[6]中的策略进行调整得到的。比较结果总结在表I中。在这里，我们可以观察到：（1）GRAT的性能优于GCN[1]、DropEdge[35]和GDEN[21]。这证明了所提出的基于注意力的GNN在进行图学习任务方面的有效性。（2）GRAT超过了其他最近的基于注意力的GNN方法，如GAT[6]、GAT-NetMF[17]、SGAT[8]和CAT[17]。这进一步证明了所提出的GRAT在传导图学习任务上的优势。（3）GRAT的表现优于同样采用图扩散技术的最近MAGNA[24]。这进一步表明了所提出的基于复制器动态的扩散机制的有效性。表IV进一步总结了在工作[6]中标准数据集划分上的比较结果。我们可以看到，我们的GRAT在这种数据设置上超过了其他比较方法。

C. 半监督节点聚类

按照实验设置[17]，我们使用与上述半监督节点分类任务相同的训练和验证集，并在测试阶段测试所有节点。实验参数设置与上述半监督节点分类任务一致。比较方法的结果是通过运行作者提供的代码获得的。比较结果如表II所示。我们可以注意到，我们提出的GRAT在所有数据集上的表现超过了其他GNNs和GAT，这进一步证明了所提出的GRAT在指导有效的GNN学习以进行图数据表示任务方面的有效性。

D. 归纳学习

我们在常用的PPI数据集[32]上评估所提出的方法，该数据集包含20个用于训练的图，2个用于验证，2个用于测试。类似于GAT[6]，我们采用具有跳跃连接的三层模型。所有层都有4个头，隐藏单元的数量设置为1024。我们遵循GAT[6]中的实验设置，并报告10次不同初始化的平均性能。对于归纳学习任务，我们将所提出的GRAT与其他一些流行方法进行比较，包括GraphSAGE[37]、GAT[6]、JK-Net[38]、IGNN[39]、SGAT[8]、CAT[17]和MAGNA[24]。对于MAGNA[24]，我们报告一次结果。所有方法的结果如表V所示。GRAT的表现超过了其他GAT变体方法，这进一步显示了所提出的GRAT在归纳图学习任务上的优势。

E. 图分类

遵循工作GIN[40]，我们报告10折交叉验证内的平均准确率。GRAT的隐藏单元数量从中选择，批量大小从中选择。我们将GRAT与WL子树核[41]和GNNs包括GCN[1]、GIN[40]、DropGIN[42]、基于注意力的方法GAT[6]和GAT-GC[43]进行比较。对于方法WL子树核、GIN、DropGIN和GAT-GC，我们直接使用他们的论文中获得的结果，因为它们都在与本文相同的数据设置下进行。对于GCN和GAT，由于它们没有在论文中报告分类性能，我们通过运行作者提供的代码并根据工作[40]中的策略调整以获得最佳性能来获得它们的结果。如图4所示，我们可以观察到：(1)GRAT在所有数据集上的表现优于GAT，这表明我们的注意力机制在指导可靠的GNN学习方面具有优势。(2)GRAT优于传统图分类方法。这进一步表明GRAT在这项任务上的有效性。

F. 链接预测

我们将所提出的GRAT应用于链接预测任务。所有方法都使用经典的GAE模型架构，其中层间卷积代码由作者提供。学习率和轮数分别设置为0.1和200。隐藏单元设置为32、16，所有基于注意力的方法的头数设置为4。其余参数设置与节点分类任务中的相同。表VI总结了Cora和Citeseer[30]数据集上的比较结果。可以观察到，我们的方法在不同评估指标上均取得了优越的性能。这表明GRAT在边缘识别任务上的能力得到了增强。

G. 参数分析

图5（左）显示了GRAT（方程(3)）中不同参数在两个数据集上的性能。我们可以观察到，(1)当时可以获得更好的学习性能。这表明通过保留基于原始特征的注意力进行GRA学习是有益的。(2)在一定的范围内，性能对参数不敏感，即大约在0.1-0.5之间。图5（右）显示了GAT和GRAT在两个数据集上不同网络深度下的性能。它表明GRAT可以比GAT更好地缓解过平滑问题。图6展示了GRAT在不同扩散步骤下的性能和运行时间（每轮）。绿线显示了GAT作为基线时的准确率。这里我们可以看到，(1)一步复制器模型可以获得理想的性能。(2)随着扩散步骤的增加，模型可以获得改善的性能，这证明了所提出的复制器动态在图注意力学习中的有效性。(3)随着扩散步骤的增加，计算时间增加。在实际应用中，我们可以使用一步复制器动态模型以考虑效率。

H. 可视化演示

为了展示GAT和GRAT学习到的注意力之间的差异，我们采用了一个差异度量指标[24]、[45]，定义为

，其中是每个节点的均匀分布得分，用于测量注意力的均匀性。这里，代表学习的注意力的均匀性，以反映注意力的丰富性。图8（a）显示了GAT[6]和GRAT在Cora[30]数据集上第一层输出的。它表明GRAT比GAT具有更高的非均匀性得分，这表明通过GRAT学习到的注意力更丰富。图7显示了在Zachary的空手道俱乐部数据集[46]上学习到的注意力的可视化。这里，我们展示了，其中。我们可以观察到：(1)对于同质邻居，即（表示节点的标签），我们的GRA权重通常比GAT大。(2)对于异质邻居，即，GRA权重通常低于GAT。此外，我们使用同质性得分[47]来衡量注意力的分布。它定义为，其中表示注意力（原始）矩阵，表示节点的标签。在Zachary的空手道俱乐部数据上，GAT获得了0.8351的同质性得分，而GRAT获得了0.8576。图8（b）还报告了每种方法在两个数据集上的平均同质性得分。总体上，我们可以观察到，通过纳入RD扩散，GRAT比包括结构编码注意力（我们称之为SEA）在内的其他一些图注意力学习方法获得了更高的同质性得分[19]，GAT，SGAT和CAT。这进一步证明，GRAT鼓励连接同一类别节点的边缘的注意力权重更高。直观上，这种属性对于图节点学习任务是有益的。

V. 结论

本文提出了一种新颖的图复制器注意力（GRA），用于学习GNNs学习中可靠的图边缘注意力。所提出的GRA是基于复制器动态导出的稀疏注意力扩散机制。GRA以自监督的方式简单实现，也可以从能量最小化模型中得到解释。使用所提出的GRA，我们然后提出了一个新颖的多层GRA网络（GRAT）用于图表示和学习。在多个图学习任务上的实验表明，我们的方法优于许多其他图注意力方法。

声明

本文内容为论文学习收获分享，受限于知识能力，本文对原文的理解可能存在偏差，最终内容以原论文为准。本文信息旨在传播和学术交流，其内容由作者负责，不代表本号观点。文中作品文字、图片等如涉及内容、版权和其他问题，请及时与我们联系，我们将在第一时间回复并处理。

#论文推广#

让你的论文工作被更多人看到

你是否有这样的苦恼：自己辛苦的论文工作，几乎没有任何的引用。为什么会这样？主要是自己的工作没有被更多的人了解。

计算机书童为各位推广自己的论文搭建一个平台，让更多的人了解自己的工作，同时促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 计算机书童 鼓励高校实验室或个人，在我们的平台上分享自己论文的介绍、解读等。

稿件基本要求：

• 文章确系个人论文的解读，未曾在公众号平台标记原创发表，

• 稿件建议以 markdown 格式撰写，文中配图要求图片清晰，无版权问题

投稿通道：

• 添加小编微信协商投稿事宜，备注：姓名-投稿

△长按添加 PaperEveryday 小编

http://mp.weixin.qq.com/s?__biz=MzI3NzI0MTk1OQ==&mid=2247503035&idx=2&sn=24a1d20b6bac7f46f3d43db971c2b117

PaperEveryday

为大家分享计算机和机器人领域顶级期刊