확률적 블록 모델(Stochastic Block Models)에서의 쿼리 제한적 커뮤니티 복구

$n$개의 정점을 가진 2-커뮤니티 확률적 블록 모델(Stochastic Block Model, SBM)에서 네트워크 데이터에 대한 제한적이고 노이즈가 있는 접근 환경에서의 정확한 커뮤니티 복구(exact community recovery)를 연구합니다. 학습자는 유한한 쿼리 예산(query budget) 내에서, 쿼리된 정점의 각 실제 이웃을 고정된 확률로 독립적으로 공개하고 비이웃은 절대 반환하지 않는 노이즈가 있는 이웃 오라클(noisy neighborhood oracle)에 쿼리할 수 있습니다. 우리는 오라클 전용 접근 방식(oracle-only access)과 학습자가 기저 그래프의 단일 서브샘플링된 복사본(subsampled copy)을 함께 관찰하는 결합 모델을 모두 고려합니다. 오라클 전용 접근 방식의 경우, 균형 잡힌 균등 쿼리(balanced uniform querying)는 날카로운 비적응적 벤치마크(non-adaptive benchmark)를 제공합니다. 즉, 각 정점이 동일한 정수 횟수만큼 쿼리될 때, 관찰 결과는 약화된 에지 확률을 가진 SBM으로 축소되며 Abbe-Bandeira-Hall의 정확한 복구 임계값(exact-recovery threshold)이 적용됩니다. 우리는 이 벤치마크가 적응적으로 최적(adaptively optimal)이 아님을 보여줍니다. 균형 잡힌 균등 쿼리가 어떤 $m > 1$에 대해 $mn$번의 쿼리를 필요로 하는 영역에서, 2단계 적응적 전략(two-stage adaptive strategy)은 $n + o(n)$번의 쿼리로 성공합니다. 추가적인 서브샘플링된 그래프가 있는 경우, 우리는 하선형 쿼리 적응성 격차(sublinear-query adaptivity gap)를 증명합니다. 하선형 예산 내에서의 균형 잡힌 데이터 독립적 균등 쿼리는 서브샘플링된 그래프 단독 사용보다 개선되지 않는 반면, 적응적 쿼리(adaptive querying)는 불확실한 정점의 작은 집합을 타겟팅하여 정확한 복구를 달성할 수 있습니다. 따라서 적응적 데이터 획득(adaptive data acquisition)은 정확한 복구의 정보 이론적 한계(information-theoretic limits)를 엄격하게 개선할 수 있습니다.