Variance Reduction in Bipartite Experiments through Correlation Clustering

Jean Pouget-Abadie, Kevin Aydin, Warren Schudy, Kay Brodersen, Vahab S. MirrokniNeurIPS 2019 · OpenReview

When running A/B tests on platforms like Amazon or Uber, treating one item can "leak" effects to others, a phenomenon known as interference. This biases the results. This paper introduces a novel method to design these "bipartite experiments" by clustering randomization units to maximize the variance of treatment exposure. By proving this objective is equivalent to the well-known correlation clustering problem, the authors provide a scalable way to significantly increase the statistical power of experiments.

The Challenge of Bipartite Interference

In a standard A/B test, we assume the "unit of randomization" (who gets the treatment) and the "unit of analysis" (whose behavior we measure) are the same. However, in many real-world systems, these are linked by a bipartite graph.

Imagine an online retailer wanting to test a discount. If they randomize by user, different users might see different prices for the same item, creating a bad user experience. If they randomize by item, they face interference: a discount on a "Nike shoe" might steal demand from an "Adidas shoe" (substitute goods). Standard causal theory fails here because the outcome for one unit depends on the treatment status of its "peers."

Comparison of interference settings in experiments

The challenge is designing an experiment that minimizes this interference bias while maintaining enough statistical power to actually detect an effect. Previous approaches used "balanced partitioning" to create clusters of equal size, but these often lead to "underpowered" experiments where everyone receives roughly the same amount of "blurred" treatment.

Maximizing Variance via Correlation Clustering

The authors propose a shift in perspective: instead of just trying to "cut" the graph evenly, we should aim to maximize the empirical variance of treatment exposure.

  1. Linear Treatment Exposure: They assume an outcome unit’s (e.g., a user) response is determined by a weighted proportion of treated diversion units (e.g., items) in their "exposure set."
  2. The Objective: They seek a clustering of diversion units that maximizes the expected variance of this exposure across all outcome units. High variance is good because it means we observe users across a wide spectrum of treatment "dosages," making it easier to estimate the true dose-response curve.
  3. The Reduction: The paper proves that maximizing this variance is mathematically equivalent to correlation clustering on a "folded" version of the bipartite graph.
  4. The Algorithm: Since correlation clustering is NP-hard, they develop a scalable heuristic. They first "fold" the bipartite graph into an item-only graph with positive and negative edge weights. Then, they use a local search algorithm to maximize the agreement of these weights.

Unlike K-means or METIS, correlation clustering doesn't require the researcher to pre-specify the number of clusters ($K$). The algorithm naturally finds the optimal number of clusters based on the graph's topology.

Experimental Validation and Results

The authors evaluate their method using a publicly available Amazon user-item review graph containing 7.7 million edges connecting 2.4 million items and 34,000 users. This graph serves as the "ground truth" for simulating bipartite experiments and comparing clustering strategies.

Mean Squared Error comparison of clustering methods

The results demonstrate significant improvements:

  • Higher Exposure Variance: The correlation clustering approach achieved nearly 70% of the theoretical maximum possible variance for treatment exposure, significantly outperforming baselines like METIS (balanced partitioning) and LINE.
  • Reduced Error: In simulations with varying levels of noise ($\sigma$), the proposed method consistently yielded a lower Mean Squared Error (MSE) for the average treatment effect estimator.
  • Scalability: The local search heuristic proved efficient enough to handle the millions of nodes in the Amazon dataset, making it practical for industrial-scale A/B testing platforms.

Limitations and Future Directions

While powerful, the method relies on a "linear treatment exposure" assumption. Real-world interference, such as auction dynamics, can be highly non-linear. Furthermore, because the underlying problem is NP-hard, the algorithm is a heuristic without theoretical guarantees of reaching the global optimum. Finally, the method is sensitive to model misspecification; if the true relationship between exposure and outcome differs fundamentally from the assumed model, power gains may diminish. Future work could adapt this framework for non-linear exposure models or settings where the bipartite graph is partially unknown.

Summary updated

Abstract

Causal inference in randomized experiments typically assumes that the units of randomization and the units of analysis are one and the same. In some applications, however, these two roles are played by distinct entities linked by a bipartite graph. The key challenge in such bipartite settings is how to avoid interference bias, which would typically arise if we simply randomized the treatment at the level of analysis units. One effective way of minimizing interference bias in standard experiments is through cluster randomization, but this design has not been studied in the bipartite setting where conventional clustering schemes can lead to poorly powered experiments. This paper introduces a novel clustering objective and a corresponding algorithm that partitions a bipartite graph so as to maximize the statistical power of a bipartite experiment on that graph. Whereas previous work relied on balanced partitioning, our formulation suggests the use of a correlation clustering objective. We use a publicly-available graph of Amazon user-item reviews to validate our solution and illustrate how it substantially increases the statistical power in bipartite experiments.
BibTeX
@inproceedings{pougetabadie2019variance,
  author = {Jean Pouget-Abadie and Kevin Aydin and Warren Schudy and Kay Brodersen and Vahab S. Mirrokni},
  title = {{Variance Reduction in Bipartite Experiments through Correlation Clustering}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=yK_ofUrWeo},
}
Figure