A flexible and robust non-parametric test of exchangeability

Alan J. Aw, Jeffrey P. Spence, Yun S. Song

Abstract

Many statistical analyses assume that the data points within a sample are exchangeable and their features have some known dependency structure. Given a feature dependency structure, one can ask if the observations are exchangeable, in which case we say that they are homogeneous. Homogeneity may be the end goal of a clustering algorithm or a justification for not clustering. Apart from random matrix theory approaches, few general approaches provide statistical guarantees of exchangeability or homogeneity without labeled examples from distinct clusters. We propose a fast and flexible non-parametric hypothesis testing approach that takes as input a multivariate individual-by-feature dataset and user-specified feature dependency constraints, without labeled examples, and reports whether the individuals are exchangeable at a user-specified significance level. Our approach controls Type I error across realistic scenarios and handles data of arbitrary dimension. We perform an extensive simulation study to evaluate the efficacy of domain-agnostic tests of stratification, and find that our approach compares favorably in various scenarios of interest. Finally, we apply our approach to post-clustering single-cell chromatin accessibility data and World Values Survey data, and show how it helps to identify drivers of heterogeneity and generate clusters of exchangeable individuals.

Introduction

In fields like statistical genomics, researchers frequently rely on two fundamental assumptions: sample exchangeability and feature independence. Sample exchangeability implies that individuals in a study are sufficiently homogeneous that their ordering does not affect their joint distribution. When this assumption fails, the data may exhibit "population stratification"—hidden subgroups that can lead to false positives in genetic association studies. Furthermore, features such as Single Nucleotide Polymorphisms (SNPs) are often assumed to be independent or grouped into independent blocks (Linkage Disequilibrium or LD blocks).

Existing tools, such as the Tracy-Widom test based on Random Matrix Theory, often struggle with the complexities of real-world data, including uneven sample sizes or intricate feature dependencies. This paper introduces the V test, a fast, non-parametric method designed to detect population stratification and validate feature independence without requiring labeled training data.

Methodology: The V Test

The V test operates on a simple premise: if a sample is exchangeable, the variance of pairwise distances between individuals should be predictable under a null hypothesis of exchangeability and feature independence (ES&IF).

Conceptual overview of the V test, illustrating the intuition behind pairwise distance variance and the construction of the null model through feature-shuffling.

The Statistic and Asymptotic Theory

The test calculates the empirical variance of pairwise distances (e.g., Hamming distance for binary genetic data). While traditional permutation tests are the gold standard for non-parametric testing, they are computationally prohibitive for high-dimensional genomic data ($P \approx 10^6$ SNPs). The authors overcome this by proving that as the number of features ($P$) grows, the null distribution of the statistic converges to a weighted sum of chi-square distributions. This asymptotic approximation is over 2,000 times faster than traditional resampling.

Handling Dependencies

To account for known dependencies like LD blocks, the V test allows for "block permutations." Users can group features (e.g., by chromosome) to maintain internal dependencies while testing for overall sample exchangeability. This flexibility allows the test to serve as a diagnostic tool for identifying optimal genomic split points.

Empirical Results and Insights

The V test was validated using extensive simulations and real-world data from the 1000 Genomes Project, focusing on Chromosome 22 across 26 global populations.

Allele dosage and frequency across LWK (Luhya) and YRI (Yoruba) populations, demonstrating the type of population stratification the V test is designed to detect.

Key Findings

  • Robustness to Imbalance: Unlike eigenanalysis-based methods, the V test remains reliable even when sub-populations are extremely imbalanced (e.g., a 1:9 ratio). It maintains an AUROC $\ge 0.5$ in scenarios where other tests become anti-conservative.
  • Rare Variant Drivers: Analysis of real genetic data revealed that removing rare variants significantly increased $p$-values. This suggests that rare variants are primary drivers of non-exchangeability, likely reflecting fine-scale family structure.
  • Computational Efficiency: For a dataset of 500 individuals and 500 features, the V test executes in milliseconds, compared to nearly 100 seconds for traditional permutation methods.

Discussion and Limitations

While the V test is robust and flexible, it requires users to specify feature dependency structures (independent blocks) beforehand. Incorrectly specified structures may compromise the test's validity. Currently optimized for binary or binarizable data, future work will focus on extending the framework to abstract metric spaces and real-valued data. The V test provides a powerful, scalable solution for ensuring data homogeneity in high-dimensional multivariate analysis, with open-source implementations available in R (flintyR) and Python (flintyPy).

Summary updated

Abstract

Many statistical analyses assume that the data points within a sample are exchangeable and their features have some known dependency structure. Given a feature dependency structure, one can ask if the observations are exchangeable, in which case we say that they are homogeneous. Homogeneity may be the end goal of a clustering algorithm or a justification for not clustering. Apart from random matrix theory approaches, few general approaches provide statistical guarantees of exchangeability or homogeneity without labeled examples from distinct clusters. We propose a fast and flexible non-parametric hypothesis testing approach that takes as input a multivariate individual-by-feature dataset and user-specified feature dependency constraints, without labeled examples, and reports whether the individuals are exchangeable at a user-specified significance level. Our approach controls Type I error across realistic scenarios and handles data of arbitrary dimension. We perform an extensive simulation study to evaluate the efficacy of domain-agnostic tests of stratification, and find that our approach compares favorably in various scenarios of interest. Finally, we apply our approach to post-clustering single-cell chromatin accessibility data and World Values Survey data, and show how it helps to identify drivers of heterogeneity and generate clusters of exchangeable individuals.
BibTeX
@article{aw2021flexible,
  author = {Alan J. Aw and Jeffrey P. Spence and Yun S. Song},
  title = {{A flexible and robust non-parametric test of exchangeability}},
  journal = {The Annals of Applied Statistics},
  year = {2021},
}
Figure