Source-linked AI summary
Graph cluster randomization: network exposure to multiple universes
Johan Ugander, Brian Karrer, Lars Backstrom, Jon Kleinberg
TL;DR
Social interference makes ordinary A/B testing unsuitable because users’ outcomes can depend on neighbors’ treatment assignments. The paper introduces network exposure and graph cluster randomization to estimate all-treated versus all-control effects, obtaining unbiased estimates with computable exposure probabilities and variance bounds. Proper clustering can reduce degree-dependent variance from exponential behavior to linear behavior on restricted-growth graphs.
Problem
Ordinary A/B testing assumes no spillover between users, but social interactions make it difficult to estimate the average effect between all-treated and all-control universes.
Method
The paper defines network exposure conditions and uses graph cluster randomization with inverse exposure-probability weighting to estimate treatment effects under interference.
Results
Proper clustering yields asymptotically small variance, including O(1/n) for bounded-size clusters and degree-linear variance for a neighborhood-based algorithm on restricted-growth graphs.
Takeaways & Limitations
Graph cluster randomization can support concurrent causal experiments with multiple exposure conditions and achieve exponentially lower variance than unsuitable clustering when its graph conditions apply.
Takeaways & Limitations
Unbiasedness depends on correctly specifying exposure conditions; misspecified conditions can introduce bias, and the variance guarantees are proved for particular graph classes or clustering conditions.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
Social interference breaks the parallel-universe interpretation of ordinary A/B tests, so the paper develops network exposure and graph cluster randomization for estimating treatment effects on social graphs. It derives unbiased estimation with computable exposure probabilities and shows that appropriate clustering can substantially control variance.
- Motivation: Social interactions violate SUTVA because one user’s treatment can affect another user’s response, contaminating ordinary A/B-test comparisons.Users assigned to different treatment and control conditions no longer behave as if they were independently sampled from two parallel universes.
- Motivation: The target is the average treatment effect between the all-treated and all-control universes, although no two users can truly occupy opposing universes simultaneously.The paper formalizes treatment assignments with potential outcomes and defines τ between z=1 and z′=0.
- Network exposure: Network exposure identifies assignments under which a user’s response matches the response that would occur when everyone receives treatment or control.Exposure conditions are modeling choices, such as requiring all neighbors or a fraction of neighbors to receive treatment.
- Graph cluster randomization: Graph cluster randomization partitions the graph into clusters, randomizes at cluster level, computes exposure probabilities exactly, and yields an unbiased inverse-probability-weighted estimator.The estimator applies when the relevant exposure probabilities can be explicitly computed.
- Variance: Bounded-size clusters give variance O(1/n), but careless clustering can produce variance exponential in vertex degrees.This creates a clustering-design trade-off: asymptotic smallness in graph size does not prevent practically large degree dependence.
- Restricted-growth graphs: Restricted-growth graphs admit neighborhood-based clustering with estimator variance bounded linearly in degree, including graphs with exponentially growing neighborhoods.The condition |B_{r+1}(v)| ≤ κ|B_r(v)| limits how many clusters can intersect a vertex’s neighborhood.
- Contribution: The framework extends causal-inference and network-bucket-testing work by supporting exposure models and simultaneous consideration of multiple exposure conditions.The paper presents this capability as necessary for concurrent causal experimentation on large social graphs.
2. NETWORK EXPOSURE MODELS
The paper models network exposure as assignment conditions that reproduce treatment or control outcomes, using local neighborhood and stronger core- or component-based conditions. Because these exposure conditions are modeling choices, misspecification can bias estimated effects.
- Exposure conditions: Network exposure groups assignment vectors that are indistinguishable from an all-treatment or all-control universe for an individual.Exposure conditions σ1_i and σ0_i contain assignments producing the same potential outcomes as everyone treated or everyone controlled.
- Exposure models: The exposure model partitions possible assignment vectors into exposure conditions, but the experimenter need only specify conditions relevant to estimating the treatment and control universes.The framework also considers global recursive dependence through core-based conditions.
- Modeling assumptions: Incorrectly chosen exposure conditions can bias the average treatment-effect estimate when observed responses do not correspond to the all-treatment and all-control outcomes.The framework notes that allowing small outcome discrepancies may trade some bias for lower variance.
- Neighborhood exposure: Full neighborhood exposure requires an individual and all neighbors to receive the same treatment condition.Absolute k- and fractional q-neighborhood exposure relax this requirement by requiring at least k neighbors or a q fraction of neighbors to receive it.
- Core exposure: Core and component exposure are stricter than corresponding neighborhood exposure because their assignment sets are contained within the neighborhood-exposure sets.Recursive exposure can be characterized using k-core or heterogeneous k-core structure.
3. RANDOMIZATION AND ESTIMATION
The paper combines cluster-level randomization with exposure probabilities and inverse-probability estimation to handle interference. Cluster assignments improve exposure opportunities, while variance remains controlled under bounded-degree and bounded-cluster-size conditions.
- Estimation: The Horvitz-Thompson estimator is unbiased when exposure probabilities are positive and the exposure conditions are correctly specified.Treatment and control exposure probabilities serve as inverse weights correcting allocation bias.
- Exposure probabilities: Under independent vertex randomization, full-neighborhood exposure probabilities are p^(d_i+1) for treatment and (1-p)^(d_i+1) for control.These probabilities can become exponentially small as vertex degree grows, increasing Horvitz-Thompson variance.
- Cluster randomization: Graph cluster randomization assigns connected vertices together more often than independent randomization, increasing expected network exposure while increasing correlations.Clusters are independently randomized after partitioning the graph.
- Exposure probabilities: Absolute and fractional neighborhood exposure probabilities are exactly computable by a dynamic program with runtime O(d_max^s).The same computation can derive all nested threshold probabilities and the exposure distribution for each individual.
- Exposure probabilities: Exact computation for k-core and fractional q-core exposure is unclear, but neighborhood-exposure containment provides useful upper bounds on core probabilities.These bounds can identify vertices whose exposure probabilities are already problematic under neighborhood exposure.
- Estimator variance: If maximum degree and cluster size are O(1), the Horvitz-Thompson variance for several neighborhood exposures is O(1/n).For general schemes, variance can grow exponentially with degree; restricted-growth clustering instead targets linear degree dependence.
4. VARIANCE ON RESTRICTED-GROWTH GRAPHS
Restricted-growth graphs admit clusterings that keep Horvitz–Thompson estimator variance linear in degree, contrasting with exponential lower bounds under vertex randomization. The analysis uses neighborhood exposure, cycle examples, and 3-net clustering to establish this variance control.
- Restricted-growth condition: Restricted-growth graphs satisfy |B_{r+1}(v)| ≤ κ|B_r(v)|, controlling neighborhood expansion beyond the first hop.The condition is designed to include low-diameter graphs whose neighborhoods may initially grow rapidly.
- Cycle examples: For cycle graphs, asymptotic variance is minimized when clusters contain c = 3 vertices, matching each vertex’s neighborhood size.For kth powers of cycles, the optimal cluster size scales approximately linearly with degree, and variance at the optimum scales linearly in k.
- 3-net clustering: A 3-net clustering limits each vertex neighborhood to at most κ^3 intersecting clusters, enabling variance bounds linear in degree.For arbitrary restricted-growth graphs, a weaker constant bound based on κ still preserves linear degree dependence.
- Variance comparison: Vertex-level randomization yields an exponential-in-degree lower bound for the variance under full neighborhood exposure.The bound applies to graphs with n vertices and shows that even one high-degree vertex can substantially increase variance.
- Variance bounds: Under full, q-fractional, or k-absolute neighborhood exposure, 3-net cluster randomization gives an estimator variance upper bounded by a function linear in degree.The resulting estimator is unbiased and has variance O(1/n) with bounded cluster sizes, while avoiding the exponential dependence caused by less careful clustering.
5. CONCLUSION
The paper develops graph cluster randomization for A/B testing with network spillovers, where ordinary individual-level randomization is inadequate. It concludes that appropriate clustering can reduce variance substantially, while several optimization and modeling questions remain open.
- Conclusion: Graph cluster randomization extends causal inference for interference by providing exposure models and randomization schemes suited to large social graphs.The method is applicable with arbitrary community-detection or graph-partitioning algorithms, although variance guarantees are not provided generally.
- Conclusion: Appropriate clustering can reduce estimator variance exponentially in the vertex degrees when treatment effects spill over through social-network links.The strongest variance guarantees are established for restricted-growth graphs.
- Open directions: A computationally tractable objective for minimizing Horvitz–Thompson estimator variance remains an open research direction.The paper also raises questions about A/A variance minimization and its relationship to A/B testing variance.
- Open directions: The framework currently uses discrete network exposure, leaving continuous exposure responses and bias from exposure-model misspecification for future work.The paper specifically suggests responses depending continuously on the number of exposed neighbors.