JDS Journal of Data Science 1683-86021680-743X1680-743X School of Statistics, Renmin University of China JDS1112 10.6339/23-JDS1112 Statistical Data Science Network A/B Testing: Nonparametric Statistical Significance Test Based on Cluster-Level Permutation ShangHongweihongwei.shang@walmart.com1∗ ShiXiaolin2 JiangBai3 Walmart Global Tech, Search Dept, Sunnyvale, CA, US Snap Inc, Santa Monica, CA, US Citadel Securities, Chicago, IL, US Corresponding author. Email: hongwei.shang@walmart.com. 20232572023213523537 Supplementary Material

The zip supplementary material file contains the Python scripts for generating graph data, computing ATE estimators, estimating p-value via permutation tests, and generating figures in this paper.

14720231472023 2023 The Author(s). Published by the School of Statistics and the Center for Applied Statistics, Renmin University of China.2023 Open access article under the CC BY license.

A/B testing is widely used for comparing two versions of a product and evaluating new proposed product features. It is of great importance for decision-making and has been applied as a golden standard in the IT industry. It is essentially a form of two-sample statistical hypothesis testing. Average treatment effect (ATE) and the corresponding p-value can be obtained under certain assumptions. One key assumption in traditional A/B testing is the stable-unit-treatment-value assumption (SUTVA): there is no interference among different units. It means that the observation on one unit is unaffected by the particular assignment of treatments to the other units. Nonetheless, interference is very common in social network settings where people communicate and spread information to their neighbors. Therefore, the SUTVA assumption is violated. Analysis ignoring this network effect will lead to biased estimation of ATE. Most existing works focus mainly on the design of experiment and data analysis in order to produce estimators with good performance in regards to bias and variance. Little attention has been paid to the calculation of p-value. We work on the calculation of p-value for the ATE estimator in network A/B tests. After a brief review of existing research methods on design of experiment based on graph cluster randomization and different ATE estimation methods, we propose a permutation method for calculating p-value based on permutation test at the cluster level. The effectiveness of the method against that based on individual-level permutation is validated in a simulation study mimicking realistic settings.

 design of experiments graph cluster randomization p-value References Aronow PM, Samii C (2012). Estimating average causal effects under general interference. In: Summer Meeting of the Society for Political Methodology, University of North Carolina, Chapel Hill, July, 19–21, Citeseer. Backstrom L, Kleinberg J (2011). Network bucket testing. In: Proceedings of the 20th International Conference on World Wide Web, WWW’11, 615–624. ACM, New York, NY, USA. Eckles D, Karrer B, Ugander J (2014). Design and analysis of experiments in networks: Reducing bias from interference. arXiv preprint: https://arxiv.org/abs/1404.7530. Gui H, Xu Y, Bhasin A, Han J (2015). Network A/B testing: From sampling to estimation. In: Proceedings of the 24th International Conference on World Wide Web, WWW’15, 399–409. ACM, New York, NY, USA. Gupta A, Krauthgamer R, Lee JR (2003). Bounded geometries, fractals, and low-distortion embeddings. In: Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, 534–543. IEEE. Jiang B, Shi X, Shang H, Geng Z, Glass A (2016). A Framework for Network A/B Test. arXiv preprint: https://arxiv.org/abs/1610.07670. Karrer B, Shi L, Bhole M, Goldman M, Palmer T, Gelman C, et al. (2021). Network experimentation at scale. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 3106–3116. Karypis G, Kumar V (1998). Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1): 96–129. https://doi.org/10.1006/jpdc.1997.1404 Katzir L, Liberty E, Somekh O (2012). Framework and algorithms for network bucket testing. In: Proceedings of the 21st International Conference on World Wide Web, WWW’12, 1029–1036. ACM, New York, NY, USA. Kohavi R, Deng A, Frasca B, Longbotham R, Walker T, Xu Y (2012). Trustworthy online controlled experiments: Five puzzling outcomes explained. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 786–794. ACM. Kohavi R, Deng A, Frasca B, Walker T, Xu Y, Pohlmann N (2013). Online controlled experiments at large scale. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1168–1176. Kohavi R, Deng A, Longbotham R, Xu Y (2014). Seven rules of thumb for web site experimenters. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’14, 1857–1866. ACM, New York, NY, USA. Kohavi R, Longbotham R, Walker T (2010). Online experiments: Practical lessons. Computer, 43(9): 82–85. https://doi.org/10.1109/MC.2010.264 Kohavi R, Tang D, Xu Y (2020). Trustworthy Online Controlled Experiments: A Practical Guide to A/B Testing. Cambridge University Press. Liu Y, Zhou Y, Li P, Hu F (2022). Adaptive A/B test on networks with cluster structures. In: International Conference on Artificial Intelligence and Statistics, 10836–10851. PMLR. Maris E, Oostenveld R (2007). Nonparametric statistical testing of EEG-and MEG-data. Journal of Neuroscience Methods, 164(1): 177–190. https://doi.org/10.1016/j.jneumeth.2007.03.024 Nishimura J, Ugander J (2013). Restreaming graph partitioning: simple versatile algorithms for advanced balancing. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1106–1114. Rubin DB (1986). Comment: Which ifs have causal answers? Journal of the American Statistical Association, 81(396): 961–962. Saveski M, Pouget-Abadie J, Saint-Jacques G, Duan W, Ghosh S, Xu Y, et al. (2017). Detecting network effects: Randomizing over randomized experiments. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1027–1035. Ugander J, Backstrom L (2013). Balanced label propagation for partitioning massive graphs. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, 507–516. Ugander J, Karrer B, Backstrom L, Kleinberg J (2013). Graph cluster randomization: Network exposure to multiple universes. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD’13, 329–337. ACM, New York, NY, USA. Ugander J, Yin H (2023). Randomized graph cluster randomization. Journal of Causal Inference, 11(1): 20220014. https://doi.org/10.1515/jci-2022-0014 Watts DJ, Strogatz SH (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684): 440–442. https://doi.org/10.1038/30918