Graph cluster randomization: network exposure to multiple universes

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. 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.

9 pages, 2 figures

References in corpus (1)

• Critical phenomena in heterogeneous k-core percolation

Cited by in corpus (13)

• Automatic Detection of Influential Actors in Disinformation Networks
• Interacting Regional Policies in Containing a Disease
• Peer Encouragement Designs in Causal Inference with Partial Interference and Identification of Local Average Network Effects
• Using Ego-Clusters to Measure Network Effects at LinkedIn
• Designing and Deploying Online Field Experiments
• Locally Estimating Core Numbers
• Estimating spillovers using imprecisely measured networks
• Exact P-values for Network Interference
• Long-term causal effects via behavioral game theory
• Feedback Shaping: A Modeling Approach to Nurture Content Creation
• Optimizing cluster-based randomized experiments under a monotonicity assumption
• A Method for Measuring Network Effects of One-to-One Communication Features in Online A/B Tests
• Analyzing two-stage experiments in the presence of interference