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

Abstract

Rejecting the null hypothesis in 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. Given samples from two densities $f_1$ and $f_0$, we consider the task of localizing occurrences of the inequality $f_1>f_0$. To avoid the challenges associated with high-dimensional space, we propose a general hypothesis testing framework where hypotheses are formulated adaptively to the data by conditioning on the combined sample from the two densities. We then investigate a special case of this framework where the notion of locality is captured by a random walk on a weighted graph constructed over this combined 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. Furthermore, we characterize the test's consistency according to a certain problem-hardness parameter, and show that our test achieves the minimax detection 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.

References in corpus (13)

• UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
• Detection of an anomalous cluster in a network
• Searching for a trail of evidence in a maze
• Optimal construction of k-nearest neighbor graphs for identifying noisy clusters
• On combinatorial testing problems
• A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps
• Manifold learning with bi-stochastic kernels
• Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation
• Detecting Localized Categorical Attributes on Graphs
• Local Two-Sample Testing: A New Tool for Analysing High-Dimensional Astronomical Data
• Instance-Based Classification through Hypothesis Testing
• Calibrating the scan statistic: finite sample performance vs. asymptotics
• High Probability Lower Bounds for the Total Variation Distance