迈向精确图编辑距离的第一步：使用二分图匹配

### 迈向精确图编辑距离的第一步：使用二分图匹配 #### 1. 引言 图编辑距离是一种灵活且通用的容错图匹配方法，能处理有向图、无向图、带标签图和无标签图，对节点和边标签的字母表无约束，还可通过成本函数适应不同应用。然而，其计算复杂度高，属于二次分配问题（QAPs），是NP完全问题，精确计算图编辑距离的时间复杂度为指数级。 近年来，为解决图编辑距离计算复杂度高的问题，提出了多种方法，其中基于二分图匹配的算法框架将图编辑距离问题转化为线性和分配问题（LSAP），可在多项式时间内求解，能显著加快图编辑距离的近似计算。但该方法在节点分配时仅考虑局部结构信息，可能导致节点分配错误，使得计算出的编辑距离大于或等于精确的图编辑距离。 为减少对真实图编辑距离的高估，有研究提出了对原框架的改进，通过后处理步骤减少错误分配的数量。具体做法是系统地交换两个节点分配的目标节点，并使用束搜索（一种带剪枝的树搜索）来搜索分配变化的空间。不过，束搜索可能在搜索过程的早期剪掉最优解，且原方法未考虑某些节点和局部分配对图编辑距离近似的影响，可能导致重要部分被过早剪掉。 本文旨在研究新的启发式方法，以提高节点分配的整体质量。具体提出了一种迭代版的改进方法，通过随机排列原始映射为束搜索改进提供起点，探讨节点排序对映射质量的影响。 #### 2. 近似图编辑距离计算 ##### 2.1 二分图编辑距离近似 给定两个图 $g_1$ 和 $g_2$，图编辑距离的基本思想是使用插入、删除和替换节点及边的操作将 $g_1$ 转换为 $g_2$。为找到最合适的编辑路径，引入成本来衡量操作的强度，图编辑距离定义为两个图之间最小成本的编辑路径。 精确计算图编辑距离的复杂度与图的节点数呈指数关系，对于大型图来说难以处理。为降低复杂度，将图编辑距离问题转化为LSAP，具体步骤如下： 1. **建立成本矩阵**：基于图 $g_1$ 和 $g_2$ 的节点集 $V_1$ 和 $V_2$，建立成本矩阵 $C$。矩阵中的元素 $c_{ij}$ 表示节点替换的成本，$c_{i\epsilon}$ 表示节点删除的成本，$c_{\epsilon j}$ 表示节点插入的成本。每个元素不仅考虑节点操作的成本，还考虑了相应节点操作所隐含的边编辑操作成本的最小和。 2. **节点分配**：对成本矩阵 $C$ 应用分配算法，找到节点（及其局部边结构）的最小成本分配。这对应于一个LSAP实例，可在多项式时间内最优求解。算法返回一个排列，对应于图 $g_1$ 到图 $g_2$ 的节点映射 $\psi$，该映射不仅包括节点替换，还包括删除和插入操作，可视为仅考虑节点操作的部分编辑路径。 3. **完成边的编辑路径**：根据相邻节点的编辑操作确定边的编辑操作，完成部分编辑路径 $\psi$ 关于边的部分，最终返回完成编辑路径的总成本作为近似图编辑距离，此算法记为 $BP(g_1, g_2)$。 ##### 2.2 使用束搜索改进近似 实验表明，$BP$ 算法的次优性（对真实编辑距离的高估）通常是由于 $\psi$ 中少数节点分配错误。为改进距离近似，以节点分配 $\psi$ 为起点，通过系统地交换两个节点分配的目标节点来改变原始节点分配，并使用树搜索来搜索分配变化的空间。 束搜索的具体算法如下： ```plaintext Algorithm 1. BP - Beam(g1, g2, ψ, b) 1. dbest = d⟨ψ⟩(g1, g2) 2. Initialize open = {(ψ, 0, d⟨ψ⟩(g1, g2))} 3. while open is not empty do 4. Remove first tree node in open: (ψ, q, d⟨ψ⟩(g1, g2)) 5. for j = (q + 1), ```