Local Two-Sample Testing over Graphs and Point-Clouds by Random-Walk Distributions.

Two-sample testing is a fundamental tool for scientific discovery. Yet, aside from concluding that two samples do not come from the same probability distribution, it is often of interest to characterize how the two distributions differ. Specifically, given samples from two densities $f_1$ and $f_0$, we consider the problem of localizing occurrences of the inequality $f_1 > f_0$ in the combined sample. We present a general hypothesis testing framework for this task, and investigate a special case of this framework where localization is achieved by a random walk over the sample. We derive a tractable testing procedure for this case employing a type of scan statistic, and provide non-asymptotic lower bounds on the power and accuracy of our test to detect whether $f_1>f_0$ in a local sense. We also characterize the test's consistency according to a certain problem-hardness parameter, and show that our test achieves the minimax rate for this parameter. We conduct numerical experiments to validate our method, and demonstrate our approach on two real-world applications: detecting and localizing arsenic well contamination across the United States, and analyzing two-sample single-cell RNA sequencing data from melanoma patients.