📊 statistics

Power properties of the two-sample test based on the nearest neighbors graph

This paper extends the theoretical understanding of two-sample tests based on nearest neighbor graphs by establishing detection thresholds for cases where the number of neighbors grows with sample size, proposing a 2-sided test to close an exponent gap, and demonstrating that increasing graph density enhances statistical power.

Original authors: Rahul Raphael Kanekar

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rahul Raphael Kanekar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out if two groups of people are actually from the same crowd or if they are secretly different. Maybe you have a pile of photos from a summer party and another pile from a winter gala, and you want to know: "Are these the same people, just dressed differently, or are they two completely different groups?" In the world of statistics, this is called the "two-sample problem." Usually, if you only have one number to look at (like height), it's easy to rank them from shortest to tallest and spot the difference. But what if you have to compare people based on a dozen traits at once—height, weight, shoe size, favorite color, and how many times they blinked? Suddenly, there's no simple way to "rank" them. You can't say one person is "greater than" another when they are different in so many ways.

To solve this, statisticians invented a clever trick: they draw a map. Instead of ranking, they connect the dots. Imagine every person is a dot on a giant piece of paper. If two dots are close together, you draw a line between them. By looking at the pattern of these lines, you can see if the two groups are mixing together or staying apart. If the groups are the same, the lines will crisscross everywhere, connecting dots from both groups. If the groups are different, the lines will mostly stay within their own groups, like two separate neighborhoods that don't talk to each other. This is the heart of "graph-based testing."

Now, here is the twist: How many lines should you draw? Should you connect every dot to just its single closest neighbor, or should you connect it to its top 10, 50, or even 100 closest neighbors? For a long time, scientists thought that connecting to just a few neighbors was the safest bet. But in this paper, Rahul Raphael Kanekar from Stanford University asks a daring question: What if we connect to more neighbors as we get more data? Does making the map "denser" help us spot the differences better, or does it just make a messy tangle of lines that confuses us?

The paper dives deep into this question using a specific type of map called the "K-nearest neighbors graph." The "K" stands for how many neighbors you connect to. The author's main discovery is that increasing K (making the graph denser) actually boosts the power of the test, but only if you do it carefully. He found that if you let K grow as your sample size gets bigger, you can detect differences that were previously invisible. However, there's a catch: the way you analyze the data changes depending on how "dense" the graph is and how many dimensions (traits) you are measuring.

The author also introduces a new way to look at the results. Traditionally, statisticians used a "one-sided" test, which only checks if there are fewer cross-group connections than expected. But the paper shows that this method can be tricky; sometimes, depending on the direction of the difference, it might miss the signal entirely. The author proposes a "two-sided" test instead, which checks for any significant deviation, whether there are too few or too many connections. This new approach is much more stable and reliable, especially when the data is complex.

Through a mix of heavy mathematical proofs and computer simulations, the paper demonstrates that using denser graphs (connecting to more neighbors) is a winning strategy. In simulations with thousands of data points, the two-sided test with a growing number of neighbors consistently outperformed older methods, correctly identifying differences that other tests missed. The paper doesn't just suggest this; it provides the mathematical "detection thresholds"—the exact rules for how much the groups need to differ before the test can spot them. It turns out that for high-dimensional data, the more neighbors you connect, the sharper your detective eye becomes, provided you use the right two-sided lens to look through.

Technical Summary: Power Properties of the Two-Sample Test Based on the Nearest Neighbors Graph

Problem Statement
This paper addresses the nonparametric two-sample problem: testing the equality of two multivariate distributions, $H_0: F = G$ versus $H_1: F \neq G$ , without assuming specific parametric forms. While graph-based tests, which utilize inter-point distances to construct a graph (e.g., Minimal Spanning Trees or $K$ -Nearest Neighbors graphs), offer a distribution-free alternative to rank-based methods, their theoretical understanding has been limited. Specifically, existing asymptotic theory relies on the "stabilizing graphs" framework of Penrose and Yukich, which applies to graphs where the local structure is independent of distant points. This framework holds for fixed $K$ but fails when the number of neighbors $K$ increases with the sample size $N$ . The paper investigates the power properties of the $K$ -nearest neighbors ( $K$ -NN) test when $K = k_N$ grows with $N$ , a regime previously lacking rigorous theoretical justification.

Methodology
The authors employ a Poissonized setting to facilitate asymptotic analysis, where the sample size follows a Poisson distribution, allowing for the use of spatial independence properties. The test statistic $T(G)$ counts the number of edges in the constructed graph that connect points from the two different samples.

