汕头网站建设sagevis,长尾关键词搜索,安全网站建设,做网站需要的东西核心思想 本文提出一种基于图神经网络的图匹配方法#xff0c;首先利用节点相似度构建初始的匹配关系#xff0c;然后利用局部的一致性对初始的匹配关系进行迭代优化#xff0c;不断筛除误匹配点#xff0c;得到最终的匹配结果。本文还提出几种措施来降低计算复杂度#x…核心思想 本文提出一种基于图神经网络的图匹配方法首先利用节点相似度构建初始的匹配关系然后利用局部的一致性对初始的匹配关系进行迭代优化不断筛除误匹配点得到最终的匹配结果。本文还提出几种措施来降低计算复杂度以实现较大规模的图匹配任务。
实现过程 首先给出基本的概念和符号定义图G(V,A.X,E)G(V,A.X,E)G(V,A.X,E)VVV表示节点集合AAA表示关联矩阵XXX表示节点特征矩阵EEE表示边特征矩阵Gs,GtG_s,G_tGs,Gt分别表示用于匹配的源图和目标图SSS表示对应关系矩阵。根据本文对图匹配问题的定义目标是寻找最优的SSS使得下述目标函数取得最大值 NT(i)N_T(i)NT(i)表示与节点iii之间的距离小于等于TTT的邻域称之为T-hop邻域。而邻域局部一致性是指对于一对匹配点i,ji,ji,j他们1-hop邻域N1(i)N_1(i)N1(i)内的所有点都是匹配点。 如上图所示算法分成两个阶段第一阶段根据节点特征之间的相似度得到初始的对应关系矩阵S(0)S^{(0)}S(0)第二阶段利用局部一致性约束进行迭代优化得到最终的对应关系矩阵S(L)S^{(L)}S(L)。第一阶段作者称之为局部特征匹配利用共享权重的图神经网络Ψθ1\Psi_{\theta_1}Ψθ1分别提取两个图Gs,GtG_s,G_tGs,Gt的深度节点特征Hs,HtH_s,H_tHs,Ht。然后利用下式得到初始的对应关系矩阵S(0)S^{(0)}S(0) 设真实的匹配关系为πgt(⋅)\pi_{gt}(\cdot)πgt(⋅)则第一阶段的损失函数为 对应关系矩阵S(0)S^{(0)}S(0)实质上是一个从源图的节点函数空间L(Gs)L(G_s)L(Gs)到目标图节点函数空间L(Gt)L(G_t)L(Gt)的一个映射因此可得 其中 以单位矩阵I∣Vs∣I_{|V_s|}I∣Vs∣的形式构建源图的节点指示函数利用对应关系矩阵S(l)S^{(l)}S(l)可以将其从源图GsG_sGs映射到目标图GtG_tGt。然后利用图神经网络Ψθ2\Psi_{\theta_2}Ψθ2向邻域内其他的节点传递信息如下式 这样每个节点上都聚合了邻域内其他顶点的信息通过计算聚合后节点特征之间的差异d⃗i,jo⃗i(s)−o⃗j(t)\vec{d}_{i,j}\vec{o}_{i}^{(s)}-\vec{o}_{j}^{(t)}di,joi(s)−oj(t)就可以计算节点对(i,j)(i,j)(i,j)之间的邻域一致性差异越小表示一致性越强。将差异d⃗i,j\vec{d}_{i,j}di,j通过一个多层感知机Φθ3\Phi_{\theta_3}Φθ3映射后用于优化对应关系矩阵 上述优化过程可以反复进行迭代LLL次。最终的损失函数如下 为了将上述匹配过程应用到大规模的匹配点集中作者提出了几点改进措施
稀疏匹配。通过将初始对应关系矩阵S(0)S^{(0)}S(0)中匹配得分较低的点滤除仅保留匹配得分最高的KKK个对应点可以使S(0)S^{(0)}S(0)变得更加稀疏。更换节点指示函数。尽管单位矩阵I∣Vs∣I_{|V_s|}I∣Vs∣计算十分高效但参数的复杂度较高。可以使用随机采样的节点函数Rs(l)∼N(0,1)R_s^{(l)} \sim N(0,1)Rs(l)∼N(0,1)来取代节点指示矩阵。Softmax规范化。sinkhorn函数计算不够高效且容易出现梯度消失的问题可以使用逐行的softmax来取代sinkhorn函数。迭代次数。相比于训练阶段测试阶段可以使用更少的迭代次数。
创新点
提出一种两阶段的基于图神经网络的图匹配方法针对大规模点集匹配问题提出了优化措施
算法总结 本文是基于深度学习尤其是基于图神经网络解决图匹配问题的代表性文章。二阶段逐步迭代优化的方式其实与传统图像处理中实现特征点匹配的思想非常接近。局部一致性限制了算法的求解规模缓解了图匹配问题随着节点数量增长计算量爆炸的问题。
