聚合不变量能否加速连续子图匹配？限制、规律与动态谱索引

# 聚合不变量能否加速连续子图匹配？极限、规律与动态谱索引
来源: https://arxiv.org/html/2606.24421

###### 摘要。

谱滤波近期在*静态*子图匹配中带来了显著的剪枝效果：拉普拉斯交错拒绝那些邻域无法容纳查询的候选节点。我们研究这种聚合结构测试能否加速动态图上的*连续*子图匹配（CSM），并分三部分回答。首先，惰性维护的谱边界恰恰在谱剪枝有价值的区域不可行：我们在形式化的扰动松弛下刻画了最紧的安全规则，并证明即使在四次触及更新内，该规则也会几乎丧失所有剪枝能力。其次，精确维护在选择性情况下是可负担的：剪枝效用与重计算成本在顶点间呈反相关——枢纽节点被证明从不剪枝——因此在触及处重计算小邻域谱能以微秒级每次更新的代价维持精确的局部谱，且完全性天然成立。第三，将其集成到解耦的CSM基准中，与剔除谱测试的完全对照相比，该测试最多可移除51%的候选节点，或在最多47%的更新中安全跳过枚举，然而枚举中间结果保持不变——除了门控跳过的第一级绑定外，通常为零——在两种引擎、四个真实图、两种流类型和77个可解查询上均成立；一个构建的半径分层工作负载证实了该工具能在异常存在时检测到它（-99.9%中间结果，快748倍）。聚合测试加速的是与候选集规模相关的操作——构造、列表扫描——而从不涉及邻域引导的探索。我们提炼出一种用于评估CSM过滤器的中间不变性方法论，并发布一个可重用的动态局部谱索引。

## 1. 引言

连续子图匹配（CSM）监控查询图 Q 在数据图 G 中的所有嵌入，其中 G 接收边插入和删除流，并报告每次更新所创建或销毁的匹配 (Kim et al., 2018; Min et al., 2021; Yang et al., 2023; Li et al., 2024)。其应用——入侵检测、欺诈环监控、实时推荐——具有两个共同特点：更新到达速率高，且关心的查询规模大且结构复杂。已发表的 CSM 索引使用标签、度和邻域标签多重集进行过滤，并通过候选邻接性上的一致性传播（边视图、动态候选空间）进行细化 (Wang et al., 2023; Sun et al., 2022b; Gou et al., 2026); 近期工作增加了基于概要的支配嵌入 (Ye et al., 2025)。但**没有**采用任何*聚合结构不变量*——例如谱、闭游走计数——来对候选邻域进行约束；值得注意的是，一致性传播操作的对象正是我们将要展示的、承载枚举成本的邻接结构，这也是聚合测试找不到立足点的部分原因。当标签信息量不足或查询规模变大时（PILOS 报告基于标签的过滤器在大约十六个查询顶点以上会彻底失效 (Skitsas et al., 2025)），基于标签的信号崩溃，枚举现象爆发。

静态子图匹配最近发现了一个更丰富的信号。PILOS (Skitsas et al., 2025) 为每个数据顶点索引其 h 跳邻域拉普拉斯矩阵的前几个特征值，并且在查询邻域的谱无法*交错*到候选节点的谱中时剪枝该候选节点：子图的填充拉普拉斯谱位置性地受其超图支配，因此该测试是单侧安全的。在低标签图和大规模查询上，这能移除大约四分之一的候选节点，并解决所有基于标签的方法都会超时的查询规模。谱编码了邻域全局结构——连通性质量、扩张性、环含量——这是任何标签或度过滤器都无法察觉的。

显而易见的研究计划——也是本文着手执行的——是将谱滤波引入 CSM。两个设计立即浮现。*惰性边界*：单个边更新会将邻域拉普拉斯矩阵扰动为一个秩为 1、范数最大为 2 的项，因此 Weyl 型不等式以每次更新 O(1) 的代价维护已认证的特征值区间，偶尔进行刷新。*精确重计算*：邻域谱在每次被触及后重新计算。两者都保留了交错性的单侧安全性，从而保证了完整性。问题在于它们是否可负担，以及产生的剪枝是否有帮助。

本文完整地回答了这两个问题，答案出乎我们最初预料。我们的研究经历了三次实验驱动的反转，每一次都重塑了设计；我们全部报告这三次反转，因为中间阶段的失败与最终系统携带的信息同样多。

#### 反转 1：惰性边界在它们关键的领域不可行。

