# Randomized Graph Cluster Randomization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2020.

## Built on by (most cited first, 14 of 14)

- [Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2402.01845/) (2024)
- [Causal Message Passing for Experiments with Unknown and General Network Interference](https://mlsanity.com/paper/2311.08340/) (2023)
- [Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2503.07555/) (2025)
- [Graph Machine Learning based Doubly Robust Estimator for Network Causal Effects](https://mlsanity.com/paper/2403.11332/) (2024)
- [Higher-Order Causal Message Passing for Experimentation with Complex Interference](https://mlsanity.com/paper/2411.00945/) (2024)
- [Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?](https://mlsanity.com/paper/2507.11891/) (2025)
- [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)
- [Cascade-based Randomization for Inferring Causal Effects under Diffusion Interference](https://mlsanity.com/paper/2405.12340/) (2024)
- [Differences-in-Neighbors for Network Interference in Experiments](https://mlsanity.com/paper/2503.02271/) (2025)
- [Choosing Online Experiment Designs under Interference in Ads, Recommendations, and Member-Experience Systems](https://mlsanity.com/paper/2605.25290/) (2026)
- [Journey to the Centre of Cluster: Harnessing Interior Nodes for A/B Testing under Network Interference](https://mlsanity.com/paper/2602.04457/) (2026)
- [Causal Inference for Sequential Settings under Interference and Latent Confounding](https://mlsanity.com/paper/2607.14940/) (2026)

## Abstract (arXiv)

The global average treatment effect (GATE) is a primary quantity of interest in the study of causal inference under network interference. With a correctly specified exposure model of the interference, the Horvitz-Thompson (HT) and H'ajek estimators of the GATE are unbiased and consistent, respectively, yet known to exhibit extreme variance under many designs and in many settings of interest. With a fixed clustering of the interference graph, graph cluster randomization (GCR) designs have been shown to greatly reduce variance compared to node-level random assignment, but even so the variance is still often prohibitively large. In this work we propose a randomized version of the GCR design, descriptively named randomized graph cluster randomization (RGCR), which uses a random clustering rather than a single fixed clustering. By considering an ensemble of many different cluster assignments, this design avoids a key problem with GCR where a given node is sometimes "lucky" or "unlucky" in a given clustering. We propose two randomized graph decomposition algorithms for use with RGCR, randomized 3-net and 1-hop-max, adapted from prior work on multiway graph cut problems. When integrating over their own randomness, these algorithms furnish network exposure probabilities that can be estimated efficiently. We develop upper bounds on the variance of the HT estimator of the GATE under assumptions on the metric structure of the interference graph. Where the best known variance upper bound for the HT estimator under a GCR design is exponential in the parameters of the metric structure, we give a comparable variance upper bound under RGCR that is instead polynomial in the same parameters. We provide extensive simulations comparing RGCR and GCR designs, observing substantial reductions in the mean squared error for both HT and H'ajek estimators of the GATE in a variety of settings.