Search papers, labs, and topics across Lattice.
This paper investigates the application of spectral filtering techniques to enhance continuous subgraph matching (CSM) in dynamic graphs, revealing that traditional lazy maintenance of spectral bounds is ineffective in high-value pruning scenarios. The authors establish that while selective exact maintenance is feasible, it must be strategically applied to avoid the anti-correlation between pruning utility and recomputation costs, particularly in hub vertices. Their method achieves significant candidate reduction, with up to 51% fewer candidates and 47% fewer update enumerations, without compromising enumeration intermediates across various graph types and query scenarios.
Aggregate spectral tests can eliminate over half of the candidates in continuous subgraph matching while maintaining performance across dynamic updates.
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.