剪枝余量——∑_t max(0, λ_t(Q) − λ_t(v)) 分离查询和候选谱的间隙——恰好是谱剪枝生效的稀疏邻域区域内的 O(1)，而每个触及边会注入特征值质量 2。我们在形式化的扰动松弛上证明了一个最优性结果：仅观察陈旧谱和插入计数的条件下，最紧的安全规则是迹预算测试（通过优超）与组合的交错移位上限的析取；并且我们经验性地展示了即使这个最优规则在第一次触及更新后仍保留不到 60% 的剪枝能力，在四次之后则几乎为零（§3）。因此，整个惰性边界族就被排除了。

#### 反转 2：精确性是可负担的——但要选择性。

扼杀惰性边界的同样稀疏性使得精确重计算成本低廉：一个 32 个顶点的邻域拉普拉斯矩阵求解只需几十微秒。此外，剪枝效用和维护成本在顶点间是*反相关的*：我们证明任何其 h 跳球包含一个度 ≥ |V(Q)| 的顶点的顶点，其主特征值永远不会被剪枝——枢纽顶点在谱上是不可剪枝的——并且测量到那些球超过 64 个节点的顶点永远不会被剪枝，同时承担最大的求解成本。一个*选择性精确*索引（SelSpec）仅在小球、标签相关的顶点上部署谱，并在每次触及后重计算，保留了 96-100% 的剪枝收益，每次更新约需 300μs，完整性天然成立（§4）。

#### 反转 3：剪枝效果并未传递。

我们将 SelSpec 作为一个即插即用的索引层集成到最先进的解耦 CSM 评估框架 (Gou et al., 2026) 中，并采用最严格的控制：完全相同的流水线减去谱测试。候选节点数量下降了 9-51%，随查询规模增长而增加，与静态设置类似；增量匹配的数量完全保持。然而，在三种查询规模和两种标签模式下，有无谱滤波时枚举中间结果的数量*完全相等*：谱测试移除的每个顶点都是邻域引导的增量枚举从未访问过的。然后，我们设计了一种静态匹配无法实现的 CSM 原生机制——一个*锚定门*——当匹配查询边周围半径 ρ 内的子查询无法嵌入到更新数据边周围球内时，跳过整个增量枚举；并且将其从谱扩展到三角形计数，后者是度信息无法企及的、子图单调的闭游走不变量。这些门在 5-47% 的更新上触发，从未出错；中间结果在第四次和第五次复制中仍然相同（§5, §6）。

这五次复制，加上一个谱图理论解释，得出了本文的核心结论：

> 聚合不变量边界规律性。在更新驱动的 CSM 中，如果流水线已经饱和了标签/度过滤，那么子图单调的聚合测试——拉普拉斯交错、顶点和边计数、三角形计数——只剪枝了那些邻域引导的枚举在其前几个扩展层级内已经丢弃的工作，在我们测量的所有自然工作负载中均是如此；昂贵的失败是注入式赋值级别的，所有聚合测试都看不见。

拉普拉斯情况并非偶然：根据 Grone–Merris–Bai 定理，拉普拉斯谱由共轭度序列优超，因此主特征值交错本质上是一个度序列测试——而度质量正是 CSM 流水线已经过滤掉的。该规律性也限定了自身的适用范围：聚合剪枝恰恰在成本随候选集规模扩展时发挥作用——静态流水线的候选空间构造以及列表驱动引擎的逐级候选列表扫描，这正是 PILOS 增益所在，也是它们为何无法传递到增量枚举的原因，因为增量枚举没有构造项；而并非邻域引导的消费者（周期性批量重新枚举、近似匹配准入控制）仍然是我们构建的门机制的有效目标。

#### 贡献。

总结如下：

- • **惰性谱维护的不可能性**（§3）：在（陈旧谱，插入计数）的形式化扰动松弛上，迹预算测试与组合交错移位上限的析取是最紧的安全规则，而即使在谱剪枝生效的区域内 O(1) 次触及后它也会崩溃。
- • **选择性精确维护原语**（§4）：一个反相关定律和一个枢纽排除定理证明了仅在可能剪枝的地方部署精确谱是合理的；由此产生的索引以微秒级的更新成本维持精确的局部谱，与图规模无关，并且可被任何消耗局部谱的动态图应用重用。
- • **聚合不变量边界规律性**（§5）：在表 2（§6.T2）的九种配置（87 个共同求解的查询）上复制，完整性违反为零，并通过 Grone–Merris–Bai 以及一个聚合与赋值的论证进行解释；此外还有 AnchorGate，一种安全、新颖的更新级机制，其 CSM 行为完善了规律性，并且其有效性对于非邻域引导的消费者仍然成立。
- • **一种方法**（§6）：中间不变性测试，它能检测候选节点减少何时与枚举无关；我们展示了候选计数在两方面都产生误导，扩展了近期 CSM 基准测试工作 (Gou et al., 2026) 提出的警示。

