집계 불변량(Aggregate Invariants)이 연속적 서브그래프 매칭(Continuous Subgraph Matching)을 가속화할

스펙트럼 필터링(Spectral filtering)은 최근 extit{정적(static)} 서브그래프 매칭(subgraph matching)에서 상당한 가지치기(pruning) 효과를 제공했습니다. 라플라시안 인터레이싱(Laplacian interlacing)은 쿼리(query)를 수용할 수 없는 이웃을 가진 후보들을 거부합니다. 우리는 이러한 집계 구조 테스트(aggregate structural tests)가 동적 그래프(dynamic graphs)에서의 extit{연속적(continuous)} 서브그래프 매칭(CSM)을 가속화할 수 있는지 연구하며, 세 부분으로 나누어 답합니다. 첫째, 게으르게 유지되는(lazily maintained) 스펙트럼 경계(spectral bounds)는 스펙트럼 가지치기(spectral pruning)가 가치를 발휘하는 바로 그 지점에서 실행 불가능합니다. 우리는 정형화된 섭동 완화(perturbation relaxation)에 대해 가장 타이트하고 안전한 규칙을 특성화하며, 심지어 이 규칙조차 네 번의 접촉 업데이트(touching updates) 이내에 본질적으로 모든 가지치기 능력을 상실함을 보여줍니다. 둘째, 선택적일 경우 정확한 유지(exact maintenance)는 감당할 수 있는 수준입니다. 가지치기 효용(pruning utility)과 재계산 비용(recomputation cost)은 정점(vertices) 전반에 걸쳐 반비례합니다. 즉, 허브(hubs)는 증명 가능한 수준으로 결코 가지치기를 수행하지 않습니다. 따라서 접촉 시 작은 이웃의 스펙트럼(spectra)을 재계산하는 것은 업데이트당 마이크로초 단위로 정확한 로컬 스펙트럼(local spectra)을 구조적으로 완벽하게 유지합니다. 셋째, 스펙트럼이 동일하지 않은 대조군과 비교한 분리된 CSM 벤치마크에 통합했을 때, 이 테스트들은 후보의 최대 $51%$를 제거하거나 업데이트 열거(update enumerations)의 최대 $47%$를 안전하게 건너뜁니다. 그러나 두 개의 엔진, 네 개의 실제 그래프, 두 개의 스트림 유형, 그리고 $77$개의 해결된 쿼리에 걸쳐, 게이트의 건너뛴 1단계 바인딩(first-level bindings, 일반적으로 0임)을 제외하면 열거 중간 단계(enumeration intermediates)는 변하지 않았습니다. 구축된 반경 계층화 워크로드(radius-stratified workload)는 이 도구가 예외가 존재할 때 이를 감지함을 확인했습니다($-99.9%$ 중간 단계, $748\times$ 더 빠름). 집계 테스트는 후보 집합(candidate sets)에 따라 확장되는 것들, 즉 구축(construction)과 리스트 스캔(list scans)은 가속화하지만, 인접성 가이드 탐색(adjacency-guided exploration)은 결코 가속화하지 않습니다. 우리는 CSM 필터를 평가하기 위한 중간 불변성 방법론(intermediate-invariance methodology)을 추출하고 재사용 가능한 동적 로컬 스펙트럼 지표(dynamic local-spectra index)를 공개합니다.