Design and Analysis of Bipartite Experiments under a Linear Exposure-Response Model

Christopher Harshaw, Fredrik Sävje, David D. Eisenstat, Vahab Mirrokni, Jean Pouget-Abadie

Abstract

In two-sided marketplaces, traditional causal inference often fails because treatment assigned to one set of units (e.g., products) affects outcomes measured on another set (e.g., customers). This paper addresses the challenge of estimating the average total treatment effect (ATTE) in such bipartite experiments. We introduce the Exposure Reweighted Linear (ERL) estimator and demonstrate that it is unbiased, consistent, and asymptotically normal under a linear exposure-response model, provided the underlying bipartite graph is sufficiently sparse. Furthermore, we provide a consistent variance estimator for valid inference and propose "Exposure-Design," a cluster-based experimental design that optimizes the distribution of exposure to maximize precision.

Introduction

In standard A/B testing, the Stable Unit Treatment Value Assumption (SUTVA) posits that the treatment status of one unit does not affect the outcomes of others. However, in complex ecosystems like Uber, Airbnb, or Amazon, this assumption is frequently violated. When an experimenter randomizes items (diversion units) but measures the behavior of users (outcome units), the resulting "interference" makes traditional estimators biased.

Because users interact with multiple items, their exposure to a treatment is rarely binary; instead, it exists on a gradient. This paper provides a rigorous statistical framework for navigating these bipartite experimental structures using a linear exposure-response model.

The Linear Exposure-Response Framework

The authors model the outcome of a unit as a linear function of its exposure. Exposure is defined as the weighted proportion of treated items a user interacts with. This framework allows for a more nuanced understanding of treatment effects than binary models, capturing how varying levels of intensity in treatment influence user behavior.

The Exposure Reweighted Linear (ERL) Estimator

The core contribution of this research is the Exposure Reweighted Linear (ERL) estimator. The ERL estimator functions by reweighting observed outcomes based on the deviation of a unit's actual exposure from its expected exposure. Specifically, if a user receives a level of exposure that is significantly higher or lower than the mean due to the random assignment of items, their outcome is given more weight. This approach ensures that the estimator remains unbiased while accounting for the complex connectivity of the bipartite graph.

Statistical Inference and Variance

Historically, a major hurdle in bipartite experiments has been the "Inference Gap." Most existing methods could not provide valid confidence intervals for complex graphs without assuming the graph consisted of isolated components. The authors derive the first provably unbiased and consistent estimator for the variance of the ERL point estimator. They demonstrate that as long as the bipartite graph is "sufficiently sparse"—meaning no single item dominates the network's connectivity—the ERL estimator is asymptotically normal, allowing for reliable p-values and confidence intervals.

Exposure-Design: Optimizing for Precision

Standard randomization (such as Bernoulli trials for every item) often leads to "mushy" data, where most users receive roughly the same average exposure. This lack of variation makes it difficult to detect a clear treatment effect.

To solve this, the authors propose "Exposure-Design," a cluster-based randomization strategy. By grouping items into clusters and randomizing at the cluster level, the design maximizes the variance of individual exposures (ensuring some users see high treatment and others see very little) while minimizing the covariance between users. The authors show that finding the optimal design is a variation of the correlation clustering problem, which can be solved efficiently using local search heuristics.

Empirical Evaluation: The Amazon Product Review Graph

The framework was tested using a massive real-world dataset from Amazon, consisting of 83 million reviews across 9.8 million items and 121,000 customers. By simulating outcomes on this actual graph structure, the authors compared the ERL estimator and Exposure-Design against a known ground truth.

Key findings include:

  • Unbiasedness: The ERL estimator centered exactly on the true Average Total Treatment Effect (ATTE).
  • Precision: Exposure-Design achieved a Root Mean Square Error (RMSE) significantly lower than simple unit-level randomization.
  • Coverage: The proposed variance estimator produced 95% confidence intervals that accurately covered the true value approximately 95% of the time.
  • Robustness: Theorem 6.1 in the paper demonstrates that even if the underlying response is non-linear, the ERL estimator still captures the best linear approximation of the treatment effect.

Discussion and Limitations

While this framework represents a significant advancement, certain constraints remain. The theoretical guarantees for asymptotic normality depend on graph sparsity; in extremely dense marketplaces where every unit is connected to nearly every other unit, these guarantees may weaken. Additionally, the model assumes the experimenter has perfect knowledge of the bipartite graph weights, which in practice are often estimated from historical data. Finally, the model focuses on interference through exposure mappings rather than direct outcome-to-outcome interference (e.g., social contagion).

By moving bipartite experiments from heuristic-based methods to a rigorous statistical framework, this work provides a vital toolkit for data scientists managing large-scale digital marketplaces.

Summary updated

Abstract

A bipartite experiment consists of one set of units being assigned treatments and another set of units for which we measure outcomes. The two sets of units are connected by a bipartite graph, governing how the treated units can affect the outcome units. In this paper, we consider estimation of the average total treatment effect in the bipartite experimental framework under a linear exposure-response model. We introduce the Exposure Reweighted Linear (ERL) estimator, and show that the estimator is unbiased, consistent and asymptotically normal, provided that the bipartite graph is sufficiently sparse. To facilitate inference, we introduce an unbiased and consistent estimator of the variance of the ERL point estimator. In addition, we introduce a cluster-based design, Exposure-Design, that uses heuristics to increase the precision of the ERL estimator by realizing a desirable exposure distribution.
BibTeX
@inproceedings{harshaw2022design,
  author = {Christopher Harshaw and Fredrik Sävje and David D. Eisenstat and Vahab Mirrokni and Jean Pouget-Abadie},
  title = {{Design and Analysis of Bipartite Experiments under a Linear Exposure-Response Model}},
  booktitle = {EC},
  year = {2022},
  doi = {10.1145/3490486.3538269},
}
Figure