## 2. 预备知识

### 2.1. 连续子图匹配

数据图 G = (V, E, l) 和查询图 Q = (V_Q, E_Q, l) 携带顶点标签 l(·)。一个*嵌入*是保持标签和边的单射映射 f: V_Q → V。给定应用于 G 的边插入和删除流，CSM 在每次更新后报告被创建或销毁的嵌入集（或计数）。所有有竞争力的 CSM 系统都遵循*索引-枚举*范式 (Kim et al., 2018; Min et al., 2021; Yang et al., 2023; Li et al., 2024; Gou et al., 2026)：索引为每个查询顶点 u 维护一个候选集 C(u) ⊆ V（通常还有查询边的候选*边视图*）；每次更新触发一个以更新边为锚点的增量枚举，仅探索那些可通过候选边从锚点到达的候选节点。我们将这种探索称为*邻域引导*：候选节点仅当通过候选边从锚点可达时才参与。标准的顶点过滤器是 LDF（标签和度）和 NLF（每种标签的邻居计数）；两者都是子图单调的必要条件。

### 2.2. 邻域谱与安全剪枝

对于 S ⊆ V，令 G[S] 表示导出子图，L(S) 为其组合拉普拉斯矩阵。令 B_h(v) 为距离 v 在 h 内的顶点集合，并令 λ_1(S) ≥ λ_2(S) ≥ ... 为 L(S) 的特征值，超出 |S| 的部分用零填充。两个经典事实给出了单侧安全性。首先，添加边会向拉普拉斯矩阵添加一个半正定项，而填充则附加零，因此如果 H 作为子图嵌入到 G[S] 中，则对所有 t 有 λ_t(H) ≤ λ_t(S)。其次，嵌入不会增加距离，因此一个嵌入 f 将查询球 B_h(u) ∩ Q 映射到 G[B_h(f(u))] 中。

我们将查询侧的球谱记为 λ_t^Q(u) := λ_t(Q[B_h(u) ∩ V_Q])，数据侧的球谱记为 λ_t^G(v) := λ_t(G[B_h(v)])。

###### 引理 0 (交错安全性 (Skitsas et al., 2025))。

如果 f 是满足 f(u)=v 的嵌入，则对所有 t 有 λ_t^Q(u) ≤ λ_t^G(v)。因此，只要存在 t 使得 λ_t^Q(u) > λ_t^G(v)，就将 v 从 C(u) 中剪枝，这永远不会移除真正的匹配。

同样的论证适用于任何*子图单调的聚合不变量* φ：如果 H ⊆ G[S] 意味着 φ(H) ≤ φ(S)，则 φ(查询侧) > φ(数据侧) 是一个安全的剪枝测试。顶点计数、边计数、所有拉普拉斯特征值以及闭游走计数 tr(A^k)（例如 k=3: 三角形计数的六倍）都是子图单调的。这一族不变量是我们研究的对象。

## 3. 惰性谱边界不可行

B_h(v) 内的单个边插入将 L(B_h(v)) 扰动为 E = (e_a − e_b)(e_a − e_b)^⊤，半正定，||E||_2 = 2；删除则减去这样一项。Weyl 不等式 (Horn and Johnson, 2013) 控制这类扰动下的特征值移动。惰性方案维护数据侧谱的已认证上界 λ̄：删除只会降低真实特征值（边界自然保持有效），而插入则通过廉价的边界更新来吸收，完全重计算被推迟到边界失去区分能力为止。使用上界进行剪枝根据引理 1 是安全的。问题在于功率衰减的速度。

### 3.1. 三个边界族与一个最优性结果

#### 平坦 Weyl。

每次插入的边，对所有 i，λ̄_i += 2。实际系统中的一个微妙之处：一次边更新可能将一个携带 k>1 条边的新顶点拉入球内；按每次*更新*而非每次*诱导边*进行 +2 核算是不安全的（我们观察到了真实的违反），