Exact Likelihood Inference for Snowball-Sampled Erd\H{o}s-Rényi Networks

기술 요약: 스노볼 샘플링된 에르되시-레니 네트워크에 대한 정확한 가능도 추론

문제 정의
스노볼 샘플링과 같은 링크 추적 설계(link-tracing designs)를 통해 수집된 네트워크 데이터는 근본적인 추론상의 과제를 안고 있다. 즉, 샘플을 선택하는 메커니즘이 분석하고자 하는 바로 그 네트워크 구조(구체적으로는 에지 밀도)에 의존한다는 점이다. 관찰된 부분 그래프(subgraph)를 샘플링 설계를 무시한 채 완전하고 대표적인 모집단 네트워크의 실현체로 취급하는 것은 체계적인 편향을 초래한다. 일반적인 네트워크 샘플링 솔루션은 가능한 네트워크 완성을 위한 난해한 조합적 합(combinatorial sums)을 요구하지만(Handcock and Gile, 210), 본 논문은 에르되시-레니(Erdős–Rényi, ER) 모집단으로부터 추출된 $r$-웨이브(wave) 스노볼 샘플링의 특정 사례를 다룬다. 저자들은 에지 확률 $\pi$에 대한 편향 없는 추정과 유효한 신뢰 구간을 가능하게 하기 위해, 샘플링 메커니즘을 고려한 정확한 가능도(exact likelihood)를 도출하는 것을 목표로 한다. 이는 샘플이 전체 네트워크의 극히 적은 부분만을 포함하는 경우에도 유효하다.

방법론
본 논문은 ER 모델 하에서 관찰된 웨이브 집합($V^{(0)}, \dots, V^{(r)}$)과 유도된 인접 행렬($Y^{(r)}$)의 결합 확률에 대한 폐쇄형 유도(closed-form derivation)를 개발한다.

1. 가능도의 인수분해: 결합 확률은 웨이브 집합의 주변 확률(marginal probability)과 해당 집합이 주어졌을 때의 인접 행렬의 조건부 확률로 인수분해된다.

   • 웨이브 집합: 특정 웨이브 크기가 관찰될 확률은 모집 과정을 일련의 베르누이 샘플링 설계로 취급함으로써 도출된다. 첫 번째 웨이브의 경우, 포함 여부는 확률 $\pi$인 단순 베르누이 시행이다. 이후의 웨이브($k \ge 2$)의 경우, 특정 정점은 이전 웨이브와 적어도 하나의 에지를 가질 때 포함되므로, 포함 성공 확률은 $1 - (1-\pi)^{n_{k-1}}$이 된다.
   • 인접 행렬: 인접 행렬의 조건부 분포는 샘플링 설계에 의해 제약된다. 인접하지 않은 웨이브 사이의 에지는 반드시 0이어야 한다. 인접한 웨이브 사이의 에지는 모든 웨이브 $k$의 정점이 웨이브 $k-1$에 대해 적어도 하나의 에지를 가져야 한다는 조건을 만족해야 한다. 동일한 웨이브 내의 에지는 제약이 없는 베르누이 시행으로 남는다.

2. 곡선 지수 가족(Curved Exponential Family): 결과적인 결합 확률 질량 함수는 매개변수 $\pi$에 대해 곡선 지수 가족에 속함을 보여준다. 이 가능도는 다음의 두 가지 스칼라 양을 통해서만 데이터에 의존한다:

   • $|E^{(r)}|$: 관찰된 에지의 수.
   • $T(n)$: "제약된" 정점 쌍의 총합을 나타내는 충분 통계량으로, 웨이브 내의 쌍, 인접한 웨이브 사이의 쌍, 인접하지 않은 웨이브 사이의 쌍, 그리고 미샘플링된 노드와 누적된 이전 웨이브 크기 사이의 곱의 합으로 정의된다.

3. 추정 및 추론:

   • 최대 가능도 추정량 (MLE): 정확한 MLE인 $\hat{\pi} = |E^{(r)}| / T(n)$이 도출된다. 이 추정량은 관찰된 부분 그래프 내의 전체 가능한 쌍으로 나누는 표준 추정량과 달리, 미샘플링된 노드와 제외 메커니즘에 대한 정보를 통합함으로써 교정한다.
   • 신뢰 구간: 샘플링 분포의 점근적 거동의 복잡성(이는 $N$과 $\pi$ 사이의 관계에 크게 의존함) 때문에, 저자들은 검정 역전(test inversion)을 통해 신뢰 구간을 구축한다. 저자들은 다양한 후보 $\pi$ 값 하에서의 MLE의 샘플링 분포를 근사하기 위해 중요도 샘플링(importance sampling)을 결합한 몬테카를로 시뮬레이션을 활용하며, 이를 통해 점근적 정규성에 의존하지 않고 보수적인 신뢰 집합을 구축할 수 있게 한다.

주요 결과

• 정확한 가능도 도출: 본 논문은 ER 네트워크로부터의 $r$-웨이브 스노볼 샘플에 대한 가능도의 첫 번째 폐쇄형 표현식을 제공하여, Crane(2018)이 제기한 특정 미해결 문제를 해결한다.
• 편향 감소: 시뮬레이션 연구는 샘플링 설계를 무시하는 표준 추정량이 특히 희소한 네트워크나 웨이브 수가 적은 경우(예: 1-웨이브 샘플에서 $\pi$를 1~2 차수만큼 과대평가함) 심각한 상향 편향을 보임을 입증한다. 반면, 제안된 스노볼 교정 MLE는 샘플이 네트워크의 0.1%만을 차지하는 경우에도 모든 테스트된 시나리오에서 근사적으로 편향되지 않은 상태를 유지한다.
• 유효한 추론: 검정 역전을 통해 구축된 몬테카를로 신뢰 구간은 다양한 에지 확률과 웨이브 수에 대해 명목 수준(예: 95%)의 커버리지를 몬테카를로 오차 범위 내에서 달성한다. 이 구간은 표준 상대 가능도 브래킷(relative likelihood brackets)을 기반으로 한 것보다 실질적으로 더 좁다.
• 충분성: 쌍 $(|E^{(r)}|, T(n))$이 $\pi$에 대한 최소 충분 통계량으로 식별되었으며, 이는 제안된 추정량이 샘플에 포함된 모든 정보를 활용함을 보장한다.

의의 및 주장
저자들은 본 연구가 기초적인 에르되시-레니 모델에 대한 선택 편향 문제의 다루기 쉽고 정확한 솔루션을 제공한다고 주장한다. 일부 조건부 ERGM 접근법처럼 샘플링 메커니즘을 무시하거나 조건화하여 제거하는 대신, 이를 명시적으로 모델링함으로써 미샘플링된 부분에 대한 정보를 회복한다.

본 논문은 다음과 같은 일반적인 원칙을 제시한다: 다이아드(dyad, 에지)에 대해 가능도가 인수분해되는 네트워크 모델의 경우, 복잡한 주변화(marginalization) 대신 표적화된 저비용 교정을 통해 스노볼 샘플링 메커니즘을 설명할 수 있다. 이는 샘플링된 네트워크를 완전한 모집단 그래프로 취급하는 추정량들에 대한 원칙적인 대안을 제공한다. 저자들은 현재의 기여를 ER 모델로 제한하며, 내생적 에고 선택(endogenous ego selection)이나 최종 웨이브의 부분적 관측 가능성은 향-연구가 필요한 확장 영역으로 논의한다. 다만 후자의 경우, 해당 에지들을 미샘플링된 것으로 취급하는 것과 형식적으로 동일함을 보여준다.