摘要
近期，谱过滤为静态子图匹配提供了显著的剪枝效果：拉普拉斯交错排除了无法容纳查询的候选者。我们研究了这样的聚合结构测试是否能加速动态图上的连续子图匹配（CSM），并分三部分给出答案。
首先，懒惰维护的谱界限在谱剪枝有价值的地方是不可行的：我们表征了在形式化扰动松弛下的最紧安全规则，并显示即使是它在四次触及更新内几乎失去所有剪枝能力。
其次，当选择性时，精确维护是可承受的：剪枝效用与重计算成本在顶点间呈反相关——中心节点显然从不剪枝——因此在触及时重新计算小邻域谱以微秒级的速度维持精确的局部谱，构造上是完整的。
第三，集成到一个与相同但不含谱的控制组相对比的解耦CSM基准中，这些测试最多可去除51%的候选者或安全跳过47%的更新枚举，但枚举中间结果保持不变——在两个引擎、四个真实图、两种流类型和77个解决查询中，通常为零。构造的半径分层工作负载确认该仪器能够检测到存在的例外（-99.9%的中间结果，748倍更快）。聚合测试加速了与候选集规模相关的操作——构造和列表扫描——而非邻接引导的探索。
我们提炼出了一种中间不变性方法论，用于评估CSM过滤器，并发布了一个可重用的动态局部谱索引。
博主点评： 该研究深入探讨了动态图中的连续子图匹配问题，提出的聚合不变量方法展示了在复杂数据结构中实现高效剪枝的潜力，尤其在处理动态更新时的应用前景值得关注。利用局部谱索引的创新思路，能够显著提升算法效率，推动图数据处理技术的进一步发展。