Hierarchical Search for High-Order Feature Interactions

51 concepts33 papers2 proposals

In machine learning, features rarely act in isolation. In genomics, a single genetic mutation might be benign, but a specific combination of three or four mutations can trigger a disease. In natural language processing, the word "not" modifies "bad," but adding "at all" completely shifts the sentiment dynamics. These synergistic relationships are known as high-order feature interactions.

The fundamental challenge in capturing these interactions is the combinatorial explosion. If a dataset contains $d$ features, the number of possible $k$-way interactions scales as $O(d^k)$. For high-dimensional datasets, such as those found in bioinformatics or large-scale recommendation systems, searching for these combinations exhaustively is computationally impossible—often exceeding $10^{17}$ possibilities, as noted by Shinya Suzumura et al. in Selective Inference for Sparse High-Order Interaction Models.

To bypass this brute-force bottleneck, researchers rely on a powerful structural intuition: the hierarchical assumption, often called the staircase property. This principle states that meaningful, high-order interactions do not appear out of nowhere; they are almost always built from informative lower-order components.

The Staircase Property: Why We Can Prune the Space

The core intuition behind hierarchical interaction search is that if a high-order interaction (e.g., between features $A$, $B$, and $C$) is highly predictive, its constituent lower-order subsets (e.g., the pairs $\{A, B\}$, $\{B, C\}$, and $\{A, C\}$) are likely significant as well.

As Yuexiang Xie et al. demonstrate in FIVES: Feature Interaction Via Edge Search for Large-Scale Tabular Data, the search space can be drastically constrained by making the discovery of complex features dependent on the structure of simpler ones. This creates a logical progression of feature complexity.

This property is not just a convenient heuristic; it is an empirical reality observed even in state-of-the-art architectures. For instance, in ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs, the authors show that large language models consistently exhibit this staircase structure, where the presence of a high-order interaction implies the significance of its lower-order subsets. By classifying feature relationships based on the number of components involved, models can systematically map local, simple patterns to global, complex structures, as explored by Qiang Li and Jian Ruan in A Unified Approach to Interpreting Self-supervised Pre-training Methods for 3D Point Clouds via Interactions.

Progressive and Stepwise Search Strategies

By leveraging this order-priority principle, algorithms can search for interactions sequentially by order rather than attempting to evaluate all combinations simultaneously. In Progressive Feature Interaction Search for Deep Sparse Network, the authors show that grounding the search for complex correlations in a foundation of validated low-order interactions mirrors effective manual feature engineering while remaining computationally efficient.

This progressive discovery typically follows one of two algorithmic patterns:

1. Bottom-Up Greedy Merging

Instead of evaluating all combinations, the algorithm starts with individual features and evaluates their initial predictive power or weight magnitudes. As shown by Alekh Agarwal et al. in Scalable Nonlinear Learning with Adaptive Polynomial Expansions, the magnitude of a feature's weight in a lower-order model serves as an excellent heuristic for identifying promising candidates for higher-order expansions.

Once individual features or pairs are validated, they are recursively merged. Martin Renqiang Min et al. implement this in Interpretable Sparse High-Order Boltzmann Machines by building a tree of dependencies that adds higher-order terms based on the significance of lower-order components. Similarly, Seokhun Park et al. utilize a stepwise search in Bayesian Neural Networks for Functional ANOVA Model, creating complex interaction nodes by copying a significant lower-order node and appending a single new variable.

2. Hierarchical Pruning

Conversely, if a lower-order interaction is found to be statistically insignificant, the algorithm can immediately prune all of its potential higher-order descendants. In Explaining Local, Global, And Higher-Order Interactions In Deep Learning, Samuel Lerman utilizes this exact heuristic to manage computational complexity, evaluating higher-order interactions only if the interactions between their constituent subsets are strong. This prevents the combinatorial explosion before it can begin.

[Feature A] (Significant)  ───┐
                              ├───> [Interaction A × B] (Significant) ───┐
[Feature B] (Significant)  ───┘                                          │
                                                                         ├───> [Interaction A × B × C]
[Feature C] (Significant)  ──────────────────────────────────────────────┘

[Feature D] (Insignificant) ───> Pruned (No higher-order combinations with D are evaluated)

Mining Structures from Tree Ensembles and Graphs

Rather than building hierarchies explicitly from raw data, some approaches extract them implicitly by analyzing models that naturally learn hierarchical relationships, such as decision trees and graph networks.

Tree Decision Paths

Decision trees inherently capture feature interactions along their branching paths: if a tree splits on feature $A$ and then immediately splits on feature $B$ within that branch, it has mapped an interaction. In iterative Random Forests to discover predictive and stable high-order interactions, the authors mine these decision paths as sets, using intersection-based algorithms to find stable, high-order interactions with linear computational complexity.

This concept is extended by Qianru Wang et al. in Epistasis regulates genetic control of cardiac hypertrophy, where features are iteratively re-weighted based on their co-occurrence within decision paths to isolate weak marginal effects that become powerful when combined. This bypasses the need for brute-force pairwise searches entirely, making high-order discovery feasible in massive genomic studies, as demonstrated by Aaron Sim and Dimosthenis Tsagkrasoulis in Random Forests on Distance Matrices for Imaging Genetics Studies.

Graph and Network Architectures

Interactions can also be structured as Directed Acyclic Graphs (DAGs) or modular neural layers. In Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning, the authors organize kernels into a DAG to ensure that a complex interaction is only selected if its underlying constituent features are already active.

On the neural network side, Jiezhu Cheng et al. design a block-based architecture in HINNPerf: Hierarchical Interaction Neural Network for Performance Prediction of Configurable Systems. The initial blocks capture individual feature influences, and subsequent blocks ingest those learned embeddings to model increasingly complex, higher-order interactions, aligning the model's internal structure directly with the physical reality of the system.

Applications in Recommendation and Explainability

The ability to navigate high-order spaces efficiently has transformed fields where feature crossing is paramount.

In Deep Recommender Systems, where user context, history, and item attributes must be combined instantly, automated feature interaction search structures the discovery process to avoid computing every possible cross-product (Ruiqi Zheng et al. in AutoML for Deep Recommender Systems: A Survey). Meta AI's Wukong architecture, detailed by Buyun Zhang et al. in Wukong: Towards a Scaling Law for Large-Scale Recommendation, stacks Factorization Machines into an "Interaction Stack," capturing exponentially higher-order relationships through successive, stable combinations.

In Model Explainability, traditional tools often fail because they treat features as independent contributors. By applying bottom-up greedy merging, frameworks can group interacting features into succinct, human-readable hierarchies. As shown by Joscha Cüppers et al. in Succinct Interaction-Aware Explanations and Michael Tsang et al. in How does This Interaction Affect Me? Interpretable Attribution for Feature Interactions, identifying pairwise relationships first and merging them into disjoint sets provides a clear, high-fidelity window into complex neural network predictions without incurring exponential attribution costs (Chandan Singh et al. in Hierarchical interpretations for neural network predictions).

Key Foundational Work

Detecting Feature Interactions from Accuracies of Random Feature Subsets (1999) — contributed 2 concept elements to this direction.
Substantial Constructive Induction Using Layered Information Compression: Tractable Feature Formation in Search (1985) — 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_progressive_interaction_search_8eb3e674,
  title = {progressive interaction search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/progressive-interaction-search/rdr_8eb3e674f9a44a7d89e5e568f810761b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_progressive_interaction_search_8eb3e674_v1,
  title = {progressive interaction search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/progressive-interaction-search/rdr_8eb3e674f9a44a7d89e5e568f810761b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake