Design and analysis of bipartite experiments under a linear exposure-response model

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

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

Introduction

In the ecosystem of modern two-sided marketplaces—such as Amazon, Uber, or Airbnb—traditional A/B testing methodologies often fail. These environments are characterized by complex interactions where the units receiving treatment (diversion units, like products or drivers) differ from the units where outcomes are measured (outcome units, like customers or riders). This structure defines a bipartite experiment.

In such settings, the Stable Unit Treatment Value Assumption (SUTVA)—the bedrock of classical causal inference—is routinely violated. Because a single customer may be exposed to multiple treated products, the "interference" between units makes standard statistical tools unreliable. Harshaw et al. address this challenge by introducing a rigorous framework for point estimation and inference under a linear exposure-response model.

The Linear Exposure-Response Model

The authors base their work on the assumption that an outcome unit’s response is a linear function of its "exposure." Exposure is defined as a weighted sum of the treatment statuses of the outcome unit’s neighbors within the bipartite graph. This model allows for a more nuanced representation of interference than binary "treated vs. control" models, capturing the intensity of treatment effects across a network.

The Exposure Reweighted Linear (ERL) Estimator

To estimate the average total treatment effect (ATTE), the authors propose the Exposure Reweighted Linear (ERL) estimator.

Traditional approaches, such as the Horvitz-Thompson estimator, typically weight observations by the inverse probability of treatment. However, in dense networks, these probabilities can become extremely small, leading to "variance explosion." The ERL estimator avoids this by weighting observed outcomes based on the normalized distance of a unit’s realized exposure from its expected exposure. The paper proves that the ERL is:

  • Unbiased: It correctly centers on the true effect.
  • Consistent and Asymptotically Normal: As the network grows, the estimator converges to the true value and follows a normal distribution, provided the bipartite graph remains "sufficiently sparse."

Inference and Variance Estimation

A significant contribution of this research is the derivation of a novel, unbiased estimator for the variance of the ERL. In finite-population interference settings, unbiased variance estimation is generally considered impossible. However, the authors demonstrate that because exposures in a bipartite graph take on many intermediate values between 0 and 1 (rather than being strictly binary), valid inference becomes tractable. This allows researchers to construct reliable 95% confidence intervals for the first time in these complex, overlapping network settings.

Exposure-Design: Optimizing Experimental Layout

Beyond estimation, the paper introduces Exposure-Design, a cluster-based experimental design intended to maximize the precision of the ERL estimator.

The design utilizes a correlation clustering objective to group diversion units. The goal is to maximize the variance of individual exposures (ensuring a wide range of data points) while simultaneously minimizing the correlation between different units' exposures. To solve this optimization problem at scale, the authors employ a local search heuristic known as "wedge sampling," making the design computationally feasible for massive industrial graphs.

Empirical Evaluation

The researchers validated the ERL framework using both synthetic simulations and a massive real-world dataset:

  1. Synthetic Simulations: These tests confirmed the estimator's unbiasedness and the validity of the confidence intervals across various scenarios, including cases where the underlying response was non-linear.
  2. Amazon Product Review Dataset: Using a graph of 83 million reviews (121,000 customers and 9.8 million items), the authors simulated a marketplace experiment.

Key Results

  • Precision Gains: In the Amazon simulation, the ERL estimator combined with Exposure-Design achieved a Root Mean Squared Error (RMSE) approximately 10 times lower than standard Bernoulli (unit-level) randomization.
  • Robustness: The variance estimator produced 95% confidence intervals that maintained accurate coverage even in dense graphs that technically pushed the boundaries of the paper’s theoretical sparsity assumptions.
  • Scalability: The clustering heuristics proved efficient enough to handle graphs with millions of edges and nodes.

Limitations and Future Directions

While the ERL framework represents a major step forward, it relies on the assumption that the experimenter has perfect knowledge of the bipartite graph (the "exposure mapping"). In practice, these graphs are often estimated from historical data and may be subject to misspecification.

Future research directions include incorporating covariate adjustments to further reduce variance and extending the model to handle dynamic graphs that evolve during the course of an experiment. Despite these remaining challenges, the ERL estimator provides a robust foundation for causal inference in the increasingly interconnected world of 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. Finally, 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 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