Network A/B Testing: Nonparametric Statistical Significance Test Based on Cluster-Level Permutation

Shang, Hongwei; Shi, Xiaolin; Jiang, Bai

doi:10.6339/23-JDS1112

Journal of Data Science

Network A/B Testing: Nonparametric Statistical Significance Test Based on Cluster-Level Permutation

Volume 21, Issue 3 (2023): Special Issue: Advances in Network Data Science, pp. 523–537

Hongwei Shang Xiaolin Shi Bai Jiang

https://doi.org/10.6339/23-JDS1112

Pub. online: 25 July 2023 Type: Statistical Data Science

Open Access

Received
14 July 2023

Accepted
14 July 2023

Published
25 July 2023

Abstract

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.

Supplementary material

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.

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

2023 The Author(s). Published by the School of Statistics and the Center for Applied Statistics, Renmin University of China.

Open access article under the CC BY license.

Keywords

design of experiments graph cluster randomization p-value

Metrics

since February 2021

392 Article info views	0 Full article views
159 PDF downloads	46 XML downloads

RSS

Authors

Abstract

Supplementary material

References

Export citation

Copy and paste formatted citation

Download citation in file