Ordering Stochastic Block Models via prior transitivity

기술 요약: 사전 전이성을 통한 순서형 확률 블록 모델링 (Ordering Stochastic Block Models via Prior Transitivity)

문제 정의
방향성 네트워크는 종종 두 가지 동시적인 구조적 특징을 나타낸다: 커뮤니티 구조(노드들이 유사한 상호작용 패턴을 가진 그룹을 형성함)와 계층 구조(그룹 간에 상호작용이 발생할 때 주로 높은 순위에서 낮은 순위의 그룹으로 흐르는 순서가 존재함). 기존 방법론들은 이러한 특징들을 분리하여 다루는 경우가 많다. 표준 확률 블록 모델(SBM)은 그룹은 찾아내지만 일관된 블록 순서를 강제하지 못하며, 순위 모델은 개별 노드의 순서는 정하지만 구조적으로 동등한 그룹을 식별하는 데 실패한다. 이러한 분리는 데이터 내에 그룹 수준의 계층 구조만 존재함에도 불구하고 엄격한 노드 수준의 순서를 강제하거나, 클러스터링된 데이터 내의 계층적 패턴을 감지하지 못하는 위험을 초래한다. 본 논문은 순서형 블록을 공동으로 추론하고, 전이적 블록 구조가 데이터에 의해 지지되는지 여부를 평가하는 통합된 프레임워크의 필요성을 다룬다.

방법론: 전이적 확률 블록 모델 (TSBM)
저자들은 방향성 가중치 네트워크를 위한 베이지안 모델인 전이적 확률 블록 모델(TSBM)을 소개한다. 이 방법론은 다섯 가지 핵심 축으로 구성된다:

1. 볼륨/방향 분해 (Volume/Direction Decomposition): 모델은 방향성 에지 수를 두 가지 성분으로 분해한다:

   • 볼륨 (Volume): 노드 간의 총 무방향 상호작용 볼륨으로, 대칭적 강도 행렬과 노드별 차수 성향(Degree-Corrected SBM 프레임워크를 따름)을 통해 모델링된다.
   • 방향 (Direction): 상호작용이 발생한다는 조건 하에 상호작용 방향의 확률. 이러한 분리를 통해 모델은 상호작용 빈도가 아닌 방향성 불균형에 계층을 부과할 수 있게 한다.

2. 전이성을 유도하는 사전 분포 (Transitivity-Inducing Priors): 모델은 방향성 로그-오즈($\psi$)에 대한 사전 분포를 통해 블록에 순서를 부여한다. 두 가지 명세가 제안된다:

   • 약한 확률적 전이성 (Weak Stochastic Transitivity, WST): 순환적 지배 패턴(예: $A \succ B \succ C \succ A$)을 배제하는 유연한 사전 분포로, 만약 블록 $k$가 $\ell$을 지배하고 $\ell$이 $m$을 지배하면 $k$가 $m$을 지배하도록 보장한다. 이는 상삼각 로그-오즈에 대한 독립적인 절단 가우시안 사전 분포를 통해 달성된다.
   • 강한 확률적 전이성 (Strong Stochastic Transitivity, SST): 더 제한적인 사전 분포인 Toeplitz SST 버전을 포함한다. 이는 방향성 우위가 순위 격차에 따라 증가한다고 가정한다(즉, 높은 순위의 블록이 중간 순위의 블록보다 낮은 순위의 블록에 대해 갖는 우위가 더 크다는 것). 이는 로그-오즈가 블록 간의 거리에만 의존하며, 양의 증분의 누적 합을 통해 단조 증가를 강제하는 방식으로 모델링된다.

3. 순서형 파티션 사전 분포 (Ordered Partition Prior): 순서형 블록 레이블은 교환 가능하지 않으므로(레이블을 치환하면 계층 구조와 따라서 가능도가 변함), 표준적인 교환 가능한 파티션 사전 분포는 적합하지 않다. 저자들은 인구 유전학에서 유래한 연령 순서 파티션 사전 분포(Donnelly and Tavaré, 1986; Donnelly and Joyce, 1991)를 채택한다. 이 사전 분포는 블록이 시간(또는 연령)에 따라 순차적으로 나타나는 것으로 취급하여, 리버서블 점프 MCMC 없이도 블록의 수와 노드 할당을 공동으로 추론할 수 있게 한다.

4. 사후 추론 (Posterior Inference): 추론은 부분적으로 붕괴된 깁스 샘플러(partially collapsed Gibbs sampler)를 통해 수행된다. 방향성 확률의 로지스틱 가능도와 가우시안 사전 분포 사이의 비공액성(non-conjugacy)을 처리하기 위해, 저자들은 Pólya-Gamma 데이터 증강을 활용한다. 이를 통해 방향성 파라미터, 볼륨 파라미터 및 노드 할당에 대한 다루기 쉬운 조건부 업데이트가 가능하다.

