介绍与指南

本页简要介绍了图匹配以及使用pygmtools的一些指南。 如果您正在寻找一些背景信息，这里就是正确的地方！

注意

有关更多技术细节，我们推荐以下两项调查。

关于基于学习的深度图匹配： Junchi Yan, Shuang Yang, Edwin Hancock. “学习图匹配及相关组合优化问题。” IJCAI 2020.

关于非学习的双图匹配和多图匹配： Junchi Yan, Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, Xiaokang Yang. “A Short Survey of Recent Advances in Graph Matching.” ICMR 2016.

为什么选择图匹配？

图匹配（GM）是模式识别、数据挖掘等领域中的一个基础但具有挑战性的问题。 GM旨在通过解决一个NP难组合问题，在多个图中找到节点到节点的对应关系。 最近，开发基于深度学习的图匹配方法引起了越来越多的兴趣。

与其他直接的匹配方法（例如贪婪匹配）相比，图匹配方法更可靠，因为它是基于优化形式的。此外，图匹配方法利用了节点亲和度和边亲和度，因此图匹配方法通常对噪声和异常值更具鲁棒性。最近的深度图匹配方法还使得许多图匹配求解器能够集成到深度学习管道中。

图匹配技术已应用于以下应用：

如果你的任务涉及匹配两个或更多图形，你应该尝试pygmtools中的求解器！

什么是图匹配？

数学公式

让我们涉及一点数学来更好地理解图匹配流程。 一般来说，图匹配具有以下形式，称为二次分配问题（QAP）：

\[\begin{split}&\max_{\mathbf{X}} \ \texttt{vec}(\mathbf{X})^\top \mathbf{K} \texttt{vec}(\mathbf{X})\\ s.t. \quad &\mathbf{X} \in \{0, 1\}^{n_1\times n_2}, \ \mathbf{X}\mathbf{1} = \mathbf{1}, \ \mathbf{X}^\top\mathbf{1} \leq \mathbf{1}\end{split}\]

符号解释如下：

  • \(\mathbf{X}\) 被称为置换矩阵，它编码了匹配结果。它也是图匹配问题中的决策变量。\(\mathbf{X}_{i,a}=1\) 表示图1中的节点 \(i\) 与图2中的节点 \(a\) 匹配，而 \(\mathbf{X}_{i,a}=0\) 表示不匹配。在不失一般性的情况下，假设 \(n_1\leq n_2.\) \(\mathbf{X}\) 有以下约束条件：

    • 每行的和必须等于1：\(\mathbf{X}\mathbf{1} = \mathbf{1}\)；

    • 每列的总和必须等于或小于1：\(\mathbf{X}\mathbf{1} \leq \mathbf{1}\)。

  • \(\mathtt{vec}(\mathbf{X})\) 表示 \(\mathbf{X}\) 的列向量化形式。

  • \(\mathbf{1}\) 表示一个所有元素都为1的列向量。

  • \(\mathbf{K}\) 被称为 亲和矩阵，它编码了输入图的信息。 节点间和边间的亲和性都编码在 \(\mathbf{K}\) 中：

    • 对角线元素 \(\mathbf{K}_{i + a\times n_1, i + a\times n_1}\) 表示图1中的节点 \(i\) 和图2中的节点 \(a\) 之间的节点亲和度；

    • 非对角线元素 \(\mathbf{K}_{i + a\times n_1, j + b\times n_1}\) 表示图1中的边 \(ij\) 和图2中的边 \(ab\) 之间的边间亲和度。

图匹配流程

解决现实世界中的图匹配问题可以分为以下几个部分：

第一部分：特征提取

从你想要匹配的图中提取节点/边的特征。这些特征用于衡量节点/边之间的相似性，并构建在图形匹配问题中至关重要的亲和矩阵。

第二部分：亲和矩阵构建

从节点/边特征构建亲和矩阵并形成特定的QAP问题。

第三部分：QAP问题解决

使用GM求解器解决生成的QAP问题（图匹配问题）。

第一部分可以根据您的应用程序的方法来完成，第二部分和第三部分可以由pygmtools处理。 下面的图表展示了一个标准的深度图匹配流程。

../_images/QAP_illustration.png

图匹配最佳实践

我们需要理解图匹配求解器的优势和局限性。如上所述，图匹配求解器的主要优势在于它们对噪声和异常值更具鲁棒性。图匹配还利用了边缘信息，这在线性匹配方法中通常被忽略。图匹配求解器的主要缺点是其效率和可扩展性，因为优化问题是NP难的。因此，为了决定哪种匹配方法最合适，需要根据应用需求在所需的匹配精度和可承受的时间和内存成本之间进行平衡。

注意

无论如何，先尝试图匹配没有坏处！

何时使用pygmtools

pygmtools 推荐用于以下情况，您可以从友好的API中受益：

  • 如果你想将图匹配作为你的管道（无论是学习还是非学习）的一个步骤。

  • 如果你想快速对pygmtools中可用的图匹配求解器进行基准测试和分析。

  • 如果您不想深入研究算法细节，也不需要修改算法。

我们提供以下指南供您参考：

  • 如果你想将图匹配求解器集成到你的端到端监督深度学习管道中，试试 neural_solvers。

  • 如果没有匹配步骤的真实标签可用，请尝试classic_solvers。

  • 如果有多个图需要联合匹配，请尝试 multi_graph_solvers。

  • 如果上述方法的时间和内存成本对您的任务来说是不可接受的，请尝试linear_solvers。

何时不使用pygmtools

作为一个高度集成的工具包，pygmtools在实现细节上缺乏一些灵活性，特别是对于图匹配领域的专家。如果您正在研究新的图匹配算法或开发下一代深度图匹配神经网络，pygmtools可能并不适合。我们推荐ThinkMatch作为学术研究的协议。

下一步

请阅读Get Started指南。