Abstract

Two-sample hypothesis testing is a fundamental problem with various applications, which faces new challenges in the high-dimensional context. To mitigate the

issue of the curse of dimensionality, high-dimensional data are typically assumed to

lie on a low-dimensional manifold. To incorporate geometric information in the data,

we propose to apply the Delaunay triangulation and develop the Delaunay weight to

measure the geometric proximity among data points. In contrast to existing similarity

measures that only utilize pairwise distances, the Delaunay weight can take both the

distance and direction information into account. A detailed computation procedure

is developed to learn the unknown manifold and approximate the Delaunay weight.

We further propose a novel nonparametric test statistic using the Delaunay weight

matrix. Asymptotic normality under the null and consistency under the alternative

of the test statistic are developed. Applied to simulated data, the new test shows

robustness to the learning of the unknown manifold and exhibits substantial power

gain if the distributions differ in the principal directions of covariance matrices. The

proposed test also detects significant differences on a real dataset of mice protein

expression levels.

Key words and phrases: Delaunay triangulation; geometric proximity; high dimension; manifold learn- ing; permutation test

Information

Preprint No.SS-2025-0280
Manuscript IDSS-2025-0280
Complete AuthorsJiaqi Gu, Ruoxu Tan, Guosheng Yin
Corresponding AuthorsRuoxu Tan
Emailsruoxut@tongji.edu.cn

