Knowledge-Based Systems 2023：基于注意力机制的图相似度学习探索

公众号新闻

2023-09-23 06:09

©作者 | 桑士龙

单位 | 南京邮电大学

论文标题：

Exploring attention mechanism for graph similarity learning

论文地址：

https://www.sciencedirect.com/science/article/abs/pii/S0950705123004896

代码地址：

https://github.com/AlbertTan404/NA-GSL

论文介绍

图相似度目前还存在三个问题：1）如何利用节点嵌入来融合局部空间邻域信息和全局上下文；2）如何从成对节点的角度有效地学习更丰富的跨图交互；3）如何利用图相似矩阵中的固有结构将相似矩阵映射到相似度得分。

为解决这些问题，本文探索了多种注意力机制进行图相似度学习：提出了一个统一的图相似度学习框架，包括（1）基于图卷积和图自注意力的节点嵌入学习混合模型；（2）用于图交互建模的跨图协同注意力（GCA）模块（3）图相似矩阵对齐的相似自注意力（SSA）模块；（4）图相似度矩阵学习用于预测相似度得分。

如图 1，现有的神经网络模型用于图相似度估计问题包括两个关键步骤：图嵌入学习和图相似度估计。但是局部结构难以通过全局嵌入来捕获，并且以往工作表明成对节点相似度机制比图级别嵌入的相似度计算更有效，可以捕获跨图之间的丰富的局部结构相似度模式。

贡献

提出了一种基于注意力的节点级图相似度学习，通过学习有效的节点级表示、建模成对节点交互以及相似矩阵中的细粒度节点相似度。对于具有复杂结构的图，从全局层面看两个结构不同的图是相似的，但子结构使图在语义上不同。
提供了第一个在图相似度学习中探索多头注意力潜力的研究，并研究了如何将注意力机制应用于图相似度学习，注意力机制以三种不同的方式引入：节点嵌入学习的图自注意力（GSA）、图交互建模的跨图注意力（GCA）以及用于融合和对齐不同语义层次相似矩阵的相似性自注意力（SSA）。

论文方法

给定两个图和，学习的目标是产生两个图之间的相似度分数，记为。本文提出的节点对注意力引导的图相似度学习（NA-GSL），包括四个模块：节点嵌入学习，图交互建模，相似矩阵对齐，相似矩阵学习，整体模型如图 2。

对于节点嵌入学习：由于高维图特征应嵌入到低维特征向量中用于下游任务，所以学习准确的图嵌入对于更好地学习图相似度至关重要。节点嵌入学习阶段负责将输入图转换为一组相应的节点嵌入。作者通过合并残差图卷积和图自注意力到图编码中以学习图嵌入：首先通过残差图卷积模块学习局部节点嵌入，然后采用图自注意力机制增强节点表示，以学习全局上下文信息。

图卷积层首先将节点嵌入与其邻居节点聚合,然后通过前馈传播转换嵌入。图卷积的主要问题就是存在过平滑，深层的图卷积模块可能导致节点表示质量的下降。因此，为了利用全局上下文并避免过平滑的问题，作者在图卷积层之间添加残差连接，以获得节点嵌入，

其中和分别是第 l 层的输入和输出。与图卷积相比，图自注意力允许在不考虑输入图中两节点距离的情况下建模任意两节点之间的远距离依赖关系。给定节点嵌入，通过线性映射计算第 m 个头的查询键和值：

图自注意力有助于提供更多全局上下文信息来增强节点嵌入。除此之外，由于图中节点之间存在自然关系，即两节点之间的相对距离。所以本文结合每两个节点之间的最短路径距离的归一化矩阵来增强表示。如果节点 p 和 q 的最短路径很大，则相对较小，表示两节点之间关系较弱，最终多头图自注意力GSA计算缩放点积：

其中r是常数，是一个缩放因子，是一个表示节点归一化距离的矩阵，。通过获得的注意力权重，可以得到第 m 个头的输出，并串联所有的输出从而得到最终的嵌入：

