Modeling Higher-Order Feature Interactions in Sparse Data

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

Version 1 of 1106 papers112 conceptsfrozen 2026-10-04

In many real-world machine learning tasks—from predicting whether a user will click an ad to identifying biological markers for cancer—the most predictive signals do not come from individual features, but from how features work together. While standard models excel at capturing linear effects and pairwise correlations, they often hit a "performance ceiling" because they ignore higher-order interactions (HOIs): dependencies involving three or more variables that create a unique joint effect.

The Pairwise Ceiling

Traditional Factorization Machines (FMs) and linear models typically restrict feature interactions to the second order ($x_i \cdot x_j$). As Enneng Yang and Xin Xin argue in Generalized Embedding Machines for Recommender Systems, this "one-size-fits-all" approach fails to account for complex N-way dependencies.

Consider a "Buy One Get One" discount in e-commerce. The predictive value of a "discount" feature might only emerge when combined with a specific "item category" and a "user demographic." In isolation, or even in pairs, these features might seem irrelevant. Chen Chen demonstrates in Improving Purchase Behavior Prediction with Most Popular Items that capturing these multi-item interactions is the "secret sauce" for distinguishing casual clicks from actual purchase intent.

Efficiently Scaling to Any Order

The primary reason researchers avoided higher-order interactions was computational cost. A model considering interactions of order $m$ across $d$ features traditionally faces $O(d^m)$ complexity—an exponential explosion that makes training impossible for high-dimensional data.

To solve this, Mathieu Blondel and colleagues introduced Higher-Order Factorization Machines (HOFMs). By leveraging ANOVA kernels and dynamic programming, they reduced the complexity to $O(dm)$, making it possible to train models of any order in linear time.

Taking this further, the Adaptive Factorization Network (AFN), developed by Weiyu Cheng, uses a logarithmic transformation layer to learn the optimal interaction order directly from the data. Instead of a human deciding to use 3rd-order or 4th-order interactions, the model might discover that a 7.5-order interaction provides the strongest signal for a specific dataset.

Identifying Synergistic Features

Higher-order interactions are also critical for feature selection. Standard methods often look at features one-by-one or in pairs, which can lead to the premature exclusion of "synergistic" variables.

A classic example is the XOR relationship: two variables might appear completely independent of the target when viewed individually, but perfectly predict it when combined. Dimitris Margaritis 0001 addresses this in Toward Provably Correct Feature Selection in Arbitrary Domains by evaluating features in groups. Similarly, Alexander Shishkin introduced CMICOT, which uses conditional mutual information to detect these high-order logical dependencies that traditional selection methods miss.

Interpreting the Black Box

As models become more complex, understanding why they make a prediction becomes harder. Interaction detection has emerged as a powerful tool for interpretability.

Fabian Fumagalli and Maximilian Muschalik developed KernelSHAP-IQ, a framework that extends Shapley values to interactions. This allows practitioners to see not just which features were important, but how specific pairs or triplets of features worked together to drive a prediction. In the context of ad recommendations, Michael Tsang showed in GLIDER that explicitly detecting and encoding these global interactions can make black-box systems both more accurate and human-readable.

Impact Across Domains

The shift toward higher-order modeling is transforming diverse fields:

  • Education: Hisashi Kashima and Jill-Jênn Vie use Knowledge Tracing Machines to model the three-way interaction between a student, a specific skill, and the learning context.
  • Biology: The QSMART model by Liang‐Chin Huang identifies how specific drug substructures interact with mutated protein residues to predict cancer treatment responses.
  • NLP: Researchers like Jaap Jumelet are using interaction analysis to uncover the internal linguistic rules learned by large language models, moving beyond simple word-pair associations to complex multi-token dependencies.

By moving beyond the "pairwise ceiling," these researchers are building models that more closely mirror the multi-faceted complexity of the real world.

Papers in this version

Showing 60 of 106 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_modeling_higher_order_feature_interactio_317e54be,
  title = {Modeling Higher-Order Feature Interactions in Sparse Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/modeling-higher-order-feature-interactions-in-sparse-data/rdr_317e54be810c43d9884a8b6e6df307b9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_modeling_higher_order_feature_interactio_317e54be_v1,
  title = {Modeling Higher-Order Feature Interactions in Sparse Data},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/modeling-higher-order-feature-interactions-in-sparse-data/rdr_317e54be810c43d9884a8b6e6df307b9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}