5. 모델 선택 (Model Selection): Leave-One-Out 교차 검증(LOO-CV)을 Pareto-smoothed 중요도 샘플링을 통해 실시하여, TSBM 변형 모델들을 표준 DC-SBM과 비교한다.

주요 기여

• 새로운 모델 공식화: TSBM은 블록 수준의 확률에 대한 전이성 제약을 사용하여 방향성 네트워크에서 확률적 동등성과 확률적 순서를 공동으로 추론하는 최초의 베이지안 모델이다.
• 계산적 용이성: Pólya-Gamma 증강과 연령 순서 파티션 사전 분포를 결합함으로써, 저자들은 순서형 블록의 수를 추정하기 위해 계산 비용이 많이 드는 차원 변화 방법(예: reversible-jump)을 피하면서도 완전한 깁스 샘플러를 도출한다.
• 유연한 전이성: WST와 Toeplitz SST의 도입은 단순한 비순환성부터 순위 의존적 지배에 이르기까지 다양한 수준의 계층적 엄격함에 모델이 적응할 수 있도록 한다.
• 진단 능력: 본 프레임워크는 순서를 부과하는 것이 해로운 시나리오(예: 비전이적 인용 네트워크)를 명시적으로 식별하며, 전이성 가설의 타당성을 평가할 수 있는 확률적 메커니지를 제공한다.

결과

• 시뮬레이션 연구: 희소한 네트워크에서 약한 방향성 신호가 있을 때, TSBM(WST 및 SST 버전 모두)은 예측 정확도(LOOIC)와 파티션 복구(Variation of Information) 측면에서 표준 DC-SBM보다 유의미하게 우수한 성능을 보인다. 강한 신호가 있는 조밀한 네트워크에서는 모든 모델이 유사한 성능을 보인다. 결정적으로, 순환(비전이적)을 포함하는 오설정된 시나리오에서는 DC-SBM이 TSBM보다 우수한 성능을 보였으며, 이는 전이성 가정이 부적절할 때 이를 감지하는 모델의 능력을 입증한다.
• 실증적 적용: 모델은 여섯 개의 방향성 가중치 네트워크(동물 지배, 저널 인용, 학교 교우 관계)에 적용되었다:
  • 동물 지배: 큰뿔양, 산양, 점박이하이에나 네트워크에서 TSBM은 일반적으로 DC-SBM보다 예측 성능을 개선했으며, 더 명확하고 일관된 계층 구조(더 적은 역방향 에지)를 가진 파티션을 생성했다.
  • 인용: 통계학 저널 인용 네트워크에서는 DC-SBM이 더 나은 성능을 보였다. 저자들은 위상적 구배(prestige gradients)가 존재하지만, 인용 패턴이 엄격하게 전이적이지 않기 때문에 순서형 사전 분포가 모델을 불필요하게 제약했다고 언급했다.
  • 마카크 원숭이: 마카크 지배 네트워크의 경우, 계층 구조가 이미 거의 완벽했다(거의 엄격한 노드 수준의 순서). 여기서 DC-SBM은 TSBM보다 약간 더 나은 성능을 보였는데, 이는 데이터에 이미 강력한 신호가 존재하여 사전 분포의 규제가 별다른 이점을 제공하지 못했기 때문이다.
  • 교우 관계: 고등학교 교우 관계 네트워크에서 TSBM은 글로벌 계층 구조와 일치하는 블록 수준의 순서를 복구한 반면, DC-SBM은 계층보다는 커뮤니티 구조를 반영하는 파티션을 생성했다.

의의 및 주장
본 논문은 TSBM이 순서형 그룹을 추정하고, 더 중요한 것은 전이적 블록 구조가 데이터에 의해 지지되는지 여부를 평가하는 확률적 프레임워크를 제공한다고 주장한다. 저자들은 모델의 가치가 단순히 순서를 강제하는 데 있는 것이 아니라, 그룹화와 계층을 공동으로 모델링함으로써 특히 방향성 신호가 약하거나 네트워크가 희소할 때 추론과 예측을 개선할 수 있다는 점에 있다고 강조한다. 이 연구는 또한 비교환 가능한 레이블을 가진 잠재 블록 모델에서 연령 순서 파티션 사전 분포의 유용성을 입증함으로써 베이지안 비모수학에 기여한다. 저자들은 모델의 성능이 데이터에 따라 달라질 수 있음을 겸허히 명시하며, 구조가 비전이적이거나 계층이 이미 매우 뚜렷한 경우 제약이 없는 DC-SBM이 여전히 선호될 수 있음을 언급한다.