为了降低头的维度，多头节点特征送入前馈网络、残差连接和 LayerNorm 模块，得到更新后的节点特征。这个图自注意力模块能够通过利用非局部图上下文捕获每个节点与其他节点之间的相关性。对输入图中的任意两个节点建模依赖关系，还考虑了每个节点对的距离。混合图编码器通过结合局部图卷积和全局多头自注意力，显著增强了节点表示，从而促进了下一步的相似度计算。

为了捕获图之间的交互，现有方法首先将节点嵌入聚合形成对应的图级嵌入，然后通过图级表示的内积或余弦函数将一对图级表示映射到一个相似度分数。然而，这种简单的图相似度学习方式忽略了节点交互。因此，给定前一阶段生成的两个图的节点嵌入，本文提出了跨图协同注意力（GCA）模块来捕获两组节点嵌入之间的相关性。

以往的工作使用余弦函数，本文通过使用可学习的相似度评分函数。GCA 模块以任意两个图为输入，并输出它们的相似矩阵。给定一对图，其中一张图的节点视为查询，来自另一个图的节点视为键和值。

然后，计算注意力权重，以建模图 i 的第 p 个节点和图 j 的第 q 个节点之间的依赖关系，并同时考虑有向信息，提出一种有向节点-节点相似度学习方案，以充分捕获交互。

令和表示和的相似矩阵。使用掩码方法允许 GCA 模块对具有不相等大小的图建模节点-节点相似度。令 M 表示指示矩阵，其中每个元素表示是否是合法的节点对。对于图对 i 和 j，如果图 i 中的第 p 个节点和图 j 中的第 q 个节点存在，则，否则。

通过 GCA，两个图的节点嵌入，被转化为多个相似矩阵，每个矩阵对应一个头，并包含根据相应头计算的成对节点-节点相似度分数。通过跨图协同注意力机制，可以保留有向相似信息。

然后，作者沿头的维度连接两个有向相似矩阵以获得第一阶段相似矩阵，，它能够在建模节点-节点交互的同时保留有向相似特性。GSA 和 GCA 模块的参数和是共享的，GCA 充当相似矩阵生成层，用于对两个图的每对节点嵌入之间的关系进行建模，生成包含节点-节点交互分数的多个相似矩阵。

GCA 中的多头机制使得该模型可以从多个语义角度捕获丰富的信息。但是，不同头关注不同的语义模式并生成多个相似矩阵，阻碍后续的相似矩阵学习过程。因此，需要自适应地融合和校准这些信息。

给定 GCA 获得的掩码相似矩阵集，本文提出相似度自注意力（SSA）模块来消除通过沿相似矩阵方向进行自注意力操作引入的不一致性，这样注意力模块可以看作是对多个不一致相似矩阵的校准。

首先将每个掩码相似矩阵

视为 token，并将矩阵 reshape 为掩码向量。与原始自注意力不同，SSA 沿 reshape 后的相似向量轴进行自注意力计算，然后将相似向量归一化以平稳地传播梯度。再在相似矩阵上进行多头自注意力模块，即每个 sangs 8 通过三个线性层映射到和，其中表示此相似度校准多头模块中的头数。然后，通过自注意力公式计算更新后的相似矩阵：

通过对齐的相似向量，将其恢复为矩阵形式。通过沿相似矩阵方向利用自注意力机制进行相似度映射，SSA 模块能够通过有效捕获全局语义依赖关系来融合多级相似信息。对于具有大量节点的数据集，相似矩阵的大小很大，会增加计算复杂度。因此，在相似矩阵校准模块之前引入自适应池化层。

获得的相似矩阵对特定的图对 i 和 j 编码了特定的相似模式，目的是充分利用固有的结构和相似矩阵中的拓扑局部信息。作者在相似矩阵上提出了结构感知编码，它由两层组成：1）跨节点相似度编码层和 2）节点相似度学习层。为了对带有掩码元素的对齐相似矩阵应用结构感知编码，本文提出用零填充掩码部分来调整相似矩阵的大小，以保留相似矩阵的重要信息并固定大小。

