Maximum entropy based testing in network models: ERGMs and constrained optimization

1. 문제 정의 (Problem Statement)

통계적 네트워크 분석에서 관측된 네트워크 데이터가 특정 확률 모델 (예: Erdős-Rényi 모델, ERGM 등) 에서 생성되었는지 확인하거나, 두 개의 다른 네트워크 샘플이 동일한 분포에서 왔는지 판단하는 것은 핵심적인 통계적 추론 문제입니다.

• 적합도 검정 (Goodness-of-fit): 주어진 네트워크가 특정 모수 (예: 에지 확률 $p$ 또는 모티프 기대값) 를 가진 모델에서 생성되었는지 검정 ($H_0: \theta = \theta_0$ vs $H_1: \theta \neq \theta_0$).
• 두 표본 검정 (Two-sample test): 두 개의 독립적인 네트워크 샘플이 동일한 생성 모델에서 왔는지 검정 ($H_0: P_1 = P_2$ vs $H_1: P_1 \neq P_2$).

기존의 방법들은 주로 모티프 카운트, 인접 행렬, 또는 스펙트럼 특성을 직접적으로 사용하는 반면, 이 논문은 제약 조건 하의 엔트로피 최대화 문제를 통해 새로운 접근법을 제시합니다.

2. 방법론 (Methodology)

저자들의 핵심 아이디어는 관측된 모티프 카운트의 경험적 분포에 대해 제약 조건을 부과하여 엔트로피를 최대화하는 것입니다.

2.1. 제약 조건 하의 엔트로피 최대화

주어진 $n$개의 네트워크 샘플 $G_1, \dots, G_n$과 모티프 $H$에 대해, 가중치 벡터 $w = (w_1, \dots, w_n)$를 찾아 다음을 최대화합니다:
$$\max_{w} -\sum_{i=1}^n w_i \log w_i$$
제약 조건:

1. $\sum_{i=1}^n w_i = 1$ (확률의 합)
2. $\sum_{i=1}^n w_i h(G_i) = 0$ (중심화된 모티프 카운트의 기대값이 0 이어야 함, 여기서 $h(G) = T(H, G) - E_{H_0}[T(H, G)]$)

이 최적화 문제의 **라그랑주 승수 (Lagrange Multiplier, $\hat{\lambda}_n$)**가 검정 통계량의 핵심이 됩니다. 라그랑주 승수는 다음 방정식의 근 (root) 으로 정의됩니다:
$$\sum_{i=1}^n h(G_i) e^{-\hat{\lambda}_n h(G_i)} = 0$$
(밀집 네트워크의 경우 스케일링 인자가 추가됨)

2.2. 검정 통계량

• Null 가정 하의 점근적 성질: 귀무가설이 참일 때, 최적화된 라그랑주 승수 $\hat{\lambda}_n$은 특정 상수 (보통 0) 로 수렴하며, 적절히 정규화되면 **점근적 정규성 (Asymptotic Normality)**을 가집니다.
• 대립가설 하의 성질: 대립가설이 참일 때, $\hat{\lambda}_n$은 0 에서 벗어나며, 그 편차가 검정력을 결정합니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

이 논문은 네트워크 크기가 고정된 경우와 샘플 크기에 따라 네트워크 크기가 증가하는 경우 (희소 및 밀집 regime) 를 모두 다루며, 각 경우에 대한 일관된 이론적 체계를 구축했습니다.

3.1. 고정 크기 네트워크 (Fixed Size Networks)

• 가정: 네트워크의 정점 수 $m$이 고정되어 있고, 샘플 수 $n$만 증가합니다.
• 결과:
  • 라그랑주 승수 $\hat{\lambda}_n$의 **일관성 (Consistency)**을 증명했습니다.
  • $\sqrt{n}(\hat{\lambda}_n - \lambda^*)$가 정규분포로 수렴함을 보였습니다.
  • 이를 바탕으로 적합도 검정을 구성할 수 있음을 입증했습니다.

3.2. 증가하는 크기 네트워크: 희소 영역 (Sparse Regime)

