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

Boris Landa, Rihao Qu, Joseph Tung‐Chieh Chang, Yuval KlugerarXiv 2020 · DOI · arXiv

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.

Introduction

In fields ranging from genomics to environmental science, researchers frequently need to compare two groups of data—for instance, healthy versus diseased cells or contaminated versus clean water sources. Traditional statistical methods focus on "two-sample testing," which provides a global p-value to determine if two distributions are identical. However, in practice, knowing that two groups differ is often less important than knowing where they differ.

This paper addresses the challenge of localization: identifying specific regions in a high-dimensional sample space where the density of one group ($f_1$) significantly exceeds the other ($f_0$). This task is notoriously difficult due to the "curse of dimensionality," where standard density estimation becomes exponentially harder as dimensions increase. Furthermore, real-world data often resides on complex, lower-dimensional manifolds (like a "Swiss Roll" shape) where traditional Euclidean distances fail to capture the true relationships between points.

Methodology: Random Walks and Graph Geometry

The proposed framework avoids high-dimensional density estimation by conditioning on the combined data points and constructing a weighted graph. In this graph, nodes represent individual data points, and edges represent the similarity between them.

To define a "local region" without relying on fixed geometric shapes like circles or rectangles, the authors utilize random-walk distributions. A random walk starting at a point $x_i$ and running for $t$ steps naturally follows the geometry of the data. If the data lies on a manifold, the walk stays on that manifold, effectively defining a neighborhood that respects the underlying structure of the data.

Multi-Scale Scanning

The time parameter $t$ of the random walk serves as a scale parameter:

  • Small $t$: Captures immediate, fine-grained neighbors.
  • Large $t$: Captures broader, cluster-level structures.

The algorithm employs a scan statistic $S(w)$ that compares the local proportion of labels within these random-walk neighborhoods to the global prior. To ensure computational feasibility, the authors use an $\epsilon$-net approach to select a finite, logarithmic number of time steps ($O(\log n)$) that represent all relevant scales, preventing redundant calculations while maintaining sensitivity.

Theoretical Guarantees

The paper provides rigorous non-asymptotic bounds on the power (the ability to detect a difference) and accuracy (how closely the detected region matches the true difference) of the test. A key contribution is the proof that this test achieves the minimax detection rate. This implies that, given the inherent noise and data density, no other statistical test can fundamentally outperform this method in detecting local differences.

Real-World Applications

Environmental Science: Arsenic Contamination

The method was applied to a USGS dataset of 20,043 domestic wells across the United States. The goal was to localize regions where arsenic levels exceeded EPA limits. Without any prior geographic knowledge, the test successfully identified known contamination clusters in the Western US (such as Fallon, Nevada). Unlike traditional spatial scans that might "blur" these regions, the graph-based approach provided precise localization by following the actual distribution of the well data.

Biomedical Research: Melanoma scRNA-seq

In a study of 16,291 immune cells from melanoma patients, the framework compared patients who responded to immunotherapy against those who did not. While global tests might only indicate a general difference in immune profiles, this method identified a specific sub-population of T-cells (within the "G9" cluster) significantly enriched in non-responders. This specific sub-type was not highlighted in the original study, demonstrating the framework's ability to find "needles in haystacks" within high-dimensional biological data.

Conclusion

By leveraging the geometry of data through random walks, this framework provides a powerful, interpretable, and computationally efficient solution for local two-sample testing. It moves beyond simple p-values to provide researchers with a weight vector that visualizes exactly which samples drive the differences between groups. While the method's performance is tied to the quality of the initial graph construction, its minimax optimality and success in complex real-world datasets mark a significant advancement in high-dimensional statistical analysis.

Summary updated

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.
BibTeX
@misc{landa2020local,
  author = {Boris Landa and Rihao Qu and Joseph Tung‐Chieh Chang and Yuval Kluger},
  title = {{Local Two-Sample Testing over Graphs and Point-Clouds by Random-Walk Distributions}},
  year = {2020},
  eprint = {2011.03418},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.03418},
}
Figure