基于节点到节点分配分类的次优图匹配

### 基于节点到节点分配分类的次优图匹配 #### 1. 引言 属性图在结构模式识别的多个研究领域有着广泛应用，因其能够通过一元和二元局部实体来表示结构化对象。为了比较属性图，人们提出了多种距离度量方法，其中图编辑距离（Graph Edit Distance，GED）是最常用的距离之一。 图编辑距离问题通常被数学表述为一个二次分配问题，即找到使目标函数最小化的节点到节点的分配，该目标函数编码了局部差异（线性项）和结构差异（二次项）。定义合适的成本函数对于实现良好的分类或识别结果至关重要，因此人们提出了多种学习编辑成本的方法。不过，图编辑距离问题已被证明是NP难问题，为此，人们提出了一些能在多项式时间内返回图对应关系的算法，但这些算法不能保证得到使图编辑距离最小的对应关系。 本文提出了一种新的图匹配算法，以次优方式推导图对应关系。该算法的新颖之处在于，首先对节点到节点的分配进行分类，然后无需使用组合优化算法（如匈牙利方法）来推导图对应关系，从而避免了其计算成本。 #### 2. 定义 ##### 2.1 属性图和图编辑距离 将属性图 $G$ 定义为一个四元组 $G = \{ \vec{v}, \vec{e}, \gamma_v, \gamma_e \}$，其中： - $\vec{v} = \{ v_i | i = 1...n \}$ 是 $n$ 个节点的集合。 - $\vec{e} = \{ e_{i,j} | i, j \in 1...n \}$ 是连接节点对的边的集合。 - $\gamma_v = \{ v_i \to \psi_i | i = 1..n \}$ 和 $\gamma_e = \{ v_i \to E(v_i) | i = 1..n \}$ 分别是将节点和边映射到其属性值的函数。$\psi_i \in R^m$ 将每个节点映射到其 $m$ 个局部属性，$E(·)$ 表示某个节点的度。 图编辑距离（GED）是两个属性图 $G$ 和 $G'$ 之间的距离，它由将 $G$ 转换为 $G'$ 的最佳编辑操作组合组成。考虑对节点的局部属性及其结构进行三种操作：替换、删除和插入。为了量化每个编辑操作引入的失真程度，会根据涉及的节点或边的属性为它们分配成本。将 $G$ 完全转换为 $G'$ 的编辑操作序列称为 $G$ 和 $G'$ 之间的编辑路径 $\lambda_{G,G'}$，编辑路径的成本是其中包含的编辑操作成本的总和。因此，GED 定义为在所有可能的编辑路径 $T_{G,G'}$ 中，从一个图到另一个图获得最小成本的编辑路径，形式上表示为： $GED(G, G') = \min_{\lambda_{G,G'} \in T_{G,G'}} Cost(G, G', \lambda_{G,G'})$ 编辑路径 $\lambda_{G,G'}$ 可以通过两个图的节点之间的节点到节点匹配 $f$ 来定义，其中 $f(v_i) = v'_a$。可以通过添加空节点来扩展图，以确保它们具有相同的阶数。 ##### 2.2 近似图编辑距离 返回 GED 的图匹配算法基于探索 $G$ 和 $G'$ 之间所有可能的对应关系 $f$ 的组合，并选择成本最小的那个。然而，为了降低 GED 计算的计算复杂度，人们提出了一些方法，但这些方法会返回次优的对应关系。通常，这些算法基于两个主要步骤： 1. **第一步**：用两个图的所有局部结构组合之间的编辑成本填充一个成本矩阵。这一步的计算成本近似为 $O(s×n^2)$，其中 $s$ 是映射局部结构的计算成本。 2. **第二步**：找到节点到节点的匹配 $f$。该问题被视为在给定成本矩阵的情况下最小化线性分配的总和。因此，这一步的计算成本为 $O(n^3)$ 或 $O(n^2)$，具体取决于匹配是通过二分图匹配（如 Munkres 或 Jonker - Volgenant 算法）还是贪婪编辑匹配来推导的。 #### 3. 学习图匹配 提出了一种次优图匹配算法，避免了经典次优图匹配算法中的第二步，因为从计算时间的角度来看，第二步比第一步更昂贵。 ##### 3.1 学习编辑成本和图嵌入 基于监督机器学习技术，人们提出了多种学习编辑成本的方法，可分为两大类： - 一类返回编辑操作的常量。 - 另一类将编辑成本定义为函数。例如，有的方法使用图编辑操作分布的概率模型，有的基于自组织映射模型，其中编辑成本是神经网络的输出。最近，有新的方法假设成本矩阵可以作为监督机器学习模型的输出进行填充。 ##### 3.2 从编辑成本估计到节点分配分类 受相关方法的启发，提出了一种监督机器学习模型，根据学习数据库是否认为节点对需要在匹配 $f$ 中进行映射，将节点到节点的分配分为两类。该模型的关键思想是使用分类器来决定图 $G$ 中的一个节点是否映射到图 $G'$ 中的一个节点，然后根据先前训练的分类器的输出分配映射或未映射的类别。如果一个节点在所有情况下都被分类为未映射，则将其视为相应节点的删除或插入。 该方法独立于分类方法（如支持向量机、K近邻、神经网络等），但需要将每个节点到节点的映射转换为向量，作为分类器的输入。因此，提出将每个匹配嵌入到一个向量中，类似于相关文献中的做法。在这种情况下，图 $G$ 中节点 $v_i$ 和图 $G'$ 中节点 $v'_a$ 之间映射的嵌入表示为 $x_{v_i \to v'_a} = [\gamma_v(v_i), \gamma_e(v_i), \gamma'_v(v'_a), \gamma'_e(v'_a)] \in R^{(m + 1)·2}$。 以下是基于节点分配分类的图匹配算法： ```plaintext Algorithm 1. Graph matching based on node assignment classification. Data: graph G and graph G′ Result: matching f 1 f = empty node-to-node correspondence 2 forall the vi in G do 3 forall the v′a in G′ and not in f do 4 x = embed(vi →v′a) 5 y = class predictor(x) 6 if y = mapped then 7 f(vi) = v′a 8 break loop 9 end 10 end 11 end ``` 该算法是一种贪婪算法，遍历图 $G$ 中的所有节点 $v_i$，并为每个节点找到图 $G'$ 中第一个可以映射到它的节点 $v'_a$。这种策略避免了经典次优图匹配算法中第二步的图对应关系的显式计算，以及第一步中整个成本矩阵的计算。需要注意的是，该模型不返回距离，只返回图对应关系，并且其性能取决于分类器的质量。 ##### 3.3 训练分类器 在监督机器学习中，数据库条目由一个元素及其预期输出组成。在本文中，数据库中的一个条目 $p$ 由一对图 $(G_p, G_p')$ 及其真实对应关系 $\hat{f}_p$ 组成。这些真实对应关系 $\hat{f}_p$ 由外部系统（通常是人类专家）推导得出，被认为是学习的最佳映射。学习方法的目标是定义一个模型，给定一对节点，当两个节点在真实对应关系中被映射时返回映射类别，否则返回未映射类别。 为此，定义了两组节点到节点的映射：一组是根据真实对应关系需要映射的节点对，另一组是假设不需要映射的节点对。由于真实对应关系是双射函数，图 $G$ 中的每个节点都映射到图 $G'$ 中的一个单一节点，而不映射到图 $G'$ 中的其他节点。这意味着对于每个被分类为映射的节点到节点映射，有 $n - 1$ 个被分类为未映射的节点到节点映射，其中 $n$ 是图的阶数。为了防止不平衡问题，在训练算法时，将映射组中的节点到节点映射重复 $n - 1$ 次。 #### 4. 实验评估 ##### 4.1 数据库描述 使用了两个数据库进行实验： - **House - Hotel 数据库**：由两个计算机建模对象的帧序列组成，分别是 111 帧的房屋和 101 帧的酒店，它们在场景中移动和旋转。每帧有 30 个手动标记的显著点，每个显著点代表一个图节点，并由 60 个上下文形状特征进行属性化。通过 Delaunay 三角剖分根据显著点的坐标构建边。由于显著点是手动标记的，因此知道图节点之间的真实对应关系。随着表示每个图的帧之间的距离增加，图之间的差异增大，图匹配过程也变得更加困难。进行了不同的实验，改变视频序列中帧之间的分离帧数，并为每个实验构建了三组图对（训练集、验证集和测试集）。 - **合成数据库**：由具有相同阶数的几组图组成。受相关方法的启发，生成了不同的图原型对，节点具有四个在 0 到 999 范围内随机生成的整数属性，边是无属性的，并且每对节点有 20% 的概率被边连接。然后，通过向每个节点的最后一个属性添加高斯噪声（标准差为 500）来扭曲原始原型，生成了一组图对。 ##### 4.2 图匹配性能 分析了图匹配的准确性和执行匹配所花费的时间。匹配准确性定义为推导的对应关系中与真实对应关系中相同的节点到节点映射的数量，除以图的阶数进行归一化。 使用了两种不同的分类器实现该方法： - 具有一个包含 60 个神经元的隐藏层和一个包含两个神经元（每个类别一个神经元：映射和未映射）的输出层的神经网络。 - 二次支持向量机，用于将节点到节点的映射分类为映射和未映射两类。 还将该方法与四种图匹配方法进行了比较，具体信息如下表所示： | 成本函数 | 求解器 | 复杂度 | 年份 | | --- | --- | --- | --- | | 编辑成本 | 匈牙利算法 | $O(n^3)$ | 2009 | | 编辑成本 | 贪婪算法 | $O(n^2)$ | 2017 | | 神经网络 | 匈牙利算法 | $O(n^3)$ | 2018 | | 神经网络 | 贪婪算法 | $O(n^2)$ | - | 使用 House - Hotel 数据库的实验结果表明，随着帧之间的分离帧数增加，图的差异增大，匹配准确性下降，运行时间略有增加。该方法在运行时间和匹配准确性之间取得了良好的平衡，准确性与神经网络方法相似，但运行时间更低。而 GED 方法虽然速度更快，但当帧之间的分离帧数增加时，匹配准确性较差。 以下是实验结果的流程 mermaid 图： ```mermaid graph LR A[选择数据库] --> B[设置实验参数] B --> C[运行不同算法] C --> D[计算匹配准确性和运行时间] D --> E[比较结果] ``` #### 4.3 运行时间分析 在合成数据库中分析了图阶数对模型性能的相关性。使用具有 6 个神经元隐藏层的神经网络实现模型，由于二次支持向量机在学习步骤中需要较高的计算时间，因此在该实验中未使用。 实验结果显示，当图的阶数达到 1500 个节点时，准确性会显著下降。使用编辑成本的方法在任何图阶数下都返回较低的准确性。而该模型的加速比随着图阶数的增加比其他方法增长得更快，在图阶数为 1500 个节点时，在加速比方面取得了最佳结果，在准确性方面排名第二。 使用分类器（如神经网络）而不是成本函数（如编辑成本）会有额外的计算成本，因为需要执行更多的内部操作。因此，当图阶数较小时，与使用编辑成本和匈牙利求解器的方法相比，在运行时间上没有改进。但对于较大的图，分类器导致的运行时间增加可以通过不需要评估所有节点到节点的对应关系以及不需要解决分配问题来得到补偿。 #### 5. 结论 提出了一种快速推导图对应关系的方法。以往的方法基于两个步骤：第一步填充成本矩阵，第二步应用线性求解器来推导图对应关系。而该提案不需要第二步，因为节点到节点的映射可以直接推导得出。通过使用分类器将节点到节点的分配分为映射和未映射两类，在实验中表明该方法在运行时间和匹配准确性之间取得了良好的平衡。 ### 基于节点到节点分配分类的次优图匹配 #### 6. 方法优势总结 - **计算效率提升**：避免了经典次优图匹配算法中第二步的图对应关系显式计算以及第一步中整个成本矩阵的计算，减少了不必要的计算量。 - **灵活性**：独立于具体的分类方法，如支持向量机、K近邻、神经网络等，可根据实际情况选择合适的分类器。 - **适应性**：在不同的数据库实验中，都能在运行时间和匹配准确性之间取得较好的平衡，尤其在图阶数较大时，加速比优势明显。 #### 7. 应用场景 - **计算机视觉**：在图像和视频处理中，可用于物体识别、跟踪和场景分析。例如，在监控视频中识别不同姿态和位置的物体，通过图匹配找到物体之间的对应关系。 - **生物信息学**：用于分析生物分子结构、基因序列等。例如，比较不同蛋白质的结构，找出相似的部分，有助于理解蛋白质的功能和相互作用。 - **社交网络分析**：分析社交网络中用户之间的关系，发现社区结构和信息传播路径。例如，通过图匹配找到不同社交网络中相似的用户群体。 #### 8. 未来展望 - **优化分类器**：进一步研究和优化分类器的结构和参数，提高分类的准确性和效率，从而提升图匹配的性能。 - **处理大规模图**：随着数据规模的不断增大，研究如何更高效地处理大规模图，减少计算时间和内存消耗。 - **结合其他技术**：将图匹配与深度学习、强化学习等其他技术相结合，探索更强大的图匹配方法。 #### 9. 总结 基于节点到节点分配分类的次优图匹配方法为图匹配问题提供了一种新的解决方案。通过避免传统方法中的复杂计算步骤，利用分类器直接推导节点到节点的映射，该方法在运行时间和匹配准确性之间取得了良好的平衡。在不同的数据库实验中，该方法都表现出了较好的性能，尤其在图阶数较大时，加速比优势明显。未来，可通过优化分类器、处理大规模图和结合其他技术等方式进一步提升该方法的性能，拓展其应用领域。 以下是图匹配方法的比较表格： | 方法 | 成本函数 | 求解器 | 复杂度 | 准确性 | 运行时间 | | --- | --- | --- | --- | --- | --- | | 本文方法（神经网络） | - | - | - | 与神经网络方法相似 | 低于神经网络方法 | | 本文方法（二次支持向量机） | - | - | - | - | - | | 编辑成本 - 匈牙利算法 | 编辑成本 | 匈牙利算法 | $O(n^3)$ | 随图差异增大而降低 | 较高 | | 编辑成本 - 贪婪算法 | 编辑成本 | 贪婪算法 | $O(n^2)$ | 随图差异增大而降低 | 较低 | | 神经网络 - 匈牙利算法 | 神经网络 | 匈牙利算法 | $O(n^3)$ | 较高 | 较高 | | 神经网络 - 贪婪算法 | 神经网络 | 贪婪算法 | $O(n^2)$ | - | - | 以下是图匹配过程的 mermaid 流程图： ```mermaid graph LR A[输入图 G 和 G'] --> B[节点到节点映射嵌入向量] B --> C[分类器分类] C --> D{是否映射?} D -- 是 --> E[记录映射关系] D -- 否 --> B E --> F[完成图匹配] ``` 通过以上内容，我们对基于节点到节点分配分类的次优图匹配方法有了全面的了解，包括其原理、实验评估、优势、应用场景和未来展望等方面。希望该方法能为相关领域的研究和应用提供有价值的参考。