# Permutation-Free High-Order Interaction Tests

arXiv: https://arxiv.org/abs/2506.05963 · HTML: https://mlsanity.com/paper/2506.05963/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 48 references that are in the map.
- First posted on arXiv 6 Jun 2025.

## Builds on (most cited first, 28 of 28)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Learning Transferable Features with Deep Adaptation Networks](https://mlsanity.com/paper/1502.02791/) (2015)
- [Demystifying MMD GANs](https://mlsanity.com/paper/1801.01401/) (2018)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian](https://mlsanity.com/paper/1807.05044/) (2018)
- [What are higher-order networks?](https://mlsanity.com/paper/2104.11329/) (2021)
- [The physics of higher-order interactions in complex systems](https://mlsanity.com/paper/2110.06023/) (2021)
- [Kernel-based Tests for Joint Independence](https://mlsanity.com/paper/1603.00285/) (2016)
- [Information Constraints on Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1805.08672/) (2018)
- [Large-Scale Kernel Methods for Independence Testing](https://mlsanity.com/paper/1606.07892/) (2016)
- [A Permutation-free Kernel Two-Sample Test](https://mlsanity.com/paper/2211.14908/) (2022)
- [A Kernel Independence Test for Random Processes](https://mlsanity.com/paper/1402.4501/) (2014)
- [Hypergraph reconstruction from network data](https://mlsanity.com/paper/2008.04948/) (2020)
- [Unveiling the higher-order organization of multivariate time series](https://mlsanity.com/paper/2203.10702/) (2022)
- [Dimension-agnostic inference using cross U-statistics](https://mlsanity.com/paper/2011.05068/) (2020)
- [A Permutation-Free Kernel Independence Test](https://mlsanity.com/paper/2212.09108/) (2022)
- [A Kernel Test for Three-Variable Interactions](https://mlsanity.com/paper/1306.2281/) (2013)
- [Unifying Feature-Based Explanations with Functional ANOVA and Cooperative Game Theory](https://mlsanity.com/paper/2412.17152/) (2024)
- [Distance Metrics for Measuring Joint Dependence with Application to Causal Inference](https://mlsanity.com/paper/1711.09179/) (2017)
- [Kernel-based independence tests for causal structure learning on functional data](https://mlsanity.com/paper/2311.08743/) (2023)
- [A Kernel Test for Three-Variable Interactions with Random Processes](https://mlsanity.com/paper/1603.00929/) (2016)
- [Kernel-based Joint Independence Tests for Multivariate Stationary and Non-stationary Time Series](https://mlsanity.com/paper/2305.08529/) (2023)
- [Interaction Measures, Partition Lattices and Kernel Tests for High-Order Interactions](https://mlsanity.com/paper/2306.00904/) (2023)
- [Information-Theoretic Measures on Lattices for High-Order Interactions](https://mlsanity.com/paper/2408.07533/) (2024)
- [Dependence and dependence structures: estimation and visualization using the unifying concept of distance multivariance](https://mlsanity.com/paper/1712.06532/) (2017)

## Built on by (most cited first, 1 of 1)

- [A Martingale Kernel Independence Test](https://mlsanity.com/paper/2605.22549/) (2026)

## Abstract (arXiv)

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.