LAD2025：一种基于约束的子图同构问题求解器

《Artificial Intelligence》：LAD2025, A constraint-based solver for the subgraph isomorphism problem

Subgraph Isomorphism Problem (SIP)求解方法LAD2025通过改进PathLAD的约束传播机制、引入权重变量排序和随机重启策略，结合路径枚举与最大团集分析的新补充标签，实验证明其效率优于Glasgow和PathLAD+。

　　

克里斯汀·索尔农（Christine Solnon）

克里斯汀·索尔农，CITI、Inria、INSA Lyon，法国维勒乌尔班（F-69621）

摘要

子图同构问题（Subgraph Isomorphism Problem，简称SIP）是一个$NP$完全问题，其目标是在目标图中找到一个模式图的副本。该问题可以非常直接地被建模为一个约束满足问题，而解决SIP的精确方法通常通过传播约束来减少搜索空间。特别是PathLAD是一种在2016年引入的求解器，它结合了局部不同（Locally All Different，简称LAD）约束和基于路径的补充约束。在本文中，我们介绍了LAD2025，它对PathLAD进行了全面重构，并增加了新功能：新的补充约束、基于权重的变量排序启发式算法、随机重启机制以及用于选择过滤级别的规则。

引言

子图同构问题（SIP）的目标是在目标图中找到一个模式图的副本。由于图被广泛用于模拟各种对象，如分子、生化反应网络、图像、3D对象或社交网络等，因此该问题具有许多应用。它也比经典的$NP$完全图问题（例如寻找阶数为的团或哈密顿路径）更为通用。

SIP可以非常直接地被建模为一个约束满足问题（Constraint Satisfaction Problem，简称CSP），解决SIP的精确方法通常通过传播约束来减少搜索空间。可以考虑不同的约束传播算法。其中一些算法比其他算法更强大，即它们能剪除更多的搜索分支，但同时也具有更高的时间复杂度。在[1]中，比较了四种经典的精确求解方法：VF2 [2]、RI [3]、Glasgow [4]和PathLAD [5]。这项实验研究表明，RI在许多简单实例上的性能非常快且简单，但在许多其他实例上无法在合理的时间内找到解。PathLAD虽然执行强度高但计算成本也高，能够解决比RI更复杂的实例，但在非常简单的实例上效率较低。Glasgow在这两种极端之间提供了良好的折中方案，并且在运行时间限制为1000秒的情况下是最成功的求解方法。最近，Wang等人[6]、[7]引入了PathLAD+，通过添加新功能使其能够在运行时间限制为一小时的情况下解决更多实例。

在本文中，我们介绍了LAD2025，它对PathLAD进行了全面重构，并加入了新的启发式算法、剪枝规则和搜索技术，其中一些是约束编程（Constraint Programming，简称CP）求解器的经典组件，另一些则是新的。我们证明了LAD2025比Glasgow和PathLAD+更为有效。

本文的贡献与概述：第2节中，我们定义了SIP并描述了现有的主要精确求解方法。第3节中，我们描述了实验中使用的基准测试和性能度量标准。

第4节中，我们基于[8]中报告的分析结果以及[9]中实现的全局不同（Global All Different，简称GAD）约束，描述了PathLAD的重构过程。

第5节中，我们展示了如何通过利用补充标签来细化搜索域。这些标签是通过枚举路径（如[10]和[11]中提出的）以及计算顶点邻域中的最大团（如[12]中提出的）来构建的。这些标签用于在开始搜索前过滤域，并用于检测边不兼容性，从而在搜索过程中加强约束传播。

第6节中，我们通过实验比较了不同的变量排序启发式算法，并展示了[13]中引入的基于权重的排序启发式算法显著改善了解决过程。

在[14]中，研究表明随机重启结合不良记录（nogood recording）和新的随机化值排序启发式算法可以加快Glasgow的求解速度。第7节中，我们介绍了一种新的值排序启发式算法，该算法借鉴了SAT求解器[15]中的阶段节省（phase saving）技术，并可以与该随机化值排序启发式算法结合使用。

第8节中，我们介绍了一个简单的规则用于选择过滤级别。

第9节中，我们通过实验将LAD2025与其他精确求解器进行了比较。

第10节中，我们总结了我们的贡献并讨论了进一步的工作。

小节片段

图的相关符号和初步定义

集合的基数表示为$\#S$。给定两个整数值和，我们用[i, j]表示从到的整数值集合（当< />时，该集合为空）。

