Nov, 2019

神经图匹配网络：学习 Lawler 的二次分配问题，并扩展到超图和多图匹配

PDF
TL;DR本篇论文提出了一种利用权值矩阵进行学习的网络来解决 Quadratic Assignment Problem (QAP) 及图匹配的问题，该模型利用嵌入网络对顶点进行分类，并通过 Sinkhorn 归一化和交叉熵损失进行端到端的学习。实验结果表明，该方法在合成数据和现实图像上均取得了很好的效果。
graph matchingquadratic assignment problemaffinity matrixlearning networkvertex classification
发现论文，激发创造
  • KerGM: 基于核函数的图匹配

    本文提出了在 Hilbert 空间中的一些规则，引入了新的外积算法，可以在重现核 Hilbert 空间中将 Lawler 的 QAP 视为 Koopmans-Beckmann 的对齐，有效地解决了大规模亲和力矩阵的问题。提出基于熵正则化的 Frank-Wolfe 算法 (EnFW) 对 QAP 进行优化，具有与原始 FW 算法相同的收敛速率，同时显著减少每个外层迭代的计算负担，实验表明我们提出的算法在匹配准确性和可扩展性方面显著优于现有技术。

    Nov, 2019

  • 学习图匹配

    本文研究的是图匹配问题，提出了一种基于学习的方法，用于解决基于图的模式识别问题。通过训练示例和标签，我们可以学习节点与边之间的兼容性，在解决问题时可以取得更好的效果。实验结果表明，该方法比现有算法更为有效。

    Jun, 2008

  • 利用谐波分析将领域知识纳入匹配问题

    探究加速解决二次分配问题（QAP）的新方法，利用特殊的优化函数方法在傅里叶空间中优化对称群 Sn，以及在多个优化任务中学习参数。实验表明，新方法在实际领域中可以优于现有方法。

    Jun, 2012

  • 集成二次分配网络用于图匹配

    通过图神经网络结合数据驱动和传统方法，该研究提出了一种解决图匹配问题的模型，该模型利用了随机抽样策略降低了计算复杂度和 GPU 内存使用，并在几个任务上得到了显著的性能提升。

    Mar, 2024

  • 通过两阶段图指针网络和强化学习解决 QAP 问题

    本文提出了一种基于深度强化学习模型的两阶段图指示器网络（GPN）来解决二次分配问题（QAP），实验结果表明它可以为 TSPLib 和 QAPLIB 的基准问题提供半最优解。

    Mar, 2024

  • 大规模（脑）图匹配的快速近似二次规划

    本文介绍了一种快速的近似二次分配算法（FAQ），能够更高效地在大数据和图值数据上处理 QAP 问题，通过在 C.elegans 连通图匹配案例上的实证表明其优越性。

    Dec, 2011

  • 通过凸松弛求解图匹配问题

    本文介绍了一种应对图匹配问题的新型凸松弛算法，通过闭合迭代的镜像下降方案，实现了在相关高斯维格纳模型下对应的唯一解高概率收敛，进一步确立了输入矩阵的新充要条件，并将其应用于噪声下的地面实况恢复中。

    Oct, 2023

  • 使用锚节点的图匹配：一种学习方法

    使用基于图拉普拉斯的节点签名以及边的点对热核映射来构建一种在锚节点已知的情况下，用于权重图匹配的距离度量方法，并使用整数二次规划法确定最优匹配。实验结果表明，该方法在随机生成的图和两个广泛使用的图像序列上具有优异的性能。

    Apr, 2018

  • 学习解决方案感知的变压器以高效解决二次分配问题

    利用机器学习的能力，针对组合优化中的 Quadratic Assignment Problem (QAP) 提出了第一种针对 QAP 的学习优化方案，该方案使用 Solutions AWare Transformer (SAWT) 架构来有效捕捉 QAP 的高阶信息。

    Jun, 2024

  • 半定规划方法求解稀疏图的二次分配问题

    本研究提出了一种新的半定规划 (SDP) 方法来解决二部图的匹配问题，采用正半定矩阵进行松弛，并通过聚类来加强松弛，使得计算复杂度和运行时间得到了缩减，可以应用于核磁共振光谱 (NMR) 等领域的匹配问题。

    Mar, 2017