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."
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.
- 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."
- 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.
- The Reduction: The paper proves that maximizing this variance is mathematically equivalent to correlation clustering on a "folded" version of the bipartite graph.
- 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.
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