# Graph cluster randomization: network exposure to multiple universes

arXiv: https://arxiv.org/abs/1305.6979 · HTML: https://mlsanity.com/paper/1305.6979/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2013.

## Built on by (most cited first, 30 of 42)

- [Learning Causal Effects on Hypergraphs](https://mlsanity.com/paper/2207.04049/) (2022)
- [Markovian Interference in Experiments](https://mlsanity.com/paper/2206.02371/) (2022)
- [Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2402.01845/) (2024)
- [Multi-Armed Bandits with Network Interference](https://mlsanity.com/paper/2405.18621/) (2024)
- [Sample Constrained Treatment Effect Estimation](https://mlsanity.com/paper/2210.06594/) (2022)
- [Causal Message Passing for Experiments with Unknown and General Network Interference](https://mlsanity.com/paper/2311.08340/) (2023)
- [Unraveling the Interplay between Carryover Effects and Reward Autocorrelations in Switchback Experiments](https://mlsanity.com/paper/2403.17285/) (2024)
- [Causal Lifting and Link Prediction](https://mlsanity.com/paper/2302.01198/) (2023)
- [Inferring Individual Direct Causal Effects Under Heterogeneous Peer Influence](https://mlsanity.com/paper/2305.17479/) (2023)
- [Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2503.07555/) (2025)
- [Balancing Interference and Correlation in Spatial Experimental Designs: A Causal Graph Cut Approach](https://mlsanity.com/paper/2505.20130/) (2025)
- [Graph Machine Learning based Doubly Robust Estimator for Network Causal Effects](https://mlsanity.com/paper/2403.11332/) (2024)
- [A Two-Part Machine Learning Approach to Characterizing Network Interference in A/B Testing](https://mlsanity.com/paper/2308.09790/) (2023)
- [Tackling Interference Induced by Data Training Loops in A/B Tests: A Weighted Training Approach](https://mlsanity.com/paper/2310.17496/) (2023)
- [Clustered Switchback Designs for Experimentation Under Spatio-temporal Interference](https://mlsanity.com/paper/2312.15574/) (2023)
- [Uplift Modeling Under Limited Supervision](https://mlsanity.com/paper/2403.19289/) (2024)
- [Simulating and Experimenting with Social Media Mobilization Using LLM Agents](https://mlsanity.com/paper/2510.26494/) (2025)
- [Network Synthetic Interventions: A Causal Framework for Panel Data Under Network Interference](https://mlsanity.com/paper/2210.11355/) (2022)
- [Cascade-based Randomization for Inferring Causal Effects under Diffusion Interference](https://mlsanity.com/paper/2405.12340/) (2024)
- [Causal Deepsets for Off-policy Evaluation under Spatial or Spatio-temporal Interferences](https://mlsanity.com/paper/2407.17910/) (2024)
- [Learning Exposure Mapping Functions for Inferring Heterogeneous Peer Effects](https://mlsanity.com/paper/2503.01722/) (2025)
- [A Two-armed Bandit Framework for A/B Testing](https://mlsanity.com/paper/2507.18118/) (2025)
- [Feedback Shaping: A Modeling Approach to Nurture Content Creation](https://mlsanity.com/paper/2106.11312/) (2021)
- [Treatment Effect Estimation with Observational Network Data using Machine Learning](https://mlsanity.com/paper/2206.14591/) (2022)
- [Contagion Effect Estimation Using Proximal Embeddings](https://mlsanity.com/paper/2306.02479/) (2023)
- [Model-Based Inference and Experimental Design for Interference Using Partial Network Data](https://mlsanity.com/paper/2406.11940/) (2024)
- [Differences-in-Neighbors for Network Interference in Experiments](https://mlsanity.com/paper/2503.02271/) (2025)
- [Bayesian Estimation of Causal Effects Using Proxies of a Latent Interference Network](https://mlsanity.com/paper/2505.08395/) (2025)
- [On Evolution-Based Models for Experimentation Under Interference](https://mlsanity.com/paper/2511.21675/) (2025)
- [Designing Time Series Experiments in A/B Testing with Transformer Reinforcement Learning](https://mlsanity.com/paper/2602.01853/) (2026)

## Abstract (arXiv)

A/B testing is a standard approach for evaluating the effect of online experiments; the goal is to estimate the `average treatment effect' of a new feature or condition by exposing a sample of the overall population to it. A drawback with A/B testing is that it is poorly suited for experiments involving social interference, when the treatment of individuals spills over to neighboring individuals along an underlying social network. In this work, we propose a novel methodology using graph clustering to analyze average treatment effects under social interference. To begin, we characterize graph-theoretic conditions under which individuals can be considered to be `network exposed' to an experiment. We then show how graph cluster randomization admits an efficient exact algorithm to compute the probabilities for each vertex being network exposed under several of these exposure conditions. Using these probabilities as inverse weights, a Horvitz-Thompson estimator can then provide an effect estimate that is unbiased, provided that the exposure model has been properly specified. Given an estimator that is unbiased, we focus on minimizing the variance. First, we develop simple sufficient conditions for the variance of the estimator to be asymptotically small in n, the size of the graph. However, for general randomization schemes, this variance can be lower bounded by an exponential function of the degrees of a graph. In contrast, we show that if a graph satisfies a restricted-growth condition on the growth rate of neighborhoods, then there exists a natural clustering algorithm, based on vertex neighborhoods, for which the variance of the estimator can be upper bounded by a linear function of the degrees. Thus we show that proper cluster randomization can lead to exponentially lower estimator variance when experimentally measuring average treatment effects under interference.