子图同构求解器与图编辑距离计算的实验评估

### 子图同构求解器与图编辑距离计算的实验评估 #### 1. 子图同构求解器的实验评估 在诱导子图同构的情况中，未解决的实例不一定是图规模最大的那些，而且不同求解器的未解决实例数量差异很大。在所有求解器都未能解决的实例中，最小的模式图有 62 条边和 30 个节点，目标图有 638 条边和 120 个节点。VF3 在诱导子图同构问题上的表现比 VF2 在非诱导子图同构问题上的表现要好很多，并且它总能快速解决那些因目标图边数少于模式图边数而明显不可行的实例。 为了更好地了解困难实例的分布情况，我们根据实例的难度将基准测试的每个类别划分为 4 个独立的组： - 简单实例：四个求解器都能在 1 秒内解决的实例。 - 困难实例：没有求解器能在 1 秒内解决，但至少有一个求解器能在 1000 秒的时间限制内解决的实例。 - 简单或困难实例：至少有一个求解器能在 1 秒内解决，而至少有一个求解器不能在 1 秒内解决的实例。 - 未解决实例：没有求解器能在 1000 秒的时间限制内解决的实例。 | 难度类型 | 定义 | | ---- | ---- | | 简单实例 | 四个求解器 1 秒内解决 | | 困难实例 | 1 秒内无解，1000 秒内至少一个求解器可解 | | 简单或困难实例 | 至少一个求解器 1 秒内可解，至少一个 1 秒内无解 | | 未解决实例 | 1000 秒内所有求解器无解 | 从结果来看，很多 randERP 实例是未解决或困难的，且没有一个是简单的，这些实例接近相变点，尽管规模小但具有挑战性。不过，并非所有未解决实例都来自 randERP。对于非诱导情况，LV 和 meshes 分别有 120 个和 11 个未解决实例；对于诱导情况，LV 有 60 个未解决实例，且这些实例并非规模最大的，有些还很小。简单实例数量很多，非诱导情况有 7787 个，诱导情况有 9109 个，这些简单实例来自除 randERP 和 randER（非诱导情况）以及 randERP（诱导情况）之外的所有类别。 下面是不同求解器在不同类别上的结果： | Class | 非诱导 SI 简单实例（G/L/V/R 时间） | 非诱导 SI 简单或困难实例（G/L/V/R #u） | 非诱导 SI 困难实例（G/L/V/R #u） | 诱导 SI 简单实例（G/L/V/R 时间） | 诱导 SI 简单或困难实例（G/L/V/R #u） | 诱导 SI 困难实例（G/L/V/R #u） | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | images |.106/.374/.201/.002 | 0(.18)/0(4.07)/13 - /0(0.01) | - - - - |.136/.388/.002/.002 | 0(.24)/0(3.58)/0(.00)/0(.01) | - - - - | | meshes |.153/.026/.044/.016 | 1 - /3 - /276 - /180 - | 20/23/91/91 |.173/.024/.001/.009 | 0(1.04)/0(.16)/103 - /237 - | 0/0/1/1 | | LV |.036/.017/.069/.008 | 12 - /9 - /886 - /206 - | 18/32/130/76 |.047/.026/.011/.024 | 4 - /8 - /52 - /96 - | 10/53/51/65 | | randERP | - - - - | 0(.21)/25 - /48 - /30 - | 0/65/69/64 | - - - - | - - - - | 0/175/175/175 | | randER | - - - - | 0(.88)/17 - /201 - /2 - | 0/57/67/14 |.021/.260/.061/.030 | 0(.43)/12 - /2 - /1 - | 0/47/5/7 | | randBVG |.017/.119/.004/.003 | 0(.07)/0(2.37)/0(.01)/2 - | - - - - |.018/.125/.002/.004 | 0(.07)/0(2.22)/3 - /4 - | - - - - | | randM |.051/.095/.013/.003 | 0(.18)/0(3.94)/18 - /2 - | - - - - |.052/.117/.003/.003 | 0(.17)/0(4.31)/6 - /0(6.11) | 0/0/1/0 | | randSF |.007/.004/.497/.001 | 0(.11)/0(.10)/80 - /15 - | - - - - |.109/.065/.027/.023 | 0(.14)/0(.21)/2 - /10 - | - - - - | | All |.094/.146/.099/.008 | 13 - /54 - /1,522 - /437 - | 38/177/357/245 |.108/.146/.005/.012 | 4 - /20 - /168 - /348 - | 10/275/233/248 | 从简单实例来看，对于非诱导情况，RI 比其他求解器快一个数量级；对于诱导情况，VF3 比 RI 快两倍，而 RI 比 Glasgow 和 LAD 快一个数量级。但在简单或困难以及困难实例上，PR 求解器解决的实例比 LAD 少，LAD 比 Glasgow 少。非诱导情况下，Glasgow、LAD、VF2 和 RI 分别有 51 个、221 个、1879 个和 682 个实例无法解决；诱导情况下，Glasgow、LAD、VF3 和 RI 分别有 14 个、295 个、416 个和 596 个实例无法解决。所以在简单或困难以及困难实例上，Glasgow 是最佳求解器。 ```mermaid graph LR A[实例输入] --> B{是否简单实例} B -- 是 --> C[RI（非诱导）/VF3（诱导）快速求解] B -- 否 --> D{是否简单或困难实例} D -- 是 --> E[Glasgow 优势求解] D -- 否 --> F{是否困难实例} F -- 是 --> E F -- 否 --> G[未解决实例] ``` 对于非诱导情况，LAD 虽然不如 Glasgow，但比 PR 求解器能解决更多实例；对于诱导情况，LAD 也不如 Glasgow，且在 randER 实例上明显不如 PR 求解器，这是因为 LAD 是为非诱导情况设计的，处理诱导情况的方式很简单。 #### 2. 求解器的实验比较与组合 在求解器的实验比较中，我们通过绘制不同难度实例的累计解决实例数量随时间的变化图来进一步分析。对于简单实例，RI（非诱导情况）和 VF3（诱导情况）在不到 0.001 秒内就能解决超过 5000 个（非诱导）和 7000 个（诱导）实例，而 CP 求解器通常需要更多时间。 对于简单或困难实例，RI（非诱导）和 VF3（诱导）能在不到 0.001 秒内解决超过 2500 个实例，但它们有数百个实例无法解决，而 Glasgow 能在不到 1 秒内轻松解决这些实例，并且在 0.3 秒后，Glasgow 解决的实例累计数量超过了 RI 和 VF3。 对于困难实例，Glasgow 明显优于其他求解器，能解决更多实例。 Glasgow 与最佳 PR 求解器（非诱导情况为 RI，诱导情况为 VF3）具有互补性。Glasgow 在非常简单的实例上需要更多时间，但能解决更多实例。我们可以利用这种互补性，先以 t1 秒为时间限制运行最佳 PR 求解器，如果在该时间限制内未解决实例，再运行 Glasgow。时间限制 t1 应足够长，让 PR 求解器有机会解决简单实例，但又不能太长，以免在 PR 求解器无法解决实例时影响总求解时间。当 t1 设为 0.1 秒时，这种简单的组合方式能充分发挥两个求解器的优势：在 0.1 秒之前，RI + Glasgow（或 VF3 + Glasgow）解决的实例累计数量与 RI（或 VF3）相同，远大于 Glasgow；0.1 秒之后，由于 Glasgow 能解决 RI（或 VF3）无法解决的实例，RI + Glasgow（或 VF3 + Glasgow）解决的实例累计数量增长速度比 RI（或 VF3）快；几秒后，由于 RI（或 VF3）运行的 0.1 秒延迟可忽略不计，RI + Glasgow（或 VF3 + Glasgow）解决的实例累计数量与 Glasgow 非常接近。 当然，这种简单的方法可以通过考虑更多求解器（包括每个求解器的更多变体，使用不同的排序启发式方法等）来改进。我们可以将所有求解器组合成一个求解器组合，使用算法选择方法动态地从组合中选择最适合解决每个新子图同构实例的求解器。 #### 3. 图编辑距离计算库 GEDLIB 图编辑距离（GED）是结构模式识别领域广泛使用的一种灵活的图不相似度度量。GEDLIB 是一个用于精确或近似计算 GED 的 C++ 库，它已经实现了许多现有的 GED 算法，并且设计得易于扩展。要实现新的编辑成本函数和 GED 算法，只需实现库中包含的抽象类。用户在实现这些扩展时可以使用多种实用工具，如深度神经网络、支持向量机、混合整数线性规划求解器、黑盒优化器以及带或不带纠错功能的线性和分配问题求解器。 总的来说，现代求解器能在几毫秒内解决许多非常简单的子图同构实例，有些实例甚至涉及具有数千个节点的大型图。但仍然存在一些小实例，任何求解器都无法在合理的时间内解决。在实际应用中，困难实例虽然不如简单实例常见，但也会出现，因此评估求解器在这些困难实例上的性能很重要。利用多核并行求解困难实例是一个有前途的研究方向，但在评估这些方法的性能时需要特别注意，因为对于 NP 完全问题，顺序求解器和并行求解器之间的平均加速比意义不大，不同实例的加速比差异很大，且与实例规模无关。例如，在简单实例上加速比通常很低，而在困难实例上出现超线性加速比并不罕见。对于真正困难的实例，由于无法在合理时间内解决，加速比无法计算。更好的性能评估指标可以是逐实例比较时间的散点图，或者是用于衡量解决相同数量实例的超时比率的聚合加速比指标。 ### 子图同构求解器与图编辑距离计算的实验评估 #### 4. 性能评估指标的深入分析 在评估子图同构求解器和图编辑距离计算方法的性能时，传统的平均加速比指标存在局限性。对于 NP 完全问题，不同实例的加速比差异巨大，且与实例规模并无直接关联。 为了更直观地展示这一现象，我们来看一个具体的例子。以并行版本的 Glasgow 求解器（使用 32 个核心）为例： - **简单实例**：在顺序版 Glasgow 能在 1 秒内解决的简单实例上，加速比在 0.1 到 32 之间波动，平均加速比接近 1。这表明在简单实例上，并行计算并没有带来显著的性能提升。 - **困难实例**：对于那些顺序版 Glasgow 在 1 秒内无法解决，但在 1000 秒内可以解决的困难实例，加速比在 1 到 583 之间，平均加速比为 14。而且，并行版 Glasgow 还能解决一些顺序版在 1000 秒内都无法解决的实例。如果将这些实例纳入计算，平均加速比会大于 19。 由此可见，平均加速比不能清晰地反映求解器的性能。相比之下，逐实例比较时间的散点图和聚合加速比指标能提供更有价值的信息。例如，聚合加速比指标通过衡量解决相同数量实例的超时比率，能更准确地评估求解器的性能。如顺序版 Glasgow 在 1000 秒内解决了 14356 个实例，其中最难的实例用时 939 秒；而并行版 Glasgow 在 19 秒的超时时间内就解决了相同数量的实例，这样计算得到的聚合加速比为 939 / 19 = 49。 #### 5. 图编辑距离计算的实际应用与挑战 图编辑距离（GED）在结构模式识别领域有着广泛的应用，如分子结构分析、街道网络建模和图像识别等。然而，GED 的精确计算是 NP 难问题，这给实际应用带来了挑战。 GEDLIB 库为解决这一问题提供了有效的途径。它不仅实现了许多现有的 GED 算法，还支持用户扩展新的编辑成本函数和算法。用户在扩展 GEDLIB 时，可以利用多种实用工具，下面是一个简单的操作步骤列表： 1. **定义需求**：明确要实现的新编辑成本函数或 GED 算法的具体需求。 2. **实现抽象类**：在 GEDLIB 中找到对应的抽象类，并按照要求实现这些类。 3. **使用实用工具**：根据具体需求，选择合适的实用工具，如深度神经网络用于特征提取，支持向量机用于分类等。 4. **测试与优化**：对实现的扩展进行测试，并根据测试结果进行优化。 在实际应用中，不同的编辑成本函数和算法可能会对 GED 的计算结果产生显著影响。因此，选择合适的方法对于提高计算效率和准确性至关重要。例如，在处理大规模图数据时，可能需要选择近似算法来降低计算复杂度；而在对精度要求较高的场景中，则需要使用精确算法。 #### 6. 求解器组合策略的优化与展望 前面提到的求解器组合策略（如 RI + Glasgow 或 VF3 + Glasgow）虽然能在一定程度上提高求解性能，但仍有优化的空间。 我们可以考虑以下优化方向： 1. **增加求解器数量**：将更多的求解器纳入组合，包括每个求解器的不同变体，使用不同的排序启发式方法，以增加求解的多样性。 2. **智能算法选择**：使用更智能的算法选择方法，根据实例的特征动态地从求解器组合中选择最适合的求解器。例如，可以通过机器学习算法对实例进行分类，然后根据分类结果选择求解器。 3. **自适应时间分配**：根据实例的难度自适应地调整每个求解器的时间限制，而不是固定为 0.1 秒。例如，对于较简单的实例，可以缩短 PR 求解器的时间限制；对于较困难的实例，可以适当延长。 以下是一个求解器组合优化的流程图： ```mermaid graph LR A[实例输入] --> B{实例特征分析} B --> C[选择求解器组合] C --> D{是否有合适求解器} D -- 是 --> E[分配时间限制] E --> F[运行求解器] F --> G{是否解决} G -- 是 --> H[输出结果] G -- 否 --> C D -- 否 --> I[扩展求解器组合] I --> C ``` 未来，随着硬件技术的发展和算法的不断创新，我们有望在子图同构求解和图编辑距离计算领域取得更大的突破。例如，量子计算技术可能为解决 NP 难问题带来新的思路，而深度学习算法也可能在特征提取和算法选择方面发挥更大的作用。 综上所述，子图同构求解器和图编辑距离计算是一个充满挑战和机遇的研究领域。通过不断优化求解器性能、改进评估指标和探索新的算法，我们可以更好地应对实际应用中的各种问题。