Multiple Hypothesis Testing To Estimate The Number Of Communities in Stochastic Block Models

1. 연구 배경 및 문제 제기 (Problem)

• 배경: 단일 세포 RNA 시퀀싱 (scRNA-seq) 데이터의 클러스터링은 세포의 생물학적 기능을 이해하는 데 핵심적입니다. 최근 네트워크 기반 커뮤니티 탐지 (Community Detection) 방법이 scRNA-seq 데이터 클러스터링에 활발히 적용되고 있습니다.
• 핵심 문제:
  1. 커뮤니티 수의 미지수: 네트워크 기반 커뮤니티 탐지 방법 (예: Louvain, Leiden 알고리즘 등) 은 대개 사전에 '진짜 커뮤니티 (블록) 의 수'를 알고 있어야 합니다.
  2. 노이즈와 민감도: scRNA-seq 데이터는 높은 노이즈를 포함하며, 기존 커뮤니티 수 추정 방법들은 노이즈가 심한 데이터에서 견고하지 (robust) 못합니다.
  3. 하이퍼파라미터 의존성: 기존 방법들은 클러스터링 품질이 하이퍼파라미터 (예: 이웃 수, 임계값 등) 선택에 매우 민감하여 사용자의 세밀한 튜닝이 필요합니다.
  4. 아웃 - 인 비율 (Out-in Ratio): scRNA-seq 에서 생성된 네트워크는 블록 간 연결 확률과 블록 내 연결 확률의 비율 (아웃 - 인 비율) 이 클 수 있는데, 기존 방법들은 이러한 높은 비율에 대해 민감하게 반응하여 성능이 저하됩니다.

2. 제안된 방법론 (Methodology)

저자들은 scRNA-seq 데이터의 커뮤니티 수를 추정하기 위해 **이중 솔루션 (Two-fold Solution)**을 제안합니다.

A. scRNA-seq 데이터로부터 SBM 네트워크 추출

• scRNA-seq 데이터에서 확률적 블록 모델 (Stochastic Block Model, SBM) 을 추출하기 위한 간단한 가능도 기반 (Likelihood-based) 접근법을 제시합니다.
• 하이퍼파라미터 자동화: 그리드 서치 (Grid-search) 를 통해 최적의 하이퍼파라미터 세트를 자동으로 선택하여, 사용자가 수동으로 튜닝할 필요를 없앱니다.
  • 데이터 필터링 (저품질 세포/유전자 제거) 및 로그 정규화 수행.
  • 상관 행렬을 유사도 행렬로 변환하고, 특정 분위수 (quantile) 임계값을 사용하여 인접 행렬 (Adjacency Matrix) 을 생성.
  • 생성된 다양한 네트워크 후보 중 SBM 과 가장 유사한 (최대 가능도를 가지는) 네트워크를 선택.

B. 순차적 다중 검정 (Sequential Multiple Testing, SMT) 알고리즘

• 핵심 아이디어: $K$개의 블록을 가진 SBM 은 $K$개의 서로 다른 Erdős-Rényi(ER) 그래프로 구성될 수 있다는 점에 착안합니다. SBM 내의 각 블록은 블록 내 연결 확률이 블록 간 연결 확률보다 높은 (Assortative) ER 그래프로 간주됩니다.
• 알고리즘 절차:
  1. 커뮤니티 수 $\hat{K}=1$로 초기화합니다.
  2. 현재 $\hat{K}$에 대해 커뮤니티 멤버십을 추정하고, 해당 블록들을 ER 그래프로 가정합니다.
  3. 각 블록의 **제 2 고윳값 (Second Eigenvalue)**을 계산합니다.
     • ER 그래프의 제 1 고윳값은 신호 (Signal) 를, 제 2 고윳값은 노이즈 (Noise) 를 나타내며, 이는 Tracy-Widom 분포를 따릅니다.
  4. 순차적 가설 검정:
     • 귀무가설 ($H_0$): 선택된 $\hat{K}$개의 블록이 모두 ER 그래프이다.
     • 대립가설 ($H_1$): 적어도 하나의 블록이 ER 그래프가 아니다 (즉, 커뮤니티 수가 더 많다).
  5. 검정 통계량이 Tracy-Widom 분포의 임계값을 초과하지 않으면 $\hat{K}$를 최종 커뮤니티 수로 채택하고 종료합니다. 그렇지 않으면 $\hat{K}$를 1 증가시켜 반복합니다.
  6. 보완 전략: 블록 내 연결 확률이 0.5 보다 큰 경우, 해당 블록의 여집합 (Complement) 그래프를 사용하여 검정력을 최적화하고 1 종 오류를 최소화합니다.