• 모델: Erdős-Rényi 모델 $G(m_n, p_n)$을 가정하며, $m_n \to \infty$이고 $p_n \to 0$입니다.
• 특징: 모티프 카운트가 포아송 분포로 수렴하는 영역을 다룹니다.
• 결과:
  • 중심극한정리 (CLT) 를 적용하여 지수적으로 기울어진 (exponentially tilted) 모티프 카운트의 점근적 정규성을 유도했습니다.
  • 이를 통해 $\hat{\lambda}_n$의 점근적 정규성을 증명하고, 적합도 검정과 두 표본 검정을 구성했습니다.
  • 특히, 두 표본의 크기가 다를 때 ($n_1 \neq n_2$) 도 검정 통계량의 분포를 유도했습니다.

3.3. 증가하는 크기 네트워크: 밀집 영역 (Dense Regime)

• 모델: Exponential Random Graph Models (ERGM) 의 아임계 (subcritical) 영역과 밀집 Erdős-Rényi 모델을 다룹니다 ($p = \Theta(1)$).
• 기술적 도약:
  • 밀집 영역에서는 모티프 카운트의 점근적 정규성이 성립하지 않을 수 있어, **비선형 대편차 이론 (Nonlinear Large Deviation Theory)**과 그래폰 (Graphon) 이론을 활용했습니다.
  • 최적화 문제의 목적 함수가 **자유 에너지 (Free Energy)**의 변분 문제 (Variational Problem) 로 수렴함을 보였습니다.
  • 로그 - 합 - 지수 (Log-sum-exp) 근사 기법을 사용하여 경험적 최적점의 수렴 속도를 분석했습니다.
• 결과:
  • $\hat{\lambda}_n$이 변분 문제의 해로 수렴함을 증명했습니다.
  • 밀집 Erdős-Rényi 모델의 경우, 에지 확률 $p$에 대한 두 표본 검정을 구성했습니다.

4. 기술적 핵심 (Technical Highlights)

1. 라그랑주 승수의 통계적 해석: 기존 경제학 등에서 제약 조건 하의 MLE 에 쓰이던 라그랑주 승수 검정 (Score test) 과 유사하지만, 네트워크 모델의 고유한 특성 (정점 수 증가, 비선형성) 을 반영하여 최대 엔트로피 원리에 기반한 새로운 검정 통계량으로 재해석했습니다.
2. 비선형 대편차 이론의 적용: 밀집 네트워크 분석을 위해 Chatterjee 와 Dembo 의 비선형 대편차 이론을 차용하여, 복잡한 네트워크 구조 하에서의 최적점 수렴을 rigorously 증명했습니다.
3. 일관된 프레임워크: 고정 크기, 희소, 밀집이라는 세 가지 다른 네트워크 성장 regime 에 대해 동일한 엔트로피 기반 프레임워크를 적용하여 일관된 검정 절차를 제시했습니다.

5. 의의 및 의의 (Significance)

• 통계적 네트워크 분석의 새로운 패러다임: 기존의 모티프 카운트나 인접 행렬 기반 검정에서 벗어나, 최대 엔트로피 원리를 통계적 추론 (가설 검정) 에 직접 적용한 최초의 체계적인 시도 중 하나입니다.
• 이론적 엄밀성: 네트워크 크기가 무한대로 발산하는 현대적인 설정 (Sparse/Dense regimes) 에서 검정 통계량의 점근적 성질 (일관성, 정규성) 을 수학적으로 엄밀하게 증명했습니다.
• 실용적 확장성: 이 프레임워크는 ERGM, Erdős-Rényi 모델뿐만 아니라 다른 네트워크 모델에도 적용 가능한 일반적인 전략을 제시합니다. 또한, 라그랑주 승수를 활용함으로써 모델의 적합도를 평가하는 새로운 도구를 제공합니다.
• 경제학 및 통계학과의 연결: 라그랑주 승수 검정이 경제학의 제약 조건 하의 MLE 에서 어떻게 작동하는지 설명하며, 이를 네트워크 데이터에 성공적으로 확장하여 학제간 연결고리를 강화했습니다.

결론

이 논문은 최대 엔트로피 원리와 라그랑주 승수를 결합하여 통계적 네트워크 모델의 적합도 및 동질성 검정을 위한 강력하고 일관된 이론적 기반을 마련했습니다. 고정 크기부터 희소 및 밀집 네트워크에 이르기까지 다양한 설정에서 검정 통계량의 점근적 성질을 규명함으로써, 대규모 네트워크 데이터 분석을 위한 새로운 표준을 제시합니다.