임계값 기반 로컬 하이퍼-플로우 확산 (Thresholded Local Hyper-Flow Diffusion)

로컬 하이퍼-플로우 확산 (Local Hyper-Flow Diffusion, HFD)은 일반적인 서브모듈러 하이퍼그래프 (submodular hypergraphs)에서 시드 기반 클러스터링 (seeded clustering)을 위해 에지 크기에 독립적인 Cheeger 유형의 보장을 제공하지만, 기존의 HFD 솔버들은 매 반복 (iteration)마다 중간 계산을 로컬하게 유지하지 못합니다. 본 논문에서는 시드 주변의 활성 영역 (active region)을 유지하고, 해당 영역 및 그 즉각적인 경계 (boundary)에 대해 투영 서브그레이디언트 (projected subgradient) 업데이트를 수행하며, 임계값 기반 (top-k) 경계 활성화를 통해 확장하는 1차 방법론인 임계값 기반 로컬 HFD (Thresholded Local HFD, TL-HFD)를 소개합니다. 우리는 로컬 업데이트가 정확함을 증명합니다. 즉, 활성 영역 및 그 경계로 제한된 차수 전처리된 (degree-preconditioned) 투영 서브그레이디언트 단계는 제한되지 않은 전역 업데이트 (unrestricted global update)와 일치합니다. 우리는 임계값 기반 업데이트를 명시적인 경계 건너뛰기 오차 (skipped-boundary error)를 가진 부정확한 투영 서브그레이디언트 단계로 취급하여, 정확한 업데이트와 임계값 기반 업데이트 모두에 대해 유한 시간 쌍대 부최적성 (finite-time dual suboptimality)을 확립합니다. 나아가, 실현된 로컬 서브그레이디언트 노름 (local subgradient norms)과 새로 활성화된 정점들 사이의 최소 경계 확장 (minimum boundary-push)에 의해 제어되는 가산적 활성화 볼륨 경계 (additive activated-volume bound)를 도출하고, 국소적 지지 (localized support)를 가진 근사적 쌍대 최적성을 조기 종료된 반복값에 대한 강건한 스윕-컷 (robust sweep-cut) 보장으로 변환합니다. 일반적인 서브모듈러 컷 비용 (submodular cut-costs)에 대해, 각 반복은 스캔된 영역 내에서 로컬하며 하이퍼에지 프리미티브 (hyperedge primitive)에 대해 오라클 민감적 (oracle-sensitive)입니다. 실험적으로 TL-HFD는 더 적은 볼륨을 활성화하면서도 종종 HFD와 대등하거나 이를 능가하는 성능을 보였으며, 확산이 비대상 정점 (non-target vertices)을 흡수하는 경향이 있는 노이즈가 있는 인스턴스에서 가장 큰 이득을 얻었습니다.