Causal clustering: design of cluster experiments under network interference

기술 요약: 인과적 클러스터링: 네트워크 간섭 하에서의 클러스터 실험 설계

1. 문제 정의

본 논문은 알려진 네트워크를 통해 단위들이 상호작용하여 파급 효과(spillover effects)가 발생하는 환경에서 클러스터 실험을 설계하는 문제를 다룹니다. 이러한 환경에서는 표준적인 개별 단위 무작위 배정(Bernoulli designs)이 클러스터 간 노출로 인한 편향을 유발하여 전역 평균 처치 효과(Global Average Treatment Effect, GATE)를 식별하는 데 실패하는 경우가 많습니다. 반대로, 클러스터 무작위 배정은 이러한 편향을 제거하지만, 클러스터 내 할당의 상관관계와 클러스터 크기의 이질성으로 인해 분산을 증가시킵니다.

핵심 과제는 사전에 지정된 행정적 클러스터(예: 마을)나 표준적인 커뮤니티 탐지 알고리즘이 인과 추론에 최적이 아닐 수 있다는 점입니다. 이러한 방식은 너무 거칠어서(높은 분산 유발) 혹은 너무 세밀해서(관련 파급 효과를 포착하지 못해 편향 유발) 문제가 될 수 있습니다. 저자들은 클러스터링의 선택을 통계적 설계 문제로 프레임화합니다. 즉, GATE에 대한 차이-평균 추정량(difference-in-means estimator)의 최악의 경우 평균 제곱 오차(MSE)를 최소화하는 파티션(partition)을 선택하는 문제입니다.

2. 방법론 및 프레임워크

2.1 국소 점근적 프레임워크 (Local Asymptotic Framework)

저자들은 파급 효과가 "0에 국한되어 있으나(local to zero)" 추론에는 무시할 수 없는 수준인 상황을 설정하기 위해 국소 점근적 프레임워크를 공식화합니다.

• 가정 1 (1차 국소 간섭): 잠재적 결과(potential outcomes)는 개인의 처치와 그 이웃들의 처치에만 의존합니다.
• 가정 2 (유계성 및 립시츠 연속성): 잠재적 결과는 균등하게 유계(uniformly bounded)이며, 파급 효과의 크기는 매개변수 $\bar{\phi}_n$에 의해 제한됩니다. 구체적으로, 잠재적 결과의 변화는 처치된 이웃의 비율에 선형적이며, 그 기울기는 $\bar{\phi}_n$에 의해 제한됩니다.
• 가정 3 (파급 효과 국소 점근성): 최대 파급 효과의 크기와 최대 차수의 제곱의 곱이 유계입니다 ($\limsup \bar{\phi}_n N_{n,max}^2 \leq \epsilon$). 이는 온라인 플랫폼과 같이 효과는 작지만 경제적으로 유의미한 시나리오에서도 적용 가능하게 합니다.

2.2 편향과 분산의 특성 규명

본 논문은 주어진 클러스터링 $C_n$ 하에서 차이-평균 추정량 $\hat{\tau}_n(C_n)$의 편향과 분산에 대한 날카로운 최악의 경우 특성을 도출합니다.

• 최악의 경우 편향: 편향은 "클러스터 간 연결성(between-cluster connectedness)"에 의해 결정되며, 이는 할당된 클러스터 외부에 있는 개인의 이웃 비율의 평균($b_n(C_n)$)으로 정의됩니다. 최악의 경우 편향은 $\bar{\phi}_n b_n(C_n)$에 비례합니다.
• 최악의 경우 분산: 국소 점근적 프레임워크 하에서, 분산은 클러스터링 설계에 의해 유도된 클러스터 내 상관관계에 의해 점근적으로 결정됩니다. 이는 결과 범위 $\bar{\psi}$에 의해 스케일링된 클러스터 크기의 제곱합($\sum n_k^2$)에 비례합니다.
• 최악의 경우 MSE: 이를 결합하면, 최소화해야 할 목적 함수는 다음과 같습니다:
  $$B^*_n(C_n, \lambda) = \bar{\psi} \frac{1}{n^2} \sum_{k=1}^{K_n} n_k^2 + \lambda \bar{\phi}_n^2 b_n(C_n)^2$$
  여기서 $\lambda$는 사용자가 지정하는 가중치(일반적으로 MSE의 경우 1)입니다.

2.3 최적화 알고리즘

저자들은 최적의 클러스터링을 찾는 것이 새로운 페널티가 부여된 최소 컷(penalized min-cut) 문제로 환원됨을 보여줍니다.

