Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models

기술적 요약: 확률적 블록 모델에서 효율적 추론 및 모델 선택을 위한 최대우도법과 최적 수송의 연결

문제 제기
본 논문은 노드가 숨겨진 군집으로 분할되고 엣지 확률이 군집 소속에 따라 결정되는 생성 프레임워크인 확률적 블록 모델 (SBM) 에서의 추론 및 모델 선택 문제를 다룹니다. SBM 은 다양한 구조를 복원하고 군집 수를 추정할 수 있는 도구를 제공한다는 점에서 모듈리티 최대화나 스펙트럴 클러스터링과 같은 대안적 클러스터링 방법보다 우위를 점하지만, 표준 추론은 종종 변분 기대값 최대화 (VEM) 에 의존합니다. VEM 의 결정적인 한계는 최적화 부드러움을 보장하기 위해 엔트로피 정규화에 의존한다는 점입니다. 이 정규화는 수송 계획이 희소해지도록 방해하여, 단일 최적화 문제 내에서 불필요한 군집을 자동으로 비활성화 (영 질량 할당) 하는 '본질적 모델 선택'을 저해합니다. 결과적으로 현재 접근법들은 종종 최적의 군집 수 ($K$) 를 결정하기 위해 계산 비용이 많이 드는 그리드 검색이나 휴리스틱 절차를 필요로 합니다.

방법론
저자들은 최적 수송 (OT) 의 관점, 특히 반-완화된 그로모프-워셔슈타인 (srGW) 발산을 활용하여 SBM 의 최대우도 변분 추론 (MLVI) 을 해석하는 새로운 프레임워크를 제안합니다.

1. srGW 로의 재형식화: 논문은 SBM 에서의 ELBO(증거 하한) 최대화가 엔트로피 정규화 항을 가진 srGW 발산 최소화와 동등함을 입증합니다. 손실 함수는 생성 모델의 음의 로그 우도에 해당합니다.
2. 비정규화 추정량: 엔트로피 정규화가 희소성을 방해한다는 점을 인식하여, 저자들은 비정규화 srGW 추정량을 조사합니다. 엔트로피 항 없이 srGW 손실을 최소화함으로써 연결 행렬 ($\Theta$) 과 수송 계획 (군집 할당을 나타내는 $T$) 에 대한 추정량을 정의합니다.
3. 모델 선택을 위한 희소성 촉진 정규화: 그리드 검색 없이 자동 모델 선택 ($K$ 추정) 을 가능하게 하기 위해, 저자들은 수송 계획에 $\ell_{1/2}$ 의사노름 페널티를 도입합니다. 이 페널티는 추정된 군집 비율이 희소해지도록 장려하여, 비최적 군집의 질량을 0 으로 설정합니다.
4. 최적화: 매개변수는 블록 좌표 하강 알고리즘을 사용하여 추정됩니다. 이는 다음을 번갈아 수행합니다:
   • 1 차 최적성 조건에서 유도된 폐쇄형 해를 사용하여 연결 행렬 $\Theta$ 업데이트.
   • 희소성 페널티를 선형화하고 결과적인 2 차 문제를 해결 (예: 프랭크-울프를 통해) 하는 주상 - 최소화 (MM) 알고리즘을 사용하여 수송 계획 $T$ 업데이트.

주요 기여

• 이론적 연결: 논문은 SBM 에서의 MLVI 가 엔트로피 정규화를 가진 반-완화 그로모프-워셔슈타인 투영으로 해석될 수 있음을 증명합니다.
• 일관성 결과: 저자들은 비정규화 srGW 추정량이 점근적 영역 ($N \to \infty$) 에서 진정한 SBM 연결 행렬과 잠재적 군집 할당을 모두 일관되게 복원함을 증명합니다.
• 자동 모델 선택: 희소성 촉진 페널티를 통합함으로써, 이 방법은 단일 최적화 단계에서 모델 매개변수의 동시 복원과 군집 수 선택을 가능하게 합니다. 이는 비용이 많이 드는 그리드 검색이나 탐욕적 휴리스틱의 필요성을 제거합니다.
• 알고리즘적 효율성: 제안된 솔버는 효율성을 위해 설계되었으며, 이론적 복잡도는 기울기 계산 ($O(N^2K + K^2N)$) 에 의해 지배되며, 최첨단 변분 추정량에 비해 CPU 에서 훨씬 빠름이 입증되었습니다.

결과
저자들은 3 가지 연결 체제 (연동형, 허브형, 비연동형) 하에서 베르누이 SBM 에서 생성된 합성 데이터에 대해 접근법을 평가했습니다.

• 클러스터링 성능: 음의 로그 우도 손실을 사용하는 제안된 srGW 추정량 (srGW-NLL) 은 조정된 랜 지수 (ARI) 측면에서 허브 및 비연동형 체제와 같이 다른 방법들의 구조적 가정이 위반되는 경우를 제외하고 루빈, 인포맵, 그리드, 변분 추정량 등 최첨단 기준선과 일관되게 성능을 초과하거나 이를 달성합니다.
• 모델 선택: 이 방법은 다양한 하이퍼파라미터 설정에서 진정한 군집 수 ($K^*$) 를 성공적으로 복원하며, 희소성 매개변수가 적절하게 조정될 때 성능이 평탄화됨을 보여줍니다.
• 효율성: srGW-NLL 방법은 주로 이러한 접근법에서 요구되는 반복적 모델 선택 루프를 우회하기 때문에 CPU 에서 변분 추정량 및 그리드 방법보다 1~2 차수 빠름이 보고되었습니다.

의의 및 주장
본 논문은 최적 수송과 확률적 블록 모델 간의 통일된 이론적 및 실용적 다리를 제공한다고 주장합니다. 그 주요 의의는 OT 기반 추정량이 매개변수 복원에 대해 일관될 뿐만 아니라 희소성 촉진을 통해 본질적 모델 선택을 수행할 수 있음을 입증하는 데 있습니다. 이는 군집 수 선택의 조합적 복잡성에 직면하는 전통적 우도 기반 방법들에 대한 계산 효율적인 대안을 제공합니다. 저자들은 이 작업을 군집 수가 알려지지 않고 그래프 구조가 복잡 (예: 허브 또는 비연동형 패턴 포함) 한 시나리오에서 더 견고하고 효율적인 그래프 분할을 향한 한 걸음으로 위치시킵니다. 그들은 점근적 일관성이 증명되었지만, 희소성 하이퍼파라미터의 조정은 향후 연구 영역으로 남아 있으며, 실제 세계 네트워크에서의 방법의 성능은 추가 연구의 주제임을 지적합니다.