{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T21:50:36Z","timestamp":1791323436850,"version":"4.3.1"},"reference-count":53,"publisher":"Institute of Mathematical Statistics","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2026,10,1]]},"abstract":"<jats:p>In this paper, we study the problem of testing the equality of two multivariate distributions. One class of tests used for this purpose utilizes geometric graphs constructed using interpoint distances. So far, the asymptotic theory of these tests applies only to graphs, which fall under the stabilizing graphs framework of Penrose and Yukich (Ann. Appl. Probab. 13 (2003) 277\u2013303). We study the case of the K-nearest neighbors graph where K=kN increases with the sample size, which does not fall under the stabilizing graphs framework. Our main result gives detection thresholds for this test in parametrized families when kN=o(N1\/4), thus extending the family of graphs where the theoretical behavior is known. We propose a 2-sided version of the test, which removes an exponent gap that plagues the 1-sided test. Our result also shows that increasing the number of nearest neighbors improves the power of the test. This provides a theoretical justification for using denser graphs in testing the equality of two distributions.<\/jats:p>","DOI":"10.1214\/26-aos2657","type":"journal-article","created":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T12:54:14Z","timestamp":1790945654000},"page":"2560-2585","source":"Crossref","is-referenced-by-count":0,"title":["Power properties of the two sample test based on the nearest neighbors graph"],"prefix":"10.1214","volume":"54","author":[{"given":"Rahul Raphael","family":"Kanekar","sequence":"first","affiliation":[{"name":"Department of Statistics, Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"38","doi-asserted-by":"publisher","unstructured":"<small>Penrose, M. D.<\/small> and <small>Yukich, J. E.<\/small> (2003). Weak laws of large numbers in geometric probability. <i>Ann. Appl. Probab.<\/i> <b>13<\/b> 277\u2013303.","DOI":"10.1214\/aoap\/1042765669"},{"key":"37","doi-asserted-by":"publisher","unstructured":"<small>Penrose, M. D.<\/small> and <small>Yukich, J. E.<\/small> (2001). Central limit theorems for some graphs in computational geometry. <i>Ann. Appl. Probab.<\/i> <b>11<\/b> 1005\u20131041.","DOI":"10.1214\/aoap\/1015345393"},{"key":"48","doi-asserted-by":"publisher","unstructured":"<small>Sz\u00e9kely, G. J.<\/small> and <small>Rizzo, M. L.<\/small> (2013). Energy statistics: A class of statistics based on distances. <i>J. Statist. Plann. Inference<\/i> <b>143<\/b> 1249\u20131272.","DOI":"10.1016\/j.jspi.2013.03.018"},{"key":"13","doi-asserted-by":"publisher","unstructured":"<small>CHEN, H.<\/small> and <small>ZHANG, N.<\/small> (2015). Graph-based change-point detection. <i>Ann. Statist.<\/i> <b>43<\/b> 139\u2013176.","DOI":"10.1214\/14-AOS1269"},{"key":"1","doi-asserted-by":"publisher","unstructured":"<small>ALDOUS, D.<\/small> and <small>STEELE, J. M.<\/small> (1992). Asymptotics for Euclidean minimal spanning trees on random points. <i>Probab. Theory Related Fields<\/i> <b>92<\/b> 247\u2013258.","DOI":"10.1007\/BF01194923"},{"key":"39","doi-asserted-by":"publisher","unstructured":"<small>PENROSE, M. D.<\/small> and <small>YUKICH, J. E.<\/small> (2005). Normal approximation in geometric probability. In <i>Stein\u2019s Method and Applications<\/i>. <i>Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap.<\/i> <b>5<\/b> 37\u201358. Singapore Univ. Press, Singapore.","DOI":"10.1142\/9789812567673_0003"},{"key":"49","unstructured":"<small>SZ\u00c9KELY, G. J.<\/small>, <small>RIZZO, M. L.<\/small> et al. (2004). Testing for equal distributions in high dimension. <i>InterStat<\/i> <b>5<\/b> 1249\u20131272."},{"key":"4","doi-asserted-by":"publisher","unstructured":"<small>BARINGHAUS, L.<\/small> and <small>FRANZ, C.<\/small> (2004). On a new multivariate two-sample test. <i>J. Multivariate Anal.<\/i> <b>88<\/b> 190\u2013206.","DOI":"10.1016\/S0047-259X(03)00079-4"},{"key":"18","unstructured":"<small>GRETTON, A.<\/small>, <small>BORGWARDT, K. M.<\/small>, <small>RASCH, M. J.<\/small>, <small>SCH\u00d6LKOPF, B.<\/small> and <small>SMOLA, A.<\/small> (2012). A kernel two-sample test. <i>J. Mach. Learn. Res.<\/i> <b>13<\/b> 723\u2013773."},{"key":"26","doi-asserted-by":"publisher","unstructured":"<small>KIM, I.<\/small>, <small>BALAKRISHNAN, S.<\/small> and <small>WASSERMAN, L.<\/small> (2020). Robust multivariate nonparametric tests via projection averaging. <i>Ann. Statist.<\/i> <b>48<\/b> 3417\u20133441.","DOI":"10.1214\/19-AOS1936"},{"key":"27","doi-asserted-by":"publisher","unstructured":"<small>KIM, I.<\/small>, <small>RAMDAS, A.<\/small>, <small>SINGH, A.<\/small> and <small>WASSERMAN, L.<\/small> (2021). Classification accuracy as a proxy for two-sample testing. <i>Ann. Statist.<\/i> <b>49<\/b> 411\u2013434.","DOI":"10.1214\/20-AOS1962"},{"key":"6","doi-asserted-by":"publisher","unstructured":"<small>BHATTACHARYA, B. B.<\/small> (2020). Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs. <i>Ann. Statist.<\/i> <b>48<\/b> 2879\u20132903.","DOI":"10.1214\/19-AOS1913"},{"key":"15","doi-asserted-by":"crossref","unstructured":"<small>FRIEDMAN, J. H.<\/small> and <small>RAFSKY, L. C.<\/small> (1979). Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests. <i>Ann. Statist.<\/i> <b>7<\/b> 697\u2013717.","DOI":"10.1214\/aos\/1176344722"},{"key":"40","doi-asserted-by":"publisher","unstructured":"<small>RAMDAS, A.<\/small>, <small>GARC\u00cdA TRILLOS, N.<\/small> and <small>CUTURI, M.<\/small> (2017). On Wasserstein two-sample testing and related families of nonparametric tests. <i>Entropy<\/i> <b>19<\/b> Paper No. 47, 15.","DOI":"10.3390\/e19020047"},{"key":"42","doi-asserted-by":"publisher","unstructured":"<small>ROSENBAUM, P. R.<\/small> (2005). An exact distribution-free test comparing two multivariate distributions based on adjacency. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>67<\/b> 515\u2013530.","DOI":"10.1111\/j.1467-9868.2005.00513.x"},{"key":"44","doi-asserted-by":"crossref","unstructured":"<small>SCHILLING, M. F.<\/small> (1986). Multivariate two-sample tests based on nearest neighbors. <i>J. Amer. Statist. Assoc.<\/i> <b>81<\/b> 799\u2013806.","DOI":"10.1080\/01621459.1986.10478337"},{"key":"5","doi-asserted-by":"crossref","unstructured":"<small>BHATTACHARYA, B. B.<\/small> (2019). A general asymptotic framework for distribution-free graph-based two-sample tests. <i>J. R. Stat. Soc. Ser. B. Stat. Methodol.<\/i> <b>81<\/b> 575\u2013602.","DOI":"10.1111\/rssb.12319"},{"key":"16","doi-asserted-by":"publisher","unstructured":"<small>GHOSAL, P.<\/small> and <small>SEN, B.<\/small> (2022). Multivariate ranks and quantiles using optimal transport: Consistency, rates and nonparametric testing. <i>Ann. Statist.<\/i> <b>50<\/b> 1012\u20131037.","DOI":"10.1214\/21-aos2136"},{"key":"12","doi-asserted-by":"publisher","unstructured":"<small>CHEN, H.<\/small> and <small>FRIEDMAN, J. H.<\/small> (2017). A new graph-based two-sample test for multivariate and object data. <i>J. Amer. Statist. Assoc.<\/i> <b>112<\/b> 397\u2013409.","DOI":"10.1080\/01621459.2016.1147356"},{"key":"20","doi-asserted-by":"publisher","unstructured":"<small>HENZE, N.<\/small> (1988). A multivariate two-sample test based on the number of nearest neighbor type coincidences. <i>Ann. Statist.<\/i> <b>16<\/b> 772\u2013783.","DOI":"10.1214\/aos\/1176350835"},{"key":"29","unstructured":"<small>LEHMANN, E. L.<\/small> (1975). <i>Nonparametrics<\/i>: <i>Statistical Methods Based on Ranks<\/i>. <i>Holden-Day Series in Probability and Statistics<\/i>. Holden-Day, San Francisco, CA."},{"key":"32","unstructured":"<small>LOPEZ-PAZ, D.<\/small> and <small>OQUAB, M.<\/small> (2017). Revisiting classifier two-sample tests. In <i>International Conference on Learning Representations<\/i>."},{"key":"36","doi-asserted-by":"publisher","unstructured":"<small>Penrose, M.<\/small> (2003). <i>Random Geometric Graphs<\/i>. <i>Oxford Studies in Probability<\/i> <b>5<\/b>. Oxford Univ. Press, Oxford.","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"7","doi-asserted-by":"publisher","unstructured":"<small>Biswas, M.<\/small>, <small>Mukhopadhyay, M.<\/small> and <small>Ghosh, A. K.<\/small> (2014). A distribution-free two-sample run test applicable to high-dimensional data. <i>Biometrika<\/i> <b>101<\/b> 913\u2013926.","DOI":"10.1093\/biomet\/asu045"},{"key":"30","unstructured":"<small>Lehmann, E. L.<\/small> and <small>Romano, J. P.<\/small> (2005). <i>Testing Statistical Hypotheses<\/i>, 3rd ed. <i>Springer Texts in Statistics<\/i>. Springer, New York."},{"key":"52","doi-asserted-by":"crossref","unstructured":"<small>ZHANG, Q.<\/small>, <small>MAHDI, G.<\/small>, <small>TINKER, J.<\/small> and <small>CHEN, H.<\/small> (2020). A graph-based multi-sample test for identifying pathways associated with cancer progression. <i>Comput. Biol. Chem.<\/i> <b>87<\/b> 107285.","DOI":"10.1016\/j.compbiolchem.2020.107285"},{"key":"33","doi-asserted-by":"publisher","unstructured":"<small>MANN, H. B.<\/small> and <small>WHITNEY, D. R.<\/small> (1947). On a test of whether one of two random variables is stochastically larger than the other. <i>Ann. Math. Stat.<\/i> <b>18<\/b> 50\u201360.","DOI":"10.1214\/aoms\/1177730491"},{"key":"10","doi-asserted-by":"publisher","unstructured":"<small>CHEN, H.<\/small> (2019). Sequential change-point detection based on nearest neighbors. <i>Ann. Statist.<\/i> <b>47<\/b> 1381\u20131407.","DOI":"10.1214\/18-AOS1718"},{"key":"11","doi-asserted-by":"publisher","unstructured":"<small>CHEN, H.<\/small> and <small>CHU, L.<\/small> (2023). Graph-based change-point analysis. <i>Annu. Rev. Stat. Appl.<\/i> <b>10<\/b> 475\u2013499.","DOI":"10.1146\/annurev-statistics-122121-033817"},{"key":"2","doi-asserted-by":"publisher","unstructured":"<small>ARIAS-CASTRO, E.<\/small> and <small>PELLETIER, B.<\/small> (2016). On the consistency of the crossmatch test. <i>J. Statist. Plann. Inference<\/i> <b>171<\/b> 184\u2013190.","DOI":"10.1016\/j.jspi.2015.10.003"},{"key":"3","doi-asserted-by":"publisher","unstructured":"<small>ASLAN, B.<\/small> and <small>ZECH, G.<\/small> (2005). New test for the multivariate two-sample problem based on the concept of minimum energy. <i>J. Stat. Comput. Simul.<\/i> <b>75<\/b> 109\u2013119.","DOI":"10.1080\/00949650410001661440"},{"key":"8","doi-asserted-by":"publisher","unstructured":"<small>CHATTERJEE, A.<\/small> and <small>BHATTACHARYA, B. B.<\/small> (2025). Boosting the power of kernel two-sample tests. <i>Biometrika<\/i> <b>112<\/b> Paper No. asae048, 22.","DOI":"10.1093\/biomet\/asae048"},{"key":"9","unstructured":"<small>CHATTERJEE, A.<\/small> and <small>RAMDAS, A.<\/small> (2025). A martingale kernel two-sample test. In 37<i>th International Conference on Algorithmic Learning Theory<\/i>."},{"key":"14","unstructured":"<small>CHWIALKOWSKI, K. P.<\/small>, <small>RAMDAS, A.<\/small>, <small>SEJDINOVIC, D.<\/small> and <small>GRETTON, A.<\/small> (2015). Fast two-sample testing with analytic representations of probability measures. <i>Adv. Neural Inf. Process. Syst.<\/i> <b>28<\/b>."},{"key":"17","unstructured":"<small>GRETTON, A.<\/small>, <small>BORGWARDT, K.<\/small>, <small>RASCH, M.<\/small>, <small>SCH\u00d6LKOPF, B.<\/small> and <small>SMOLA, A.<\/small> (2006). A kernel method for the two-sample-problem. <i>Adv. Neural Inf. Process. Syst.<\/i> <b>19<\/b>."},{"key":"19","doi-asserted-by":"publisher","unstructured":"<small>GY\u00d6RFI, L.<\/small> and <small>NEMETZ, T.<\/small> (1978). <i>f<\/i>-dissimilarity: A generalization of the affinity of several distributions. <i>Ann. Inst. Statist. Math.<\/i> <b>30<\/b> 105\u2013113.","DOI":"10.1007\/BF02480206"},{"key":"21","doi-asserted-by":"publisher","unstructured":"<small>HENZE, N.<\/small> and <small>PENROSE, M. D.<\/small> (1999). On the multivariate runs test. <i>Ann. Statist.<\/i> <b>27<\/b> 290\u2013298.","DOI":"10.1214\/aos\/1018031112"},{"key":"22","doi-asserted-by":"crossref","unstructured":"<small>HSIAO, C.<\/small>, <small>LIU, M.<\/small>, <small>STANTON, R.<\/small>, <small>MCGEE, M.<\/small>, <small>QIAN, Y.<\/small> and <small>SCHEUERMANN, R. H.<\/small> (2016). Mapping cell populations in flow cytometry data for cross-sample comparison using the Friedman\u2013Rafsky test statistic as a distance measure. <i>Cytometry, Part A<\/i> <b>89<\/b> 71\u201388.","DOI":"10.1002\/cyto.a.22735"},{"key":"23","doi-asserted-by":"publisher","unstructured":"<small>HUANG, Z.<\/small> and <small>SEN, B.<\/small> (2024). A kernel measure of dissimilarity between <i>M<\/i> distributions. <i>J. Amer. Statist. Assoc.<\/i> <b>119<\/b> 3020\u20133032.","DOI":"10.1080\/01621459.2023.2298036"},{"key":"24","unstructured":"<small>JITKRITTUM, W.<\/small>, <small>SZAB\u00d3, Z.<\/small>, <small>CHWIALKOWSKI, K. P.<\/small> and <small>GRETTON, A.<\/small> (2016). Interpretable distribution features with maximum testing power. <i>Adv. Neural Inf. Process. Syst.<\/i> <b>29<\/b>."},{"key":"25","doi-asserted-by":"crossref","unstructured":"<small>KANEKAR, R. R.<\/small> (2026). Supplement to \u201cPower properties of the two sample test based on the nearest neighbors graph.\u201d <a href=\"https:\/\/doi.org\/10.1214\/26-AOS2657SUPP\">https:\/\/doi.org\/10.1214\/26-AOS2657SUPP<\/a>","DOI":"10.1214\/26-AOS2657SUPP"},{"key":"28","doi-asserted-by":"crossref","unstructured":"<small>LANG, K.<\/small> (1995). Newsweeder: Learning to filter netnews. In <i>Machine Learning Proceedings<\/i> 331\u2013339. Elsevier, Amsterdam.","DOI":"10.1016\/B978-1-55860-377-6.50048-7"},{"key":"31","unstructured":"<small>LIU, F.<\/small>, <small>XU, W.<\/small>, <small>LU, J.<\/small>, <small>ZHANG, G.<\/small>, <small>GRETTON, A.<\/small> and <small>SUTHERLAND, D. J.<\/small> (2020). Learning deep kernels for non-parametric two-sample tests. In <i>Proceedings of the<\/i> 37<i>th International Conference on Machine Learning<\/i> (H. D. III and A. Singh, eds.). <i>Proceedings of Machine Learning Research<\/i> <b>119<\/b> 6316\u20136326. PMLR."},{"key":"34","doi-asserted-by":"publisher","unstructured":"<small>MUKHERJEE, S.<\/small>, <small>AGARWAL, D.<\/small>, <small>ZHANG, N. R.<\/small> and <small>BHATTACHARYA, B. B.<\/small> (2022). Distribution-free multisample tests based on optimal matchings with applications to single cell genomics. <i>J. Amer. Statist. Assoc.<\/i> <b>117<\/b> 627\u2013638.","DOI":"10.1080\/01621459.2020.1791131"},{"key":"35","doi-asserted-by":"publisher","unstructured":"<small>PAN, W.<\/small>, <small>TIAN, Y.<\/small>, <small>WANG, X.<\/small> and <small>ZHANG, H.<\/small> (2018). Ball divergence: Nonparametric two sample test. <i>Ann. Statist.<\/i> <b>46<\/b> 1109\u20131137.","DOI":"10.1214\/17-AOS1579"},{"key":"41","doi-asserted-by":"crossref","unstructured":"<small>REIMERS, N.<\/small> and <small>GUREVYCH, I.<\/small> (2019). Sentence-BERT: Sentence embeddings using Siamese BERT-networks. In <i>Proceedings of the<\/i> 2019 <i>Conference on Empirical Methods in Natural Language Processing<\/i>. Association for Computational Linguistics.","DOI":"10.18653\/v1\/D19-1410"},{"key":"43","doi-asserted-by":"crossref","unstructured":"<small>RUTH, D. M.<\/small> (2014). A new multivariate two-sample test using regular minimum-weight spanning subgraphs. <i>J. Stat. Distrib. Appl.<\/i> <b>1<\/b> 22.","DOI":"10.1186\/s40488-014-0022-4"},{"key":"45","doi-asserted-by":"crossref","unstructured":"<small>SHEKHAR, S.<\/small>, <small>KIM, I.<\/small> and <small>RAMDAS, A.<\/small> (2022). A permutation-free kernel two-sample test. in: <i>Advances in Neural Information Processing Systems<\/i> <b>35<\/b> 18168\u201318180.","DOI":"10.52202\/068431-1321"},{"key":"46","unstructured":"<small>SMIRNOFF, N.<\/small> (1939). On the estimation of the discrepancy between empirical curves of distribution for two independent samples. <i>Bull. Math. Univ. Moscou<\/i> <b>2<\/b> 16."},{"key":"47","doi-asserted-by":"publisher","unstructured":"<small>SONG, H.<\/small> and <small>CHEN, H.<\/small> (2024). Generalized kernel two-sample tests. <i>Biometrika<\/i> <b>111<\/b> 755\u2013770.","DOI":"10.1093\/biomet\/asad068"},{"key":"50","doi-asserted-by":"publisher","unstructured":"<small>WALD, A.<\/small> and <small>WOLFOWITZ, J.<\/small> (1940). On a test whether two samples are from the same population. <i>Ann. Math. Stat.<\/i> <b>11<\/b> 147\u2013162.","DOI":"10.1214\/aoms\/1177731909"},{"key":"51","doi-asserted-by":"publisher","unstructured":"<small>WEISS, L.<\/small> (1960). Two-sample tests for multivariate distributions. <i>Ann. Math. Statist.<\/i> <b>31<\/b> 159\u2013164.","DOI":"10.1214\/aoms\/1177705995"},{"key":"53","unstructured":"<small>ZHAO, T.<\/small>, <small>SOTO, S.<\/small> and <small>MURPHY, R. F.<\/small> (2006). Improved comparison of protein subcellular location patterns. In 3<i>rd IEEE International Symposium on Biomedical Imaging<\/i>: <i>Nano to Macro<\/i> 562\u2013565. IEEE."}],"container-title":["The Annals of Statistics"],"original-title":[],"deposited":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T21:05:48Z","timestamp":1791320748000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-54\/issue-5\/Power-properties-of-the-two-sample-test-based-on-the\/10.1214\/26-AOS2657.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,1]]},"references-count":53,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2026,10,1]]}},"URL":"https:\/\/doi.org\/10.1214\/26-aos2657","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,1]]}}}