Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.24421v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
밴딧 피드백을 활용한 동적 그래프에서의 로컬 워크 학습
Learning from Local Walks on Dynamic Graphs with Bandit Feedback
우리는 동적 그래프 위의 확률적 다중 슬롯 머신 밴딧(stochastic multi-armed bandits)을 연구한다. 여기서 각 암(arm)은 시간에 따라 엣지가 변하는 네트워크의 정점(vertex)에 대응된다. 이 설정에서 학습자는 로컬 이동만 허용되어, 매 라운드마다 현재 노드 또는 인접 이웃 노드만을 선택할 수 있다. 이 제약은 최적 암 식별과 활용(exploitation)을 분리시킨다. 즉, 최적 암이 식별된 이후에도 학습자는 진화하는 위상 구조(topology)를 통해 해당 암에 도달하지 못할 수 있다. 우리는 슬라이딩 윈도우 믹싱(sliding-window mixing)에 기반한 프로세스-비종속적(process-agnostic) 구조 조건을 규명하며, 이를 통해 그래프의 내재적 워크(walk)가 탐험(exploration)과 탐색 모두에서 안정적으로 유지됨을 보장한다. 이 체제 하에서 로컬 탐험 후 확정(explore-then-commit) 알고리즘 계열을 분석하고 준선형(sublinear) 기댓값 후회(expected regret)를 확립한다. 우리의 프레임워크는 보상(reward)-인식 전략을 포함하며, 이에 대해 최악의 경우 안전성 정리(worst-case safety theorem)와 별도의 성능 향상 정리(performance gain theorem)를 증명한다.
소프트맥스가 버리는 것: 증거 누적을 위한 질량 인식 어텐션
What Softmax Throws Away: Mass-Aware Attention for Evidence Accumulation
높은 태스크 성능은 모델이 내부 표현에서 예측과 관련된 구조적 정보를 유지하는지 여부를 보여주지 않는다. 예를 들어, 시간 그래프 모델은 높은 future-link AUC를 달성할 수 있지만, 동일한 표현에서 기본 그래프 통계를 복원하는 것은 여전히 어렵다. 우리는 이러한 격차의 한 원인을 표준 어텐션에서 사용하는 가중 평균에서 찾는다. 증거 패턴이 반복되면 분자와 분모가 같은 속도로 증가하므로, 누적된 증거의 양이 다른 입력들이 동일한 집계값을 만들 수 있다. 우리는 표준 L1 정규화를 Lp 계열로 일반화하는 Mass-Aware Attention(MAA)을 제안한다. 반복 상황에서 MAA는 분자와 분모가 서로 다른 속도로 스케일되게 하여, 표현 크기에 기여하는 입력의 유효 개수를 표현 크기에 유지한다. MAA는 추가적인 지도, 파라미터, 은닉 차원, 또는 명시적 개수 특징을 추가하지 않으며, p=1에서 표준 어텐션을 복원한다. 4개의 연속 시간 동적 그래프 모델과 3개의 데이터셋에 걸쳐, MAA는 12개의 모델-데이터셋 셀 중 11개에서 future-link AUC를 개선한다. 동일한 은닉 표현에서의 선형 복원은 평균 4.49% 증가하며, family-wise correction 후 preferential-attachment 복원은 12개 셀 모두에서 개선된다. 또한 marked temporal point process(MTPP), temporal knowledge graph(TKG), 검색-증강 생성(RAG), 시공간 point process(STPP)에서도 일관된 증거를 관찰한다. 정보 접근성과 태스크 유용성은 여전히 구별된다. MTPP에서 NLL은 개선되지만, TKG에서는 랭킹이 대체로 유지되고, RAG의 추가 정보는 진단 헤드를 개선하지 않으며, STPP에서는 하류 LayerNorm이 신호를 지울 수 있다. 이 결과들은 MAA를 표준 어텐션에서 반복 불변성(repetition invariance)을 제어함으로써 예측기 대면 표현의 정보성을 개선하는 일반적인 정규화 원리로 자리매김한다.
그래프 신경망의 깊이 인식 장거리 전파를 위한 스펙트럴 플로우 인증
Spectral Flow Certificates for Depth-Aware Long-Range Propagation in Graph Neural Networks
그래프 신경망(GNN)은 지역적 메시지 전달(message passing)을 통해 정보를 전파하지만, 그래프 위상(topology) 자체가 학습을 아무리 많이 해도 장거리(long-range) 과제를 해결하지 못하게 조용히 막을 수 있다. GNN을 새로운 그래프에 배포할 때, 현재는 학습이 시작되기 전에 그래프 구조가 먼 노드들 사이에서 정보가 충분히 멀리 전달될 수 있게 허용하는지를 알아낼 저비용 방법이 없다. 우리는 스펙트럴 플로우 인증(Spectral Flow Certificates, SFC)을 제안하여 이 공백을 해소한다. SFC는 그래프의 정규화(normalised) 라플라시안(Laplacian)으로부터 수 초 만에 계산되는 단일 스칼라 값으로, 모델 학습이나 라벨 데이터가 필요하지 않다. SFC는 그래프의 대수적 연결성(algebraic connectivity)과 선택된 메시지 전달 깊이(depth)를 하나의 숫자로 융합하여, 가용한 깊이 예산(depth budget) 내에서 중요한 스펙트럴 병목(spectral bottleneck)의 어느 정도를 통과할 수 있는지를 측정한다. 원시 스펙트럴 갭(spectral gap)과 달리 SFC는 정적이고 깊이와 무관(depth-agnostic)한 반면, SFC는 레이어 수가 증가함에 따라 적응하므로 깊이가 달라질 때 엄격히 더 많은 진단 정보를 담는다. 평균 유효 저항(average effective resistance)과 그래프 직경(graph diameter) 같은 고전적 구조 통계와 비교했을 때, SFC는 학습된 GNN의 장거리 정확도(long-range accuracy) 분산(variance)의 두 배 이상을 설명한다. 경로(path), 순환(cycle), 격자(grid), 정규 그래프(regular graph), 무작위 그래프(random graph)를 아우르는 25개의 합성 그래프 계열에 걸쳐, SFC는 어떤 기울기(gradient)도 계산하기 전에 학습된 정확도를 예측하며, 테스트된 모든 깊이에서 90% 이상의 설명력(explanatory power)을 달성한다. 동일한 예측 관계는 세 개의 독립적인 벤치마크(benchmark) 데이터셋(dataset)에서 추출한 150개의 실제 분자 그래프 위상에서도 성립하며, 이는 해당 결과가 합성 구조의 인공물(artefact)이 아님을 확인해 준다. 종합하면, 이러한 결과는 단일 고유값(eigenvalue) 계산만으로도 값비싼 학습 파이프라인에 투입하기 전에 위상(topology)에 의해 제한된 그래프를 표시하기에 충분하며, GNN 배포를 위한 원칙적인 1차 필터를 제공함을 보여준다.
개연성과 허용 가능성 사이의 격차를 메우기: 동적 그래프 시스템을 위한 제약 인식 Flow Map
Bridging the Gap Between Plausibility and Admissibility: Constraint-Aware Flow Maps for Dynamic Graph Systems
생성 모델은 그럴듯한 미래 시스템 궤적의 앙상블을 생성함으로써 불확실성 하에서의 의사결정을 지원할 수 있지만, 통계적 개연성(statistical plausibility)이 구조적 실행 가능성(structural feasibility)을 보장하지는 않는다. 본 연구는 동적 그래프 구조 시스템에서 생성적 궤적 모델링의 신뢰성을 사후 샘플링(post-sampling) 기호적(symbolic) 제약이 개선할 수 있는지 조사한다. 조건부 확산 모델(conditional diffusion model)이 부분 관측으로부터 미래 그래프 상태 궤적을 생성하고, 외부 기호 층(symbolic layer)이 하드 필터링(hard filtering), 소프트 가중(soft weighting), 또는 투영 기반(projection-based) 복구(repair)를 적용한다. 이 프레임워크는 구조적 유효성, 샘플 효율성, 다양성, 견고성(robustness), 교정(calibration) 지표를 사용하여 두 가지 통제된 합성 체제—컴팩트 그래프와 중간 복잡도 의존성 그래프—에서 평가된다. 컴팩트 체제에서 모델은 0.002996의 무효 확률 질량(invalid probability mass)을 생성하며, 이는 거의 완전히 허용 가능한(admissible) 궤적 매니폴드를 나타낸다. 동일한 아키텍처와 학습 프로토콜 하에서, 중간 복잡도 체제에서는 무효 질량이 0.155929로 증가한다. 하드 필터링은 생성된 샘플의 84.4%를 보존하면서 보존된 모든 무효 궤적을 제거하는 반면, 소프트 가중은 유효 표본 크기(effective sample size)를 보존하지만 제한적인 유효성 향상만을 제공한다. 계열(family) 수준 분석은 의존성 제약(dependency constraints)이 관측된 거의 모든 비허용(inadmissibility)을 설명함을 보여준다. 이 결과는 통계적 개연성과 구조적 허용 가능성이 서로 다른 신뢰성 속성임을, 그리고 그래프 구조적 복잡도가 증가할수록 기호적 제약 처리가 더 가치 있어짐을 나타낸다.
동적 그래프의 노드 친화도를 이용한 기관 주식 보유 예측
Institutional Equity Holdings Prediction Using Node Affinities of Dynamic Graphs
SEC Form 13F 제출 자료에 공개된 기관 주식 보유는 대형 투자 운용사의 포트폴리오 결정에 대한 풍부한 시계열 기록을 제공한다. 그러나 공시 지연, 보고 노이즈, 기관 행동의 강한 지속성(persistence) 때문에 미래 배분을 예측하고 미래 수요를 모델링하는 것은 여전히 어렵다. 우리는 시간적 그래프 머신러닝을 사용하여 이러한 작업을 위한 최초의 벤치마크를 도입하며, 전처리된 제출 자료에서 추출한 운용사와 증권의 이산 시간(temporal) 이분 그래프(bipartite graph)에서 보유 예측을 노드 친화도(node affinity) 예측, 즉 포트폴리오 비중 예측으로 정식화한다. 99명의 운용사와 S&P 500 지수(2013--2025년 48분기에 걸친 503개 증권, 209,351개의 시간적 엣지)로 구성된 샘플링된 데이터셋에서, Virtual State를 사용하는 Node Affinity 예측 모델(NAVIS)은 특징(features) 포함 시 최첨단 테스트 Normalized Discounted Cumulative Gain(NDCG) 0.9127(미포함 시 0.9121)을 달성하여, 모든 동적 그래프 표현 학습 경쟁 모델을 상당한 마진으로, 모든 휴리스틱 방법을 능가한다. 주목할 만하게, 단순한 지수 이동 평균(Exponential Moving Average) 기준선이 0.8882를 달성하여 NAVIS를 제외한 모든 동적 그래프 모델과 Persistent Forecast(0.8891)를 제외한 모든 휴리스틱을 능가하며, 이는 기관 포트폴리오의 강한 평활성(smoothness)과 지속성을 부각한다. 도메인 특화 노드 특징은 극히 미미한 향상(<1.2%)만 제공하며, 이는 13F 소유권 그래프의 시간적 및 구조적 신호가 이미 예측 가능한 정보의 대부분을 포착하고 있음을 시사한다. 실제 13F 데이터에 대해 특징 유무 모두에서 노드 친화도 예측 설정 하에 Temporal Graph Benchmark(TGB) 모델 무리를 벤치마킹함으로써, 본 연구는 보유 예측 및 포트폴리오 배분에서 시간적 그래프 머신러닝을 위한 재현 가능한 기반을 제공한다.
그래프 합성곱 어텐션: 그래프 노이즈 제거와 확산에 대한 스펙트럴 관점
Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion
그래프 노이즈 제거는 그래프 학습의 근본적인 문제이자 그래프 확산 모델의 핵심 연산이다. 그래프 트랜스포머와 같은 어텐션 기반 아키텍처는 최근 그래프 노이즈 제거에서 가능성을 보여주고 있다. 그러나 어텐션 기반 그래프 노이즈 제거에 대한 원리적 이해는 여전히 제한적이며, 표준 어텐션이 이 작업에 적합한 메커니즘인지 불분명하다. 본 논문에서는 노이즈 제거 목적 함수 하에서 선형 어텐션이 준최적(suboptimal)이며 학습 분포 전반에 걸쳐 평균 스펙트럴 노이즈 제거 필터만 학습할 수 있음을 보인다. 그래프는 분포 전반에 걸쳐 스펙트럴 특성이 자주 달라지기 때문에 이는 근본적인 한계를 야기한다. 이 한계를 극복하기 위해 입력 그래프 스펙트럼을 직접 활용하는 Spectral Attention을 도입하며, 이는 분포의 스펙트럴 다양성에 의해 결정되는 마진만큼 선형 어텐션을 증명 가능하게 능가한다. 이어서 그래프 필터링된 쿼리와 키를 통해 스펙트럴 노이즈 제거를 구현하는, 이 아이디어의 실용적이고 순열 등변(permutation-equivariant) 실현인 Graph Convolutional Attention(GCA)을 도출한다. 확률적 블록 모델(stochastic block models)에서 GCA는 이상적인 Spectral Attention 메커니즘과 증명 가능하게 동등한 성능을 달성한다. 또한 어텐션 이후에 적용되는 소프트맥스 연산이 노이즈가 있는 고유벡터를 깨끗한 고유공간에 근사 투영함으로써 추가적인 노이즈 제거를 제공함을 보인다. 실험적으로, 선형 어텐션을 GCA로 교체하면 합성 및 실제 데이터셋에서 그래프 노이즈 제거와 확산이 일관되게 향상되며, 그 성능 향상은 스펙트럴 다양성과 강한 상관관계를 보인다. DiGress에서 GCA는 비용이 큰 구조적 특징 계산 없이 표준 그래프 트랜스포머 성능에 필적하며, 최근 제안된 PEARL 위치 인코딩과 결합하면 명시적인 고유분해 계산을 피할 수 있어 품질 저하 없이 더 빠른 추론이 가능하다. 코드는 github.com/shervinkhalafi/graph_conv_att에서 확인할 수 있다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.