超图匹配中的超图神经网络

1266G GGGGGGGGG G GG用于超图匹配的超图神经网络廖晓伟1，2徐勇1，2，3，*凌海滨4，*1华南大学计算机科学与工程学院技术，中国广州2鹏程实验室，深圳，中国3广东省通信与计算机网络实验室4美国纽约石溪大学计算机科学系liao. mail.scut.edu.cn，yxu@scut.edu.cn，hling@cs.stonybrook.edu摘要超图匹配是通过考虑高阶结构信息来找到特征对应的有用工具最近，深度学习的应用在图的匹配方面取得了很大的进展，这表明了它在超图方面的潜力。因此，在本文中，我们提出了第一，据我们所知，统一超图神经网络（HNN）的超图匹配解决方案。具体地说，给定两个待匹配超图，我们首先构造一个关联超图，并将超图匹配问题转化为关联超图上的节点然后，我们设计了一个新的超图神经网络，有效地解决了节点分类问题。端到端可训练，我们提出的方法，命名为HNN-HM，共同学习其所有组件与改进的优化。对于评估，HNN-HM在各种基准上进行测试，并显示出明显优于现有技术的优势。1. 介绍特征对应对于许多计算机视觉任务至关重要，例如形状匹配[2]，图像配准[17]和对象识别[26]。给定两组特征，特征对应旨在将一组中的每个特征通常，同一集合中的特征是相关的，并且具有固有的结构，这有利于相应的任务。使用特征之间的成对关系（二阶结构），可以从两个特征集（节点表示特征，边表示关系）构建两个图，并将相应的问题转换为图匹配问题[14，33]。类似地，为了结合更高阶的结构信息（即涉及两个以上特征的关系），可以构建两个超图并将问题转换为hy-*通讯作者。一DCBE图1.超图该超图具有五个节点（A、B、C、D）。D和E）和两个超边（{A，B，C}和{C，D，E}）。pergraph匹配问题[10，44]。一个超图（如图2所图1）是图的一般化，由每个超边捕获多个（通常多于两个）节点之间的关系的想法刺激超图匹配的任务是通过考虑两个给定超图的对应节点和超边的亲和度来寻找它们之间的节点对应关系。给定节点和超边的亲和性，超图匹配问题可以被公式化为具有挑战性的组合优化问题。大多数超图匹配算法集中在如何近似地解决优化问题[10，19，20，27，28，40，44]。虽然这些算法一直在推动性能的前沿，但由于手工制作的仿射和任务不可知的组合求解器，它们实际上是有限的。最近，深度学习的应用在图匹配问题的研究中取得了很大进展[12，30，36，39，41，42]，这表明其在超图匹配问题中的潜力。受上述工作的启发，在本文中，我们提出了第一个，据我们所知，统一的超图神经网络（HNN）超图匹配的解决方案（如图所示）。2）的情况。具体来说，给定两个待匹配的超图1和2，我们首先在它们上构造一个关联超图aa中的每个节点表示来自1和2的一对节点，并且a中的每个超边捕获来自1和2的两个超边之间的高阶关系。对于a，1之间的匹配和2转换为a上的节点选择问题。然后，我们提出了一种新的超图神经网络1267GGGGENCENC核心核心核心Dechaysspoecrigartaiopnh编码器核心解码器合并副本分类节点图2.我们提出的超图神经网络（HNN-HM）的说明。要匹配超图1和2、我们先构造并将匹配问题转换为a上的节点分类问题。分类问题，然后解决我们提出的HNN-HM，它包括几个超图神经网络块（编码器模块，核心模块，解码器模块）。编码器模块使用更新将Ga从输入空间变换到嵌入空间。函数（rCENCeENCvENC ，和g）独立地为每个属性然后多次应用核心模块进行更新Ga在嵌入空间中的状态，其中超边（r）的更新函数C核心e核心 ）的更新函数节点（v）和全局属性（g））顺序施加。 最后，解码器模块将将关联超图从嵌入空间映射到期望的概率空间，使用节点的更新函数（v）。解决节点选择/分类问题。提出的网络是由几个超图神经网络块。每个块接受一个关联超图作为输入，并返回一个更新的版本作为输出.具体地，在每个块中，与超边相关的节点属性将被聚合以更新超边属性;并且更新的超边缘属性也将被聚合以更新相关节点的属性。这样，将利用关联超图的结构来动态地更新其属性节点和超边更新操作都是移位不变的，从而放弃了最后，我们可以解码关联超图的更新状态，并将每个节点的属性重新解释为节点被选中的概率。所提出的方法，表示为HNN-HM，是端到端的可训练的，因此允许所有组件进行联合优化。特别地，它允许亲和学习和组合优化一起学习以吸收它们的交互。为了评估，HNN-HM在四个基准上进行测试，与七个最先进的超图匹配算法进行比较。结果清楚地表明，我们的方法比以前的解决方案的优势。综上所述，我们的主要贡献包括• 我们提出了第一个统一的超图神经网络（HNN）超图匹配的解决方案;• 我们将超图匹配问题转化为节点分类问题，并开发超图神经网络来解决它;• 我们在各种基准点上测试我们提出的HNN-HM，并获得最先进的结果。我们工作的源代码可以在https：//github.com/xwliao/HNN-HM网站。2. 相关工作2.1. 图匹配图匹配的算法可以大致分为两类：非基于学习的（例如，[722，25，38，43，45]）和基于学习的（例如，[第五、六、十二、二十三、三十、36、39、41、42]）。非基于学习的算法通常将图匹配视为二次分配问题（QAP），其已知为NP难的，并且通常通过放松损失函数或约束来追求近似解。其中，SM [21]将置换矩阵的约束放宽到单位Frobenius范数的矩阵，从而通过求亲和矩阵的主特征向量来基于此，进一步考虑仿射约束导致SMAC [9]。为了遵守离散约束，IPFP [22]将线性分配求解器和线搜索方法注入功率迭代算法。RRWM [7]将图匹配问题转化为关联图上的随机行走问题，并在其迭代子过程中引入约束PATH [43]将图匹配问题放松为凸优化问题和凹优化问题（具有相同的最优解），并使用路径跟踪策略近似求解一系列加权组合问题。BPF [38]通过检测奇异点并切换到更好的解决方案路径来改进路径跟踪策略。FGM [45]将图匹配问题中的亲和矩阵分解为更小的分量，并遵循路径跟踪策略迭代求解。GNCCP [25]遵循凸-凹松弛过程，而没有明确表达松弛。基于学习的算法参数化图匹配问题的一些或所有组件，并以数据驱动的方式学习这些组件。考虑到结构-，，，，，1268联系我们联系我们关于我们----输入图的作用，[6]建议学习任务驱动图用于不同的图匹配任务。GMN [42]设计了第一个端到端深度学习框架来解决图匹配问题。PCA-GM [36]采用图卷积网络[18]将图结构嵌入节点特征。然而，这两种深度学习算法仅学习图属性，并使用固定的Sinkhorn算法来找到特征对应解决方案。为了学习组合求解器，[39]将图匹配问题转换为关联图上的节点分类问题，并采用图神经网络来解决转换后的问题。虽然它已经取得了巨大的成功，但它仅限于二阶图。我们的工作受到[39]的启发，但打破了它的二阶图的限制，并表现得与它相当或更好。DGMC [12]使用图神经网络（GNNs）和Sinkhorn算法迭代地估计和细化节点对应性，并在SplineCNN [13]的帮助下， 它的性能相当好。BB-GM[30]不是学习组合求解器，而是嵌入现有的精心设计的组合求解器，并通过计算可微inter-matrix来以端到端的方式学习适当的特征提取器。通过处理迭代的一阶或二阶子问题来解决该问题。它的后继者[28]消除了对序提升的需要，并且还可以保证收敛。ADGM [19]将图匹配问题改写为一个等价的问题，该问题具有多个考虑不同约束的分解在[31]中，基于最初用于多目标跟踪的秩-1张量近似[32]提出了多超图匹配解决方案。最近，[37]将PCA-GM [36]方法扩展到超图和多重图匹配。3. 超图匹配问题本节介绍超图和超图匹配问题的形式化。3.1. 超图对于一个具有Nv个节点和Ne个超边的属性超图1，我们用Vi和Vi表示它的第i个节点和相关的属性向量，用Ej和ej表示它的第j个超边和相关的属性向量.因此一个属性超图可以由5元组G=（V，E，V，E，g）指示，其中组合求解器的极化基于他们以前的• V={V}指示节点的集合;工作[35]。通过使用SplineCNN [13]提取节点嵌入，BB-GM [30]获得了非常令人印象深刻的结果。2.2.超图匹配与图匹配相比，对超图匹配的研究相对较新[10，19，20，24，27，28，37，40，44]，并且这些方法中的许多是先前图匹配算法的直接扩展TM [10]是SM [21]的推广，通过估计仿射张量的秩-1近似，找到了超图匹配问题的近似解。[24]中的工作介绍了对超图匹配的学习，并提出了一种执行顺序二阶近似的超图匹配算法（基于IPFP [22]）。RRWHM[20]将超图匹配问题转换为关联超图上的随机行走问题，并以与RRWM [7]类似的方式解决它。从概率的角度出发，假设节点之间的匹配是独立的i1≤i≤Nv• E={Ej}1≤j≤Ne表示超边的集合• V=vi1iNv表示与每个节点相关联的属性向量的多集合;• E=e_j_l_j_N_e指示与每个超边缘相关联的属性向量的多集合;以及• g表示与整个超图相关联的全局属性向量此外，还有一些相关的概念如下• K-一致超图：每个超边恰好与K个节点相关联;• 无向超图：每个超边是V的子集，例如，E1={V1，V2，V3};• 有向超图2：每个超边是包含来自V的元素的元组，例如，E1=（V1，V2，V3）。在本文中，我们将超边（Ej）定义为K元组，其元素是V的子集：Ej=（E（1），E（2），. . . ，E（K））1 ≤ j≤ Ne，（1）在已知要匹配的两个超图的结构之后，HGM [44]将问题简化为线性哪里j j j（k）分配问题，可以解决准确和有效。HADGA [40]将超图匹配问题近似为使用先前解决方案的顺序线性分配问题。虽然它可以避免后离散步骤，并有收敛性的承诺，它是困扰的次优逼近。针对两个3-一致超图的匹配问题，BCAGM[27]将三阶问题转化为具有相同解的四阶多线性问题，然后Ej V1≤k ≤ K。（二）因此，无向超边是K =1时的特殊情况，并且可以由（ Vi1， Vi2，. . .，Vin），或Vi1，Vi2，. . . ，Vin。 我们可以用（Vi 1）表示K-一致有向超边 、Vi2 ，的。. .、ViK），或（Vi1，Vi2，. . . ，V1K）。因此，本附注-它可以灵活地表达各种超边。1我们不加区别地使用超图和属性超图2这里定义的有向超图与[15]不同。1269V E G V EGV EG V E0,J我ΣPJJJJJJ我JJJJ1J2JK我我我JGJ3.2.超图匹配问题给定两个K-一致有向超图1=（1，1，二、2，V2，E2，g2），我们想找到它们之间的节点对应关系考虑节点亲和度（cij=θv（v1，v2））和超-属性超图′=（，，V′，E′，g′）作为输出。它使用超图结构（，）来更新属性（V，E，g）并保持超图结构未被污染。设每个超边都是一个子集的K-元组（定义在Eq.（1）），我们可以定义一个边缘亲和性（I je1个2个HNN-HM块作为DIJ =θ（eI，eJ））。如果没有基因活性的丧失，我们假设。V1. ≤。V2。.e′=Φe（ej，V（1），V（2），. . . ，V（K），{g}），（6a）节点对应关系可以由as表示分配矩阵X∈{0，1}|V1|×个|V2|被定义为v′=Φv（vi，E（1）′，E（2）′，. . . ，E（K）′，{g}），（6b）.1 如果V1匹配V2，g′=Φg（g，V′，E′），（6c）其中（1≤k≤K）Xi，j=Ij0否则。（三）V（k）=. vi|Vi∈ E（k） 1 ≤ i ≤ N vΣ，（7）并且所有的亲和度都可以用亲和度张量3来表示E（k）′=. e′|Vi∈ E（k）1≤j≤NeΣ，（8）A ij，…Ij =cijifi=ik∧j=jkk，dIJifE1∈E1∧E2∈E2，（四）V′={vi′ |1 ≤ i ≤ N v}，（9）E′=. 埃杰|1 ≤ j ≤ N eΣ。（十）1 1K KIJ否则当量（7）指出，对于超边Ej中的第k个节点集E（k），我们将所有相关联的节点属性收集到一个其中I是对应于（i1，i2，. . . ，i，K）（一个多集V（k）。类似地，Eq.（8）表示对于每个节点1），E1=（V1，V1，. . . ，V1）是V的任何可能的K元组Ii1i 2iK节点从1，并且E2=（V2，V2，. . . ，V2）。给定亲和张量，超图匹配问题可以形式化为优化问题：i中，我们首先找到在其第k个节点集中包含该节点的所有超边，然后收集所有相关联的超边属性（其已经在等式1中更新）。（6a））转换为多集E（k）′。因此，更新函数Eq.（6a）聚合所有MaxX∈Pi1，…iK，j1，…JKAi1j1，……iKjKXi1，j1···X iK，jK、（五）与超边相关的节点属性，然后使用它们（与全局属性组合）来更新该超边的属性。之后，通过使用Eq.（6b），每个节点将通过聚合所有相关的hy来更新其属性。哪里是（部分）置换矩阵的空间，响应于一对一（至多）约束。超图匹配求解器存在两个主要挑战。一个是不完美的亲和张量（通常是手工制作的），另一个是优化问题的内在硬度。大多数以前的超图匹配算法集中在第二个挑战，找到一个近似的解决方案。然而，我们通过在统一的超图神经网络中共同学习亲和力和组合求解器来处理这两个挑战。1270ΣΣΣ4. 提出的超图神经网络本节提出了一种通用超图神经网络（HNN-HM）框架。如何将其应用于超图匹配问题的细节将在第5节中解释。4.1. 超图神经网络块所提出的超图神经网络由一堆超图神经网络块（HNN-HM）peredge 属 性 和 全 局 属 性 。 最 后 ， 使 用 Eq. 在 步 骤（6c）中，将通过聚合节点和超边的所有更新的属性来更新全局属性注意，等式（1）中的所有更新函数都是(6)共享表单y′= Φ（y，X1，X2，. . . ，XN）（11）其中每个Xt是包含具有相同维度的向量的多集。通过引入归约函数xt=Ψt（y，Xt） 1≤t ≤ N，（12）我们可以进一步限制等式（11）要有形式y′=（y，x1，x2，. . . ，XN），（13）其中，通常是一个可学习的神经网络。Ψ（y，X）（忽略下标t）的一些有用的约简函数是Ψsum（y，X）=Ψsum（X）=X;（14）x∈X块）。每个HNN-HM块接受属性超图G=（V，E，V，E，g）作为输入，并返回更新Ψ均值 （y，X）=ψ是说⑵=lx;（15）|X|x∈X3为简单起见，任何超边的所有节点都不完全相同。请注意，亲和张量的大小为。. V1. ·V2。ΣK，但它通常是稀疏的。Ψatten（y，X）= attention（y，x）·x。（十六）x∈X1271合并副本解码器核心编码器我.Σ我 JI1IKJ1JK图），如果我们让Ej=（{第j个尾节点}，{第j个头节点}）IJI1J1I2J2IKJKIJi1j1i2j2iKjKIJ我JIJ我J我 J我J我 J我JIJ我 JJ.ΣIJ.ΣE=. E|E ∈ E ∧ E ∈ EΣ，（20）.| ∀∈ V ∧∈ VΣ输入输出图3.一个具有递归的编码-处理-解码模型。5.1.关联超图考虑一对K-一致有向超边（分别来自两个超图G1和G2）：. E1，E2Σ =..V1，. . . ，V1Σ，.V2，. . . ，V 2ΣΣ，（17）我们可以重新安排对于2-一致有向超图（即 有向Ea=..V1、V 2Σ、.V1、V 2Σ、. . . ，的。V1，V2ΣΣ（18）表示每个超边并且令Ψ（y，X）=ψ（X），则我们的HNN-HM块退化为GN块[1]。由于所有超边共享相同的更新函数当量(6a)并且所有节点共享相同的Eq.（6 b）我们的亲-关联超图的概念背后的启示是：我们可以将Va=V1，V2视为一个新的超图和关于Ea=. Va，V a，. . . ，V aΣ as假设的HNN-HM块具有与GN块[1]相同的益处：它不假定超图的特定结构，并且可以应用于任意K-固定4超图。此外，通过添加不同种类的超边，让每一种都拥有自己的更新功能，建议HNN-HM块可以包含更多类型的信息。4.2.超图神经网络HNN-HM块是我们的HNN-HM的核心。我们可以多次运行一个块或堆叠不同的块以控制不同类型/级别的信息聚合。K个节点）。的所创建的新超图是关联超图。更具体地说，两个K-一致有向超图（G1和G2）上的关联超图可以定义为具有以下分量的K-一致有向超图Ga=（Va，Ea，Va，Ea，ga）Va = V a|V 1∈ V1 ∧ V 2∈ V2，（19）a a1 1 2 2Va=θv（v1，v2）V1 1V2 2，（21）Ea=.θe（e1，e2）|E1∈E1∧E2∈E2Σ，（22）在[1]之后，我们使用具有递归结构的编码-处理-解码模型（参见图1）。（3）第三章。架构中的所有组件（编码器模块、核心模块和解码器模块）是HNN-HM块。编码器模块将输入超图从输入空间变换到适合于稍后处理的嵌入空间。之后，多次应用核心模块以更新超图在嵌入空间中的状态最后，解码器模块将超图从嵌入空间转换到期望的输出空间。5. 超图匹配在超图匹配问题和所提出的HNN-HM之间仍然存在差距：我们有两个要匹配的超图，而建议的网络接受ga=θg（g1，g2），（23）其中θv、θe和θg是用于合并来自两个超图的属性的任务特定函数。对于超图匹配问题，可以使用预定义的节点亲和度函数和边亲和度函数分别作为θv和θe。5在本文中，我们简单地按照[39]通过连接合并属性。若对有向结合超图中的每个超边（Ea），它的所有置换点都是超边并且这些超边具有相同的属性，则有向关联超图可化为无向关联超图。由于我们有一个关联超图构造的两个超图进行匹配，我们可以把超图匹配问题转化为一个节点选择问题的关联超图。特别地，如果选择关联超图中的节点Va=V1，V2图分开，然后将它们传递到组合求解器。然而，这可能受到组合求解器的次优性的影响。相反，我们将匹配问题转换为关联超图上的节点分类问题，并将其传递给我们的HNN-HM。在本节中，我们首先解释关联超图的创建，然后详细说明我们的HNN-HM框架的所有组件4它确实要求K对于所有输入超图都是相同的。超边缘（带有only one.可以使用HNN-HM来更新每个超1272IJ该节点选择/分类问题可以使用所提出的HNN-HM来学习和解决。此外，为了对分配矩阵的约束进行编码，我们添加了两种新类型的超边：行超边和列超边。根据等式在等式（3）中，每个Xij对应于关联超图中的节点Va因此对于与相同的从这个角度来看，稀疏亲和张量也可以被认为是关联超图的表示。则我们认识到节点V1与节点V2匹配。我J1273Kg=ENCENCKVij，Vij，.. . ，Vij泥芯 泥芯 泥芯不同的是，所有的MLP都是相同的。第11章1个2个1K我ENC我CG V ERCkencKl芯lideci行或列的分配矩阵，我们添加一个undirected超边（行超边或列超边）行超边，c表示列超边，e表示关联超边。在本文中，所有的更新函数（r，指示它（例如， .aaaΣ是一个行超-C、e，v和g核心边缘）。 因此，对于两个K-一致超图匹配，本文中使用的关联超图是a=（本发明公开了一种复合材料，本发明公开了一种复合材料，本发明公开了一种复合材料，a，Va，Ea，Ra，Ca，ga），其中a和a是行超边和列超边，Ra和Ca是它们的美德.先知-愿如第4.1节所述，建议的HNN-导函数（ψvr，ψvc，ψev，ψrv，ψcv，ψvg，ψeg，ψrg和ψcg）是和约简函数Eq. （14）。对于无向关联超图，使用以下更新函数r′=r（rl，ψvr（Vr），g），（26a）HM框架可以处理不同类型的超边，并且每种类型可以具有其自己的更新函数。Lc′k核心C核心L（ck，ψvc（Vc），g）（26b）e′=e（ej，ψve（ej，Vi），g），（26c）5.2. 编码器模块j铁心v′=v（vi，ψev（vi，E′），ψrv（R′），ψcv（C′），g），（26d）i核心i i i编码器模块用于将输入空间中的属性转换到适合核G核心（g，ψvg（V′），ψeg（E′），ψrg（R′），ψcg（C′））. （26e）module.在这个模块中，每个属性都由一个多层感知器（MLP）进行自我更新，即ra′=r（ra）对于每个关联超边，（24a）与Eq不同。 (25)，对于关联节点和的关联超边，我们使用的减少功能方程。(16)[34]对于ψ ve和ψ ev，扩展了多头[34]。通过使用该约化函数，我们可以区分lencLca′ =c（ca） 对于每行超边缘，（24b）ea′ =e（ea） 对于每个列超边缘，（24c）同一个multiset中不同元素的贡献。所有更新函数和其它约简函数与等式（1）相同。（25）.JencJva′=v（va）对于每个关联节点，（24d）5.4.解码器模块阿格ENC（ga）对于全局属性，（24e）与编码器模块相反，解码器模块用于从嵌入中提取期望的信息其中rCENCeENCvENC ，和g是不同的MLP。空间 由于我们正在解决节点分类问题，5.3. 核心模块在所提出的HNN-HM框架中多次应用相同的核心模块。对于每一步，我们通过连接相应的属性向量来合并编码器的输出和核心模块的最后输出，并再次使用核心模块对其进行处理。步数控制消息在超图中的节点和超边之间传递的距离。在我们的实验中，我们发现十个步骤足以完成我们的任务。我们提出了两种不同的更新策略：一个是K-一致有向结合超图，另一个是无向结合超图。对于K-均匀有向关联超图6，更新函数（忽略上标a）为r′=r（rl，ψvr（Vr），g），（25a）我们只使用由核心模块返回的超图中的节点属性，并按如下方式更新它们：va′=v（va），（ 27）其中dec是我们实验中的MLP。之后，为了以宽松的形式近似一对一（至多）一约束，我们使用行式softmax层作为输出层，即，预测分配矩阵的每一行在测试中，匈牙利算法被进一步用于后处理。5.5. 优化由于我们的HNN-HM的所有组件都是可区分的，因此可以以端到端的方式对其进行训练，并且可以联合优化所有组件。分配矩阵指示来自不同超图的两个节点是否匹配，从而作为所有节点的基础事实c′kC核心 （ck，ψvc（Vc），g）（25b）=′g=，，，=1274核心EEE核心我我我我在关联超图中。 我们实验中使用的损失-e′j=e（ej，v（1），vJ（2）、. .. ，vJ（K）、（g）、（25c）项是二进制交叉熵，它由AMSGrad [29]算法具有学习率衰减。v′=v.vi，.ψev（E（k）′）Σ，ψrv（R′），ψcv（C′），gΣ，（25d）G核心（g，ψvg（V′），ψeg（E′），ψrg（R′），ψcg（C′））. （25e）我们将我们的HNN-HM与七种最先进的这里使用的符号与Eq. (6)带有附加标签以区分不同的超边：R for6请记住，这是一个关联超图，其中每个超边都有K个节点，并且这些K个节点的顺序很重要。三阶算法的合成数据集和三个真实的数据集。特别地，我们使用这些算法：TM [10] 7，7我们使用修正了错误的TM版本（https://duchenne.net/publications/code/codeCVPR09fixed.zip）。′g=雷克6. 实验1275一一二NNN112233IJγ射线我J2--表1.Willow对象数据集上的精度（%）(a) 无异常值（b）有异常值（#异常值=5）算法车鸭脸电机酒AVGTM [10]69.083.396.082.910086.2IPFP-HM [24] 66.977.694.782.510084.3RRWHM [20] 68.679.797.682.810085.7[27]第二十七话67.477.998.188.310086.3BCAGM3 [28] 67.377.797.488.610086.2ADGM1 [19]72.076.591.990.798.986.0ADGM2 [19]72.277.494.591.999.387.1HNN-HM91.592.310099.910096.8算法汽车鸭脸电机。酒AVGTM [10]40.3 48.2 56.250.191.757.3IPFP-HM [24] 40.6 47.3 60.149.391.957.9RRWHM [20] 41.6 50.0 64.553.391.560.2[27]第二十七话42.3 49.0 69.054.594.661.9BCAGM3 [28] 41.8 49.1 68.454.494.561.6ADGM1 [19]41.9 46.4 46.950.686.154.4ADGM2 [19]41.6 45.7 52.852.085.855.6HNN-HM76.7 72.9 97.585.693.385.2表2.Pascal VOC数据集的准确度（%）算法航空自行车鸟船botl 总线 车猫 柴科·德塔布·多格·霍斯有限公司 沙发电视AVGTM [10]29.1 35.5 42.6 43.393.2 32.7 40.8 39.8 31.9 36.5 44.7 34.2 35.7 34.3 31.7 65.0 39.3 45.6 75.1 39.843.5IPFP-HM [24]26.9 34.6 41.4 42.1 87.0 32.8 40.0 37.8 30.9 34.9 50.2 32.4 33.7 33.6 30.2 63.4 37.0 44.5 72.8 38.142.2RRWHM [20]28.0 36.2 42.7 43.3 91.1 33.8 40.9 38.6 32.2 35.6 49.2 34.0 35.9 34.5 31.4 63.2 38.9 46.5 75.3 39.943.6[27]第二十七话28.0 38.1 41.7 44.3 90.2 36.1 41.5 39.4 32.8 35.4 49.3 33.6 34.4 34.8 31.8 63.0 39.5 47.3 76.8 39.943.9BCAGM3 [28]28.3 38.6 41.9 45.0 90.3 36.1 42.3 38.6 33.5 35.7 51.4 33.6 34.0 35.0 31.1 62.6 39.1 47.9 77.5 39.644.1ADGM1 [19]26.5 38.5 37.3 38.2 91.4 38.3 38.6 35.4 31.8 35.9 53.3 32.9 33.3 35.2 30.3 63.4 34.9 51.3 45.2 29.541.1ADGM2 [19]26.8 38.5 38.1 39.6 91.1 40.0 38.4 35.6 31.4 36.1 54.1 33.3 32.5 34.8 29.5 63.6 35.0 50.5 57.0 31.041.8HNN-HM39.6 55.7 60.7 76.487.386.2 77.6 54.2 50.0 60.7 78.8 51.2 55.8 60.2 52.5 96.5 58.7 68.4 96.2 92.868.0IPFP-HM（[24]中的算法3），RRWHM [20]，BCAGM变 体 中 最 好 的 两 个 ： BCAGM+MP [27] （ 简 称BCAGM ） 和 Adapt-BCAGM 3 +MP [28] （ 简 称BCAGM 3 ） ， 以及 ADGM [19]算 法 的两 种 变 体 ：ADGM 1和ADGM 2。在我们的实验中使用推荐的或默认的为了得到一个合适的分配矩阵，我们使用匈牙利算法来分解-在亲和张量中的非零值，这实际上减少了关联超边的数量为了进一步减少关联超边的数量，我们还将有向关联超边转换为无向超边，并从编码器中平均其输出以获得顺序不敏感属性。例如，所有以下六个缔合高度：（Va，Va，Va），（Va，Va，Va），（Va，Va，Va），（Va，Va），（Va，Va，Va），（Va，Va，Va），（Va，Va，Va，Va），（Va，Va，Va，Va），（Va，Va，Va，Va），（Va，Va，Va，（Va，Va，Va，Va），（Va，Va，Va，（Va，Va，Va，11223311332222 11 33cretize所有方法的输出。（Va，Va，Va）、（Va，Va，Va）和（Va，Va，Va）将是223311331122332211在[10，20，27]之后，我们仅使用几何信息（即每个点的坐标）来构造用于匹配的超图，并评估关于三阶超图匹配问题的所有算法节点亲和性设置为零。超边亲和度（由其他算法使用，而不是我们的算法）由以下公式计算：转换为一个无向超边Va、Va、Va，以及它们来自编码器的所有输出的平均值将被视为新的无向超边的属性向量。如果我们将它们的每个关联属性向量都视为它们之间的亲和性特征向量，则这是有意义的两个三元组的节点：（V1，V1，V1）和（V2，V2，V2），因此一二三一二三10 - 12-2013（¨e−e¨）（28）我们可以预期所有这些属性向量都应该是一样的在此操作之后，关联的所有超边超图是无向。因此，我们可以使用无向关联超图的其中γ是所有距离的平均值，e1和e2是超边缘属性8按照I[10]计算。J在我们的算法中使用的关联超图是以与RRWHM[20]相同的方式构造的。但是，我们直接使用点坐标作为算法的属性，而不是使用亲和度（从点坐标导出）作为在我们的实验中，全局属性向量、行属性向量和列属性向量的初始值被设置为零。就像[10，19，20，27，28]一样，我们遵循TM [10]中提出的相同采样策略来减少8每个超边属性是由相应三角形（由该超边中的三个点构成）的三个角核心模块 在Willow数据集上，我们尝试了无向和有向版本，发现它们的准确性相当：96.8%（非定向的）和96.5%（定向的）。由于无向版本是内存高效的，我们更喜欢它在我们所有的实验。合成数据集我们首先评估我们的算法匹配2D点集。在[27]之后，我们从高斯分布（0，1）中随机抽取n个内点作为第一个超图中的节点，并通过缩放这些点，添加从（σ，1）中提取的高斯噪声，并附加从（0，1）中提取的n个离群点作为离群点来获得另一个超图中的节点。第一个超图的超边是通过选择12761.0000.9751.0间隙为50，并增加n的值异常值 从0到10。0.9500.9250.9000.8750.8500.825TMIPFP-HMRRWHMBCAGMBCAGM3ADGM1ADGM20.90.80.70.60.50.4TMIPFP-HMRRWHMBCAGMBCAGM3ADGM1ADGM2再次，在具有相同序列间隙（间隙=50）的所有帧对上对结果进行平均。在该数据集中，我们的HNN-HM的准确性接近100%（参见图1B）。5），这显示了其优于其他最先进算法的能力。Willow对象数据集Willow对象数据集[6] con-0.800HNN-HMHNN-HM0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200噪声水平(a) 变化噪声电平电话：020 - 406080100离群值数量(b) 变野值包含五个类别，每个类别至少有40个图像，每个图像标记有10个地标。我们选择20张图片1.000.950.90图4.对合成数据集的评价。1.0000.9950.9900.985每个类别的培训，让其余的测试。在每个类别的1000对图像（从测试集中随机选择）上评估所有算法。为了测试它们在异常值下的性能，我们使用SIFT来检测五个关键点，并将它们作为异常值附加到十个标记点。Willow对象数据集上的结果显示在Ta-0.850.800.7510二十个三十个四十个50人六十七十八十九十100人间隙0.9800.9750.9700.965TMIPFP-HMRRWHMBCAGMBCAGM3ADGM1ADGM2HNN-HM0 2 4 6 810离群值数量表1.没有任何异常值（见表1a），ADGM2 [19]优于其前代产品。对于五个异常值（参见表1b），BCAGM[27]在使用MPM [8]方面表现相当好，MPM [8]对异常值具有鲁棒性。然而，我们的方法在这两种情况下都显著优于所有竞争对手(a)变化的间隙（异常值数量=10）（b）变化的异常值（间隙=50）图5.对CMU内部数据集的评价。节点和第二超图中的超边是完全连通的。之后，应用TM [10]中的采样策略来减少亲和张量中的非零值。进行两组实验一 个是用于测试对噪声的鲁棒性（由σ控制），因此我们设置n内点=20，并将噪声水平σ从0变化到0。2，无标度或离群值。 另一个是用于评估对异常值的稳定性，因此我们设置ninlier = 10，并将异常值的数量noutlier从0增加到100，其中1。5倍缩放并且σ = 0。03. 结果表明，该方法是可行的。4（每条曲线在100次运行中取平均）表明，我们的方法在噪声和离群值上表现良好，并且与最先进的方法相似或更好CMU house数据集CMU house数据集在评估超图匹配算法方面很受欢迎[10，19，20，27，28]。它由一个序列111帧取自同一个移动的玩具房子。两帧之间的序列间隙越大，房屋对象的变形越多每个帧标记有30个关键点。为了模拟异常值场景，我们在一个帧中保留所有30个点，并在另一帧中移除n个异常值为了训练我们的方法，我们从数据集中均匀地采样23帧。在两种设置下评估算法：变形设置和异常值设置。对于变形设置，我们在第一帧中选择20个点，在第二帧中选择所有30个点（即n异常值=10），并且以10的步长将序列间隙从10增加到100。结果在具有相同序列空位的所有帧对上平均对于离群值设置，我们设置序列Pascal VOC数据集具有标记关键点[3]的Pascal VOC数据集[11]有20个类，并且具有各种规模，姿势和照明的挑战性。在[36]之后，我们使用过滤后的数据集（7020个训练和1682个测试图像）。为了进行评估，我们从测试集中的每个类中随机选择1000个图像表2总结了结果。除了bottle类，我们的方法几乎超过了其他所有方法，这清楚地显示了我们方法的优势。7. 结论在本文中，我们提出了HNN-HM算法，这是第一个统一的超图神经网络（HNN）超图匹配的解决方案。我们首先将超图匹配问题转化为关联超图上的节点分类问题，然后开发一个HNN解决方案来解决节点分类问题。实验结果清楚地表明，我们的方法比国家的最先进的超图匹配算法的优势谢谢。我们真诚地感谢匿名重新观众的深刻意见。徐勇感谢国家自然科学基金（62072188）和广东省科技计划（2019A050510010）的支持。引用[1] Peter W.杰西卡？巴塔利亚Hamrick，Victor Bapst，Al-varoSanchez-Gonzalez ， Vin´ıcius Flores Zambaldi ，Mateusz Malinowski，Andrea Tacchetti，David Raposo，Adam San-toro，RyanFaulkne r，CaglarGu¨ l c ehre，H. 放大图片作者：FrancisSong， Andrew J. Ballard，JustinGilmer，George E.放大图片创作者：John R.艾伦查尔斯·纳什维多利亚·兰斯顿TMIPFP-HMRRWHMBCAGMBCAGM3ADGM1ADGM2HNN-HM精度精度精度精度1277Chris Dyer、Nicolas Heess 、Daan Wierstra、PushmeetKohli、Matthew Botvinick、Oriol Vinyals、Yujia Li和Razvan Pas-canu。关系归纳偏差、深度学习和图网络。CoRR，abs/1806.01261，2018。[2] Ser