Scaling High-Order Feature Interaction Discovery

38 concepts39 papers3 proposals

In machine learning, we often assume that features affect the target variable independently or through simple pairwise relationships. But real-world systems are rarely so cooperative. In genomics, a disease might only manifest when a specific recipe of five distinct gene mutations occurs simultaneously—a phenomenon known as epistasis. In click-through rate (CTR) prediction, an advertisement's success might depend on the intricate confluence of a user's demographics, search history, time of day, and device type.

These scenarios represent high-order feature interactions, where the joint effect of a combination of variables cannot be predicted by looking at any subset of them in isolation.

The fundamental challenge in capturing these interactions is the combinatorial explosion. If a dataset contains $d$ features, the number of potential $k$-way interactions grows as $\binom{d}{k}$, which scales as $O(d^k)$. For a modest dataset with 1,000 features, evaluating all possible 5-way interactions requires searching through more than 8 trillion combinations. This exponential growth creates a severe computational and statistical ceiling, leading to intractable training times, high risks of overfitting, and severe multiple-testing issues.

To bypass this combinatorial wall, researchers have developed a suite of algorithmic and architectural strategies designed to discover, model, and explain high-order interactions without exhaustively searching the entire space.


The Mathematical Wall: Why Exhaustive Search Fails

To understand why high-order interaction discovery is difficult, consider the classic parity function (or generalized XOR problem). As Dimitris Margaritis demonstrates in Toward Provably Correct Feature Selection in Arbitrary Domains, variables in a parity function reveal absolutely zero statistical association with the target when evaluated individually or in small groups; their relevance only emerges when the entire group is considered together.

Traditional feature selection methods that rely on greedy, one-at-a-time filtering completely fail in these domains. This issue is highly pronounced in biological systems. For instance, Lara Sucheston et al. in Comparison of information-theoretic to statistical methods for gene-gene interactions in the presence of genetic heterogeneity and Pritam Chanda et al. in Information-theoretic gene-gene and gene-environment interaction analysis of quantitative traits highlight that information-theoretic metrics like $k$-way interaction information (KWII) can successfully identify these multi-variable synergies, but scaling them beyond three or four variables quickly becomes computationally prohibitive without high-performance computing resources.


Strategy 1: Mathematical Pruning and Statistical Bounds

One way to conquer the combinatorial explosion is to avoid evaluating combinations that are mathematically guaranteed to be irrelevant or statistically insignificant. Instead of guessing which features interact, algorithms can use analytical bounds to prune the search space.

Pruning Continuous Spaces

In Finding Statistically Significant Interactions between Continuous Features, Mahito Sugiyama et al. introduced the C-Tarone algorithm. By leveraging rank-order statistics and analytical $p$-value bounds, the algorithm can mathematically prove that certain combinations of continuous features cannot pass a statistical significance threshold, allowing it to safely discard massive branches of the combinatorial search tree.

Tree-Based Pruning and Selective Inference

When searching through billions of candidate interactions, the risk of false positives skyrockets due to the multiple testing problem. Shinya Suzumura et al. addressed this in Selective Inference for Sparse High-Order Interaction Models. They combined a tree-based pruning strategy with "selective inference"—a framework that adjusts statistical significance boundaries based on the search path taken—enabling the valid identification of true interactions within search spaces as large as $10^{17}$ possibilities.

Random Intersection Trees

Another approach relies on stochastic pruning. In iterative Random Forests to discover predictive and stable high-order interactions, Sumanta Basu et al. developed the iterative Random Forest (iRF) algorithm. Instead of an exhaustive search, iRF uses the decision paths of a collection of random forests to weight features, and then applies Random Intersection Trees to rapidly extract stable, high-order interactions (such as 5-way or 6-way biological recipes) in linear time.


Strategy 2: Structural Factorization and Low-Rank Tensors

Rather than searching for explicit combinations, another paradigm embeds features into low-dimensional spaces where high-order interactions can be computed implicitly through algebraic identities.

Higher-Order Factorization Machines (HOFMs)

Standard Factorization Machines (FMs) model pairwise interactions by computing the dot product of feature embedding vectors, bypassing the need to learn a dense interaction matrix. However, extending this to an $m$-th order interaction traditionally required an exponential increase in parameters.

Mathieu Blondel et al. solved this bottleneck in Higher-Order Factorization Machines. By establishing a mathematical link to ANOVA kernels and utilizing dynamic programming, the authors created an algorithm capable of training HOFMs of any arbitrary order $m$ in linear time $O(dm)$, where $d$ is the number of features. This allows the model to capture high-order relationships without a separate parameter explosion for each degree of interaction.

