AAAIDec, 2023

基于 SAT 的正则图模式匹配算法

PDF
TL;DR我们提出了一种图同构的泛化方法，通过声明式规范来检查复杂的结构属性，其中规范以一种类似于正则表达式的图形形式给出，并且通过基于 SAT 的算法来检查目标图是否匹配给定的规范，并通过对 CodeSearchNet 数据集的广泛实验评估提出了一种优化算法的预处理技术。
发现论文，激发创造
  • 关于图匹配和图同构问题的谱特性

    本文证明了对于某类图形，图匹配问题及其最常见的凸松弛问题是等价的，基于相应邻接矩阵的谱特性。此外，本文还推导了图的自同构群的结果，并提供了邻接矩阵的基本谱特性。

    Sep, 2014

  • 利用同态性挖掘网络中的模式

    该研究提出了一种使用子图同态挖掘网络中的树模式的替代方法，具有良好的时间复杂度，同时解决了子图同构中的两个特殊问题。

    Oct, 2011

  • 学习图匹配

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

    Jun, 2008

  • 使用图拓扑的不确定性感知高效子图同构

    在没有节点标签的情况下，我们提出了一种在不精确匹配的情况下识别子图与完整图之间节点对应关系的方法，该方法包括两个步骤：提取子图的最小唯一拓扑保持子集及在全图中查找可行匹配，实现基于边界可交换性的独特路径配对扩展匹配集，并通过共识算法。

    Sep, 2022

  • 利用图模型同构的知识图谱问答

    本文提出了一种基于图同构的 QA 方法 ——TeBaQA，其通过学习 SPARQL 查询的基本图模式来回答问题，从而在减少训练数据量的同时实现了与最先进技术相同的性能，在 QALD 和 LC-QuAD v1 数据集上都具有极高的性能。

    Mar, 2021

  • 图匹配的函数表示

    本研究提出一种新的基于功能表征的图匹配方法，能够降低相关算法的时间和空间复杂度，并且具有比现有方法更准确的匹配性能。

    Jan, 2019

  • 图的频谱对齐

    本文提出了一种改进的广义图对齐方法，该方法结合了匹配和不匹配两种条件，在不同的图案例中，通过矩阵的谱分解达到了较好的性能表现，尤其在对齐正则图结构方面显著优于现有方法。

    Feb, 2016

  • KerGM: 基于核函数的图匹配

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

    Nov, 2019

  • 图匹配：自行决定松弛程度的风险

    研究了图匹配问题，通过实验证明了最优解不可达，证实了松弛算法加梯度下降算法的方法能在实践中达到优秀的效果。

    May, 2014

  • 图匹配：松弛与否？

    本研究考虑权重无向图的精确和非精确匹配问题，通过定义 “friendly graphs” 和发展准确和近似解的确切条件和界限，以及优化找到最优近似同构的能力的凸松弛技术进行解决。

    Jan, 2014