Efficient Discovery of High Order Feature Interactions

This direction is split into other directions: high-order interaction complexity. Its last version stays readable and citable here.

Version 1 of 1184 papers188 conceptsfrozen 2026-10-04

In machine learning, we often assume that features act independently. A linear model adds up the contribution of "Age," "Income," and "Education" to predict a result. But the real world is rarely additive. In genomics, a specific disease might only trigger if three different mutations are present simultaneously—a phenomenon known as epistasis. In recommendation systems, the combination of "User Gender," "Time of Day," and "Current Location" might be far more predictive than any of those factors alone.

These are high-order interactions: synergistic relationships where the effect of a group of variables cannot be explained by their individual parts. While deep neural networks and gradient-boosted trees can "learn" these patterns internally, identifying them explicitly is a massive computational challenge.

The Combinatorial Ceiling

The fundamental problem in interaction discovery is the combinatorial explosion. If you have $d$ features and want to check every possible 3-way interaction, you have to evaluate $\binom{d}{3}$ combinations. For a dataset with 1,000 features, searching for 5-way interactions involves checking over 8 trillion combinations.

As Kazuya Nakagawa and Ichiro Takeuchi note in Safe Feature Pruning for Sparse High-Order Interaction Models, this makes traditional solvers fail immediately. We cannot simply "brute force" our way to understanding complex dependencies.

Pruning the Search Space

To bypass this ceiling, researchers have developed algorithms that prune the search space—discarding billions of irrelevant combinations without ever looking at them.

One approach uses statistical bounds. Mahito Sugiyama and Karsten Borgwardt introduced C-Tarone in Finding Statistically Significant Interactions between Continuous Features. C-Tarone uses rank-order statistics to derive a mathematical bound on $p$-values. If the best possible $p$-value for a branch of feature combinations is already above a significance threshold, the algorithm prunes that entire branch, drastically reducing the search space while maintaining strict control over false positives.

Another strategy involves iterative refinement. Instead of looking at all combinations at once, the iterative Random Forest (iRF) algorithm, developed by Sumanta Basu and Karl Kumbier, weights features based on their importance in previous iterations. By using Random Intersection Trees, iRF identifies high-order "molecular recipes" (like 5-way or 6-way interactions) that are both predictive and stable across different subsets of data.

In large-scale industrial settings, such as click-through rate (CTR) prediction, the search for interactions must be even faster. Yuexiang Xie and Ce Zhang proposed FIVES (Feature Interaction Via Edge Search for Large-Scale Tabular Data), which treats feature selection as a graph problem. By formulating the search as a differentiable "edge search" on a graph, FIVES can automate the discovery of interactions like "Gender $\otimes$ Age $\otimes$ Income" using the same optimization techniques used to train neural networks.

Similarly, Rui Zhang and Yixin Su developed $L_0$-SIGN, which uses $L_0$ regularization to prune "noisy" interactions in recommender systems, ensuring the model only keeps the most beneficial feature crosses.

Peeking Inside the Black Box

Sometimes, we don't want to build a new model; we want to understand an existing one. This is the goal of post-hoc interaction detection.

Zirui Liu and colleagues introduced Persistence Interaction Detection (PID) in Detecting Interactions from Neural Networks via Topological Analysis. PID uses persistent homology—a tool from algebraic topology—to analyze the "shape" of the neural network's weights. It identifies which features are topologically connected in a way that drives the model's predictions.

For global interpretability, Qiang Liu developed DNN2LR (DNN2LR: Interpretation-inspired Feature Crossing for Real-world Tabular Data). This framework measures "interpretation inconsistency"—how much a feature's local importance fluctuates across different samples. High fluctuation suggests the feature is interacting with others. DNN2LR extracts these interactions and feeds them into a simple Logistic Regression, creating a "white-box" model that rivals the performance of deep learning.

Quantifying Synergy with Shapley Values

Finally, researchers are moving toward unified mathematical frameworks for these interactions. Fabian Fumagalli and Maximilian Muschalik introduced SHAP-IQ (SHAP-IQ: Unified Approximation of any-order Shapley Interactions). By extending the game-theoretic concept of Shapley values to "Cardinal Interaction Indices," SHAP-IQ provides a way to calculate exactly how much a specific group of features (of any size) contributes to a prediction beyond their individual effects.

By framing interaction discovery as a problem of efficient search, statistical pruning, and topological analysis, this field is turning the "black box" of complex dependencies into a transparent, provably correct map of how variables truly work together.

Papers in this version

Showing 60 of 184 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_efficient_discovery_of_high_order_featur_4b42690c,
  title = {Efficient Discovery of High Order Feature Interactions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-discovery-of-high-order-feature-interactions/rdr_4b42690c96494dc2b85ff27550563a71},
  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_efficient_discovery_of_high_order_featur_4b42690c_v1,
  title = {Efficient Discovery of High Order Feature Interactions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-discovery-of-high-order-feature-interactions/rdr_4b42690c96494dc2b85ff27550563a71/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}