Exhaustive Tensor Representation:
[Feature 1] ⊗ [Feature 2] ⊗ ... ⊗ [Feature M]  ==>  O(d^M) Parameters (Explosion)

HOFM Factorization (ANOVA Kernels + Dynamic Programming):
[Feature Embeddings] ==> Dynamic Programming Recursion ==> O(d · m) Time & Space

Graph and Tensor Factorization

Modern architectures often represent the interaction space as a graph or a tensor to enforce sparsity and structure. For example, Shu Wu et al. proposed GraphFM in GraphFM: Graph Factorization Machines for Feature Interaction Modelling, which models features as nodes in a graph and dynamically learns to select only the most predictive interaction edges, filtering out combinatorial noise. Similarly, in multi-view learning, Luhuan Fei et al. utilized Exclusive Sparse Tensor Factorization in Multi-View Multi-Label Personalized Classification via Generalized Exclusive Sparse Tensor Factorization to capture complex, high-order dependencies between features and labels while maintaining a highly compressed, overparameterization-resistant model structure.


Strategy 3: Adaptive and Progressive Growth

Instead of defining a fixed interaction order before training, adaptive methods start with a simple linear model and progressively grow the interaction space based on where the model's residual errors indicate a need for higher complexity.

  • Adaptive Polynomials: In Scalable Nonlinear Learning with Adaptive Polynomial Expansions, Alekh Agarwal et al. introduced the APPLE algorithm. It adaptively instantiates high-order polynomial features during training only when they provide a verifiable gain in predictive power, achieving the statistical expressiveness of deep nonlinear models at the computational cost of linear regression.
  • Progressive Architecture Search: In deep learning networks, Chen Gao et al. developed PROFIT in Progressive Feature Interaction Search for Deep Sparse Network. PROFIT uses Neural Architecture Search (NAS) to discover high-performing feature interaction layers order-by-order, progressively building up interaction complexity while keeping model size and inference latency strictly constrained.

Explaining the Learned Interactions

Discovering or training a model with high-order interactions is only half the battle; we must also be able to interpret what the model has learned. If a neural network utilizes complex multi-way feature combinations to make a prediction, how do we extract that knowledge?

Any-Order Shapley Interactions

Shapley values are widely used to explain feature importance, but traditional local explanation methods struggle to isolate high-order synergies. To resolve this, Fabian Fumagalli et al. developed SHAP-IQ in SHAP-IQ: Unified Approximation of any-order Shapley Interactions. By introducing a novel representation called "Cardinal Interaction Indices," the authors created a single, unbiased sampling algorithm capable of approximating interactions of any arbitrary order, bypassing the need to evaluate the full exponential combination space.

The same authors later expanded on this in PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression, providing a mathematical proof that common post-hoc explanation heuristics (like paired sampling) are theoretically equivalent to fitting low-order polynomial regressions over the interaction space.

Interaction-Aware Partitioning

To make these complex explanations digestible for humans, Joscha Cüppers and Sascha Xu proposed iSHAP in Succinct Interaction-Aware Explanations. Recognizing that a human cannot interpret a raw list of millions of high-order interactions, iSHAP automatically partitions features into distinct, highly interacting groups. This compresses a super-exponential explanation space into a succinct, human-readable format without sacrificing the underlying fidelity of the complex model.


Conclusion

The study of high-order interaction complexity is a transition from brute-force computation to structural and statistical efficiency. Whether through mathematical pruning (C-Tarone, selective inference), algebraic factorization (HOFMs, GraphFM), or progressive growth (APPLE, PROFIT), the core insight remains the same: the combinatorial explosion is a property of the unconstrained search space, not the underlying data. By enforcing sparsity, leveraging low-rank structures, and applying rigorous statistical bounds, modern algorithms can successfully isolate and utilize complex multi-variable synergies that were once considered computationally impossible to reach.

Key Foundational Work

Toward Provably Correct Feature Selection in Arbitrary Domains (2009) — contributed 1 concept elements to this direction.
Comparison of information-theoretic to statistical methods for gene-gene interactions in the presence of genetic heterogeneity (2010) — contributed 1 concept elements to this direction.
Information-theoretic gene-gene and gene-environment interaction analysis of quantitative traits (2009) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_high_order_interaction_complexity_e610b325,
  title = {high-order interaction complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-order-interaction-complexity/rdr_e610b3250cdc4c06b3a5c9d1dbda5421},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_high_order_interaction_complexity_e610b325_v1,
  title = {high-order interaction complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-order-interaction-complexity/rdr_e610b3250cdc4c06b3a5c9d1dbda5421/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake