Research map / Probabilistic and scientific modeling / Molecules and proteins
Permutation-Free High-Order Interaction Tests
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes permutation-free kernel tests for high-order joint independence (x̄dHSIC) and partial/complete factorisation (x̄LI, x̄SI) using V-statistics, data splitting and cross-centring, yielding N(0,1) null distributions.
Problem
Kernel-based high-order interaction tests (dHSIC, Lancaster, Streitberg) rely on costly permutation schemes to approximate null distributions, limiting scalability to many variables and large samples.
Approach
Combine data splitting, V-statistics and a novel cross-centring of kernel matrices so that normalised statistics have a standard normal limit under the null, giving a single-computation test for joint independence, Lancaster factorisation and Streitberg (complete) factorisation for any d.
Key results
- x̄dHSIC reaches maximum power roughly 100 times faster than permutation-based dHSIC with p=100 permutations on d=4 MVG data.
- For n=500 XOR data with d=5, x̄SI+x̄LI runs in about 0.5 seconds versus roughly 6 minutes for permutation-based SI.
- x̄SI+x̄LI is the only method in the feature-selection experiment that recovers the ground-truth feature set (MSE 4.35, matching ground truth).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use xSI+xLI instead of the other listed feature-selection methods | Synthetic feature selection · Synthetic feature selection | MSE: 4.35 vs. 5.01 (xdHSIC); 4.35 vs. 5.01 (xLI); 4.35 vs. 4.67 (Sequential: 4.69; RFE: 4.47; SHAP: 4.67; xHSIC: 4.67) | Helped |
| Use xSI+xLI rather than permutation-based SI | High-order interaction testing · XOR interaction, n=500 | computation time: 0.5 seconds vs. roughly 6 minutes | Helped |
| Use xLI rather than permutation-based LI | V-structure detection · V-structure detection | computation time: 0.082s vs. 7.6s | Helped |
| Use xLI rather than permutation-based LI | V-structure detection · V-structure detection | statistical power | Hurt |
| Use xdHSIC rather than permutation-based dHSIC | Joint independence testing · d=4 multivariate Gaussian | power | No clear effect |
| Use xSI+xLI rather than SI alone | Complete factorisation testing · Factorisation as P12 P345, d=5 | interaction detection | Helped |
| Use xdHSIC rather than dHSIC | Causal DAG recovery · DAG causal structural learning, d=4 | DAG recovery accuracy: 200-fold computational speed-up | Helped |
| Use permutation-based methods instead of permutation-free methods in the low-sample regime | High-order interaction tests · n≤50 and d≤5 | statistical power: n≤50; d≤5; p=100 | Mixed |
Surprising findings
- For small sample sizes (n≤50) and low order d≤5, permutation-based methods perform comparably to and occasionally slightly better than the permutation-free methods.
- Using x̄SI alone for all subhypotheses is computationally less advantageous than combining x̄LI with x̄SI.
Limitations
- Data-splitting and i.i.d. assumption restrict applicability to dependent data such as time series, network or spatial data.
- Permutation-free methods are less reliable than permutation-based ones at small sample sizes due to data splitting.
- Only joint independence and factorisation hypotheses are covered; conditional independence and other composite hypotheses are not addressed.
Experimental setup
Datasets: synthetic multivariate Gaussian XOR gate synthetic data V-structure datasets A and B (Mooij/Kernel CI benchmarks) additive noise DAG simulations S&P 500 daily returns 2020-2024
Benchmarks: synthetic MVG power curves XOR interaction power V-structure detection datasets A and B DAG structure recovery feature selection XOR+MVG dataset S&P 500 sector interactions
Metrics: statistical power type-I error runtime structural Hamming distance mean squared error percentage of significant interactions
Baselines: dHSIC LI SI x̄HSIC KCI RFE SHAP sequential feature selection
Builds on: HSIC dHSIC Lancaster interaction test Streitberg interaction test x̄HSIC
Closest papers by meaning
- On the sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery (ICML 2024 · similarity 0.85)
- Extracting Rare Dependence Patterns via Adaptive Sample Reweighting (ICML 2025 · similarity 0.85)
- Permutation-based Rank Test in the Presence of Discretization and Application in Causal Discovery with Mixed Data (ICML 2025 · similarity 0.85)
- Causal Discovery via Conditional Independence Testing with Proxy Variables (ICML 2024 · similarity 0.84)
- Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies (AAAI 2025 · similarity 0.84)
- PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.