23430尺寸变化的深度图匹配的图上下文注意力网络0Zheheng Jiang, Hossein Rahmani, Plamen Angelov, Sue Black, Bryan M.Williams Lancaster University Bailrigg, Lancaster, LA1 4WA, United Kingdom0[z.jiang11,h.rahmani,p.angelov,sue.black,b.williams6]@lancaster.ac.uk0摘要0深度学习在图匹配方面受到了越来越多的关注，并在过去十年中迅速发展。尽管最近的深度图匹配方法在计算机视觉领域中在相等大小的图之间的匹配上表现出优秀的性能，但是在图像中的关键点数量可能因遮挡而变化的大小不同的图匹配问题仍然是一个开放且具有挑战性的问题。为了解决这个问题，我们首先提出将图匹配的组合问题形式化为整数线性规划（ILP）问题，这种方法更灵活高效，可以比较不同大小的图。然后，我们提出了一种新颖的图上下文注意力网络（GCAN），它可以同时捕捉内在的图结构和跨图信息，以提高节点特征的区分度，并通过节点对应关系监督来解决这个ILP问题。我们进一步展示了所提出的GCAN模型在解决图级匹配问题上的高效性，并能够通过图级匹配自动学习节点之间的相似性。我们在三个公开的关键点匹配数据集和一个血管图案图匹配数据集上评估了所提出的方法，实验结果表明其在关键点和图级匹配方面优于现有的最先进算法。01. 引言0图匹配是一种在图结构数据中建立节点对应关系的方法，具有广泛的实际应用，例如目标关键点匹配[1]、静脉图案匹配[2]和2D/3D形状匹配[3]。图匹配是一个众所周知的一般性NP难问题，通常被形式化为二次分配问题（QAP）[4]。最近，基于深度学习的图匹配方法表现出优于传统方法的性能。深度图匹配研究通常集中在两个方面：开发图嵌入和解决组合问题。0网络和解决组合问题。一般来说，深度图匹配的方法首先从深度卷积神经网络（CNN）中提取节点特征。由于具有相似的深度CNN特征的节点很难区分，设计了一个图嵌入网络来建模和改进节点特征，以期捕捉内在的图结构和跨图信息，以提高节点的区分度。受到流行的图卷积神经网络（GCN）[5]的启发，GCN及其变体被广泛用作图嵌入方法[6-9]。近年来，基于注意力机制来捕捉不同单词之间或不同图像部分之间关系的变压器模型[10-13]由于其优于传统CNN模型的性能而受到更多关注。受此启发，我们提出了一种新颖的图上下文注意力网络，以共同捕捉图内节点之间的关系和图之间的节点之间的关系。在组合问题方面，最近的研究将其形式化为Lawler的二次分配规划（QAP）问题[7,14]或Koopmans-Beckmann的QAP问题[6,9]。这些方法将节点对应问题视为二元分类任务。组合问题通常通过在预测的分类得分矩阵上执行匈牙利算法来解决。然而，这些方法假设图G2中的节点V2包括图G1中的所有节点V1，即V1�V2。如果V2中包含一些在V1中不可见的异常值，[7,14]建议添加虚拟节点以允许这些异常值在匈牙利算法中被分配。然而，在更一般的情况下，匹配图可能包含不同数量的节点，并且在测试期间两个图中的异常值的数量是未知的。我们观察到匈牙利算法在处理这种尺寸变化的图匹配问题时存在困难。此外，上述方法需要节点对应关系的监督，在本文中我们还探讨了无节点级标记的图匹配。0我们的主要贡献总结如下：01. 为了处理更一般和更具挑战性的图匹配问题23440对于具有大小不同的图的匹配问题，我们提出将组合问题形式化为整数线性规划问题。2.为了获得更具区分性的节点特征，我们提出了一种新颖的图上下文注意力网络，具有注意机制，以捕捉和建模内在的图结构和跨图信息。3.我们证明我们的网络可以以传统的监督方式进行训练，这是解决此类问题的典型方法，需要地面实况节点对节点的对应关系，或者以一种新颖的无监督方式进行训练。在无监督的情况下，我们通过在图级匹配上进行推理，避免了通常需要手动标记节点对应关系的要求，使我们的网络能够学习节点之间的相似性。4.我们在三个公共关键点匹配数据集上进行了大小相等和大小不同的关键点匹配任务的评估，并在一个血管图数据集上进行了图级匹配任务的评估。我们的实验结果表明，所提出的方法在所有任务上都优于当前最先进的方法。我们还进行了消融研究，展示了所提出方法的每个组成部分的有效性。02. 相关工作02.1. 图神经网络0由于其在图相关任务上的最先进性能，GNN引起了相当大的关注。GNN的基本思想是使用节点的消息传递函数来聚合来自图中邻居的特征消息。流行的图卷积网络[5]（GCN）通过使用均值池化操作来聚合信息来计算节点更新。GraphSAGE[15]将节点特征和均值/最大值/LSTM池化的邻域信息连接起来表示新的节点特征。图注意力网络[16]通过引入可训练的注意力权重来聚合邻域信息，在节点分类上取得了出色的性能。最近，[17]指出以前的模型无法区分网络中对称/同构位置的节点，并额外计算了目标节点到随机采样的锚点集的距离。02.2. 图匹配的学习0上述工作只利用了内在的图结构。对于图匹配任务，最近的工作主要集中在开发先进的图嵌入网络，其中编码了跨图亲和力信息和匹配一致性。例如，[6]将GCN与跨图节点嵌入层相结合，以重新表示图匹配任务。0通过骨干架构提供的节点嵌入来细化。[14]进一步开发了一个匹配感知嵌入模型，其中将预测的软分配分数与节点嵌入连接起来。为了解决图匹配任务中的组合问题，问题通常由[6, 7, 9,14]以Lawler的二次分配规划（QAP）问题或Koopmans-Beckmann的QAP问题的形式进行建模，可以使用匈牙利算法来解决。已经应用了几种组合损失函数来以监督方式训练图匹配模型。[6]证明了交叉熵排列损失相对于像素偏移损失具有更好的性能。[7]通过应用匈牙利注意机制进一步改进了他们的工作。[18]提出了一种成本边界损失，相对于传统的汉明距离损失对分布偏移更具鲁棒性，并被[8]采用为训练损失。最近，[9]应用了聚焦损失来解决类别不平衡问题。尽管上述大多数模型都使用匈牙利算法来离散化预测的匹配分数，但我们发现这种方法在处理大小不同的图时效率不高。此外，它们需要节点级别的标记进行监督训练，如何将GNN模型扩展到无节点级别标记的图匹配仍然是一个未解决的问题。在本文中，我们还通过在图级匹配上进行推理来探索节点之间相似性得分的计算。03. 提出的方法0我们的图上下文注意力网络的整体框架如图1所示。给定一对带有图形的图像，首先采用CNN通过双线性插值提取关键点特征，然后进行节点位置编码和通道注意力权重计算，以支持我们的GCA模块。我们的GCA模块（如图2所示）不仅设计用于建模有效的节点表示的内在图结构，还用于两个图之间具有k-hop邻域的根节点的相似度。整个模型的训练采用两种类型的损失函数，以实现端到端的训练。对于节点匹配，聚合和归一化所有GCA模块的匹配得分后引入整数线性规划（ILP）注意力损失。对于图级匹配，首先提出了图级聚合器来计算图级表示，然后使用基于边缘的成对损失来训练所提出的模型。03.1. 问题定义0给定两个图G1 = (V1, E1, U1)和G2 = (V2, E2,U2)，其中V1和V2是顶点集，E1和E2是边集，U1和U2由局部定义连接节点之间空间关系的伪坐标组成，我们的模型旨在生成23450图1：提出的基于transformer的图匹配框架的整体框架。节点特征从CNN网络中提取，然后进行位置编码和我们的图上下文注意力（GCA）模块。整个网络可以通过我们的整数线性规划注意力损失进行节点级匹配训练，也可以通过基于边缘的成对损失进行图级匹配训练。0相似度得分S = �sk�Vk1, Vk2�|Kk=1, s(G1, G2)�，其中sk�Vk1,Vk2�是两个图之间具有k-hop邻域的根节点的相似度得分，s(G1, G2)是向量空间中的图级相似度。03.2. 位置编码0在自然语言处理[10, 11]和基于视觉的任务[12,13]中，大多数transformer的实现中，首先引入位置编码/嵌入来捕捉序列中每个单词（一维）或网格中每个块（二维）的位置信息。然而，序列或网格的位置编码/嵌入方法是为规则数据设计的，不能直接应用于图形等不规则数据。尽管GNN能够捕捉图的结构信息，但忽略了节点在图结构上下文中的位置信息。为了在二维空间中编码位置信息，我们定义：0dposi = di +0j∈Ni dj ⊙ g(u(i, j)) (1)0其中di和dj分别是节点i和节点j的特征向量，⊙表示逐元素乘积，Ni表示节点i的邻居，g(.)是一个依赖于坐标u(i, j) = (|xi- xj|, |yi - yj|) = (∆xi, ∆yi) ∈ U1,U2的核函数。对于核函数的选择，我们采用了[20]中提出的B样条核函数，因为它在[8,14]中表现出了令人印象深刻的性能。令Nmvert,δ和Nmhor,δ'分别表示垂直和水平空间中的B样条基函数，0图2：我们的图上下文注意力模块由两个主要组件组成：跨图注意力层和自图注意力层。0具有δ * δ'的核大小。核函数定义为：0g(u(i, j)) = �0p ∈P ωp ∙ Nmvert,p(∆xi) ∙ Nmhor,p(∆yi) (2)0其中，ωp表示每个元素p的可训练权重向量，维度与di相同。P是B样条基函数Nmvert,δ和Nmhor,δ'的笛卡尔积，由此0个 δ � δ ′ 元素。03.3. 图上下文注意力模块0在这里，我们引入了GCA模块，通过保持两个图之间的结构相似性来建立对应关系。每个GCA模块由一个交叉注意力层和一个自注意力层组成，定义如下。0交叉注意力层在这一层中，使用注意力机制首先衡量节点之间的相似性ai′→i =exp��αh ⊙ h(k)i, αh ⊙ h(k)i′��ˆi′ expαh ⊙ h(k)i, αh ⊙ h(k)ˆi′(3)αh = tanh (Favg ∗ Wc + Fpool ∗ Wc)(4)fcr�h(k)i,�h(k)i′�i′ ∈V ′�=h(k)i�����i′ai′→i�h(k)i− h(k)i′�(5)fse�hcri ,�h(k)j�j∈Ni�=K∥k=1�j∈Niakj→ihcrj ∗ Ws(6)aj→i =exp��hcri ∗ Ws, hcrj ∗ Ws���ˆj exp��hcri ∗ Ws, hcrˆj ∗ Ws��(7)h(k+1)i=fse�hcri ,h(k)jj∈Ni�+ hcri(8)23460然后通过聚合这种跨图信息来改进节点特征。我们计算图之间的节点相似性如下：0其中，�∙ , ∙�表示内积，αh是一个用于利用特征之间的通道关系的通道注意力权重向量，受到最近流行的通道注意力模块[21]的启发。我们计算α h如下：0其中，F avg和Fpool分别表示从CNN模型的最后一个卷积层计算得到的平均池化特征和最大池化特征。W c ∈ R D F × Dh是一个可训练的权重矩阵，D F和Dh分别表示平均/最大池化特征F和节点特征h的维度。tanh(∙)是双曲正切函数。为了聚合这种跨图信息，我们使用a i ′ →i作为注意力系数，并定义如下：0其中，如果i ∈ V = V 1，则i ′ ∈ V ′ = V 2，或者如果i ∈V = V 2，则i ′ ∈ V ′ = V 1。∥表示连接操作，� h ( k ) i �0其中，i ∈注意力机制之前的节点表示集合0交叉注意力层。0自注意力层为了编码图结构，图卷积网络通常用于图匹配任务[1, 6, 9,22]。然而，这些模型在从邻域传递消息到中心节点时，对邻域赋予了相等的重要性，并忽略了邻域特征之间的关系。相反，我们利用注意力机制学习邻域的重要性，并提出了自注意力层：0其中，h cr i和h cr j是经过交叉注意力层后的节点特征，Ws ∈ R D cr × D se是一个可训练的权重矩阵，D cr和Dse分别表示经过交叉注意力层和自注意力层后的节点特征F的维度，a j →i是由第k个注意力机制计算得到的归一化注意力系数，定义如下：0根据上述定义，每个GCA模块可以表示为：0该架构具有一个很好的特性，即它能够将节点之间的相似性保留到下一个GCA模块，并且通过自注意力层改善节点特征的区分性。0图级聚合器提出的GCAN可以在有地面真实节点对应的情况下以监督方式训练用于节点匹配问题，如第3.3.1节所讨论的。要将GCAN应用于图级匹配问题或通过对图级匹配进行推理来学习节点之间的相似性，需要一个图级聚合器，它接收节点表示集合 � h ( K ) i �0i ∈V作为第K个GCA模块的输入，并计算图级表示，如下所示：0hG = 0i ∈ V σ � αG ⊙ h(K)i�WG' � � WG (9)0其中WG'和WG是可训练的权重矩阵。αG是类似于公式4的通道注意力权重向量，但使用从最后一个GCA模块计算的平均池化特征和最大池化特征。在图表示之后，可以通过在向量空间中使用欧氏、余弦或汉明相似性来计算G1和G2的配对图hG1和hG2的相似性。03.3.1 学习0所提出的模型以一对具有节点特征的图作为输入，可以训练用于节点级匹配问题或图级匹配问题。对于节点匹配，可以使用地面真实节点对节点对应进行监督式训练[6,9,14]。许多先前的工作[6,9,14,23]将节点匹配问题视为双射匹配问题，即在具有相同节点数的两个图之间进行节点匹配（参见图3），这可以通过匈牙利算法轻松解决。在这种情况下，在训练和测试过程中会对不可见和遮挡节点进行过滤。为了解决更灵活的分配问题，我们将其制定为整数线性规划问题，适用于双射节点匹配和非双射节点匹配。为了解决不可见和遮挡节点的分配问题，我们引入一个占位符，并定义m ∈M � 0，n ∈ N �0，其中m和n是源节点和目标节点的索引，0是“虚拟”节点的占位符。我们将此分配问题的一种可能解定义为：0θ ∈ Θ = {amn | amn ∈ {0, 1} m ∈ M � 0, n ∈ N � 0}(10)= mins.t.∀m ∈ M ∗,∀n ∈ N ∗,Lperm = −�i∈V1i′∈V2max {ai,i′, Yi,i′}�Yi,i′ log ¯Yi,i′+ (1 − Yi,i′) log�1 − ¯Yi,i′��(15)Lgraph =YG ∥hG1 − hG2∥ + (1 − YG) max {0, λ − ∥hG1 − hG2∥}(16)23470图3：节点匹配的描述。左侧显示了两个图的所有节点。蓝色实心圆表示可见节点。黄色三角形和绿色正方形分别表示G1和G2中的不可见节点。顶部和中间分支展示了最近的工作[6,9,14,23]如何解决双射匹配问题，其中关键点通过交集或包含过滤进行筛选。然后使用匈牙利算法解决方块亲和力矩阵中的节点分配问题。底部分支展示了我们的方法解决的更一般的节点匹配问题，不进行过滤。我们通过添加行和列的虚拟节点来考虑所有关键点进行匹配，这允许未匹配的节点被分配。0其中Θ包含所有可能的源到目标的分配。每个可能分配的得分定义为：0S（θ）=0n ∈ N � 0, m ∈ M � 0 S(amn)amn (11)0其中S（amn）是所有GCA模块的聚合和归一化得分。我们将分配问题重写为最小化问题：0Lt = min θ ∈ Θ −(log(S(θ)))0n ∈ N � 0, m ∈ M � 0 − (log S(amn) ∙ amn)(12)0n ∈ N � 0 amn = 1 (13)0m ∈ M � 0 amn = 1 (14)0约束（13），（14）确保每个源节点唯一分配给目标节点或虚拟节点，每个目标节点唯一分配给源节点或虚拟节点。然后应用分支定界算法[24]找到最优解。为了训练模型，由于地面真实节点对节点对应的稀疏性，使用交叉熵损失。0之前的方法倾向于向负样本反向传播更多的梯度，导致对负类的预测偏向。[9]使用的焦点损失能够通过引入类权重来处理这种类别不平衡，但类权重是用户定义的，且严重依赖于实验经验。为了解决这个问题，我们提出了一个整数线性规划注意力损失：0其中 Y i,i ′ 和 ¯ Y i,i ′ 分别是地面真实值和预测值，a i,i ′是ILP分配结果。如果两个图的节点数不同，则 i ∈ V 1 =M � 0 且 i ′ ∈ V 2 = N � 0 。否则，i ∈ V 1 = M � 且 i ′∈ V 2 = N �。请注意，在这个损失函数中，节点匹配被视为一个二分类任务，其中1和0分别表示匹配和不匹配。通过引入 a i,i ′，提出的模型将专注于最小化正样本和高ILP响应的损失。0对于没有给定节点标签的情况，提出的模型仍然可以通过我们的跨图注意力层计算节点之间的相似性分数。为了训练具有图级匹配的模型，我们使用欧氏相似性和基于边界的成对损失：0其中 Y G 是一个二进制标志，对于负样本对等于0，对于正样本对等于1，λ> 0 是一个边界参数。04. 实验0在本节中，我们在两种类型的任务上评估了提出的图网络：(i) 关键点匹配和(ii)图级匹配。我们使用三个公共关键点匹配数据集和一个血管图数据集将我们的图网络与现有的最先进方法进行比较。结果表明，我们的图网络始终优于所有其他方法。6:hcri← fcri′ ∈V ′�(Eq. 5)8:hsei← fsejNi�(Eq. 9)i,i′using branch-23480算法1 节点匹配的训练算法0输入: 图对 G 1 , G 2 ; 图像对 I 1 , I 2 ; 地面真实节点对应关系 Y �01: 通过双线性映射从CNN中提取关键点特征02:将从CNN中提取的关键点特征连接起来，以表示GCAN中的节点特征{03: 从CNN的最后一个卷积层计算平均池化特征 F avg和最大池化特征 F pool04: 对于每个attention模块k
下载后可阅读完整内容，剩余1页未读，立即下载
