动态图中用谱特性加速子图匹配,可减少51%候选集
Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index
- 基于局部谱特性构建动态索引,更新时仅重算受影响节点
- 实验显示最多砍掉51%候选节点或跳过47%更新枚举
- 适合大规模动态图上需频繁匹配子结构的场景
谱滤波最近在静态子图匹配中实现了显著剪枝:拉普拉斯交错可排除无法容纳查询邻域的候选。我们研究此类整体结构测试能否加速动态图上的连续子图匹配(CSM),并分三部分回答。首先,懒惰维护的谱界在谱剪枝最有价值时失效:我们在形式化扰动松弛下刻画最紧的安全规则,发现其在四次连续更新内几乎完全丧失剪枝能力。其次,选择性精确维护可行:剪枝效率与重计算成本呈负相关——枢纽节点理论上永不剪枝,因此仅在触达节点上重算小邻域谱,每更新耗时微秒级,天然保证精确局部谱。第三,集成至解耦式CSM基准,对比相同但无谱测试的对照组,测试可移除高达51%候选或安全跳过47%更新枚举,而枚举中间结果不变——在两个引擎、四个真实图、两种流类型、77个求解查询中,除被跳过的初始绑定外,中间结果基本为零;构造的半径分层工作负载证实该工具在例外情况能检测到(中间结果-99.9%,速度提升748倍)。聚合测试加速随候选集规模扩展的部分——如构造、列表扫描——而非邻接引导探索。我们提炼出一种中间不变性方法论用于评估CSM过滤器,并发布可复用的动态局部谱索引。
原文摘要 · Abstract (English)
Spectral filtering recently delivered substantial pruning for \emph{static} subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query. We study whether such aggregate structural tests can accelerate \emph{continuous} subgraph matching (CSM) over dynamic graphs, and answer in three parts. First, lazily maintained spectral bounds are infeasible exactly where spectral pruning has value: we characterize the tightest safe rule over a formalized perturbation relaxation and show that even it loses essentially all pruning power within four touching updates. Second, exact maintenance is affordable when selective: pruning utility and recomputation cost are anti-correlated across vertices -- hubs provably never prune -- so recomputing small-neighborhood spectra on touch sustains exact local spectra at microseconds per update, complete by construction. Third, integrated into a decoupled CSM benchmark against an identical-minus-spectra control, the tests remove up to $51\%$ of candidates or safely skip up to $47\%$ of update enumerations, yet enumeration intermediates remain unchanged -- beyond the gates' skipped first-level bindings, typically zero -- across two engines, four real graphs, two stream types, and $77$ solved queries; a constructed radius-stratified workload confirms the instrument detects the exception when one exists ($-99.9\%$ intermediates, $748\times$ faster). Aggregate tests accelerate what scales with candidate sets -- construction, list scans -- never adjacency-guided exploration. We distill an intermediate-invariance methodology for evaluating CSM filters and release a reusable dynamic local-spectra index.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。