Aggregate Invariants Accelerate Continuous Subgraph Matching

Continuous subgraph matching (CSM) in dynamic graphs is a computationally intensive task, and researchers have explored whether aggregate structural tests, such as spectral filtering, can speed up this process. Spectral filtering has previously shown promise in pruning candidates for static subgraph matching by using Laplacian interlacing to reject neighborhoods that cannot host a query. The study reveals that lazily maintained spectral bounds quickly lose their pruning power in dynamic settings, becoming ineffective after just a few updates. However, the research demonstrates that exact maintenance of local spectra can be affordable and highly effective when applied selectively. This is because pruning utility and recomputation cost are inversely correlated across vertices, meaning hubs rarely prune, but small-neighborhood spectra can be recomputed in microseconds per update. When integrated into a decoupled CSM benchmark, these dynamic spectral tests successfully removed up to 51% of candidates and allowed up to 47% of update enumerations to be safely skipped. While these tests primarily accelerate operations that scale with candidate sets, such as construction and list scans, they do not significantly alter adjacency-guided exploration. The findings highlight the value of a reusable dynamic local-spectra index for accelerating specific aspects of CSM.