{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T06:56:52Z","timestamp":1792047412135,"version":"4.4.0"},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T00:00:00Z","timestamp":1555286400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,7,1]]},"abstract":"<jats:title>Summary<\/jats:title>\n                  <jats:p>Testing equality of two multivariate distributions is a classical problem for which many non-parametric tests have been proposed over the years. Most of the popular two-sample tests, which are asymptotically distribution free, are based either on geometric graphs constructed by using interpoint distances between the observations (multivariate generalizations of the Wald\u2013Wolfowitz runs test) or on multivariate data depth (generalizations of the Mann\u2013Whitney rank test). The paper introduces a general notion of distribution-free graph-based two-sample tests and provides a unified framework for analysing and comparing their asymptotic properties. The asymptotic (Pitman) efficiency of a general graph-based test is derived, which includes tests based on geometric graphs, such as the Friedman\u2013Rafsky test, the test based on the K-nearest-neighbour graph, the cross-match test and the generalized edge count test, as well as tests based on multivariate depth functions (the Liu\u2013Singh rank sum statistic). The results show how the combinatorial properties of the underlying graph affect the performance of the associated two-sample test and can be used to validate and decide which tests to use in practice. Applications of the results are illustrated both on synthetic and on real data sets.<\/jats:p>","DOI":"10.1111\/rssb.12319","type":"journal-article","created":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T06:38:46Z","timestamp":1555310326000},"page":"575-602","source":"Crossref","is-referenced-by-count":29,"title":["A General Asymptotic Framework for Distribution-Free Graph-Based Two-Sample Tests"],"prefix":"10.1093","volume":"81","author":[{"given":"Bhaswar B.","family":"Bhattacharya","sequence":"first","affiliation":[{"name":"University of Pennsylvania , Philadelphia , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2019,4,15]]},"reference":[{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF01194923","article-title":"Asymptotics for Euclidean minimal spanning trees on random points","volume":"92","author":"Aldous","year":"1992","journal-title":"Probab. Theory Reltd Flds"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","article-title":"The complexity and approximability of finding maximum feasible subsystems of linear relations","volume":"147","author":"Amaldi","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/j.jspi.2015.10.003","article-title":"On the consistency of the crossmatch test","volume":"171","author":"Arias-Castro","year":"2016","journal-title":"J. Statist. Planng Inf."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1080\/00949650410001661440","article-title":"New test for the multivariate two-sample problem based on the concept of minimum energy","volume":"75","author":"Aslan","year":"2005","journal-title":"J. Statist. Computn Simuln"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0047-259X(03)00079-4","article-title":"On a new multivariate two-sample test","volume":"88","author":"Baringhaus","year":"2004","journal-title":"J. Multiv. Anal."},{"key":"2023022002404402200_","first-page":"1","volume-title":"Proc. 18th Conf. Emerging Technologies and Factory Automation","author":"Bayer","year":"2013"},{"key":"2023022002404402200_","volume-title":"Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs","author":"Bhattacharya","year":"2018"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1214\/16-AAP1205","article-title":"Universal Poisson and Normal limit theorems in graph coloring problems with connections to extremal combinatorics","volume":"27","author":"Bhattacharya","year":"2017","journal-title":"Ann. Appl. Probab."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/aoms\/1177697800","article-title":"A distribution free version of the Smirnov two sample test in the p-variate case","volume":"40","author":"Bickel","year":"1969","journal-title":"Ann. Math. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1093\/biomet\/asu045","article-title":"A distribution-free two-sample run test applicable to high-dimensional data","volume":"101","author":"Biswas","year":"2014","journal-title":"Biometrika"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.1080\/01621459.2017.1307757","article-title":"A weighted edge-count two sample test for multivariate and object data","volume":"113","author":"Chen","year":"2019","journal-title":"J. Am. Statist. Ass."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1080\/01621459.2016.1147356","article-title":"A new graph-based two-sample test for multivariate and object data","volume":"112","author":"Chen","year":"2017","journal-title":"J. Am. Statist. Ass."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1214\/14-AOS1269","article-title":"Graph-based change-point detection","volume":"43","author":"Chen","year":"2015","journal-title":"Ann. Statist."},{"key":"2023022002404402200_","first-page":"1972","volume-title":"Proc. A. Conf. Neural Information Processing Systems","author":"Chwialkowski","year":"2015"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1214\/aos\/1176345462","article-title":"The jackknife estimate of variance","volume":"9","author":"Efron","year":"1981","journal-title":"Ann. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1214\/aos\/1176344722","article-title":"Multivariate generalizations of the Wolfowitz and Smirnov two-sample tests","volume":"7","author":"Friedman","year":"1979","journal-title":"Ann. Statist."},{"key":"2023022002404402200_","first-page":"723","article-title":"A kernel two-sample test","volume":"16","author":"Gretton","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1093\/biomet\/89.2.359","article-title":"Permutation tests for equality of distributions in high-dimensional settings","volume":"89","author":"Hall","year":"2002","journal-title":"Biometrika"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1214\/aos\/1176350835","article-title":"A multivariate two-sample test based on the number of nearest neighbour type coincidences","volume":"16","author":"Henze","year":"1988","journal-title":"Ann. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1214\/aos\/1018031112","article-title":"On the multivariate runs test","volume":"27","author":"Henze","year":"1999","journal-title":"Ann. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","article-title":"The densest hemisphere problem","volume":"6","author":"Johnson","year":"1978","journal-title":"Theor. Comput. Sci."},{"key":"2023022002404402200_","volume-title":"Nonparametrics: Statistical Methods based on Ranks","author":"Lehmann","year":"1975"},{"key":"2023022002404402200_","volume-title":"Testing Statistical Hypotheses","author":"Lehmann","year":"2005","edition":"3rd edn"},{"key":"2023022002404402200_","volume-title":"Randomized near neighbour graphs, giant components, and applications in data science","author":"Linderman","year":"2017"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1214\/aos\/1176347507","article-title":"On a notion of data-depth-based on random simplices","volume":"18","author":"Liu","year":"1990","journal-title":"Ann. Statist."},{"key":"2023022002404402200_","first-page":"279","volume-title":"L1-statistical Analysis and Related Methods","author":"Liu","year":"1992"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1080\/01621459.1993.10594317","article-title":"A quality index based on data-depth and multivariate rank tests","volume":"88","author":"Liu","year":"1993","journal-title":"J. Am. Statist. Ass."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1214\/aos\/1032526956","article-title":"Reducing multidimensional two-sample data to one-dimensional interpoint comparisons","volume":"24","author":"Maa","year":"1996","journal-title":"Ann. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1214\/aoms\/1177730491","article-title":"On a test of whether one of two random variables is stochastically larger than the other","volume":"18","author":"Mann","year":"1947","journal-title":"Ann. Math. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1214\/aoms\/1177728719","article-title":"On the asymptotic efficiency of certain nonparametric two-sample tests","volume":"25","author":"Mood","year":"1954","journal-title":"Ann. Math. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-0468-3","volume-title":"Multivariate Nonparametric Methods with R: an Approach based on Spatial Signs and Ranks","author":"Oja","year":"2010"},{"key":"2023022002404402200_","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1214\/aoap\/1015345393","article-title":"Central limit theorems for some graphs in computational geometry","volume":"11","author":"Penrose","year":"2001","journal-title":"Ann. Appl. Probab."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1214\/aoap\/1042765669","article-title":"Weak laws of large numbers in geometric probability","volume":"13","author":"Penrose","year":"2003","journal-title":"Ann. Appl. Probab."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1111\/j.1467-9868.2005.00513.x","article-title":"An exact distribution-free test comparing two multivariate distributions based on adjacency","volume":"67","author":"Rosenbaum","year":"2005","journal-title":"J. R. Statist. Soc."},{"key":"2023022002404402200_","volume-title":"Statistical depth meets computational geometry: a short survey","author":"Rousseeuw","year":"2015"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jmva.2000.1981","article-title":"On distribution-free tests for the multivariate two-sample location-scale model","volume":"80","author":"Rousson","year":"2002","journal-title":"J. Multiv. Anal."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1080\/01621459.1986.10478337","article-title":"Multivariate two-sample tests based on nearest neighbours","volume":"81","author":"Schilling","year":"1986","journal-title":"J. Am. Statist. Ass."},{"key":"2023022002404402200_","first-page":"523","volume-title":"Proc. Int. Congr. Mathematics, Vancouver, 1974","author":"Tukey","year":"1975"},{"key":"2023022002404402200_","volume-title":"Asymptotic Statistics","author":"van der Vaart","year":"2000"},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1214\/aoms\/1177731909","article-title":"On a test whether two samples are from the same distribution","volume":"11","author":"Wald","year":"1940","journal-title":"Ann. Math. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1214\/aoms\/1177705995","article-title":"Two-sample tests for multivariate distributions","volume":"31","author":"Weiss","year":"1960","journal-title":"Ann. Math. Statist."},{"key":"2023022002404402200_","doi-asserted-by":"crossref","first-page":"2879","DOI":"10.1214\/009053606000000876","article-title":"On the limiting distributions of multivariate depth-based rank sum statistics and related tests","volume":"34","author":"Zuo","year":"2006","journal-title":"Ann. Statist."}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Frssb.12319","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/81\/3\/575\/49269999\/jrsssb_81_3_575.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/81\/3\/575\/49269999\/jrsssb_81_3_575.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,16]],"date-time":"2024-07-16T18:36:12Z","timestamp":1721154972000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/81\/3\/575\/7048374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,15]]},"references-count":43,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,4,15]]},"published-print":{"date-parts":[[2019,7,1]]}},"URL":"https:\/\/doi.org\/10.1111\/rssb.12319","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,7]]},"published":{"date-parts":[[2019,4,15]]}}}