Permutation-Free High-Order Interaction Tests

Zhaolu Liu, Robert Peach, Mauricio Barahona
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:39244-39260, 2025.

Abstract

Kernel-based hypothesis tests offer a flexible, non-parametric tool to detect high-order interactions in multivariate data, beyond pairwise relationships. Yet the scalability of such tests is limited by the computationally demanding permutation schemes used to generate null approximations. Here we introduce a family of permutation-free high-order tests for joint independence and partial factorisations of $d$ variables. Our tests eliminate the need for permutation-based approximations by leveraging V-statistics and a novel cross-centring technique to yield test statistics with a standard normal limiting distribution under the null. We present implementations of the tests and showcase their efficacy and scalability through synthetic datasets. We also show applications inspired by causal discovery and feature selection, which highlight both the importance of high-order interactions in data and the need for efficient computational methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-liu25bb, title = {Permutation-Free High-Order Interaction Tests}, author = {Liu, Zhaolu and Peach, Robert and Barahona, Mauricio}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {39244--39260}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/liu25bb/liu25bb.pdf}, url = {https://proceedings.mlr.press/v267/liu25bb.html}, abstract = {Kernel-based hypothesis tests offer a flexible, non-parametric tool to detect high-order interactions in multivariate data, beyond pairwise relationships. Yet the scalability of such tests is limited by the computationally demanding permutation schemes used to generate null approximations. Here we introduce a family of permutation-free high-order tests for joint independence and partial factorisations of $d$ variables. Our tests eliminate the need for permutation-based approximations by leveraging V-statistics and a novel cross-centring technique to yield test statistics with a standard normal limiting distribution under the null. We present implementations of the tests and showcase their efficacy and scalability through synthetic datasets. We also show applications inspired by causal discovery and feature selection, which highlight both the importance of high-order interactions in data and the need for efficient computational methods.} }
Endnote
%0 Conference Paper %T Permutation-Free High-Order Interaction Tests %A Zhaolu Liu %A Robert Peach %A Mauricio Barahona %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-liu25bb %I PMLR %P 39244--39260 %U https://proceedings.mlr.press/v267/liu25bb.html %V 267 %X Kernel-based hypothesis tests offer a flexible, non-parametric tool to detect high-order interactions in multivariate data, beyond pairwise relationships. Yet the scalability of such tests is limited by the computationally demanding permutation schemes used to generate null approximations. Here we introduce a family of permutation-free high-order tests for joint independence and partial factorisations of $d$ variables. Our tests eliminate the need for permutation-based approximations by leveraging V-statistics and a novel cross-centring technique to yield test statistics with a standard normal limiting distribution under the null. We present implementations of the tests and showcase their efficacy and scalability through synthetic datasets. We also show applications inspired by causal discovery and feature selection, which highlight both the importance of high-order interactions in data and the need for efficient computational methods.
APA
Liu, Z., Peach, R. & Barahona, M.. (2025). Permutation-Free High-Order Interaction Tests. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:39244-39260 Available from https://proceedings.mlr.press/v267/liu25bb.html.

Related Material