Key methodological steps include:

Overcoming Non-Stabilization: Since the $k_N$ -NN graph is not stabilizing when $k_N \to \infty$ , the authors cannot rely on standard limit theorems for stabilizing functionals. Instead, they perform a "hands-on" analysis of the test statistic, explicitly quantifying the local dependence structure induced by the growing number of neighbors.
Asymptotic Normality: Using Stein's method for dependency graphs applied to a truncated version of the statistic, the authors establish a Central Limit Theorem (CLT) for the test statistic under general alternatives. They prove that for $k_N = o(N^{1/4})$ , the standardized statistic converges to a normal distribution.
Conditional vs. Unconditional Analysis: The paper derives CLTs for both the unconditional statistic and a conditional statistic (conditioned on point locations, relevant for permutation tests). The conditional CLT holds for a broader range of $k_N$ ( $k_N = o(N)$ ), whereas the unconditional CLT requires the stricter $k_N = o(N^{1/4})$ due to higher dependence between points in the marginal distribution.
Local Power Analysis: The authors analyze the detection thresholds for local alternatives where the parameter difference $\|\theta_N - \theta_1\|$ decays at a rate $\epsilon_N$ . They define a critical dimension $d_c(\gamma) = \lfloor 8(1-\gamma) \rfloor$ (assuming $k_N = N^\gamma$ ) to categorize the behavior of the test.

Key Contributions

Extension of Theoretical Framework: The paper extends the theoretical understanding of graph-based tests beyond the stabilizing framework to the case of growing $K$ , specifically for the $K$ -NN graph.
Detection Thresholds: The authors derive exact detection thresholds for both 1-sided and 2-sided versions of the test. They demonstrate that the behavior of these tests diverges significantly when the dimension $d$ exceeds the critical dimension $d_c(\gamma)$ .
Resolution of the "Exponent Gap": A primary contribution is the proposal and analysis of a 2-sided test. The authors show that the traditional 1-sided test suffers from an "exponent gap" in high dimensions ( $d > d_c(\gamma)$ ), where its power depends critically on the direction of the alternative (suffering from a "curse of dimensionality" in some directions). The 2-sided test eliminates this gap, providing stable detection thresholds regardless of the direction of the alternative.
Power Enhancement via Graph Density: The results provide theoretical justification for the empirical observation that increasing the number of nearest neighbors (denser graphs) boosts the power of the test, particularly for the 2-sided version, as the detection threshold approaches the parametric rate ( $N^{-1/2}$ ) as $k_N$ increases.

Results

Below Criticality ( $d \leq d_c(\gamma)$ ): Both 1-sided and 2-sided tests share the same detection threshold of $N^{-1/4}$ . The limiting power is determined by the standard normal CDF.
Above Criticality ( $d > d_c(\gamma)$ ):
- 1-sided Test: Exhibits an exponent gap. The detection threshold is either $N^{-1/2 - 2(1-\gamma)/d}$ (a "blessing of dimensionality") or $N^{-2(1-\gamma)/d}$ (a "curse of dimensionality"), depending on the direction of the alternative. In the gap between these rates, the power is either 0 or 1 depending on the sign of a specific directional term $b(h, \theta_1)$ .
- 2-sided Test: Demonstrates stable behavior with a single detection threshold of $N^{-1/2 - 2(1-\gamma)/d}$ . It does not suffer from the exponent gap and its power improves with dimension, approaching the parametric rate $N^{-1/2}$ as $k_N$ grows.
Simulations: Empirical results on synthetic data (Gaussian scale perturbations, log-normal families) and real data (20 Newsgroups) validate the theoretical findings. They confirm that the 1-sided test's power is highly sensitive to the direction of the alternative in high dimensions, while the 2-sided test remains robust. Simulations also suggest that increasing $K$ improves power, with $K \leq N/30$ offering a practical compromise between power and the validity of the normal approximation.

Significance
The paper claims to fill a critical gap in the literature by linking the growth of $K$ to the power of two-sample tests in parametric families. By rigorously analyzing the non-stabilizing $K$ -NN graph, the authors provide the first theoretical justification for using denser graphs to improve test power. Furthermore, the identification of the exponent gap in 1-sided tests and the demonstration that a 2-sided version removes this instability offers a concrete methodological improvement for practitioners working with high-dimensional data. The work suggests that while 1-sided tests may be unreliable in high dimensions due to directional sensitivity, 2-sided tests based on denser graphs offer a robust and powerful alternative.

More like this