图由一个有序对(V, E)定义，其中V是顶点集，E?V×V是称为边的无序顶点对集合。如果(u, v)∈E，则称两个顶点和为相邻顶点。u的邻域，表示为$N(\mathrm{u)}$，即它的相邻顶点集合。

基准测试

在本文中，我们使用了与[5]中相同的基准测试集，所有这些基准测试都可以在http://perso.citi-lab.fr/csolnon/SIP.html找到。

LV是[18]中引入的基准测试，它基于Stanford GraphBase，其中包含了[23]中描述的各种类型的图。LV包含了3767个实例，这些实例是通过考虑所有图对(G, G′)得到的，其中G（或G′）是GraphBase中的前50个（或112个）图之一（不包括没有边的第一个图），并且G′至少具有...

PathLAD（V0）的重构

在第4.1节中，我们描述了[20]中介绍的LAD过滤算法。在[9]中，Gent等人讨论了实现问题并报告了对allDifferent约束的传播算法不同关键组件的实验评估。此外，[8]中分析了确保LAD约束满足DC（Decidable Compatibility）的算法，Knuth在私人通信中提出了一些改进措施。最重要的改进在第4.2至4.5节中描述。

补充标签（V1）

补充标签是与顶点（单标签）或顶点对（双标签）相关联的整数值。

定义2 补充标签

• •
  单标签是一个函数
  $l:V\cup V^{\prime }\to N$，对于任何子同构函数f和任何模式顶点u∈V，都有l(u)≤l(f(u)。

•

双标签是一个函数

$l:V\times V\cup V^{\prime }\times V^{\prime }\to N$，对于任何子同构函数f和任何模式顶点对(u, v)∈V×V，都有l(u, v)≤l(f(u)，f(v)。

补充标签用于定义不兼容性。

变量排序启发式（V2）

变量排序启发式（Variable Ordering Heuristics，简称VrOHs）在搜索树的每个节点上用于选择下一个要赋值的变量。在我们的上下文中，变量与模式顶点相关联，因此目标是选择一个尚未映射到目标顶点的模式顶点。在PathLAD（以及V0和V1中），我们使用称为minDom的VrOH，即选择满足$\#D_u$的最小值的变量。如果有多个候选变量，我们使用与Glasgow中相同的规则来打破平局，即...

重启和值排序启发式（V3）

将随机搜索与重启相结合是避免在探索搜索空间时遇到“重尾”现象的经典方法[40]。为了避免多次探索相同的搜索空间部分，通常会将随机重启与不良记录（nogood recording）结合起来：在重启搜索之前，会添加不良约束以防止再次访问已访问的节点。在[41]中，Lecoutre等人引入了在回溯搜索算法每次重启时提取的负最后决策不良（negative last decision nogoods）。

实例过滤选择（LAD2025）

在密集图上，LAD过滤算法的成本较高，因为每个二分图都有$G_{u{u}^{\prime }}$条边。在[7]中，过滤级别在搜索过程中动态调整。更具体地说，首先传播约束1和约束2，并进行简单的前向检查，即当变量< />_u的域被简化为单元素集{u′}时，u′将从所有其他变量的域中移除；对于每条模式边{u, v），所有不与u′相邻的目标顶点v′也将从< />_v中移除。

与其他精确方法的实验比较

现在让我们将LAD2025与第2节中描述的其他精确方法进行比较，即PathLAD、RI、Glasgow和PathLAD+（我们将[6]中描述的求解器称为PathLAD+23，将[7]中描述的求解器称为PathLAD+24）。我们还包括了VF3 [46]的结果，该算法最初是为解决诱导的SIP设计的，最近已扩展为解决非诱导的SIP（VF3的作者称之为edge-induced SIP）。

在表5中，我们展示了每个基准测试的未解决实例数量。

讨论

在本文中，我们发现实现非常重要：PathLAD和V0构建了相同的搜索树，但从总体加速效果来看，V0的速度是PathLAD的10倍。然而，仅凭仔细的实现并不足以获得最先进的结果。本文中描述的一些改进是CP求解器中常用的技术，例如基于权重的变量排序启发式和带有不良记录的随机重启。这些技术确实提高了我们的求解器的性能。

CRediT作者贡献声明

克里斯汀·索尔农：撰写——审阅与编辑、撰写——原始草稿、可视化、验证、软件开发、资源管理、方法论研究、形式化分析、概念化。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。