3. 주요 기여 및 이론적 성과 (Key Contributions & Theoretical Results)

• 일관성 (Consistency): 제안된 SMT 추정량이 중간 정도의 희소성 (Moderate Sparsity) 조건 하에서 진짜 커뮤니티 수 $K(n)^*$로 수렴함을 증명했습니다.
  • 희소 그래프 ($d \ge O(\log n)$) 와 밀집 그래프 모두에서 일관성을 가집니다.
  • 커뮤니티 수 $K$가 $n$에 따라 증가하는 경우 ($O(\log n)$ 또는 $O(n^{1/4-\tau})$) 에도 적용 가능합니다.
• 검정력 (Power): 모델이 과소적합 (Under-fitted) 일 때 (즉, 실제 커뮤니티 수보다 적게 추정할 때), 가설 검정이 1 의 확률로 귀무가설을 기각함을 보였습니다.
• 아웃 - 인 비율에 대한 강건성: 기존 방법들은 전체 네트워크를 사용하여 커뮤니티 수를 추정하는 반면, SMT 는 개별 ER 블록의 제 2 고윳값에 의존합니다. 이로 인해 아웃 - 인 비율이 큰 (노이즈가 많은) 네트워크에서도 기존 방법들보다 훨씬 강건한 성능을 보입니다.
• 계산 효율성: 교차 검증 (Cross-validation) 기반 방법이나 베이지안 방법보다 계산 비용이 적게 듭니다.

4. 실험 결과 (Results)

• 시뮬레이션 연구:
  • 다양한 네트워크 크기 ($N$), 커뮤니티 수 ($K$), 평균 차수 (Degree), 아웃 - 인 비율 조건에서 SMT 를 기존 방법 (LRBIC, StGoF, NCV, ECV, BHMC, EigCV 등) 과 비교했습니다.
  • 결과: 아웃 - 인 비율이 증가할수록 대부분의 기존 방법의 정확도가 급격히 떨어지는 반면, SMT 는 아웃 - 인 비율 변화에 가장 덜 민감하여 높은 정확도를 유지했습니다. 특히 $K$가 크고 ($15, 20$), 네트워크가 크고 ($N=5000$) 아웃 - 인 비율이 높은 조건에서도 SMT 가 우세한 성능을 보였습니다.
• 실제 데이터 분석 (Benchmark & Real Data):
  • 벤치마크 데이터: Kiselev et al. (2017) 이 제시한 6 가지 scRNA-seq 골드 스탠다드 데이터셋에서 SMT 를 적용했습니다. 하이퍼파라미터를 자동 선택한 결과, 기존 방법 (SC3 등) 과 비교해 동등하거나 더 나은 커뮤니티 수 추정 성능을 보였습니다.
  • 인간 망막 이극성 세포 (Human Retina Bipolar Cells): 실제 생물학적 데이터에 적용하여 세포 하위 그룹 (Subgroups) 을 성공적으로 추정했습니다. 이 과정에서 하이퍼파라미터를 고정하지 않고 최적화 과정을 거쳤습니다.

5. 의의 및 결론 (Significance)

• 노이즈가 많은 scRNA-seq 데이터에 최적화된 접근: scRNA-seq 데이터의 높은 노이즈와 아웃 - 인 비율 문제를 해결하기 위해, 네트워크의 전체 구조가 아닌 블록 단위의 통계적 성질 (제 2 고윳값) 을 활용하는 새로운 패러다임을 제시했습니다.
• 하이퍼파라미터 불필요: 사용자의 주관적인 튜닝 없이 데이터 기반의 자동화된 프로세스를 통해 커뮤니티 수를 추정할 수 있어 재현성과 객관성을 높였습니다.
• 이론적 엄밀함과 실용성의 결합: Tracy-Widom 분포를 기반으로 한 엄밀한 통계적 이론 (일관성 증명) 을 바탕으로 하면서도, 실제 생물학적 데이터 분석에 바로 적용 가능한 효율적인 알고리즘을 제공했습니다.

이 논문은 복잡한 scRNA-seq 데이터에서 세포 군집을 식별하는 데 있어, 기존 네트워크 기반 방법들의 한계를 극복하고 통계적으로 견고하며 계산 효율적인 새로운 표준을 제시한다는 점에서 중요한 의의를 가집니다.