子图同构求解器的实验评估

### 子图同构求解器的实验评估 #### 1. 引言 子图同构（Subgraph Isomorphism，SI）是一个NP完全问题，其核心在于在目标图中寻找模式图的副本，即找到一种映射，使每个模式节点与不同的目标节点关联，同时保持边的连接关系。SI有两种主要变体：非诱导情况下，只需保留模式边；诱导情况下，目标边也必须保留。 在模式识别领域，解决SI问题最著名的算法有VF2、VF3和RI，这些被称为PR求解器。PR求解器在状态空间中进行深度优先搜索，每个状态对应部分映射，通过递归扩展部分映射来增加新的映射节点对。 在约束编程领域，SI可直接建模为约束满足问题。自Ullman以来，提出了许多基于约束的求解器，如nRF+、ILF、LAD、SND和Glasgow等，这些被称为CP求解器。CP求解器同样递归扩展部分映射，但不同的是，它们会为每个未映射的模式节点维护候选目标节点列表，并通过传播约束来减少列表，虽然这种约束传播机制在内存和时间上开销较大，但能减少需要探索的状态数量。 近期的PR和CP求解器能够快速解决涉及数千个节点的大型SI实例。NP完全问题并不意味着所有实例都难以解决，有些实例可能很容易。Cheeseman等人指出，NP完全问题可以用至少一个“序参数”来概括，难题通常出现在该参数的临界值处。McCreesh等人利用此方法，根据三种随机图模型生成“极难”的随机SI实例。例如，对于Erdős-Rényi随机图，通过固定模式和目标节点数量，改变边的概率，可以生成非诱导SI实例，在模式稀疏、目标密集和模式密集、目标稀疏之间会发生相变，通过计算预期解的数量可以预测相变位置，处于相变位置的实例即使图规模较小，对所有求解器来说也具有计算挑战性。此外，一些被预测为简单、能被CP求解器轻松解决的小实例，对PR求解器却具有挑战性。 本文通过对来自八个基准测试的14,621个实例进行实验，扩展了相关研究。评估和比较了RI、VF2、VF3、Glasgow和LAD求解器，旨在探究求解时间与图大小的关系，识别难易实例，以及展示如何结合PR和CP求解器以发挥它们的互补性。 #### 2. 实验设置 - **测试套件**：考虑来自八个基准测试的14,621个实例，具体信息如下表所示： | 类别 | 实例数量 | 模式图 | | | 目标图 | | | | --- | --- | --- | --- | --- | --- | --- | --- | | | | 节点数 | 边数 | 密度 | 节点数 | 边数 | 密度 | | | | 最小 | 最大 | 最小 | 最大 | 最小 | 最大 | 最小 | 最大 | 最小 | 最大 | 最小 | 最大 | | images | 6,302 | 4 | 170 | 4 | 241 | .02 | .67 | 1,072 | 5,972 | 1,539 | 8,888 | .00 | .00 | | meshes | 3,018 | 40 | 199 | 114 | 539 | .02 | .15 | 201 | 5,873 | 252 | 15,292 | .00 | .02 | | LV | 3,831 | 10 | 128 | 10 | 4,950 | .02 | 1.00 | 10 | 6,671 | 10 | 209,000 | .00 | 1.00 | | randERP | 200 | 30 | 30 | 128 | 387 | .29 | .89 | 150 | 150 | 4,132 | 8,740 | .37 | .78 | | randER | 270 | 40 | 360 | 41 | 12,410 | .02 | .21 | 200 | 600 | 436 | 34,210 | .02 | .19 | | randBVG | 540 | 40 | 480 | 43 | 2,137 | .01 | .20 | 200 | 800 | 299 | 3,600 | .00 | .05 | | randM | 360 | 51 | 777 | 76 | 2,075 | .01 | .08 | 256 | 1,296 | 672 | 4,377 | .00 | .03 | | randSF | 100 | 180 | 900 | 478 | 5,978 | .01 | .17 | 200 | 1000 | 592 | 7,148 | .01 | .16 | 其中，images和meshes来自实际应用，模式和目标图分别从分割图像和3D网格中提取。LV基准测试使用来自斯坦福图数据库的113个具有不同属性的图，将图分为两部分，考虑满足模式图属于第一部分、目标图属于第一或第二部分且目标图节点数不少于模式图的所有图对。rand*系列是随机生成的实例，randERP实例接近相变位置，预计较难，所有图为Erdős-Rényi图；randER、randBVG和randM分别来自特定数据库，图分别为Erdős-Rényi图、（修改后的）有界价图和4D网格；randSF包含无标度图。除randSF中的20个实例外，randER、randBVG、randM和randSF中的所有实例在构造上都是可行的，因为模式图是从目标图中提取的。所有图的边数至少与节点数相同，因此图的大小主要由边数决定。 - **性能指标**：实验在EPCC Cirrus HPC设施上进行，系统配备双Intel Xeon E5 - 2695 v4 CPU和256 Gb RAM，运行Centos 7.3.1611，编译器为GCC 7.2.0。每次运行的CPU时间限制为1,000 s，有些实例即使将时间限制增加到100,000 s仍无法解决。考虑两种不同的性能指标：当所有求解器都能解决基准测试中的所有实例时，报告平均求解时间；当部分实例在时间限制内未解决时，报告在时间限制内解决的实例数量，并绘制解决实例的累积数量随时间的变化曲线。不将内存消耗作为性能指标，因为所有求解器的内存复杂度都是多项式的，即使对于最大的实例也不会耗尽内存，但CP求解器比PR求解器需要更多内存，因为它们需要维护候选目标节点列表。Glasgow考虑其默认的有偏变体。 #### 3. 求解时间是否取决于图的大小？ 为研究求解时间与实例大小的关系，绘制了每个求解器在每个实例上的求解时间图。每个实例对应一个点(x, y)，其中x是模式图的边数，y是目标图的边数，颜色表示求解时间：黄色表示小于1秒，黑色表示在1000 s内未解决（如果多个实例大小相同，颜色对应所有这些实例的平均求解时间）。 正如NP完全问题所预期的，这些图表明实例的难度并不取决于其大小。以非诱导情况为例，未解决的实例（黑点）并不特别集中在图的右上角（对应最大的实例）。不同求解器未解决的实例数量差异较大，但有些黑点对所有求解器都是相同的。在所有求解器都无法解决的实例中，最小的模式图有62条边和30个节点，最小的目标图有400条边和86个节点，而许多更大的实例可以在1秒内解决。灰色线将目标边数多于模式边数的实例（左上角）与目标边数少于模式边数的实例（右下角）分开，右下角的所有实例显然是不可行的，但VF2和RI无法解决其中一些实例。 以下是不同类别中未解决实例的相关信息： | 类别 | 非诱导SI | | | | | | 诱导SI | | | | | | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 可行性 | | 难度 | | | | 可行性 | | 难度 | | | | | | 可行 | 不可行 | 容易 | 难易不定 | 难 | 未解决 | 可行 | 不可行 | 容易 | 难易不定 | 难 | 未解决 | | images | 52 | 6,250 | 2,555 | 3,747 | 0 | 0 | 50 | 6,252 | 2,764 | 3,538 | 0 | 0 | | meshes | 88 | 2,930 | 2,361 | 553 | 93 | 11 | 0 | 3,018 | 2,492 | 521 | 1 | 0 | | LV | 596 | 3,235 | 2,097 | 1,477 | 137 | 120 | 191 | 3,640 | 2,939 | 693 | 139 | 60 | | randERP | 164 | 36 | 0 | 48 | 69 | 83 | 0 | 200 | 0 | 0 | 180 | 20 | | randER | 270 | 0 | 0 | 203 | 67 | 0 | 270 | 0 | 72 | 141 | 57 | 0 | | randBVG | 540 | 0 | 461 | 79 | 0 | 0 | 540 | 0 | 454 | 86 | 0 | 0 | | randM | 360 | 0 | 309 | 51 | 0 | 0 | 360 | 0 | 313 | 45 | 2 | 0 | | randSF | 80 | 20 | 4 | 96 | 0 | 0 | 80 | 20 | 75 | 25 | 0 | 0 | | 总计 | 2,150 | 12,471 | 7,787 | 6,254 | 366 | 214 | 1,491 | 13,130 | 9,109 | 5,053 | 379 | 80 | 从这些数据可以看出，不同类别和不同类型（非诱导和诱导）的SI问题在可行性、难易程度和未解决实例数量上存在差异。 下面用mermaid流程图展示求解时间与图大小关系的分析流程： ```mermaid graph LR A[开始] --> B[绘制求解时间图] B --> C[分析未解决实例分布] C --> D{实例难度是否取决于大小?} D -- 否 --> E[得出结论: 难度与大小无关] D -- 是 --> F[进一步分析特殊情况] F --> E E --> G[结束] ``` 综上所述，通过对大量实例的实验分析，我们对SI问题的求解时间与图大小的关系有了更深入的理解，为后续选择合适的求解器和优化求解策略提供了依据。 #### 4. 识别难易实例 通过对实验数据的进一步分析，可以识别出不同求解器在处理不同难度实例时的表现差异。 - **PR求解器在简单实例上的优势**：RI和VF3等PR求解器能够非常快速地解决大量简单实例，而Glasgow或LAD等CP求解器在处理这些实例时可能需要更多时间。这是因为PR求解器在状态空间的搜索方式相对直接，对于一些结构较为简单、易于匹配的实例，能够迅速找到解决方案。例如，在某些rand*系列的简单实例中，PR求解器可以在极短的时间内完成求解。 - **CP求解器在困难实例上的表现**：然而，当遇到一些复杂的实例时，PR求解器往往会遇到困难，而CP求解器则能够发挥其优势。CP求解器通过维护候选目标节点列表和传播约束的方式，减少了需要探索的状态数量，从而在处理困难实例时更加高效。例如，在一些来自实际应用的复杂实例中，Glasgow或LAD能够快速解决，而RI和VF3则可能失败。 以下是不同求解器在不同难度实例上的表现对比表格： | 求解器 | 简单实例求解时间 | 困难实例求解情况 | | --- | --- | --- | | RI | 短 | 部分失败 | | VF3 | 短 | 部分失败 | | Glasgow | 部分较长 | 多数成功 | | LAD | 部分较长 | 多数成功 | 从表格中可以清晰地看出，不同求解器在处理不同难度实例时具有明显的差异。 下面用mermaid流程图展示识别难易实例的流程： ```mermaid graph LR A[开始] --> B[分析求解时间数据] B --> C{实例求解时间短?} C -- 是 --> D[标记为简单实例] C -- 否 --> E{实例求解失败?} E -- 是 --> F[标记为困难实例] E -- 否 --> G[标记为中等难度实例] D --> H[统计简单实例数量] F --> I[统计困难实例数量] G --> J[统计中等难度实例数量] H --> K[对比求解器表现] I --> K J --> K K --> L[结束] ``` #### 5. 结合PR和CP求解器 由于PR求解器和CP求解器在处理不同难度实例时具有互补性，因此可以将它们结合起来使用，以充分发挥各自的优势。 - **结合策略**：一种简单有效的结合策略是，首先使用PR求解器对实例进行求解，如果在较短时间内（例如设定一个时间阈值）无法解决，则切换到CP求解器继续求解。这种策略可以在保证对简单实例快速求解的同时，也能够处理复杂实例。 以下是结合PR和CP求解器的伪代码示例： ```python def combined_solver(instance, time_threshold): # 首先使用PR求解器 pr_solver = PR_Solver() result = pr_solver.solve(instance, time_limit=time_threshold) if result is not None: return result # 如果PR求解器失败，使用CP求解器 cp_solver = CP_Solver() return cp_solver.solve(instance) ``` - **结合效果**：通过实验验证，这种结合策略能够显著提高整体的求解效率。在处理大量实例时，既可以利用PR求解器的快速性解决简单实例，又可以依靠CP求解器的强大能力解决困难实例，从而减少了总的求解时间，提高了求解成功率。 下面用mermaid流程图展示结合PR和CP求解器的流程： ```mermaid graph LR A[开始] --> B[使用PR求解器] B --> C{在时间阈值内解决?} C -- 是 --> D[输出结果] C -- 否 --> E[使用CP求解器] E --> F[输出结果] D --> G[结束] F --> G ``` ### 总结 通过对来自八个基准测试的14,621个实例的实验评估，深入研究了子图同构（SI）问题的求解情况。实验结果表明，SI问题的求解时间并不取决于图的大小，一些小实例可能比大实例更难解决。不同的求解器在处理不同难度的实例时表现各异，PR求解器在简单实例上具有优势，而CP求解器在困难实例上表现更好。通过结合PR和CP求解器，可以充分发挥它们的互补性，提高整体的求解效率和成功率。这些研究结果为实际应用中选择合适的求解器和优化求解策略提供了重要的参考依据。未来，可以进一步探索更有效的结合策略和优化算法，以应对更加复杂的SI问题。