为了捕获相似矩阵的基本拓扑表示，文中提出了跨节点相似度编码层（CSL），它通过聚合与两端节点相关的连接特征来利用相似度矩阵中的局部连接性。与 CNN 中的空间局部性不同，本文的局部性是指局部连接结构。如图 3，与图像不同的是相似度矩阵中不存在位置信息。因此，相似矩阵中的局部性表示与图 i 的第 p 个节点和图 j 的第 q 个节点相关联的所有行和列。

为了捕获局部信息，跨节点相似度编码层包含多个针对图中空间局部性的交叉形卷积核。令 M 表示跨节点相似度编码层的相似特征图，定义输入特征图。跨节点相似度编码层的交叉形卷积核是计算量较小的水平和垂直方向滤波器组合而来，这两个基础滤波器在每个位置进行单独的元素相乘，并在此对两个输出求和。跨节点相似度编码层定义为：

其中表示第 l 层第 p 和第 q 个节点之间连接的权重。CSL 的滤波器计算从第 q 个节点到第 p 个节点的所有连接上的权重之和。连接节点对包含了局部结构信息，这有利于节点相似度学习。

节点相似度学习层（NSL）以 CSL 增强的边嵌入为输入，并通过一维卷积滤波器将其映射以从节点视角生成节点嵌入。NSL 定义为：

其中是经过 NSL 的第 p 个节点的嵌入，是 NSL 中的通道数。图卷积层通过聚合自己的特征和邻居特征来更新节点表示，而 NSL 是通过聚合相关的边嵌入来获得节点表示的。

最终的训练损失为 MSE 损失：

实验结果

与 SimGNN 和 GraphSim 相比，NA-GSL 考虑了更合适的交互方式和更有效的相似度矩阵学习方法，从而获得了更高的准确率。NA-GSL 模型的提升有三个原因：1）更全面的节点嵌入学习；2）更合适的图交互和 3）更有效的图相似度学习。该结果从节点的角度揭示了局部相似性特征学习的重要性，以获得准确的图相似性得分。

表 3 到表 5 是不同数据集的消融实验，研究（i）节点嵌入学习过程中的残差连接、GSA 和节点距离感知；（ii）图相似度矩阵生成过程中的权重共享机制、GCA 和 SSA 模块；和（iii）. 图相似度矩阵学习过程中的 SSL。

去除 GSA 后，NA-GSL 的图相似度估计性能大幅下降，表明远距离依赖关系对节点嵌入学习至关重要，可以获得更好的性能。节点距离感知机制有助于 GSA 更有效地捕获非局部上下文。

测试了三个不同的图卷积模块，GraphSAGE 在 AIDS 数据集上表现最好，因为 GraphSAGE 在异构图上表现更好。从图 5 中可以看出，GCA 生成的相似度矩阵之间存在差距。此外，经过 SSA 后，不同语义层次的相似矩阵的 token 序列变得相似，这表明 SSA 对不同语义层次的相似矩阵对齐是有效的。

为了评估节点嵌入大小和头的数量如何影响我们的模型学习，进行参数敏感性分析，MSE 并没有随着节点嵌入规模的增大而减小，这表明较大的嵌入规模对于图相似度估计是不必要的，尤其是在 Linux 和 IMDBMulti 数据集上。在基于注意力的框架中加入更多的头，通常会带来更好的图相似性性能。可能的原因是，该模型可以从更多头部诱导的更多角度学习到更好的图相似性。

总结

本文旨在通过引入多个基于注意力的模块，从节点角度改进图相似性学习。图相似度学习有两个关键步骤：1）通过编码每个节点周围的特征和结构属性进行图嵌入学习；2）基于这些特征向量进行相似度计算。

然而，图嵌入学习忽略了节点周围的局部结构，图相似度计算方式没有充分建模节点交互，也没有充分捕捉相似矩阵中的细粒度局部结构。针对该问题，提出一种节点注意力引导的图相似性学习方法，专注于学习有效的节点级表示、建模充分的节点-节点交互以及利用相似矩阵中的细粒度节点相似性模式。最后通过实验证明了模型的性能。

更多阅读