Cascade-Based Randomization with Balanced Covariates via Rerandomization = 재무작위화를 통한 공변량 균형 기반 캐스케이드 기반 무작위화

다국어 초록 (Multilingual Abstract)

Randomized experiments on networks are complicated by interference: treating one unit can affect others through multi-hop spillovers. Cascade-Based Randomization (CasBR) generates treatment assignments according to the Independent Cascade (IC) model and yields design-unbiased estimation of the Total Treatment Effect (TTE), but it does not explicitly enforce covariate balance or restrict treated-control connections that create unallowable peer effects. This thesis proposes Rerandomized Cascade-Based Randomization (ReCasBR), which conditions CasBR on joint balance constraints: covariate imbalance measured by the Mahalanobis distance M(Z) and cross-group connectivity measured by the number of treated-control edges B(Z). ReCasBR repeatedly samples CasBR assignments until M(Z) ≤ a and B(Z) ≤ b, with (a,b) set by empirical CasBR quantiles. Because both the base design and acceptance rule are label-symmetric, rerandomization preserves CasBR’s design-unbiasedness for TTE. Across synthetic graphs, ReCasBR consistently tightens joint balance relative to complete randomization, cluster-based randomization, and CasBR. On real networks, ReCasBR reduces cross-group edges and the need for bystander post-processing, and achieves lower TTE estimation error than competing designs.

국문 초록 (Abstract)

네트워크 실험에서는 간섭(interference)으로 인해 한 개체의 처리가 다중 홉 전파를 통해 다른 개체의 결과에 영향을 미칠 수 있다. Cascade-Based Randomization(CasBR)은 독립 전파(Independent Cascade, IC) 모형에 부합하는 확산 인지형 설계로서 전체 처리 효과(Total Treatment Effect, TTE)에 대한 설계-불편성(design-unbiasedness)을 보장한다. 그러나 CasBR은 사전 공변량 균형을 명시적으로 보장하지 않으며, 처리군-대조군 간 연결을 직접 제어하지 않아 잔여 스필오버로 인한 허용 불가능한 동료 효과(unallowable peer effects)가 발생할 수 있다.
본 논문은 CasBR에 재무작위화(rerandomization)를 결합한 Rerandomized Cascade-Based Randomization(ReCasBR)을 제안한다. ReCasBR은 CasBR로부터 생성된 할당 중 (i) 마할라노비스 거리 기반 공변량 불균형과 (ii) 처리군-대조군 교차 엣지 수가 각각 임계값 이하인 경우만을 수용한다. 또한 수용 규칙의 레이블 대칭성을 통해 ReCasBR이 TTE에 대한 설계-불편성을 유지함을 이론적으로 보인다.
합성 및 실제 네트워크(Facebook, ArXiv ca-GrQc) 실험에서 ReCasBR은 공변량 균형과 교차 집단 노출을 동시에 개선하고, bystander 후처리로 인한 제외 비율을 줄이며, 기존 설계 대비 더 낮은 TTE 추정 오차(RMSE)를 달성한다. 이는 확산 인지형 무작위화에 재무작위화를 통합하는 접근이 네트워크 간섭 하에서 이론적으로 타당하고 실무적으로도 유효함을 시사한다.

목차 (Table of Contents)

• Abstract i
• Contents ii
• Chapter 1 Introduction 1
• 1.1 Motivation 1
• 1.2 Need for Interference-Aware Experimental Design 2
• 1.3 Existing Approaches and Their Limitations 2
• 1.4 A Need for Improved Design 4
• 1.5 Contributions 4
• 1.6 Research Goals 5
• Chapter 2 Related Works 6
• 2.1 Causal Inference Under Interference 7
• 2.2 Cluster-Based Randomization (CBR) 8
• 2.3 Graph-Based Exposure Designs 9
• 2.4 Exposure-Based Methods 9
• 2.5 Diffusion-Aware Randomization: CasBR 9
• 2.6 Covariate-Balanced Rerandomization 11
• 2.7 Summary and Positioning of This Work 12
• Chapter 3 Preliminaries 14
• 3.1 Notation and Graph Structure 14
• 3.2 Potential Outcomes Under Interference 15
• 3.3 Total Treatment Effect (TTE) 16
• 3.4 Independent Cascade (IC) Diffusion Model 16
• 3.5 Cluster-Based Randomization (CBR) 17
• 3.6 Cascade-Based Randomization (CasBR) 18
• 3.7 Summary 19
• Chapter 4 Method 20
• 4.1 Problem Setup 20
• 4.2 Covariate- and Structure-Aware Rerandomization 23
• 4.3 Algorithm: Rerandomized CasBR (ReCasBR) 26
• 4.4 Theoretical Justification 27
• Chapter 5 Experiments 29
• 5.1 Synthetic Experiments 30
• 5.1.1 Setup 30
• 5.1.2 Results 33
• 5.2 Real-World Experiments 43
• 5.2.1 Results 45
• Chapter 6 Conclusion 55
• 요약 60
• Appendix A Synthetic Graph Details 61
• A.1 Additional Results for Balance and Estimation Error (Q2) 61
• Appendix B Additional Experimental Results 64
• B.1 RMSE vs. Number of Assignments (Single-Run Results) 64