Graph cluster randomization

TLDR

A/B testing estimates average treatment effects but is poorly suited for experiments with social interference, where treatment effects spill over along a social network. This study introduces a graph‑clustering methodology to estimate average treatment effects under social interference. By characterizing graph‑theoretic exposure conditions, the authors develop a graph‑cluster randomization algorithm that efficiently computes vertex exposure probabilities, which are then used as inverse weights in a Horvitz‑Thompson estimator to yield unbiased effect estimates.

Abstract

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.