  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 using inter-point distances between the
observations (multivariate generalizations of the Wald-Wolfowitz's runs test)
or on multivariate data-depth (generalizations of the Mann-Whitney rank test).
  This paper introduces a general notion of distribution-free graph-based
two-sample tests, and provides a unified framework for analyzing and comparing
their asymptotic properties. The asymptotic (Pitman) efficiency of a general
graph-based test is derived, which include tests based on geometric graphs,
such as the Friedman-Rafsky test (1979), the test based on the $K$-nearest
neighbor graph, the cross-match test (2005), the generalized edge-count test
(2017), as well as tests based on multivariate depth functions (the Liu-Singh
rank sum statistic (1993)). The results show how the combinatorial properties
of the underlying graph effect 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 real
datasets.
