TL;DR
This paper introduces GeoCUTS, a novel algorithm for creating geographically clustered regions for running randomized experiments on large-scale web services. By intelligently clustering regions based on user movement patterns, GeoCUTS aims to minimize interference between experimental groups and improve the reliability of experimental results, outperforming traditional grid-based and hand-designed approaches.
What Problem Does This Paper Address?
Large online services frequently use A/B testing to improve their products. A common approach is to run experiments on geographical regions to avoid the complexities of tracking individual users across devices and browsers. However, this method faces a significant challenge: user mobility. When users travel between regions, they can be exposed to different experimental treatments, violating the Stable Unit Treatment Value Assumption (SUTVA) and leading to biased results. Existing methods for geographic clustering often ignore actual user movement patterns, leading to interference between treatment and control groups. This paper addresses the need for a data-driven approach to geographic clustering that accounts for user mobility to create more reliable experimental units.
Methods
The core of the paper is the GeoCUTS algorithm, which operates in two phases:
- Phase 1: Graph Building:
- Location Discretization: Geographic locations are rounded to a grid of discrete points.
- Node Weights: Grid points (nodes) are assigned weights based on the number of user visits, using a square root normalization to mitigate the impact of a few highly active users.
- Edge Weights: Edges between nodes represent user movement, weighted by the geometric mean of user visits to connected locations, again with normalization.
- Sparsity: Edges are pruned if the geographical distance between nodes is too large, reducing graph size and focusing on local interactions.
- Coverage: Gaps in data density are filled by creating new nodes with small weights and low-weight edges between nearby nodes to ensure geographic plausibility.
- Normalization: Logarithmic normalization is applied to node and edge weights to handle the long-tail distribution of traffic.
- Phase 2: Graph Clustering:
- Balanced Partitioning: The algorithm aims to find clusters of roughly equal size while minimizing the "cut" (edges crossing between clusters). This is an NP-hard problem, so GeoCUTS uses a distributed heuristic.
- Natural Cuts: A key technique involves computing "natural cuts" around seed nodes. This is achieved by performing a breadth-first search (BFS) to identify a core region, contracting it, and then finding a minimum cut in the remaining graph.
- Distributed Implementation: The algorithm leverages MapReduce and distributed hash tables for parallel processing of graph contraction, connected components, and seed selection (using Hilbert curves for better distribution).
- In-Memory Merging: A final stage contracts the graph further in memory to produce the final clusters.
The paper also introduces two metrics for evaluating cluster quality:
- Q-metric: Measures interference, with a higher value indicating less interference. A Q-metric of 1 means perfect isolation.
- B-metric: Measures balance, with a value of 0 indicating perfect balance.
Datasets
The authors evaluated their algorithm using a massive dataset of 1% of Google Search queries over 28 days. This dataset consists of anonymized browser cookies, each associated with approximate locations of issued search queries. They created two types of datasets for analysis:
- Highly Mobile Cookies: Cookies that issued queries in at least two different grid cells.
- Highly Active Cookies: Cookies that issued queries on more than 10 out of 28 days.
They also compared their results against:
- Nielsen's DMAs (Designated Market Areas): A set of hand-designed geographic regions for the US.
- Simple Grid Clustering: An automatic clustering method that divides the area into a uniform grid.
- Linear Embedding and Hilbert Curve Partitions: Other state-of-the-art automatic clustering methods.
Key Insights and Ideas
- User Mobility is Key: The paper strongly emphasizes that ignoring user movement patterns is a critical flaw in traditional geographic clustering for experiments. GeoCUTS's core innovation is to explicitly model and leverage this mobility.
- Bipartite Graph Structure: The problem is framed around a bipartite graph of users and regions, which is then transformed into an interference graph between regions. This allows for a more nuanced understanding of how user movement impacts experimental outcomes.
- Q-metric as a Novel Interference Measure: The introduction of the Q-metric provides a principled way to quantify interference in a bipartite experimental setting, extending existing graph-cut metrics.
- Trade-off Between Interference and Balance: The paper highlights the inherent trade-off between minimizing interference (high Q-metric) and ensuring balanced clusters (low B-metric). GeoCUTS aims to optimize this trade-off.
- Data-Driven Regions Outperform Hand-Designed Ones: Empirical results show that GeoCUTS can achieve comparable or better performance than hand-designed regions like DMAs, without requiring manual effort and being generalizable to any region.
Key Results
- Improved Q-metric: GeoCUTS consistently achieved higher Q-metrics (indicating less interference) compared to baseline grid clustering across various datasets (US, France, highly active, highly mobile).
- Comparable to DMAs: For the US, GeoCUTS performed comparably to Nielsen's DMAs in terms of the Q-metric, demonstrating its effectiveness against established, hand-crafted regions.
- Better Balance for Mobile Users: While GeoCUTS performed comparably to other methods in balance (B-metric) for highly active users, it showed a slight improvement for highly mobile users, who pose a greater challenge.
- Superior Cut Size: GeoCUTS produced better cut sizes (a measure of partitioning quality) compared to DMA, grid, Linear Embedding, and Hilbert curve partitions on US data.
- Normalization Matters: Logarithmic normalization of node and edge weights was found to be critical for achieving good performance, balancing interference and balance.
Limitations and Future Work
- Dataset Specificity: The experiments were conducted on Google Search query data. While this is a rich source of movement information, results might vary with different types of user activity or data sources.
- Grid Granularity: The choice of grid cell size (coarseness) involves a trade-off between Q-metric and B-metric. The paper suggests that 0.25 degrees offers a good balance, but optimal coarseness might be application-dependent.
- Future Work: The authors suggest that the ideal number of clusters is experiment-dependent and recommend evaluating covariate imbalance and simulating user responses to determine optimal experimental design. They also mention that while their algorithm is distributed, further optimizations might be possible. The paper also notes that their approach is primarily focused on geographic graphs, and extending it to other network structures could be a future direction.
Summary updated