Abstract
We consider the problem of detecting associations between random vectors of any dimension. Few tests of independence exist that are consistent against all dependent alternatives. We propose a powerful test that is applicable in all dimensions and consistent against all alternatives. The test has a simple form, is easy to implement, and has good power.
Introduction
Detecting dependencies between sets of variables is a fundamental task in modern data science, with applications spanning genomics, neuroscience, and economics. Traditional methods, such as Pearson’s correlation, are limited to detecting linear relationships. In many real-world scenarios, variables exhibit complex, non-linear dependencies—such as circular or parabolic patterns—where linear correlation coefficients may be zero, leading to false conclusions of independence.
While "consistent" tests like Distance Covariance (dCov) have been developed to address these limitations, they often lack sufficient power to detect non-monotone or highly complex relationships, particularly in high-dimensional spaces or with heavy-tailed distributions.
Methodology: Ranks of Pairwise Distances
The proposed test by Heller, Heller, and Gorfine utilizes the ranks of pairwise distances to identify regions where joint distributions deviate from independence. The core algorithm follows a four-step process:
- Neighborhood Definition: For every pair of observations $(i, j)$, point $i$ is treated as a center with the distance to point $j$ serving as a radius, defining "balls" in both the $X$ and $Y$ feature spaces.
- Contingency Table Construction: For each pair, a $2 \times 2$ contingency table is constructed by counting how many other points fall inside or outside these respective balls.
- Evidence Aggregation: A Pearson chi-square statistic is calculated for each table to measure the local deviation from independence.
- Global Statistic: The final test statistic is the sum of these chi-square values across all possible pairs.
To ensure scalability, the authors developed an optimized algorithm that reduces the computational complexity from $O(N^3)$ to $O(N^2 \log N)$ using a modified merge-sort approach for counting inversions in distance ranks.
Experimental Evaluation
The test was evaluated against synthetic benchmarks and real-world datasets, including bivariate relations (Circles, W-shapes, Diamonds) and high-dimensional simulations in up to 1,000 dimensions.
Performance on Non-Linear Patterns
The new test demonstrates a significant "Circle Advantage." In simulations involving circular data, the dCov test failed completely (power $\approx 0$), whereas the proposed test achieved near-perfect detection (power $= 0.993$). Similar performance gains were observed across other non-linear shapes like the Diamond and Parabola.
Robustness to Heavy Tails and High Dimensions
A key strength of the distance-rank approach is its robustness. Because it operates on distances rather than raw coordinates, it is dimension-agnostic and performs well even when moments (like mean or variance) are undefined, as in Cauchy distributions. In 1,000-dimensional mixture models with heavy tails, the new test maintained high power (0.580) while dCov dropped to near-zero (0.020).
Discussion and Conclusion
The proposed test is universally consistent, meaning it is guaranteed to detect any form of dependence as sample size increases, regardless of whether the data is continuous, discrete, or mixed. Its superior power in non-linear and high-dimensional settings makes it a robust alternative to existing methods. On real-world data, such as the Saviotti aircraft dataset, the test identified highly significant relationships ($p < 0.00001$) where Pearson correlation failed ($p \approx 0.80$). Future work may focus on improving computational efficiency for massive datasets and developing methods to localize the specific regions or sub-vectors driving the detected associations.
Summary updated