Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index

# Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index
Source: [https://arxiv.org/html/2606.24421](https://arxiv.org/html/2606.24421)
###### Abstract\.

Spectral filtering recently delivered substantial pruning for*static*subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query\. We study whether such aggregate structural tests can accelerate*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 to51%51\\%of candidates or safely skip up to47%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, and7777solved queries; a constructed radius\-stratified workload confirms the instrument detects the exception when one exists \(−99\.9%\-99\.9\\%intermediates,748×748\\timesfaster\)\. 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\.

## 1\.Introduction

Continuous subgraph matching \(CSM\) monitors all embeddings of a query graphQQin a data graphGGthat receives a stream of edge insertions and deletions, reporting the matches created or destroyed by each update\(Kim et al\.,[2018](https://arxiv.org/html/2606.24421#bib.bib14); Min et al\.,[2021](https://arxiv.org/html/2606.24421#bib.bib20); Yang et al\.,[2023](https://arxiv.org/html/2606.24421#bib.bib27); Li et al\.,[2024](https://arxiv.org/html/2606.24421#bib.bib18)\)\. Its applications—intrusion detection, fraud\-ring monitoring, real\-time recommendation—share two characteristics: updates arrive at high rates, and queries of interest are large and structurally complex\. Published CSM indexes filter with labels, degrees, and neighborhood label multisets, refined by consistency propagation over candidate adjacency \(edge views, dynamic candidate spaces\)\(Wang et al\.,[2023](https://arxiv.org/html/2606.24421#bib.bib26); Sun et al\.,[2022b](https://arxiv.org/html/2606.24421#bib.bib24); Gou et al\.,[2026](https://arxiv.org/html/2606.24421#bib.bib8)\); recent work adds synopsis\-based dominance embeddings\(Ye et al\.,[2025](https://arxiv.org/html/2606.24421#bib.bib28)\)\. What none uses is an*aggregate structural invariant*—spectra, closed\-walk counts—of candidate neighborhoods; and notably, consistency propagation operates on exactly the adjacency structure that, as we will show, carries enumeration cost, which is part of why aggregate tests find no purchase\. When labels are uninformative or queries grow large \(PILOS reports label\-based filters failing wholesale beyond roughly sixteen query vertices\(Skitsas et al\.,[2025](https://arxiv.org/html/2606.24421#bib.bib21)\)\), the label\-based signals collapse and enumeration explodes\.

Static subgraph matching recently found a richer signal\. PILOS\(Skitsas et al\.,[2025](https://arxiv.org/html/2606.24421#bib.bib21)\)indexes, for every data vertex, the top eigenvalues of the Laplacian of itshh\-hop neighborhood, and prunes a candidate whenever the query neighborhood’s spectrum cannot*interlace*into the candidate’s: a subgraph’s padded Laplacian spectrum is dominated position\-wise by its supergraph’s, so the test is one\-sided safe\. On low\-label graphs and large queries this removes roughly a quarter of candidates and solves query sizes at which all label\-based methods time out\. Spectra encode neighborhood\-global structure—connectivity mass, expansion, cycle content—that no label or degree filter sees\.

The obvious research program, and the one this paper set out to execute, is to bring spectral filtering to CSM\. Two designs suggest themselves immediately\.*Lazy bounds*: a single edge update perturbs a neighborhood Laplacian by a rank\-one term of norm at most 2, so Weyl\-type inequalities maintain certified eigenvalue intervals atO​\(1\)O\(1\)per update, refreshed occasionally\.*Exact recomputation*: neighborhood spectra are recomputed whenever touched\. Both preserve the one\-sided safety of interlacing, hence completeness\. The questions are whether either is affordable, and whether the resulting pruning helps\.

This paper answers both questions completely, and the answers are not what we expected when we began\. Our study proceeded through three experiment\-driven reversals, each of which reshaped the design; we report all three because the intermediate failures carry as much information as the final system\.

#### Reversal 1: lazy bounds are impossible where they matter\.

Pruning margins—the gaps∑tmax⁡\(0,λt​\(Q\)−λt​\(v\)\)\\sum\_\{t\}\\max\(0,\\lambda\_\{t\}\(Q\)\-\\lambda\_\{t\}\(v\)\)separating query from candidate spectra—areO​\(1\)O\(1\)in exactly the sparse\-neighborhood regime where spectral pruning fires, while each touching edge injects eigenvalue mass 2\. We prove an optimality result over a formalized perturbation relaxation: the tightest safe rule observing only the stale spectrum and an insert count is the disjunction of a trace\-budget test \(via majorization\) with composed interlacing\-shift ceilings; and we show empirically that even this optimal rule retains under60%60\\%of pruning power after one touching update and essentially none after four \(§[3](https://arxiv.org/html/2606.24421#S3)\)\. The entire lazy\-bound family is thereby closed off\.

#### Reversal 2: exactness is affordable—selectively\.

The same sparsity that kills lazy bounds makes exact recomputation cheap: a 32\-vertex neighborhood Laplacian solve costs tens of microseconds\. Moreover, pruning utility and maintenance cost are*anti\-correlated*across vertices: we prove that any vertex whosehh\-hop ball contains a vertex of degree≥\|V​\(Q\)\|\\geq\|V\(Q\)\|can never be pruned on its leading eigenvalue—hubs are spectrally unprunable—and measure that vertices with balls above 64 nodes never prune at all, while carrying the largest solve costs\. A*selective exact*index \(SelSpec\) that deploys spectra only on small\-ball, label\-relevant vertices and recomputes on touch retains96−100%96\\\!\-\\\!100\\%of pruning benefit at∼300​μ​s\\sim\\\!300\\mu sper update, completeness holding by construction \(§[4](https://arxiv.org/html/2606.24421#S4)\)\.

#### Reversal 3: the pruning does not transfer\.

We integratedSelSpecinto a state\-of\-the\-art decoupled CSM evaluation framework\(Gou et al\.,[2026](https://arxiv.org/html/2606.24421#bib.bib8)\)as a drop\-in index layer, against the strictest possible control: the identical pipeline minus the spectral test\. Candidates fall by9−51%9\\\!\-\\\!51\\%, growing with query size as in the static setting; the number of incremental matches is preserved exactly\. Yet across three query scales and two label regimes, the count of enumeration intermediates is*exactly equal*with and without spectral filtering: every vertex the spectral test removes is one the adjacency\-guided delta enumeration never visits\. We then designed a CSM\-native mechanism unavailable to static matching—an*anchored gate*that skips a whole delta enumeration when the sub\-query within radiusρ\\rhoof the matched query edge cannot embed in the ball around the updated data edge—and extended it beyond spectra to triangle counts, which are subgraph\-monotone closed\-walk invariants outside the reach of degree information\. The gates fire on5−47%5\\\!\-\\\!47\\%of updates, never wrongly; the intermediates remain identical a fourth and a fifth time \(§[5](https://arxiv.org/html/2606.24421#S5), §[6](https://arxiv.org/html/2606.24421#S6)\)\.

These five replications, together with a spectral\-graph\-theoretic explanation, yield the central result of the paper:

> Aggregate\-invariant boundary regularity\.In update\-driven CSM whose pipeline already saturates label/degree filtering, subgraph\-monotone aggregate tests—Laplacian interlacing, vertex and edge counts, triangle counts—pruned only work that adjacency\-guided enumeration discarded within its first expansion levels, in every natural workload we measured; the expensive failures were injective\-assignment\-level, invisible to every aggregate\.

The Laplacian case is not an accident: by the Grone–Merris–Bai theorem, the Laplacian spectrum is majorized by the conjugate degree sequence, so top\-eigenvalue interlacing is, up to majorization slack, a degree\-sequence test—and degree mass is precisely what CSM pipelines already filter\. The regularity also delimits its own scope: aggregate pruning pays exactly where cost scales with candidate\-set size—static pipelines’ candidate\-space construction and the per\-level candidate\-list scans of list\-driven engines, which is where PILOS’s gains live and why they cannot transfer to delta enumeration, which has no construction term; and consumers that are not adjacency\-guided \(periodic batch re\-enumeration, approximate\-matching admission control\) remain valid targets for the gate machinery we built\.

#### Contributions\.

In summary:

- •Impossibility of lazy spectral maintenance\(§[3](https://arxiv.org/html/2606.24421#S3)\): the disjunction of a trace\-budget test and composed interlacing\-shift ceilings is the tightest safe rule over a formalized perturbation relaxation of \(stale spectrum, insert count\), and even it collapses withinO​\(1\)O\(1\)touches in the regime where spectral pruning fires\.
- •A selective exact maintenance primitive\(§[4](https://arxiv.org/html/2606.24421#S4)\): an anti\-correlation law and a hub\-exclusion theorem justify deploying exact spectra only where they can prune; the resulting index maintains exact local spectra at microsecond update cost, independent of graph size, and is reusable for any dynamic\-graph application consuming local spectra\.
- •The aggregate\-invariant boundary regularity\(§[5](https://arxiv.org/html/2606.24421#S5)\): replicated across the nine configurations of Table[2](https://arxiv.org/html/2606.24421#S6.T2)\(8787co\-solved queries\) with zero completeness violations, explained via Grone–Merris–Bai and an aggregate\-versus\-assignment argument; plusAnchorGate, a safe, novel update\-level mechanism whose CSM behavior completes the regularity and whose validity persists for non\-adjacency\-guided consumers\.
- •A methodology\(§[6](https://arxiv.org/html/2606.24421#S6)\): the intermediate\-invariance test, which detects when candidate reductions are enumeration\-irrelevant; we show candidate counts mislead in both directions, extending the caveat raised by recent CSM benchmarking work\(Gou et al\.,[2026](https://arxiv.org/html/2606.24421#bib.bib8)\)\.

## 2\.Preliminaries

### 2\.1\.Continuous Subgraph Matching

A data graphG=\(V,E,ℓ\)G=\(V,E,\\ell\)and query graphQ=\(VQ,EQ,ℓ\)Q=\(V\_\{Q\},E\_\{Q\},\\ell\)carry vertex labelsℓ​\(⋅\)\\ell\(\\cdot\)\. An*embedding*is an injective mappingf:VQ→Vf:V\_\{Q\}\\to Vpreserving labels and edges\. Given a stream of edge insertions and deletions applied toGG, CSM reports after each update the set \(or count\) of embeddings created or destroyed\. All competitive CSM systems follow an*index–enumerate*paradigm\(Kim et al\.,[2018](https://arxiv.org/html/2606.24421#bib.bib14); Min et al\.,[2021](https://arxiv.org/html/2606.24421#bib.bib20); Yang et al\.,[2023](https://arxiv.org/html/2606.24421#bib.bib27); Li et al\.,[2024](https://arxiv.org/html/2606.24421#bib.bib18); Gou et al\.,[2026](https://arxiv.org/html/2606.24421#bib.bib8)\): an index maintains, for each query vertexuu, a candidate setC​\(u\)⊆VC\(u\)\\subseteq V\(and often candidate*edge views*for query edges\); each update triggers a delta enumeration anchored at the updated edge, exploring only candidates adjacent to the partial embedding under construction\. We call this exploration*adjacency\-guided*: a candidate participates only if reachable from the anchor through candidate edges\. The standard vertex filters are LDF \(label and degree\) and NLF \(per\-label neighbor counts\); both are subgraph\-monotone necessary conditions\.

### 2\.2\.Neighborhood Spectra and Safe Pruning

ForS⊆VS\\subseteq VletG​\[S\]G\[S\]denote the induced subgraph andL​\(S\)L\(S\)its combinatorial Laplacian\. LetBh​\(v\)B\_\{h\}\(v\)be the set of vertices within distancehhofvv, and letλ1​\(S\)≥λ2​\(S\)≥⋯\\lambda\_\{1\}\(S\)\\geq\\lambda\_\{2\}\(S\)\\geq\\cdotsbe the eigenvalues ofL​\(S\)L\(S\), padded with zeros beyond\|S\|\|S\|\. Two classical facts give one\-sided safety\. First, adding edges adds a PSD term to the Laplacian, and padding appends zeros, so ifHHembeds intoG​\[S\]G\[S\]as a subgraph thenλt​\(H\)≤λt​\(S\)\\lambda\_\{t\}\(H\)\\leq\\lambda\_\{t\}\(S\)for alltt\. Second, embeddings do not increase distances, so an embeddingffmaps the query ballBh​\(u\)∩QB\_\{h\}\(u\)\\cap QintoG​\[Bh​\(f​\(u\)\)\]G\[B\_\{h\}\(f\(u\)\)\]\.

We writeλtQ​\(u\):=λt​\(Q​\[Bh​\(u\)∩VQ\]\)\\lambda^\{Q\}\_\{t\}\(u\):=\\lambda\_\{t\}\\\!\\big\(Q\[B\_\{h\}\(u\)\\cap V\_\{Q\}\]\\big\)for the query\-side ball spectrum atuuandλtG​\(v\):=λt​\(G​\[Bh​\(v\)\]\)\\lambda^\{G\}\_\{t\}\(v\):=\\lambda\_\{t\}\\\!\\big\(G\[B\_\{h\}\(v\)\]\\big\)for the data\-side ball spectrum atvv\.

###### Lemma 0 \(Interlacing safety\(Skitsas et al\.,[2025](https://arxiv.org/html/2606.24421#bib.bib21)\)\)\.

Ifffis an embedding withf​\(u\)=vf\(u\)=v, thenλtQ​\(u\)≤λtG​\(v\)\\lambda^\{Q\}\_\{t\}\(u\)\\leq\\lambda^\{G\}\_\{t\}\(v\)for alltt\. Hence pruningvvfromC​\(u\)C\(u\)whenever∃t:λtQ​\(u\)\>λtG​\(v\)\\exists t:\\ \\lambda^\{Q\}\_\{t\}\(u\)\>\\lambda^\{G\}\_\{t\}\(v\)never removes a true match\.

The same argument applies to any*subgraph\-monotone aggregate invariant*ϕ\\phi: ifH⊆G​\[S\]H\\subseteq G\[S\]impliesϕ​\(H\)≤ϕ​\(S\)\\phi\(H\)\\leq\\phi\(S\), thenϕ​\(Q​\-side\)\>ϕ​\(data\-side\)\\phi\(Q\\text\{\-side\}\)\>\\phi\(\\text\{data\-side\}\)is a safe pruning test\. Vertex and edge counts, all Laplacian eigenvalues, and closed\-walk countstr​\(Ak\)\\mathrm\{tr\}\(A^\{k\}\)\(e\.g\.k=3k\{=\}3: six times the triangle count\) are all subgraph\-monotone\. This family is the object of our study\.

## 3\.Lazy Spectral Bounds Are Infeasible

A single edge insertion insideBh​\(v\)B\_\{h\}\(v\)perturbsL​\(Bh​\(v\)\)L\(B\_\{h\}\(v\)\)byE=\(ea−eb\)​\(ea−eb\)⊤E=\(e\_\{a\}\-e\_\{b\}\)\(e\_\{a\}\-e\_\{b\}\)^\{\\\!\\top\}, PSD with‖E‖2=2\\\|E\\\|\_\{2\}=2; deletions subtract such a term\. Weyl’s inequalities\(Horn and Johnson,[2013](https://arxiv.org/html/2606.24421#bib.bib12)\)control the eigenvalue movement under such perturbations\. The lazy program maintains certified upper boundsλ¯\\bar\{\\lambda\}on the data\-side spectrum: deletions only lower true eigenvalues \(bounds stay valid for free\), and insertions are absorbed by cheap bound updates, with full recomputation deferred until the bounds lose discriminating power\. Pruning with upper bounds is safe by Lemma[1](https://arxiv.org/html/2606.24421#S2.Thmtheorem1)\. The question is how fast the power decays\.

### 3\.1\.Three Bound Families and an Optimality Result

#### Flat Weyl\.

λ¯i\+=2\\bar\{\\lambda\}\_\{i\}\\mathrel\{\+\}=2per inserted edge, for everyii\. A subtlety with real systems: one edge update can pull a new vertex carryingk\>1k\>1edges into the ball; accounting\+2\+2per*update*rather than per*induced edge*is unsafe \(we observed genuine violations\), so the reverse index must track induced edge deltas\.

#### Rank\-one shift\.

For one inserted edge,λ1′≤λ1\+2\\lambda\_\{1\}^\{\\prime\}\\leq\\lambda\_\{1\}\+2butλi′≤λi−1\\lambda\_\{i\}^\{\\prime\}\\leq\\lambda\_\{i\-1\}fori≥2i\\geq 2\(Weyl withμ2​\(E\)=0\\mu\_\{2\}\(E\)=0\): the bound vector*shifts*rather than inflates, tightening the flat rule by∼40%\{\\sim\}40\\%in our measurements\.

#### Trace budget\.

kkinserted edges add total eigenvalue mass exactly2​k2k, and each eigenvalue can only increase\. For the stale spectrumdd\(descending\) to come to dominate the query spectrumqq, the minimal mass needed is the majorization costC​\(q,d\)=∑tmax⁡\(0,qt−dt\)C\(q,d\)=\\sum\_\{t\}\\max\(0,\\,q\_\{t\}\-d\_\{t\}\)\. Hence

\(1\)prune iff​C​\(q,dstale\)\>2​kins\\text\{prune iff \}C\(q,d^\{\\text\{stale\}\}\)\>2k\_\{\\text\{ins\}\}is safe, costsO​\(r\)O\(r\), and dominates both per\-component rules whenever several components sit near their margins\.

Neither per\-component family subsumes the other, and neither does the trace rule alone: the shift constraint can disprove domination when the mass budget cannot \(a largeqiq\_\{i\}above the ceilingdi−kd\_\{i\-k\}\), and vice versa\. To speak of optimality we must fix the constraint set\. Define the*perturbation relaxation*ℛ​\(d,k\)\\mathcal\{R\}\(d,k\)as the set of descending sequencesλ′\\lambda^\{\\prime\}satisfying the three families we can prove forkkcomposed rank\-one PSD insertions: \(M\)λi′≥di\\lambda^\{\\prime\}\_\{i\}\\geq d\_\{i\}\(monotonicity\); \(S\)λi′≤ci:=min0≤j≤min⁡\(k,i−1\)⁡\(di−j\+2​\(k−j\)\)\\lambda^\{\\prime\}\_\{i\}\\leq c\_\{i\}:=\\min\_\{0\\leq j\\leq\\min\(k,\\,i\-1\)\}\\big\(d\_\{i\-j\}\+2\(k\-j\)\\big\), the lattice\-path minimum over all interleavings of the per\-step alternatives “interlace one position” or “gain at most norm22”—mixed paths can dominate both pure options when the spectrum decays steeply, so neither the pure shiftdi−kd\_\{i\-k\}nor the pure norm bound is the minimizer in general; \(T\)∑i≤r\(λi′−di\)≤2​k\\sum\_\{i\\leq r\}\(\\lambda^\{\\prime\}\_\{i\}\-d\_\{i\}\)\\leq 2k\(trace budget\)\. Our measured rule composes the per\-step pointwise minimumb1′=b1\+2b^\{\\prime\}\_\{1\}=b\_\{1\}\+2,bi′=min⁡\(bi−1,bi\+2\)b^\{\\prime\}\_\{i\}=\\min\(b\_\{i\-1\},\\,b\_\{i\}\+2\)kktimes, which is exactly the dynamic program computing the ceilingscic\_\{i\}\.ℛ\\mathcal\{R\}ignores graph realizability and the finer interpolating Weyl inequalities \(whose perturbation eigenvalues are not observable fromkkalone\), so it over\-approximates the truly reachable spectra: rules safe w\.r\.t\.ℛ\\mathcal\{R\}are safe in reality\.

###### Theorem 1 \(Optimal rule in the relaxation\)\.

The rule “prune iffC​\(q,dstale\)\>2​kinsC\(q,d^\{\\text\{stale\}\}\)\>2k\_\{\\text\{ins\}\}or∃i:qi\\exists i:\\,q\_\{i\}exceeds its ceiling in \(S\)” is the tightest safe rule overℛ​\(dstale,kins\)\\mathcal\{R\}\(d^\{\\text\{stale\}\},k\_\{\\text\{ins\}\}\): it prunes exactly when noλ′∈ℛ\\lambda^\{\\prime\}\\in\\mathcal\{R\}dominatesqq\.

###### Proof sketch\.

The pointwise\-minimal candidateλi′=max⁡\(qi,di\)\\lambda^\{\\prime\}\_\{i\}=\\max\(q\_\{i\},d\_\{i\}\)is descending \(maximum of two descending sequences\), satisfies \(M\) by construction, satisfies \(S\) iff everyqiq\_\{i\}respects its ceiling, and consumes mass exactlyC​\(q,d\)C\(q,d\), the minimum any dominating sequence must spend under \(M\)\. Hence a dominating member ofℛ\\mathcal\{R\}exists iff both conditions hold\. ∎

We state plainly what this does and does not claim: optimality is relative toℛ\\mathcal\{R\}; a rule exploiting structure outsideℛ\\mathcal\{R\}\(e\.g\. graph realizability\) could in principle be tighter\. The collapse below is measured for the optimal\-in\-ℛ\\mathcal\{R\}rule itself, and Observation[1](https://arxiv.org/html/2606.24421#Thmobservation1)explains why any rule whose admissible set inflates with injected trace mass meets the same fate\.

### 3\.2\.Collapse

Theorem[1](https://arxiv.org/html/2606.24421#S3.Thmtheorem1)makes the empirical question sharp: if even the optimal\-in\-ℛ\\mathcal\{R\}rule fails, every rule in this information class fails\. On sparse graphs with dense queries—the regime where exact interlacing prunes77–27%27\\%of candidates beyond NLF \(§[6](https://arxiv.org/html/2606.24421#S6)\)—we measured retention, the fraction of exact\-spectrum prunes still made by each rule, as a function of the numberτ\\tauof touching updates since refresh \(Figure[3](https://arxiv.org/html/2606.24421#S6.F3)b\)\. Flat Weyl, the composed ceilingscic\_\{i\}, and the optimal trace∨\\veeceiling rule retain5454/5656/58%58\\%atτ=1\\tau\{=\}1,1414/1616/19%19\\%atτ=2\\tau\{=\}2, and nothing beyondτ=4\\tau\{=\}4\. The mechanism is structural: prune marginsC​\(q,d\)C\(q,d\)concentrate between 1 and 8 in sparse neighborhoods, while each touching update injects mass≈5\{\\approx\}5on average—margins and perturbations share a scale, so no bound family can hold a useful invariant across even a handful of updates\. Safety was never violated \(with correct edge accounting\); power simply evaporates\.

###### Observation 1\.

The regimes are inseparable: spectral pruning requires sparse, small neighborhoods \(rich ones dominate every query spectrum\), and sparse, small neighborhoods are exactly where one edge is a large relative perturbation\. Lazy maintenance is infeasible precisely where it would be useful\.

## 4\.Selective Exact Maintenance

Observation[1](https://arxiv.org/html/2606.24421#Thmobservation1)has a constructive reading: in the useful regime, neighborhoods are small, so*exact*recomputation is cheap\. The design question becomes*where*exactness must be paid\.

### 4\.1\.The Anti\-Correlation Law and Hub Exclusion

###### Theorem 1 \(Hub exclusion, top\-ttform\)\.

Letdtd\_\{t\}denote thett\-th largest degree withinG​\[Bh​\(v\)\]G\[B\_\{h\}\(v\)\]andqmax=maxQ⁡\|VQ\|q\_\{\\max\}=\\max\_\{Q\}\|V\_\{Q\}\|over registered queries\. Ifdt≥qmax\+t−1d\_\{t\}\\geq q\_\{\\max\}\+t\-1, then the component\-tttestλtQ​\(u\)\>λtG​\(v\)\\lambda^\{Q\}\_\{t\}\(u\)\>\\lambda^\{G\}\_\{t\}\(v\)never fires for any registered query: the Brouwer–Haemers boundλt​\(L\)≥dt−t\+2\\lambda\_\{t\}\(L\)\\geq d\_\{t\}\-t\+2, valid under its mild edge\-count precondition\(Brouwer and Haemers,[2008](https://arxiv.org/html/2606.24421#bib.bib6)\)\(satisfied here, since a vertex of degreedt≥td\_\{t\}\\geq tsupplies the required edges\), givesλtG​\(v\)≥qmax\+1\\lambda^\{G\}\_\{t\}\(v\)\\geq q\_\{\\max\}\+1, while every query\-ball eigenvalue is at most its vertex count≤qmax\\leq q\_\{\\max\}\.

In particular \(t=1t\{=\}1\) a single vertex of degree≥qmax\\geq q\_\{\\max\}inside the ball kills the leading component; empirically, a short run of high\-degree vertices kills the top components, which carry8888–100%100\\%of observed prunes\.

Empirically the exclusion extends far beyond component 1: across an Erdős–Rényi family, a Watts–Strogatz family, and a real collaboration network, the per\-vertex pruning frequency against a dense query workload decays monotonically with ball size—0\.900\.90,0\.600\.60,0\.240\.24,0\.0650\.065,0\.0000\.000for ball sizes1−81\\\!\-\\\!8,9−169\\\!\-\\\!16,17−3217\\\!\-\\\!32,33−6433\\\!\-\\\!64,≥65\\geq\\\!65on the real graph \(Figure[3](https://arxiv.org/html/2606.24421#S6.F3)d\)—while per\-solve cost grows with ball size\. Utility and cost are anti\-correlated:*the most expensive vertices to maintain are precisely those that never prune*\. Component attribution shows the top two eigenvalues fire88−100%88\\\!\-\\\!100\\%of all prunes, sor∈\{2,4\}r\\in\\\{2,4\\\}components suffice—two to four floats per deployed vertex\.

### 4\.2\.TheSelSpecIndex

undeployed\(pass\-through\)deployedexactλ1\.\.r\\lambda\_\{1\.\.r\}evicted\(pass\-through\)first consult;lazy solve\|Bh​\(v\)\|\>Smax\|B\_\{h\}\(v\)\|\{\>\}S\_\{\\max\}touch:re\-solve\+\+resyncFigure 1\.SelSpecvertex lifecycle\. Deployment is lazy \(first consult\), refresh is eager on touch \(Theorem[2](https://arxiv.org/html/2606.24421#S4.Thmtheorem2)’s resync\), eviction is permanent and always safe\.SelSpecdeploys spectra on the vertex set\{v:\|Bh​\(v\)\|≤Smax\}\\\{v:\|B\_\{h\}\(v\)\|\\leq S\_\{\\max\}\\\}, intersected with label\-relevant candidates of registered queries\. A vertex’s lifecycle \(Figure[1](https://arxiv.org/html/2606.24421#S4.F1)\) is:*lazy deploy*on first consult \(its spectrum is computed when a query first tests it, so build cost scales with consulted candidates, not\|V\|\|V\|\);*eager refresh*on every touching update while deployed;*evict*when the ball outgrowsSmaxS\_\{\\max\}\. Spectra are maintained*exactly*:

- •Trigger\.An update\(a,b\)\(a,b\)changesG​\[Bh​\(v\)\]G\[B\_\{h\}\(v\)\]iff both endpoints lie in the \(new\) ball; a reverse ball\-membership index locates affected deployed vertices inO​\(1\)O\(1\)amortized\.
- •Recompute on touch\.Affected spectra are recomputed by a dense symmetric eigensolve on≤Smax\\leq S\_\{\\max\}vertices \(tens of microseconds via LAPACK\); vertices whose balls outgrowSmaxS\_\{\\max\}are*evicted*: marked pass\-through and dropped from the reverse index at its next compaction\. Eviction is permanent in our implementation—a ball that later shrinks back belowSmaxS\_\{\\max\}is not re\-deployed, which forfeits pruning on that vertex but never completeness \(pass\-through admits everything\); re\-deployment would only require re\-running the lazy first\-consult path\.
- •Bidirectional resync\.An insertion can*raise*an affected vertex’s spectrum, re\-legalizing a previously pruned candidate; affected vertices are therefore re\-checked against all label\-matching query vertices in both directions\. Deletions only lower true spectra, so stale entries over\-admit—never over\-prune—and completeness is unconditional\.

###### Theorem 2 \(Completeness\)\.

Under any update sequence,SelSpec’s candidate sets contain every vertex participating in any embedding\.

###### Proof sketch\.

Spectra consulted at pruning time are exact for deployed vertices \(eager refresh on touch; lazily computed on first consult\), undeployed vertices pass through, and the test is safe by Lemma[1](https://arxiv.org/html/2606.24421#S2.Thmtheorem1); the resync step restores any candidate whose spectrum change reverses a past rejection\. ∎

###### Theorem 3 \(Update cost\)\.

LetAAbe the set of deployed vertices whose induced ball subgraph is changed by the update \(both endpoints inside the new ball\)\. Per edge update, maintenance costsO​\(\|A\|⋅\(Smax3\+Smax​d¯\)\)O\\\!\\big\(\|A\|\\cdot\(S\_\{\\max\}^\{3\}\+S\_\{\\max\}\\,\\bar\{d\}\)\\big\)—one dense eigensolve plus a capped\-ball BFS re\-extraction with average degreed¯\\bar\{d\}per affected vertex—independent of\|V\|\|V\|\.

###### Lemma 0 \(Reverse\-index maintenance\)\.

The reverse ball\-membership index stores, for each deployed vertex, its≤Smax\\leq S\_\{\\max\}ball members \(O​\(D⋅Smax\)O\(D\\cdot S\_\{\\max\}\)memory forDDdeployed vertices\); locatingAAcostsO​\(\|Ra\|\+\|Rb\|\)O\(\|R\_\{a\}\|\+\|R\_\{b\}\|\)list reads for the endpoint listsRa,RbR\_\{a\},R\_\{b\}, which self\-compact to live entries at each access; and a recompute re\-registers at mostSmaxS\_\{\\max\}entries, so amortized maintenance isO​\(\|A\|⋅Smax\)O\(\|A\|\\cdot S\_\{\\max\}\)per update\.

Empirically,\|A\|≈4\.5\|A\|\\approx 4\.5on a real collaboration graph with the end\-to\-end kernel near313​μ​s313\\mu sper update; the same machinery costs∼0\.5\{\\sim\}0\.5ms per update on com\-Amazon where nearly all vertices are deployable, and the index \(spectra plus reverse lists\) reaches∼10×\{\\sim\}10\\timesthe NLF index footprint there \(§[6\.4](https://arxiv.org/html/2606.24421#S6.SS4)\)—the memory price of deployability\.

On the real graph,Smax=32S\_\{\\max\}\{=\}32deploys63\.6%63\.6\\%of vertices and retains96\.1%96\.1\\%of all pruning;Smax=64S\_\{\\max\}\{=\}64retains100%100\\%\(Figure[3](https://arxiv.org/html/2606.24421#S6.F3)d\)\.SelSpecis, to our knowledge, the first dynamic\-graph index maintaining exact local Laplacian spectra, and is application\-agnostic: any consumer of neighborhood spectra over a dynamic graph \(anomaly scoring, graph kernels, spectral features\) inherits the primitive\.

## 5\.Filtering: Where Aggregates End

### 5\.1\.Vertex\-Level Filtering and the Weak\-Candidate Effect

Plugged into a decoupled CSM framework as an index layer over NLF,SelSpecremoves9−51%9\\\!\-\\\!51\\%of candidate vertices, growing with query size, at unchanged match outputs \(§[6](https://arxiv.org/html/2606.24421#S6)\)\. Yet enumeration time does not improve, and the count of enumeration intermediates is*identical*to the spectral\-free control at every query size\. The diagnosis is structural\. The interlacing test fires on candidates whose neighborhoods are spectrally*poorer*than the query’s; but the delta enumeration is adjacency\-guided—a candidate contributes cost only if a partial embedding reaches it through candidate edges, which requires local structural support\. Spectrally poor candidates lack precisely that support and die at the first adjacency check\. We call this the*weak\-candidate effect*:

###### Observation 2\.

In adjacency\-guided delta enumeration, the prunable set of the interlacing test and the cost\-bearing set of the enumeration are nearly disjoint\. Where the test*does*pay is in cost terms that scale with candidate\-set size: static pipelines pay a large per\-query candidate\-space construction term, and engines in the GraphQL/worst\-case\-optimal\-join style\(He and Singh,[2008](https://arxiv.org/html/2606.24421#bib.bib11); Mhedhbi and Salihoglu,[2019](https://arxiv.org/html/2606.24421#bib.bib19)\)additionally scan or intersect materialized candidate lists per level; CS\-edge\-guided engines \(CECI/DAF style\(Bhattarai et al\.,[2019](https://arxiv.org/html/2606.24421#bib.bib5); Han et al\.,[2019](https://arxiv.org/html/2606.24421#bib.bib10)\)\) chase adjacency even in the static setting and their exploration is as immune as delta enumeration’s \(§[6\.5](https://arxiv.org/html/2606.24421#S6.SS5)\)\.

### 5\.2\.Anchored Gates: a CSM\-Native Mechanism

CSM offers a handle static matching lacks: every incremental match contains the updated edge\. If\(a,b\)\(a,b\)is matched to query edge\(u,u′\)\(u,u^\{\\prime\}\), then for anyρ\\rho, the sub\-queryQρ​\(u,u′\)=Q​\[\{w:min⁡\(dQ​\(w,u\),dQ​\(w,u′\)\)≤ρ\}\]Q\_\{\\rho\}\(u,u^\{\\prime\}\)=Q\[\\\{w:\\min\(d\_\{Q\}\(w,u\),d\_\{Q\}\(w,u^\{\\prime\}\)\)\\leq\\rho\\\}\]must embed intoG​\[Bρ​\(\{a,b\}\)\]G\[B\_\{\\rho\}\(\\\{a,b\\\}\)\]\. Any subgraph\-monotone invariantϕ\\phitherefore yields a safe*update\-level*gate:

###### Theorem 1 \(Gate safety\)\.

If for every label\-compatible query edge\(u,u′\)\(u,u^\{\\prime\}\)there existρ\\rhoand a subgraph\-monotoneϕ\\phiwithϕ​\(Qρ​\(u,u′\)\)\>ϕ​\(G​\[Bρ​\(\{a,b\}\)\]\)\\phi\(Q\_\{\\rho\}\(u,u^\{\\prime\}\)\)\>\\phi\(G\[B\_\{\\rho\}\(\\\{a,b\\\}\)\]\), then the update\(a,b\)\(a,b\)creates no incremental match, and its delta enumeration can be skipped entirely\.

The symmetric statement holds for deletions: every*disappearing*match contains the deleted edge, and the same ball argument applies on the pre\-deletion graph, so a failing test there licenses skipping the negative delta enumeration as well\.

QQuuu′u^\{\\prime\}Qρ​\(u,u′\)Q\_\{\\rho\}\(u,u^\{\\prime\}\)GGaabbBρ​\(\{a,b\}\)B\_\{\\rho\}\(\\\{a,b\\\}\)ϕ​\(Qρ\)≤ϕ​\(Bρ\)\\phi\(Q\_\{\\rho\}\)\\\!\\leq\\\!\\phi\(B\_\{\\rho\}\)?update edge\(a,b\)\(a,b\)Figure 2\.AnchorGate: every incremental match mapsQρ​\(u,u′\)Q\_\{\\rho\}\(u,u^\{\\prime\}\)intoBρ​\(\{a,b\}\)B\_\{\\rho\}\(\\\{a,b\\\}\); a subgraph\-monotone invariantϕ\\phifailing for every label\-compatible query edge licenses skipping the whole delta enumeration \(Theorem[1](https://arxiv.org/html/2606.24421#S5.Thmtheorem1)\)\.We instantiateϕ\\phiwith vertex count, edge count, top\-rrLaplacian eigenvalues, and triangle count \(tr​\(A3\)/6\\mathrm\{tr\}\(A^\{3\}\)/6\), evaluated atρ∈\{1,2\}\\rho\\in\\\{1,2\\\}with a ball\-size cap \(capped balls are rich and pass for free, by the anti\-correlation law\)\. Sub\-query invariants are precomputed at registration; the data ball is assembled per update in microseconds\. Crucially,QρQ\_\{\\rho\}of a dense query is far richer than any single\-vertex neighborhood, so the gate’s discriminating power exceeds vertex\-level tests by construction, and triangle counts add a*cycle\-mass*dimension invisible to degree information\.

### 5\.3\.The Boundary Regularity

The gates fire on5−47%5\\\!\-\\\!47\\%of updates with zero wrong skips—and the enumeration intermediates remain exactly unchanged, a fourth time for the Laplacian gate and a fifth for the triangle gate \(§[6](https://arxiv.org/html/2606.24421#S6)\)\. The updates that pass the gate are exactly the expensive ones\. Together with §[5\.1](https://arxiv.org/html/2606.24421#S5.SS1), five configurations spanning two granularities \(vertex, update\) and two invariant families \(degree mass, cycle mass\) replicate one phenomenon, which we state as an*empirical regularity*backed by a mechanism explanation—not as a theorem:

> *In label/NLF\-saturated, update\-driven CSM, subgraph\-monotone aggregate tests pruned only work that adjacency\-guided enumeration discarded within its first expansion levels—in every configuration we measured\.*

Two arguments explain the observations, with different reach\.*\(i\) Degree mass is largely spoken for\.*By Grone–Merris \(proved by Bai\)\(Grone and Merris,[1994](https://arxiv.org/html/2606.24421#bib.bib9); Bai,[2011](https://arxiv.org/html/2606.24421#bib.bib4)\), the Laplacian spectrum is majorized by the conjugate degree sequence, which*bounds the headroom*of top\-eigenvalue interlacing over degree\-based filters such as NLF\. The bound is not exhaustive: spectra do carry information beyond degrees—C6C\_\{6\}and2×C32\{\\times\}C\_\{3\}share a degree sequence yet differ inλ1\\lambda\_\{1\}\(44vs\.33\)—and that cycle\-structure residue is precisely why spectral signals are attractive at all\. GMB explains attenuation, not absence—and the attenuation is quantifiable: over the3,5063\{,\}506deployed balls of ca\-GrQc, the top\-44Laplacian partial sum reaches a median73%73\\%of its conjugate\-degree\-sequence ceiling \(IQR5959–91%91\\%\), so most of what the interlacing statistic measures on this workload is degree\-determined, with a real but minority cycle\-structure residue\.*\(ii\) Aggregate deficiency tends to be self\-punishing\.*A region poor in the tested aggregate lacks raw structural material, and adjacency\-guided search starved of material tends to halt within its first expansion levels; expensive failures, in everything we measured, arose where material abounds but no*injective, label\-consistent assignment*exists—a property no multiset aggregate of the region can witness\. This is a mechanism, not a guarantee\. Configurations escaping it are conceivable: a region abundant within radius 1 yet deficient at radius 2 can host combinatorially many injective partial assignments before exhausting, which aρ=2\\rho\{=\}2gate would skip at real savings; engines that select matching orders from candidate\-set sizes couple candidate reductions to exploration \(§[6\.10](https://arxiv.org/html/2606.24421#S6.SS10)\); and engines scanning materialized candidate lists pay per\-candidate costs that pruning does reduce \(§[6\.5](https://arxiv.org/html/2606.24421#S6.SS5)\)\. We did not encounter the first configuration in any natural workload; we delimit rather than universalize\.

The regularity delimits, rather than condemns, the machinery: consumers that are*not*adjacency\-guided—periodic full re\-enumeration, batch candidate\-space construction \(the static setting, where PILOS\(Skitsas et al\.,[2025](https://arxiv.org/html/2606.24421#bib.bib21)\)demonstrably gains\), admission control for approximate matching—retain the full benefit ofSelSpec\-maintained spectra andAnchorGates, with Theorems[2](https://arxiv.org/html/2606.24421#S4.Thmtheorem2)and[1](https://arxiv.org/html/2606.24421#S5.Thmtheorem1)intact\.

## 6\.Experiments

Our evaluation has two layers\.*Probes*\(Python/LAPACK\) isolate each mechanism’s intrinsic behavior;*framework experiments*\(C\+\+17, single\-threaded\) integrateSelSpecand the gates into the decoupled CSM benchmark of Gou et al\.\(Gou et al\.,[2026](https://arxiv.org/html/2606.24421#bib.bib8)\)as a drop\-in index \(index\_type 6\), against the strictest control: the identical pipeline with the identical NLF index minus the spectral layer \(NLFI\), with the enumeration engine fixed \(NewSP\-style\)\. This isolates the tested signal and respects the implementation\-sensitivity lesson of\(Lee et al\.,[2024](https://arxiv.org/html/2606.24421#bib.bib16)\)\. Data: synthetic Erdős–Rényi \(avg\. degree 3\) and Watts–Strogatz families; real graphs ca\-GrQc \(4\.2K vertices, collaboration\) and email\-Enron \(33\.7K vertices, communication\) and com\-Amazon \(334\.9K\)\(Leskovec and Krevl,[2014](https://arxiv.org/html/2606.24421#bib.bib17)\), with uniform labelsL∈\{4,8\}L\\in\\\{4,8\\\}and a90:1090\{:\}10initial/insert\-stream split; update streams are uniformly shuffled \(these graphs carry no timestamps\), the standard protocol for untimestamped data\(Sun et al\.,[2022b](https://arxiv.org/html/2606.24421#bib.bib24)\)\. Queries are dense BFS\-ball samples following standard CSM practice\(Sun et al\.,[2022b](https://arxiv.org/html/2606.24421#bib.bib24)\): a*main*workload of sizes1616–3232\(five per size\) and a*thickening*workload of sizes88/1212\(ten per size\) whose easier instances mostly solve within budget\. Eigensolves use LAPACKdsyev;h=2h\{=\}2,r∈\{4,8\}r\\in\\\{4,8\\\},Smax=64S\_\{\\max\}\{=\}64unless noted\. All experiments run single\-threaded on an AMD Ryzen Threadripper PRO 3945WX \(12 cores, 64 GB RAM\) under Ubuntu 24\.04, GCC 13\.3 at\-O3\. The per\-query time budget is6060s throughout, covering stream processing only and checked between updates—a query is stopped after the update that crosses the line, so index maintenance within that update \(and per\-query graph loading, excluded from the budget\) can push wall times past6060s; key results are re\-verified at5×5\\timesand10×10\\timesbudgets\. Table[1](https://arxiv.org/html/2606.24421#S6.T1)lists the graphs; probe experiments \(§[6\.1](https://arxiv.org/html/2606.24421#S6.SS1)\) usen=3,000n\{=\}3\{,\}000–8,0008\{,\}000synthetics and ca\-GrQc\. All counters are deterministic\. Wall times are single\-run; a three\-repeat check on the thickening workload bounds run\-to\-run spread at1\.1%1\.1\\%\(control\) and1\.4%1\.4\\%\(spectral\) of the median, an order of magnitude below every time difference we interpret\. We define the central metric here: an enumeration*intermediate*is one binding of a data vertex to a non\-anchor query vertex followed by a descent of the backtracking search \(the counter incremented at each recursive extension; engines count at different sites, which is immaterial since all comparisons are within\-engine\); raw totals are reported on solved queries\.

Table 1\.Graphs used in framework experiments\.### 6\.1\.Probe Results

![Refer to caption](https://arxiv.org/html/2606.24421v1/x1.png)Figure 3\.Feasibility probes\. \(a\) Spectral pruning power beyond NLF\+size grows with query size on sparse graphs\. \(b\) Lazy\-rule pruning retention collapses withinτ≤4\\tau\\leq 4touching updates for flat Weyl, the composed ceilingscic\_\{i\}, and the trace∨\\veeceiling rule, which is optimal in the perturbation relaxation \(Theorem[1](https://arxiv.org/html/2606.24421#S3.Thmtheorem1)\)\. \(c\) Maintenance cost scales as\(τ\+1\)×\(\\tau\{\+\}1\)\\times; warm\-started iterative solvers lose to direct solves at deployment\-scale neighborhoods\. \(d\) The benefit/cost anti\-correlation on two synthetic families and a real collaboration network\.Figure[3](https://arxiv.org/html/2606.24421#S6.F3)summarizes\.\(a\) Pruning power exists and grows with query size\.On sparse graphs with dense queries, exact interlacing removes77–27%27\\%of candidates beyond NLF and size screening \(q32, ER:26\.7%26\.7\\%\), replicating the magnitude PILOS reports statically; on tree\-like random\-walk queries it removes≈0%\{\\approx\}0\\%—the applicability domain is sharp\.\(b\) Lazy bounds collapse\(§[3\.2](https://arxiv.org/html/2606.24421#S3.SS2)\): retention5454/5656/58%58\\%atτ=1\\tau\{=\}1,≤19%\{\\leq\}19\\%atτ=2\\tau\{=\}2,0%0\\%atτ=4\\tau\{=\}4for flat Weyl, the composed ceilingscic\_\{i\},*and*the optimal trace∨\\veeceiling rule; with naive per\-update \(rather than per\-edge\) accounting we additionally observed genuine safety violations, confirming the accounting requirement of §[3\.1](https://arxiv.org/html/2606.24421#S3.SS1)\.\(c\) Maintenance\.Lazy scheduling saves only\(τ\+1\)×\(\\tau\{\+\}1\)\\times, moot given \(b\); selective exact recomputation costs5252–225​μ​s225\\mu sper solve in the deployment range, and with the exact trigger rule \(both endpoints inside the ball;4\.554\.55true triggers per update vs\.20\.320\.3under the naive superset rule\) the end\-to\-end kernel cost is313​μ​s313\\mu sper update on ca\-GrQc\.\(d\) Anti\-correlation lawon three graph families; on ca\-GrQc,Smax=32S\_\{\\max\}\{=\}32covers63\.6%63\.6\\%of vertices and retains96\.1%96\.1\\%of pruning,Smax=64S\_\{\\max\}\{=\}64retains100%100\\%; the top two eigenvalues fire8888–100%100\\%of prunes\.

### 6\.2\.The Boundary Regularity In\-Framework

Table 2\.Replication matrix for intermediate invariance\. Every cell is a configuration in which all co\-solved queries had exactly equal match totals and intermediates; “solved” counts queries solved by both sides\.Gate\-bearing rows are equal up to skipped doomed bindings:0–11per query where raw counters were captured on Enron,11–88on the com\-Amazon gate runs \(≤2\.2%\\leq 2\.2\\%of that query’s bindings, §[6\.4](https://arxiv.org/html/2606.24421#S6.SS4)\); vertex\-only rows are exact\.

For context beyond the NLFI control, we also ran the framework’s full index family \(NI, DCG, DCS, CaLiG\) on the same workload with the expected relative behavior\.111CaLiG’s kernel\-and\-shell search is sensitive to this dense low\-selectivity workload \(one query spent1,4971\{,\}497s inside a single uninterruptible update enumeration\); we report its seven queries completing within a 90\-minute envelope\. None of this affects the controlled comparison, which varies only the spectral layer\.We do not compare against DIVINE\(Ye et al\.,[2025](https://arxiv.org/html/2606.24421#bib.bib28)\)experimentally: its dominance\-embedding synopses are coupled to its own engine rather than exposed behind the decoupled framework’s index interface, so any end\-to\-end gap would conflate signal with implementation—the confound the framework exists to remove\(Lee et al\.,[2024](https://arxiv.org/html/2606.24421#bib.bib16)\)\. Our lens applies to its signal nonetheless \(§[7](https://arxiv.org/html/2606.24421#S7)\)\.

Table[3](https://arxiv.org/html/2606.24421#S6.T3)is the paper’s central table\. Five configurations—vertex\-level interlacing at three query sizes, the Laplacian anchored gate, and the triangle\-extended gate—all prune substantially by their own meter, never violate completeness \(match totals identical to NLFI on all2020solved queries, ranging from11to2\.8×1082\.8\\times 10^\{8\}matches\), and leave the per\-update intermediate\-result count*exactly equal*\. The gates’ fired updates are exactly those whose enumerations were already free: on the hardest solved query \(∼23\{\\sim\}23s\), zero of eight processed updates fired any gate\. Maintenance overhead, not enumeration, accounts for the entire residual time difference \(\+7\+7–31%31\\%on solved queries\), and an overhead\-reduction pass \(reverse\-index compaction, change\-gated resync; memory−40%\-40\\%\) left time unchanged—consistent with the law: even at zero overhead there is no enumeration time to win\.

Table 3\.Intermediate invariance by test configuration \(ca\-GrQc,L=8L\{=\}8unless noted; cross\-engine/graph/stream replications in Table[2](https://arxiv.org/html/2606.24421#S6.T2)\)\. “Prune” is the configuration’s own meter: candidate\-vertex reduction \(vertex level\) or gate fire rate among processed updates \(update level\)\. Intermediates equal the NLFI control in every configuration; match counts always agree\.“Equal” is exact for vertex\-level rows; for gate rows, raw totals can differ by the gate’s skipped doomed bindings—0–88per query on natural workloads \(≤2\.2%\\leq 2\.2\\%, typically≪0\.1%\\ll 0\.1\\%\), first\-level bindings of matchless updates and thus precisely the “work discarded within first expansion levels” of the regularity\. Prune rates are measured on the*main*workload \(dense queries,\|VQ\|∈\{16,24,32\}\|V\_\{Q\}\|\\in\\\{16,24,32\\\}, five per size\)\. Invariance is asserted on solved queries only \(truncated runs progress differently\): the main workload solves two \(\|VQ\|=24\|V\_\{Q\}\|\{=\}24\) at the default budget and a third \(\|VQ\|=16\|V\_\{Q\}\|\{=\}16\) at10×10\\times—the latter with raw intermediates exactly equal at1\.56×1091\.56\\times 10^\{9\}bindings and2\.13×1092\.13\\times 10^\{9\}matches, the strongest single datum in the paper—and a*thickening*workload of twenty easier dense queries \(\|VQ\|∈\{8,12\}\|V\_\{Q\}\|\\in\\\{8,12\\\}, ten per size\) solves eighteen more\. Invariance is further stable under5×5\\times/10×10\\timesbudgets, across an insert/delete\-mixed stream \(§[6\.8](https://arxiv.org/html/2606.24421#S6.SS8)\), under a second enumeration engine on all twenty thickening queries \(§[6\.9](https://arxiv.org/html/2606.24421#S6.SS9)\), and on two further graphs \(§[6\.3](https://arxiv.org/html/2606.24421#S6.SS3)–[6\.4](https://arxiv.org/html/2606.24421#S6.SS4)\)\.

### 6\.3\.Cross\-Graph Replication

On email\-Enron \(33\.733\.7K vertices, avg\. degree10\.710\.7;18,08118\{,\}081\-insert stream\) the regularity replicates under its strongest single test: the main\-workload query solved within budget processes the*entire*update stream, the triangle\-extended gate fires on15\.7%15\.7\\%of its updates \(2,8482\{,\}848skipped enumerations,1,2471\{,\}247triangle disproofs, zero wrong skips—121,157121\{,\}157matches, identical to control\), with intermediates\-per\-update exactly equal \(611\.857611\.857\)\. The thickening workload adds twelve more solved queries on this graph: all twelve match totals agree \(up to2\.86×1092\.86\\times 10^\{9\}matches on one query\); under raw counters, intermediates are exactly equal on ten \(e\.g\.6,801,9766\{,\}801\{,\}976on both sides of the heaviest\) and differ by a*single*gate\-skipped doomed binding on two \(95,91595\{,\}915vs\.95,91695\{,\}916, equal denominators\)—the continuum of §[6\.4](https://arxiv.org/html/2606.24421#S6.SS4)at its natural floor\. The\+3\.5\+3\.5s residual on this query equals the measured per\-update maintenance\-plus\-gate cost times the stream length, confirming once more that the entire time difference is overhead, none of it enumeration\. Candidate reductions are smaller here \(11–7%7\\%\) than on the sparse collaboration graph: with average degree10\.710\.7, balls are larger, fewer vertices are deployable, and fewer are spectrally weak—the anti\-correlation law \(§[4](https://arxiv.org/html/2606.24421#S4)\) predicting its own diminishing domain\.

### 6\.4\.At Scale: the Overhead Verdict

com\-Amazon \(334\.9334\.9K vertices, avg\. degree5\.55\.5;92,58792\{,\}587\-insert stream\) completes the picture, a further invariance replication with a twist\. Sparsity makes this the spectral test’s best regime: vertex\-level pruning fires up to415415K times per query and removes up to51%51\\%of candidates\. It is also the regime where nearly every vertex is deployable, so every update refreshes∼5\{\\sim\}5cached spectra: the control completes all ten queries in4646s total while the spectral configuration needs over ten minutes—match counts identical on every query both sides finish \(10,080=10,08010\{,\}080=10\{,\}080on the largest\), and intermediates equal up to the gate’s skipped doomed bindings,11–88per query under raw counters \(both gate\-bearing configurations skip the same updates; e\.g\.359359vs351351on one light query,19,670,52519\{,\}670\{,\}525vs19,670,52419\{,\}670\{,\}524on the heaviest\)\. Pruning at its most active, enumeration gains at a few first\-level bindings: this is the boundary regularity priced out\. Two design points separate the mechanism from the engineering\. The*eager*configuration \(materialized spectral candidate maps require touch\-time recompute and bidirectional resync for completeness\) pays∼0\.5\{\\sim\}0\.5ms per update and accounts for the ten minutes\. A*lazy gate\-only*configuration—drop the vertex layer entirely \(for edge\-view\-driven engines its read\-path tests never reach exploration anyway, §[5\.1](https://arxiv.org/html/2606.24421#S5.SS1)\) and keep the self\-containedAnchorGate—completes all ten queries in11m5555s with identical matches; raw intermediates differ only by the gate’s skipped doomed bindings,11–88per query \(19,670,52419\{,\}670\{,\}524vs\.19,670,52519\{,\}670\{,\}525on the largest\)—the continuum’s natural end, against the constructed workload’s−99\.9%\-99\.9\\%\(§[6\.6](https://arxiv.org/html/2606.24421#S6.SS6)\)\. So “not yet engineered well” is partly true of the eager design: a5×5\\timesoverhead reduction exists inside the design space\. What no engineering can change is the numerator: with intermediates provably untouched, the best achievable online outcome is the control’s runtime plus a nonzero gate cost—still a strict loss on every natural workload we measured \(§[6\.6](https://arxiv.org/html/2606.24421#S6.SS6)shows the constructed exception\)\.

At com\-Youtube scale \(1\.131\.13M vertices,2\.992\.99M edges,298,762298\{,\}762\-insert stream\) the design split repeats\. The eager configuration is feasible \(init\+2\+2–1414s, index2525–3939MB\) but solves*neither*of the control’s two in\-budget queries \(32\.432\.4s,11\.911\.9s\)—its maintenance overhead alone converts both into timeouts\. The lazy gate\-only configuration recovers both, with identical match totals \(2\.08×1082\.08\\times 10^\{8\}and1\.59×1081\.59\\times 10^\{8\}\) at50\.950\.9s and38\.638\.6s—the residual being pure gate cost over a299299K\-update stream—and its total wall time over the twenty\-query thickening workload sits within4%4\\%of the control’s, the other eighteen queries timing out on both sides\. Million\-scale, then, confirms both halves: overhead engineering matters \(eager loses solved queries; lazy keeps them\), and no engineering recovers a win \(the lazy variant still pays the gate for intermediates that never change\)\.

### 6\.5\.The Positive Boundary: Where Aggregates Do Pay

We rebuilt the static pipeline—candidate generation, CECI\-style candidate\-space \(CS\) construction, full backtracking enumeration—and compared NLF against NLF\+spectral candidates on ER and ca\-GrQc with dense q16 queries\. CS construction cost, metered implementation\-independently as adjacency\-scan operations, drops in near proportion to candidates \(−2\-2to−43%\-43\\%, tracking the−4\-4to−38%\-38\\%candidate reductions\); match outputs agree exactly on every uncapped query\. Enumeration*nodes*, however, remain identical even here: our enumerator draws its pools from CS edges and is thus adjacency\-guided too\. This sharpens the boundary regularity into an architectural statement:

> *Aggregate pruning accelerates exactly the cost terms that scale with candidate\-set size \(candidate\-space construction, candidate\-list intersection\), and never adjacency\-guided exploration, in static and dynamic settings alike\.*

Static matchers pay a large construction term per query, which is where PILOS’s measured gains live; delta enumeration pays no construction term at all \(its index is maintained incrementally\), leaving aggregates nothing to accelerate\. The practical guidance follows: spend aggregate tests where candidate sets are*materialized or scanned*\(batch/static evaluation, index \(re\)builds, admission control\), not where exploration is pointer\-chasing through adjacency\.

### 6\.6\.A Constructed Exception: the Instrument Can Detect Non\-Invariance

The regularity’s mechanism \(§[5\.3](https://arxiv.org/html/2606.24421#S5.SS3)\) names its own escape hatch—a region abundant at radius 1 yet deficient at radius 2—and a fair objection is that an instrument that has only ever reported equality might be unable to report anything else\. We therefore constructed the escape hatch\. Query: a near\-clique core \(K8K\_\{8\}minus one edge\) with a two\-hop tail,1010vertices, maximum degree77\. Data:5050decoy regions \(isolatedK8K\_\{8\}, each missing one edge whose arrival is the update\) matching the query’s degree profile exactly—NLF admits every decoy vertex for every query vertex, and the control must discover failure by exhausting injectivity \(1010query vertices,88decoy vertices\) through deep partial assignments; plus one true region with the tail, completed by the final update\. Result: the control performs7,543,8147\{,\}543\{,\}814intermediate extensions in8\.988\.98s;AnchorGate’s vertex\-count screen \(\|B2​\(\{a,b\}\)\|=8<\|Q2\|=9\|B\_\{2\}\(\\\{a,b\\\}\)\|=8<\|Q\_\{2\}\|=9\) disproves every mapping on all5050decoy updates and passes the true one, yielding7,9427\{,\}942intermediates \(−99\.9%\-99\.9\\%\) in0\.0120\.012s \(748×748\\times\), with identical match totals \(720720\)\. The instrument detects non\-invariance decisively when exploration crosses an aggregate\-visible boundary; on natural workloads it never does— that contrast*is*the finding\.

### 6\.7\.Robustness: Label Skew, Sparse Queries, Borderline Budgets

Under Zipf\-distributed labels \(s=1\.5s\{=\}1\.5\), five of ten queries solve and all five agree exactly in totals and intermediates\. \(All label assignments in this paper are synthetic, per standard practice for unlabeled SNAP graphs; replaying natively labeled benchmark streams such as LSBench/Netflow\(Sun et al\.,[2022b](https://arxiv.org/html/2606.24421#bib.bib24); Gou et al\.,[2026](https://arxiv.org/html/2606.24421#bib.bib8)\)is the immediate external\-validity extension\.\) Under sparse random\-walk queries—the regime where the probe predicts near\-zero spectral pruning—candidate reductions indeed shrink to0\.50\.5–4%4\\%, nine of ten queries agree exactly, and the domain boundary closes from the inside: where the tests cannot fire, nothing changes by construction\. One borderline case is instructive: a query the control finishes at59\.559\.5s \(of a6060s budget\) is pushed past the line by the spectral configuration’s maintenance overhead—it finds the identical8\.45×1088\.45\\times 10^\{8\}matches but lands at60\.860\.8s\. Overhead does not merely fail to help; near budget boundaries it can flip outcomes\.

### 6\.8\.Deletion\-Mixed Streams

Deletions are the easy direction for safety—they only lower true spectra, so stale entries over\-admit and never over\-prune \(§[4\.2](https://arxiv.org/html/2606.24421#S4.SS2)\)—but they exercise the bidirectional resync and eviction machinery\. We extended the framework’s driver to70:3070\{:\}30insert/delete streams \(a patch we release with our artifacts\) and re\-ran the ca\-GrQc workload: all configurations complete, solved queries produce identical outputs and identical intermediates across control and spectral runs, and no safety anomaly appears in5,7505\{,\}750exercised deletions, consistent with the over\-admit argument\. In these runsAnchorGateis applied to insertions only; the pre\-deletion form licensed by Theorem[1](https://arxiv.org/html/2606.24421#S5.Thmtheorem1)’s symmetric statement is left unexercised\.

### 6\.9\.A Second Engine, and the Pruned\-Visited Intersection

Two checks address the most natural objections\. First, the framework’s decoupling lets us swap the enumeration engine: under the SymBi\-style engine \(a different search process with its own intermediate counter\), all2020thickening queries solve on both sides, all2020match totals agree—up to1\.5×1091\.5\\times 10^\{9\}matches on a single query—and all2020per\-engine intermediate counts are again pairwise identical\. The regularity is not an artifact of one search process\. Second, we measured the claim behind the regularity*directly*rather than through counter equality: instrumenting the engine to record every \(query\-vertex, data\-vertex\) binding it performs and the index to record every binding the spectral test rejects, accumulated over the whole stream\. The overlap is0–77bindings per query \(≈0\.5%\{\\approx\}0\.5\\%of visited bindings; exactly0on1111of2020queries\)\. The residue is not pruned\-yet\-visited leakage: at any moment enumeration draws only from the candidate map, which excludes currently\-rejected bindings by construction; the overlapping bindings are those whose status legitimately*flipped*during the stream—rejected at one point, re\-admitted by the bidirectional resync when an insertion raised the candidate’s spectrum \(§[4\.2](https://arxiv.org/html/2606.24421#S4.SS2)\), and visited only while admitted\. The accumulated overlap thus measures the resync mechanism at work, and its sparseness shows how rarely the spectral frontier moves across enumeration\-relevant bindings\.

### 6\.10\.Methodology: the Intermediate\-Invariance Test

Candidate counts misled in both directions in our study: they*overstate*usefulness at the vertex level \(Table[3](https://arxiv.org/html/2606.24421#S6.T3)\) and can*understate*it for edge\-view\-rich indexes\(Gou et al\.,[2026](https://arxiv.org/html/2606.24421#bib.bib8)\)\. We propose reporting, for any new CSM filter, the intermediate count with the filter on and off under a fixed engine*and fixed matching order*: a filter that does not move this number cannot move enumeration time, no matter what it does to candidates\. Two qualifications\. \(i\) The test is*engine\- and order\-relative*: our primary engines derive matching orders from the query graph alone \(verified in the order\-generation code\), so candidate reductions cannot feed back into exploration\. We probed the feedback channel directly by switching to a candidate\-cardinality\-driven order \(greedy smallest\-candidate\-first from the anchor\) and re\-running the thickening workload: match totals stay identical, but intermediates now move*in both directions*— one query inflates from5\.4×1075\.4\\times 10^\{7\}to1\.2×1081\.2\\times 10^\{8\}bindings \(17\.817\.8s→41\.8\{\\to\}41\.8s\) while another drops32%32\\%—because the spectral layer’s candidate reductions reorder exploration unpredictably\. Under order feedback the invariance test certifies the filter’s direct effect only; whole\-system claims additionally need the order held fixed, and practitioners adding any filter to a candidate\-driven\-order system should expect bidirectional, workload\- dependent swings unrelated to the filter’s pruning quality\. \(ii\) For a deterministic engine the equality itself is expected whenever pruned candidates are never visited; the informative measurements are the fire rates alongside the invariance, and the direct intersection of §[6\.9](https://arxiv.org/html/2606.24421#S6.SS9)\.

## 7\.Related Work

#### CSM systems\.

From early active\-graph systems\(Kankanamge et al\.,[2017](https://arxiv.org/html/2606.24421#bib.bib13)\), four generations of index design—TurboFlux’s data\-centric spanning tree\(Kim et al\.,[2018](https://arxiv.org/html/2606.24421#bib.bib14)\), SymBi’s bidirectional dynamic candidate space\(Min et al\.,[2021](https://arxiv.org/html/2606.24421#bib.bib20)\), RapidFlow\(Sun et al\.,[2022a](https://arxiv.org/html/2606.24421#bib.bib23)\), CaLiG’s candidate\-lighting graph with kernel\-and\-shell search\(Yang et al\.,[2023](https://arxiv.org/html/2606.24421#bib.bib27)\), and NewSP’s compatible\-set reuse\(Li et al\.,[2024](https://arxiv.org/html/2606.24421#bib.bib18)\)— each improved over its predecessor by one to three orders of magnitude, all filtering with labels, degrees, and neighbor\-label multisets, refined by consistency propagation over candidate adjacency\(Wang et al\.,[2023](https://arxiv.org/html/2606.24421#bib.bib26)\)\. DIVINE\(Ye et al\.,[2025](https://arxiv.org/html/2606.24421#bib.bib28)\)is the first to add a non\-structural signal \(vertex\-dominance embeddings over degree\-grouped star synopses, maintained incrementally\)\. Its synopses are built from degree\-grouped star substructures—degree\-sequence\-adjacent information in the sense of our GMB analysis—and our methodology supplies the test any such signal should face: report intermediates with the filter on and off under a fixed engine and order; unless the prunable set intersects the cost\-bearing set of adjacency\-guided enumeration, candidate reductions will not become time\.

#### Experimental studies\.

Sun et al\.\(Sun et al\.,[2022b](https://arxiv.org/html/2606.24421#bib.bib24)\)unified six CSM algorithms under incremental view maintenance and identified scenario\-dependent index choice; the delta\-compilation study of Lee et al\.\(Lee et al\.,[2024](https://arxiv.org/html/2606.24421#bib.bib16)\)showed an optimized implementation of an old method beats CaLiG by up to48\.6×48\.6\\times, making implementation\-controlled comparison mandatory, echoing the common\-codebase discipline of earlier static\-matching studies\(Lee et al\.,[2012](https://arxiv.org/html/2606.24421#bib.bib15)\)—our evaluation therefore swaps only the index layer inside the decoupled framework of Gou et al\.\(Gou et al\.,[2026](https://arxiv.org/html/2606.24421#bib.bib8)\), whose caveat that candidate counts can*understate*filtering power we extend to the converse direction with the intermediate\-invariance test\. The SIGMOD’24 survey of static matching\(Zhang et al\.,[2024](https://arxiv.org/html/2606.24421#bib.bib29)\)evaluates 534 combinations and finds enumeration dominant; our law refines where that dominance does and does not leave room for filtering\.

#### Spectral and static matching\.

PILOS\(Skitsas et al\.,[2025](https://arxiv.org/html/2606.24421#bib.bib21)\)introduced interlacing on neighborhood Laplacians for static matching, building on candidate\-space frameworks\(Bhattarai et al\.,[2019](https://arxiv.org/html/2606.24421#bib.bib5); Sun and Luo,[2020](https://arxiv.org/html/2606.24421#bib.bib22); Arai et al\.,[2023](https://arxiv.org/html/2606.24421#bib.bib3)\)and a static\-matching lineage scaling exploration to billion\-node graphs\(Sun et al\.,[2012](https://arxiv.org/html/2606.24421#bib.bib25)\); its index is offline and static\. We show its natural dynamic extensions are either infeasible \(lazy bounds\) or ineffective for delta enumeration \(the boundary regularity\), while its static gains are consistent with our positive\-boundary analysis\. The Grone–Merris conjecture\(Grone and Merris,[1994](https://arxiv.org/html/2606.24421#bib.bib9)\), proved by Bai\(Bai,[2011](https://arxiv.org/html/2606.24421#bib.bib4)\), underpins our explanation that Laplacian interlacing is largely a degree\-sequence statistic on matching workloads\. Dynamic spectral sparsifiers\(Abraham et al\.,[2016](https://arxiv.org/html/2606.24421#bib.bib2)\)maintain global spectral approximations under updates, and incremental eigenpair tracking follows leading eigenpairs of a single evolving matrix\(Chen et al\.,[2018](https://arxiv.org/html/2606.24421#bib.bib7)\); maintaining exact local*neighborhood*spectra for all \(deployable\) vertices of a dynamic graph, asSelSpecdoes, appears new to our knowledge\.

## 8\.Conclusion

We set out to bring spectral filtering to continuous subgraph matching and instead mapped its boundary\. Lazy maintenance is provably hopeless in the useful regime; exact maintenance is cheap if deployed where an anti\-correlation law directs it; and the resulting pruning—however safe, however large in candidate counts—cannot touch adjacency\-guided enumeration, a fact replicated across the eight configurations of Table 3 and confirmed in our own static rebuild, where the same tests cut candidate\-space construction work by up to43%43\\%while leaving exploration untouched\. The regularity’s final form is architectural: aggregate invariants accelerate what scales with candidate sets, never what chases adjacency\. The positive residue is a reusable primitive \(exact dynamic local spectra\), a safe update\-level gating framework whose yield lands wherever candidate sets are materialized, and a methodological test \(intermediate invariance\) that we believe should accompany every future claim that a new filter accelerates CSM\.

## References

- \(1\)
- Abraham et al\.\(2016\)Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng\. 2016\.On Fully Dynamic Graph Sparsifiers\. In*57th IEEE Annual Symposium on Foundations of Computer Science, FOCS*\. 335–344\.[https://doi\.org/10\.1109/FOCS\.2016\.44](https://doi.org/10.1109/FOCS.2016.44)
- Arai et al\.\(2023\)Junya Arai, Yasuhiro Fujiwara, and Makoto Onizuka\. 2023\.GuP: Fast Subgraph Matching by Guard\-based Pruning\.*Proc\. ACM Manag\. Data*1, 2 \(2023\)\.[https://doi\.org/10\.1145/3589312](https://doi.org/10.1145/3589312)
- Bai \(2011\)Hua Bai\. 2011\.The Grone\-Merris Conjecture\.*Trans\. Amer\. Math\. Soc\.*363, 8 \(2011\), 4463–4474\.[https://doi\.org/10\.1090/S0002\-9947\-2011\-05393\-6](https://doi.org/10.1090/S0002-9947-2011-05393-6)
- Bhattarai et al\.\(2019\)Bibek Bhattarai, Hang Liu, and H\. Howie Huang\. 2019\.CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching\. In*Proceedings of the 2019 International Conference on Management of Data, SIGMOD*\. 1447–1462\.[https://doi\.org/10\.1145/3299869\.3300086](https://doi.org/10.1145/3299869.3300086)
- Brouwer and Haemers \(2008\)Andries E\. Brouwer and Willem H\. Haemers\. 2008\.A lower bound for the Laplacian eigenvalues of a graph—proof of a conjecture by Guo\.*Linear Algebra Appl\.*429, 8\-9 \(2008\), 2131–2135\.[https://doi\.org/10\.1016/j\.laa\.2008\.06\.008](https://doi.org/10.1016/j.laa.2008.06.008)
- Chen et al\.\(2018\)Pin\-Yu Chen, Baichuan Zhang, and Mohammad Al Hasan\. 2018\.Incremental eigenpair computation for graph Laplacian matrices: theory and applications\.*Soc\. Netw\. Anal\. Min\.*8, 1 \(2018\), 4\.[https://doi\.org/10\.1007/s13278\-017\-0481\-y](https://doi.org/10.1007/s13278-017-0481-y)
- Gou et al\.\(2026\)Xiangyang Gou, Lei Zou, Jeffrey Xu Yu, and Wenjie Zhang\. 2026\.An Extensive Experimental Study of Indexes in Continuous Subgraph Matching\.*Proc\. ACM Manag\. Data*4, 1 \(2026\)\.[https://doi\.org/10\.1145/3786623](https://doi.org/10.1145/3786623)
- Grone and Merris \(1994\)Robert Grone and Russell Merris\. 1994\.The Laplacian Spectrum of a Graph II\.*SIAM J\. Discrete Math\.*7, 2 \(1994\), 221–229\.[https://doi\.org/10\.1137/S0895480191222653](https://doi.org/10.1137/S0895480191222653)
- Han et al\.\(2019\)Myoungji Han, Hyunjoon Kim, Geonmo Gu, Kunsoo Park, and Wook\-Shin Han\. 2019\.Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together\. In*Proceedings of the 2019 International Conference on Management of Data, SIGMOD*\. 1429–1446\.[https://doi\.org/10\.1145/3299869\.3319880](https://doi.org/10.1145/3299869.3319880)
- He and Singh \(2008\)Huahai He and Ambuj K\. Singh\. 2008\.Graphs\-at\-a\-time: Query Language and Access Methods for Graph Databases\. In*Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data*\. 405–418\.[https://doi\.org/10\.1145/1376616\.1376660](https://doi.org/10.1145/1376616.1376660)
- Horn and Johnson \(2013\)Roger A\. Horn and Charles R\. Johnson\. 2013\.*Matrix Analysis*\(2nd ed\.\)\.Cambridge University Press\.
- Kankanamge et al\.\(2017\)Chathura Kankanamge, Siddhartha Sahu, Amine Mhedhbi, Jeremy Chen, and Semih Salihoglu\. 2017\.Graphflow: An Active Graph Database\. In*Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD*\. 1695–1698\.[https://doi\.org/10\.1145/3035918\.3056445](https://doi.org/10.1145/3035918.3056445)
- Kim et al\.\(2018\)Kyoungmin Kim, In Seo, Wook\-Shin Han, Jeong\-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong\. 2018\.TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data\. In*Proceedings of the 2018 International Conference on Management of Data, SIGMOD*\. 411–426\.[https://doi\.org/10\.1145/3183713\.3196917](https://doi.org/10.1145/3183713.3196917)
- Lee et al\.\(2012\)Jinsoo Lee, Wook\-Shin Han, Romans Kasperovics, and Jeong\-Hoon Lee\. 2012\.An In\-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases\.*Proc\. VLDB Endow\.*6, 2 \(2012\), 133–144\.[https://doi\.org/10\.14778/2535568\.2448946](https://doi.org/10.14778/2535568.2448946)
- Lee et al\.\(2024\)Yukyoung Lee, Kyoungmin Kim, Wonseok Lee, and Wook\-Shin Han\. 2024\.In\-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework\.*Proc\. ACM Manag\. Data*2, 3 \(2024\)\.[https://doi\.org/10\.1145/3654950](https://doi.org/10.1145/3654950)
- Leskovec and Krevl \(2014\)Jure Leskovec and Andrej Krevl\. 2014\.SNAP Datasets: Stanford Large Network Dataset Collection\.[http://snap\.stanford\.edu/data](http://snap.stanford.edu/data)\.
- Li et al\.\(2024\)Ziming Li, Youhuan Li, Xinhuan Chen, Lei Zou, Yang Li, Xiaofeng Yang, and Hongbo Jiang\. 2024\.NewSP: A New Search Process for Continuous Subgraph Matching over Dynamic Graphs\. In*40th IEEE International Conference on Data Engineering, ICDE*\. 3324–3337\.[https://doi\.org/10\.1109/ICDE60146\.2024\.00257](https://doi.org/10.1109/ICDE60146.2024.00257)
- Mhedhbi and Salihoglu \(2019\)Amine Mhedhbi and Semih Salihoglu\. 2019\.Optimizing Subgraph Queries by Combining Binary and Worst\-Case Optimal Joins\.*Proc\. VLDB Endow\.*12, 11 \(2019\), 1692–1704\.[https://doi\.org/10\.14778/3342263\.3342643](https://doi.org/10.14778/3342263.3342643)
- Min et al\.\(2021\)Seunghwan Min, Sung Gwan Park, Kunsoo Park, Dora Giammarresi, Giuseppe F\. Italiano, and Wook\-Shin Han\. 2021\.Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming\.*Proc\. VLDB Endow\.*14, 8 \(2021\), 1298–1310\.[https://doi\.org/10\.14778/3457390\.3457395](https://doi.org/10.14778/3457390.3457395)
- Skitsas et al\.\(2025\)Konstantinos Skitsas, Davide Mottin, and Panagiotis Karras\. 2025\.Pilos: Scalable Large\-Subgraph Matching by Online Spectral Filtering\. In*41st IEEE International Conference on Data Engineering, ICDE*\.[https://doi\.org/10\.1109/ICDE65448\.2025\.00093](https://doi.org/10.1109/ICDE65448.2025.00093)
- Sun and Luo \(2020\)Shixuan Sun and Qiong Luo\. 2020\.In\-Memory Subgraph Matching: An In\-depth Study\. In*Proceedings of the 2020 International Conference on Management of Data, SIGMOD*\. 1083–1098\.[https://doi\.org/10\.1145/3318464\.3380581](https://doi.org/10.1145/3318464.3380581)
- Sun et al\.\(2022a\)Shixuan Sun, Xibo Sun, Bingsheng He, and Qiong Luo\. 2022a\.RapidFlow: An Efficient Approach to Continuous Subgraph Matching\.*Proc\. VLDB Endow\.*15, 11 \(2022\), 2415–2427\.[https://doi\.org/10\.14778/3551793\.3551803](https://doi.org/10.14778/3551793.3551803)
- Sun et al\.\(2022b\)Xibo Sun, Shixuan Sun, Qiong Luo, and Bingsheng He\. 2022b\.An In\-Depth Study of Continuous Subgraph Matching\.*Proc\. VLDB Endow\.*15, 7 \(2022\), 1403–1416\.[https://doi\.org/10\.14778/3523210\.3523218](https://doi.org/10.14778/3523210.3523218)
- Sun et al\.\(2012\)Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li\. 2012\.Efficient Subgraph Matching on Billion Node Graphs\.*Proc\. VLDB Endow\.*5, 9 \(2012\), 788–799\.[https://doi\.org/10\.14778/2311906\.2311907](https://doi.org/10.14778/2311906.2311907)
- Wang et al\.\(2023\)Xi Wang, Qianzhen Zhang, Deke Guo, and Xiang Zhao\. 2023\.A survey of continuous subgraph matching for dynamic graphs\.*Knowl\. Inf\. Syst\.*65, 3 \(2023\), 945–989\.[https://doi\.org/10\.1007/s10115\-022\-01753\-x](https://doi.org/10.1007/s10115-022-01753-x)
- Yang et al\.\(2023\)Rongjian Yang, Zhijie Zhang, Weiguo Zheng, and Jeffrey Xu Yu\. 2023\.Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction\.*Proc\. ACM Manag\. Data*1, 1 \(2023\), 15:1–15:26\.[https://doi\.org/10\.1145/3588695](https://doi.org/10.1145/3588695)
- Ye et al\.\(2025\)Yutong Ye, Xiang Lian, Nan Zhang, and Mingsong Chen\. 2025\.Continuous Subgraph Matching via Cost\-Model\-based Dynamic Vertex Dominance Embeddings\.*Proc\. ACM Manag\. Data*3, 6 \(2025\)\.[https://doi\.org/10\.1145/3769774](https://doi.org/10.1145/3769774)
- Zhang et al\.\(2024\)Zhijie Zhang, Yujie Lu, Weiguo Zheng, and Xuemin Lin\. 2024\.A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction\.*Proc\. ACM Manag\. Data*2, 1 \(2024\)\.[https://doi\.org/10\.1145/3639315](https://doi.org/10.1145/3639315)