1. Home
  2. Issues
  3. Volume 21, Issue 3 (2023): Special Issue: Advances in Network Data Science
  4. Network A/B Testing: Nonparametric Stati ...

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
Pub. online: 25 July 2023      Type: Statistical Data Science      Open accessOpen 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

PDF XML
PDF XML

Copyright
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
562

Article info
views

230

PDF
downloads


Share


RSS