• 재구성: 이 문제는 반정부호(semi-definite) 제약 조건이 있는 트레이스 최적화 프로그램(trace-optimization program)으로 재구성됩니다.
• 볼록 완화 (Convex Relaxation): 정확한 문제는 조합론적(combinatorial)이므로, 저자들은 반정부호 프로그래밍(SDP) 완화를 제안합니다. 목적 함수는 클러스터 행렬의 트레이스(분산 성분)와 정규화된 컷의 제곱(편향 성분)의 가중 합을 최소화하는 것을 포함합니다.
• 라운딩 (Rounding): SDP 솔루션의 고유 벡터(eigenvectors)에 K-means 클러스터링을 적용하여 실행 가능한 클러스터링을 얻습니다.
• 알고리즘 1: 이 절차는 클러스터 수($K$)와 편향-분산 트레이드오프를 조절하는 보정 매개변수 $\xi_n = (\lambda \bar{\phi}_n^2 / \bar{\psi})^{-1}$에 대해 반복 수행됩니다. 이 알고리즘은 최적의 클러스터링에 대한 근사 성능 인증(approximation bound)을 제공합니다.

3. 주요 기여

1. 클러스터링을 위한 의사결정 이론적 프레임워크: 기존 문헌이 클러스터링을 주어진 것으로 취급하거나 커뮤니티 탐지에 집중하는 것과 달리, 본 논문은 GATE에 대한 최악의 경우 MSE를 최소화하려는 인과적 목적으로부터 직접 클러스터링을 도출합니다.
2. 날카로운 최악의 경우 특성 규명: 네트워크 간섭 하에서의 편향과 분산에 대한 명시적이고 날카로운 경계값을 제공하며, 편향은 클러스터 간 노출에, 분산은 클러스터 크기 분산에 의존함을 보여줍니다.
3. 새로운 최적화 문제: 저자들은 최적의 클러스터링이 클러스터 크기에 의한 분산 성분까지 내부화하는 페널티 부여된 최소 컷 문제를 해결함을 확인했습니다. 이는 표준적인 스펙트럴 클러스터링(spectral clustering)이나 정규화된 컷(normalized cuts)이 클러스터 크기에 의한 분산 성분을 고려하지 않는 것과 다릅니다.
4. 실용적인 설계 규칙:
   • Bernoulli vs. Cluster: 파급 효과의 크기와 결과 분산의 비율, 그리고 클러스터 수를 기반으로 클러스터 설계가 Bernoulli 설계보다 우월한지를 결정하는 규칙을 도출합니다.
   • 알려지지 않은 파급 효과: 최악의 경우 MSE 비율에 대해 오라클(oracle) 대비 최악의 회한(regret)을 최적화하는 미니맥스 회한(minimax regret) 접근 방식을 사용하여 알려지지 않은 파급 효과 크기를 다루는 프레임워크를 확장합니다.
5. 경험적 검증: 제안된 방법론을 독특한 Facebook 네트워크 데이터와 중국 농촌 지역의 현장 실험(Cai et al., 2015)에 적용했습니다.
   • Facebook 데이터에서 제안된 방법은 기존 클러스터링 알고리즘(Louvain, Balanced Partitioning)의 순위를 매겼으며, 많은 클러스터를 가진 Louvain이 종종 가장 좋은 성능을 보임을 발견했습니다.
   • 현장 실험에서 이 방법은 다양한 신호 대 잡음비(SNR) 환경에서 행정적 마을 경계 및 표준 클러스터링 알고리즘(Spectral, $\epsilon$-net)보다 우수한 대안적 파티션을 구축합니다.

4. 결과 및 의의

본 논문은 제안된 "인과적 클러스터링(Causal Clustering)" 방법이 네트워크 간섭이 존재하는 상황에서 실험 설계를 위한 견고한 절차를 제공한다고 주장합니다.

• 성능: 1차 간섭 설정으로 보정된 시뮬레이션에서, 인과적 클러스터링은 0.0% - 0.2%의 매우 낮은 회한을 달려 높은 회한(최대 50% 이상)을 보이는 벤치마크 모델들(Spectral clustering, Louvain 등)을 크게 압도했습니다.
• 강건성: 결과가 이웃의 처치뿐만 아니라 이웃의 결과에도 의존하는 오설정된 전역 간섭 모델(misspecified global interference models) 하에서도, 이 방법은 경쟁력을 유지하며 다른 방법들이 보이는 심각한 성능 저하를 피합니다.
• 실용적 유용성: 이 프레임워크를 통해 연구자들은 편향과 분산 사이의 트레이드오프를 명시적으로 정량화할 수 있습니다. 또한 행정적 경계나 휴리스틱한 커뮤니티 탐지에 의존하는 대신, 데이터에 기반하여 클러스터의 수와 구조를 선택할 수 있는 방법을 제공합니다.

저자들은 이 접근 방식이 파급 효과는 작지만 무시할 수 없으며, 규모 있는 정책의 총 효과를 추정하는 것이 목표인 온라인 플랫폼(예: Meta/Facebook) 및 현장 실험에 특히 유용하다고 강조합니다. 이 방법은 그래프 클러스터링 문헌과 인과 추론 사이의 간극을 메우며, 복잡한 설계 문제에 대한 계산 가능한(SDP를 통한) 솔루션을 제공합니다.