References

  1. Abadie, A. and L’Hour, J. (2021). A penalized synthetic control estimator for disaggregated data. Journal of the American Statistical Association, 116(536):1817–1834.
  2. Arias-Castro, E., Pelletier, B., and Saligrama, V. (2018). Remember the curse of dimensionality: The case of goodness-of-fit testing in arbitrary dimension. Journal of Nonparametric Statistics, 30(2):448–471.
  3. Bhattacharya, R. and Patrangenaru, V. (2003). Large sample theory of intrinsic and extrinsic sample means on manifolds. The Annals of Statistics, 31(1):1–29.
  4. Bickel, P. J. (1969). A distribution free version of the Smirnov two sample test in the p-variate case. The Annals of Mathematical Statistics, 40(1):1–23.
  5. Cai, T. T., Liu, W., and Xia, Y. (2013). Two-sample covariance matrix testing and support recovery in high-dimensional and sparse settings. Journal of the American Statistical Association, 108(501):265–277.
  6. Cai, T. T., Liu, W., and Xia, Y. (2014). Two-sample test of high dimensional means under dependence. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(2):349–372.
  7. Cao, Y., Nemirovski, A., Xie, Y., Guigues, V., and Juditsky, A. (2018). Change detection via affine and quadratic detectors. Electronic Journal of Statistics, 12(1):1–57.
  8. Chang, J., Zheng, C., Zhou, W.-X., and Zhou, W. (2017). Simulation-based hypothesis testing of high dimensional means under covariance heterogeneity. Biometrics, 73(4):1300– 1310.
  9. Chang, T. H., Watson, L. T., Lux, T. C. H., Butt, A. R., Cameron, K. W., and Hong,
  10. Y. (2020). Algorithm 1012: DELAUNAYSPARSE: Interpolation via a sparse subset of the Delaunay triangulation in medium to high dimensions. ACM Transactions on M h i l S f 46(4) 38 1 38 20
  11. Chen, H. (2019). Sequential change-point detection based on nearest neighbors. The Annals of Statistics, 47(3):1381–1407.
  12. Chen, H., Chen, X., and Su, Y. (2018). A weighted edge-count two-sample test for multivariate and object data. Journal of the American Statistical Association, 113(523):1146– 1155.
  13. Chen, H. and Friedman, J. H. (2017). A new graph-based two-sample test for multivariate and object data. Journal of the American Statistical Association, 112(517):397–409.
  14. Cheng, X. and Xie, Y. (2024). Kernel two-sample tests for manifold data. Bernoulli, 30(4):2572–2597.
  15. Chwialkowski, K., Strathmann, H., and Gretton, A. (2016). A kernel test of goodness of fit. In Balcan, M. F. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2606–2615, New York, New York, USA. PMLR.
  16. Dorrity, M. W., Saunders, L. M., Queitsch, C., Fields, S., and Trapnell, C. (2020). Dimensionality reduction by UMAP to visualize physical and genetic interactions. Nature Communications, 11(1):1537.
  17. Facco, E., d’Errico, M., Rodriguez, A., and Laio, A. (2017). Estimating the intrinsic dimension of datasets by a minimal neighborhood information. Scientific Reports, 7(1):12140.
  18. Friedman, J. H. and Rafsky, L. C. (1979). Multivariate generalizations of the Wald– Wolfowitz and Smirnov two-sample tests. The Annals of Statistics, 7(4):697–717.
  19. Gong, S., Boddeti, V. N., and Jain, A. K. (2019). On the intrinsic dimensionality of image representations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 3987–3996.
  20. Gretton, A., Borgwardt, K. M., Rasch, M. J., Sch¨olkopf, B., and Smola, A. (2012). A kernel two-sample test. Journal of Machine Learning Research, 13(25):723–773.
  21. Gretton, A., Fukumizu, K., Harchaoui, Z., and Sriperumbudur, B. K. (2009). A fast, consistent kernel two-sample test. In Advances in Neural Information Processing Systems, volume 22, pages 673–681, Red Hook, New York, USA. Curran Associates, Inc.
  22. Gu, J. and Yin, G. (2021). Crystallization learning with the Delaunay triangulation. In Meil˘a, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3854– 3863. PMLR.
  23. Hall, P. and Tajvidi, N. (2002). Permutation tests for equality of distributions in highdimensional settings. Biometrika, 89(2):359–374.
  24. Hediger, S., Michel, L., and N¨af, J. (2022). On the use of random forest for two-sample testing. Computational Statistics & Data Analysis, 170:107435.
  25. Henze, N. (1988). A multivariate two-sample test based on the number of nearest neighbor type coincidences. The Annals of Statistics, 16(2):772–783.
  26. Henze, N. and Penrose, M. D. (1999). On the multivariate runs test. The Annals of Statistics, 27(1):290–298.
  27. Higuera, C., Gardiner, K. J., and Cios, K. J. (2015). Self-organizing feature maps identify proteins critical to learning in a mouse model of Down syndrome. PLOS ONE, 10(6):e0129126.
  28. Jureˇckov´a, J. and Kalina, J. (2012). Nonparametric multivariate rank tests and their unbiasedness. Bernoulli, 18(1):229–251.
  29. Kim, I., Lee, A. B., and Lei, J. (2019). Global and local two-sample tests via regression. Electronic Journal of Statistics, 13(2):5253–5305.
  30. Kolmogorov, A. N. (1933). Sulla determinazione empirica di una legge di distribuzione. Giornale dell’Istituto Italiano degli Attuari, 4:83–91.
  31. Kruskal, J. B. (1964). Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1):1–27.
  32. Leibon, G. and Letscher, D. (2000). Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In Proceedings of the sixteenth annual symposium on Computational geometry, pages 341–349, New York, New York, USA. Association for Computing Machinery.
  33. Liu, W., Yu, X., Zhong, W., and Li, R. (2024). Projection test for mean vector in high dimensions. Journal of the American Statistical Association, 119(545):744–756.
  34. Liu, Y. and Xie, J. (2020). Cauchy combination test: A powerful test with analytic p-value calculation under arbitrary dependency structures. Journal of the American Statistical Association, 115(529):393–402.
  35. Mann, H. B. and Whitney, D. R. (1947). On a test of whether one of two random variables is stochastically larger than the other. The Annals of Mathematical Statistics, 18(1):50–60.
  36. Marozzi, M. (2015). Multivariate multidistance tests for high-dimensional low sample size case-control studies. Statistics in Medicine, 34(9):1511–1526.
  37. Meil˘a, M. and Zhang, H. (2024). Manifold learning: What, how, and why. Annual Review of Statistics and Its Application, 11(1):393–417.
  38. Moon, K. R., Stanley, III, J. S., Burkhardt, D., van Dijk, D., Wolf, G., and Krishnaswamy,
  39. S. (2018). Manifold learning-based methods for analyzing single-cell RNA-sequencing data. Current Opinion in Systems Biology, 7:36–46.
  40. Morgan, K. L. and Rubin, D. B. (2012). Rerandomization to improve covariate balance in experiments. The Annals of Statistics, 40(2):1263–1282.
  41. Pless, R. and Souvenir, R. (2009). A survey of manifold learning for images. IPSJ Transactions on Computer Vision and Applications, 1:83–94.
  42. Rosenbaum, P. R. (2005). An exact distribution-free test comparing two multivariate distributions based on adjacency. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(4):515–530.
  43. Schilling, M. F. (1986). Multivariate two-sample tests based on nearest neighbors. Journal of the American Statistical Association, 81(395):799–806.
  44. Sibson, R. (1978). Locally equiangular triangulations. The Computer Journal, 21(3):243– 245.
  45. Smirnov, N. (1948). Table for estimating the goodness of fit of empirical distributions. The Annals of Mathematical Statistics, 19(2):279–281.
  46. Sz´ekely, G. J. and Rizzo, M. L. (2004). Testing for equal distributions in high dimension. InterStat, (5).
  47. Tenenbaum, J. B., de Silva, V., and Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323.
  48. Terradot, L., Durnell, N., Li, M., Li, M., Ory, J., Labigne, A., Legrain, P., Colland,
  49. F., and Waksman, G. (2004). Biochemical characterization of protein complexes from the Helicobacter pylori protein interaction map: Strategies for complex formation and evidence for novel interactions within type IV secretion systems. Molecular & Cellular Proteomics, 3(8):809–819.
  50. Wald, A. and Wolfowitz, J. (1940). On a test whether two samples are from the same population. The Annals of Mathematical Statistics, 11(2):147–162.
  51. Wang, W., Lin, N., and Tang, X. (2019). Robust two-sample test of high-dimensional mean vectors under dependence. Journal of Multivariate Analysis, 169:312–329.
  52. Wilcoxon, F. (1945). Individual comparisons by ranking methods. Biometrics Bulletin, 1(6):80–83.
  53. Yan, J. and Zhang, X. (2023). Kernel two-sample tests in high dimensions: Interplay between moment discrepancy and dimension-and-sample orders. Biometrika, 110(2):411– 430.
  54. Yang, S., Zheng, S., and Li, R. (2024). A new test for high-dimensional two-sample mean problems with consideration of correlation structure. The Annals of Statistics, 52(5):2217–2240.
  55. Zhao, D., Wang, J., Lin, H., Chu, Y., Wang, Y., Zhang, Y., and Yang, Z. (2021). Sentence representation with manifold learning for biomedical texts. Knowledge-Based Systems, 218:106869.

Acknowledgments

We thank the Editor, the Associate Editor and two referees for their careful reviews and

many insightful comments, which led to a much better exposition of our work.

Tan’s

research was supported by the National Natural Science Foundation of China (No. 12401363

and 12471263), the Fundamental Research Funds for the Central Universities, and the Key

Laboratory of Intelligent Computing and Applications (Ministry of Education).

Yin’s

research was supported by the Patrick SC Poon endowment fund.