Graph cluster randomization: network exposure to multiple universes

By Johan Ugander, Brian Karrer, Lars Backstrom, Jon M. Kleinberg. 2013

306 citations recorded by the source corpus.

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.

Subfields: Communication, Statistical and Nonlinear Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Communication

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Social Data: Biases, Methodological Pitfalls, and Ethical Boundaries (2019, background): “Alas, this assumption is often violated in the presence of network eﬀects, including common social features (e.g., hashtags, messaging, community support) that provide value through network usage (Ugander et al., 2013).”
The Econometrics of Randomized Experiments (2016, background): “Recently, Wager and Athey (2015) propose a modified version of the random forest algorithm that produces treatment effect estimates that can be shown to be asymptotically normal and centered on the true value of the treatment effect, and they propose a consistent estimator for the asymptotic varianc”
Elements of estimation theory for causal effects in the presence of network interference (2017, background): “With the rise of interest in social networks, many authors have proposed that observed network of interactions or relationships between units may inform how causal effects can be transmitted between units [Ugander et al., 2013, Eckles et al., 2014, Athey et al., 2015].”
Almost-Matching-Exactly for Treatment Effect Estimation under Network Interference (2020, background): “Some of this work makes explicit use of observed network structure to randomly assign treatment so as to reduce interference (Ugander et al., 2013; Toulis and Kao, 2013; Eckles et al., 2016, 2017; Jagadeesan et al., 2019).”
Estimating peer effects in networks with peer encouragement designs (2016, background): “Lasso (23) Fig.”
Handbook of Big Data (2016, background): “Combined pan/zoom based on focus rectangles is described in Section 6.4.3.”