gTestsMulti: New Graph-Based Multi-Sample Tests

Hoseung Song, Hao ChenOpenalex Unknown 2022 · DOI · OpenAlex

Abstract

New multi-sample tests for testing whether multiple samples are from the same distribution. They work well particularly for high-dimensional data. Song, H. and Chen, H. (2022) doi:10.48550/arXiv.2205.13787.

Introduction

In modern data science, researchers frequently encounter "high-dimensional" data—where the number of features (variables) is large relative to the number of observations. Traditional statistical tools like ANOVA or the Kruskal-Wallis test often lose power or fail entirely in these settings. Furthermore, when data is non-Euclidean (such as networks, images, or genomic sequences), defining a "mean" or "variance" becomes difficult.

The gTestsMulti R package addresses the challenge of multi-sample testing: given $K$ different groups of data, do they all come from the same underlying probability distribution? The goal is to provide a test that is both computationally efficient and statistically powerful, even when the data is complex or lives in a high-dimensional space.

Methodology

The package implements the methodology proposed by Song and Chen (2022), which centers on the use of similarity graphs. The process involves three primary steps:

  1. Graph Construction: The user pools all observations from the $K$ samples and constructs a similarity graph (e.g., a Minimum Spanning Tree or a $k$-nearest neighbor graph) based on the distances between points.
  2. Test Statistics ($S$ and $S^A$): The core logic relies on counting edges in the graph that connect points from different classes. If the samples come from the same distribution, the "colors" (class labels) of the nodes in the graph should be well-mixed. If they differ, nodes of the same class will likely cluster together, resulting in fewer cross-class edges than expected by chance.

The function requires specific inputs to perform these tests, as detailed in the package documentation.

Input arguments for the gTestsMulti function, including the edge matrix and data list.

Statistical Inference

The package provides two ways to calculate p-values, allowing users to balance computational cost and precision:

  • Asymptotic Theory: For large datasets, the package uses mathematical approximations (including a Bonferroni procedure for the $S$ statistic) to provide quick results.
  • Permutation Testing: For smaller datasets or higher precision, the package can shuffle the class labels thousands of times to build an empirical distribution of the test statistic.

The output of the test includes both raw statistics and various p-value approximations.

Description of the test statistics and p-values returned by the gTestsMulti function.

Implementation and Key Insights

The documentation provides a synthetic benchmark to demonstrate the package's utility using a High-Dimensional Gaussian Example. The authors simulate three groups in a 50-dimensional space ($d=50$) with 50 samples each, but with slightly shifted means. This scenario represents a "high-dimensional, low-sample size" (HDLSS) problem where traditional tests often struggle.

Key insights from this approach include:

  • Geometry to Topology: By converting raw data into a graph, the test shifts the focus from specific coordinates to relative proximity, making it flexible for non-standard data types.
  • Scalability: The inclusion of both $S$ and $S^A$ statistics allows users to choose between a more conservative approach (Bonferroni-corrected $S$) and a more direct asymptotic approach ($S^A$).
  • Robustness: Because the graph-based approach relies on distances rather than estimating high-dimensional covariance matrices, it avoids many pitfalls of classical multivariate tests.

Limitations

While powerful, the method has some constraints. Permutation tests can be computationally intensive for large datasets; the authors explicitly warn that setting perm > 10,000 can be very time-consuming. Additionally, the power of the test is tied to the quality of the similarity graph and the choice of distance metric. If the metric does not capture meaningful differences between distributions, the test will lose power.

For those interested in the underlying proofs and extensive power comparisons, the authors point to their 2022 paper: arXiv:2205.13787.

Summary updated

Abstract

New multi-sample tests for testing whether multiple samples are from the same distribution. They work well particularly for high-dimensional data. Song, H. and Chen, H. (2022) &lt;<a href="https://doi.org/10.48550/arXiv.2205.13787" target="_top">doi:10.48550/arXiv.2205.13787</a>&gt;.
BibTeX
@inproceedings{song2022gtestsmulti,
  author = {Hoseung Song and Hao Chen},
  title = {{gTestsMulti: New Graph-Based Multi-Sample Tests}},
  booktitle = {Openalex Unknown},
  year = {2022},
  doi = {10.32614/cran.package.gtestsmulti},
}
Figure